大学《数据结构》试题及答案
数据结构是计算机存储、组织数据的方式。以下是由阳光网小编整理关于大学《数据结构》试题的内容，希望大家喜欢!
大学《数据结构》试题及答案(一)
1.属性与服务相同的对象构成类，类中的每个对象称为该类的一——·
2.在类的继承结构中，位于上层的类叫做一——，其下层的类则 叫做 类.
3.若设串S=“documentHash.doc\O”，则诙字符串S的长度为——·
4.线性表的链接存储只能通过—————————顺序访问。
5.设链栈中结点的结构为(data，link)，栈顶 指针为top，则向该链栈插入、—个新结点*p
时，应依次执行—————————————和一————操作。
6.广义表的深度定义为广义表中括号被嵌套的——一·
7.在一棵高度为h的完全二又树中，最少含有——个结点.假定树根结点的高度为O.
8.从有序击(12，10，30，43，56，78，02，95)中折半搜索56和98元素时，其搜索长度分别为——和——·
9。n个(n>o)顶点的连通无向图中各顶点的度之和最少为————·
10.设图的顶点数为n，则求解最短路径的Dijkstra算法的时间复杂度为————·
11.给定一组数据对象的关键码为{46，79，56，38，40，84}，则利用堆排序方法建立的初始最大堆的堆首和堆尾的关键码分别为——和——·L2.在索引表中，着一个索引项对应数据对象表中的一个表项，0C称此索引为稠密索引
若对应数据对象表中的若干表项，则称此索引为——一索引.
答案
1.实例
2.基类 派生(或于类)
3. 16
4.链接指针
5.p一>Link=top top=p
6.重数
7.2h
8. 3 2
9.2(n-1)
10。O(n2)
11.84 46
12。稀疏
大学《数据结构》试题及答案(二)
1、填空题。(每小题2分，本题满分20分)
(1) C++语言中，数组是按行优先顺序存储的，假设定义了一个二维数组A[20][30]，每个元素占两个字节，其起始地址为2140，则二维数组A的最后一个数据元素的地址为 2140+2*(30*20-1) = 3338(3338,3339) 。
(2) 若A，B是两个单链表，链表长度分别为n和m，其元素值递增有序，将A和B归并成一个按元素值递增有序的单链表，并要求辅助空间为O(1)，则实现该功能的算法的时间复杂度为 O(m+n) 。
(3) 快速排序的平均时间复杂度是______________。
(4) 假设有一个包含9个元素的最小堆，存放在数组A中，则一定比A[3]大的元素有个;一定比A[3]小的元素有个。(元素从第0个位置开始存放)
(5) 广义表(((A)),(B,C), D, ((A), ((E,F)))) 的长度是，深度是。
(6) 有10个元素的有序表，采用折半查找，需要比较4次才可找到的元素个数为。 (7)当两个栈共享一存储区时，栈利用一维数组A[n]表示，两栈顶指针为top[0]与top[1]，则栈满时的判断条件为___top[0]+1=top[1]_ 或者 top[0] = top[1]+1 ___。 (8) 假设计算斐波那契数的'函数Fib(long n)定义如下：
long Fib(long n){ if(n<=1) return n;
else return Fib(n-1)+Fib(n-2) }
计算Fib(5)时的递归调用树(即指明函数调用关系的树)的高度是___4 _____。假设叶子结点所在的高度为0。
(9) 完全二叉树按照层次次序，自顶向下，同层从左到右顺序从0开始编号时，编号为i的结点的左子结点的编号为___2*i+1______。
(10) 假设用子女—兄弟链表方式表示森林，对应的二叉树的根结点是p，那么森林的第三棵树的根结点在二叉树中对应的结点是： ___p->rightchild->rightchild____________。假
2、选择题。(每小题2分，本题满分20分)
(1) 如果能够在只知道指针p指向链表中任一结点，不知道头指针的情况下，将结点*p从链
表中删除，则这个链表结构应该是： ( B,C )(多选题) A. 单链表 B. 循环链表 C. 双向链表 D. 带头结点的单链表 (2) 以下哪种矩阵压缩存储后会失去随机存取的功能?( A )
A. 稀疏矩阵 B. 对称矩阵 C. 对角矩阵 D. 上三角矩阵
(3) 下面哪一方法可以判断出一个有向图是否有环(回路)：( B ) (选A，B也对)
A. 广度优先遍历 B. 拓扑排序 C. 求最短路径 D.求关键路径 (4) n个结点的线索二叉树(没有头结点)上含有的线索数为( B )
A. 2n B. n-l C. n+l D. n
(5) 循环队列存储在数组A[0..m]中，则入队时队尾指针rear的操作为( D )
A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
(6) 使用加权规则得到改进的Union操作WeightedUnion，其目的是： ( B )
A. 提高Union操作的时间性能 B. 提高Find操作的时间性能 C. 减少Union操作的空间存储 D. 减少Find操作的空间存储
【大学《数据结构》试题及答案】相关文章：