数据结构期末考试题

得 分 评卷人 第一部分 第二部分 第三部分 第四部分 总 分 核分人 j个儿子的编号是________。

6. 求解带权连通图最小生成树的Prim算法使用图的________作为存储结构。 7. 在重连通图中每个顶点的度至少为________。

得 分 评卷人

班级

三、选择题（共20分，每题2分）

1.若语句S的执行时间为O（1），那么下列程序段的时间复杂度为（ ）。

for(i=0; ifor(j=0; j<=i; j++)

S;

B．O(n*n)

C．O(nlogn)

D．O(n*i)

一、判断题：（共10分，每题1分）

1、满二叉树也是完全二叉树。（ ）

2、二叉树可以用0≤度≤2的有序树来表示。（ ）

3、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（ ）

4、带权连通图中某一顶点到图中另一顶点的最短路径不一定唯一。（ ） 5、在n个结点的无向图中,若边数少于n-1,则该图必是非连通图。（ ） 6、树的带权路径长度最小的二叉树中必定没有度为1的结点。（ ） 7、哈希表的查找无需进行关键字的比较。（ ）

8、折半查找方法可以用于按值有序的线性链表的查找。（ ） 9、对一个堆按层次遍历，不一定能得到一个有序序列。（ ）

10、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。（ ）

得 分 评卷人 A．O(n)

2. 已知一堆栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列（ ）。

A．1234

B．4321

C．2143

D．4123

3. 深度为5的二叉树至多有（ ）个结点.

A．16

B．32

C．31

D．10

4. 堆(HEAP)是一种（ ）。

A．二叉树

B．线性表

C．图

D．算法

5. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（ ）。

A．1和5

B．2和4

C．4和2

D．5和1

6. 下列哪种排序算法的平均时间复杂度为O（nlogn）（ ）。

A．简单选择排序

B．简单插入排序

C．冒泡排序

D．归并排序

二、填空题（共20分，每空2分）

1.栈和队列都是________线性表。

2.下三角形矩阵按行存储的下标计算公式为_______，三对角矩阵按行存储的计算公式为________。

3.在简单插入排序、希尔排序、简单选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有：________。

4.请举例输出树形结构的两种存储方法________、 。

5.按满二叉数的概念可推广出满K叉数的概念。若对满K叉树的节点逐层编号（从1开始，同层中从左到右），则编号为i的节点的父节点编号是________，编号为i的节点的第

7. 用冒泡排序（交换排序）算法对(12 37 42 19 27 35 56 44 10)数据进行从小到大排序。在将最大的数“沉”到最后时，数据的顺序是（ ）。

A．12 37 42 19 27 35 44 10 56 C．12 37 19 27 35 42 44 10 56

8. 下列哪种排序算法更适合于外部排序（ ）。

A．选择排序

B．插入排序

C．冒泡排序

D．归并排序

B．12 37 42 19 27 35 10 44 56 D．10 12 19 27 35 37 42 44 56

9. 对下列二叉树进行后序遍历，其遍历结果为（ ）。

a

第 1 页 共 3 页

b c

d e f

g

A．gfedcba

B．dbegfca

C．bdecgfa

D．dbaecgf

void tinorder ( threaded_pointer tree) { threaded_pointer temp=tree; for(; ;){

temp = insucc (temp); if (________) break; printf (\"%3c\

10. 在待排序的元素基本有序的前提下，效率最高的排序方法是（ ）。

A．简单插入排序

得 分 评卷人

四、应用题（共30分）

1.请对右图有向图（共10分）：

（1）画出相应邻接链表（adjacency list）表示法（链表中，按节

点编号大小从小到大向后排）（6分）

（2）指出按深度优先遍历算法在上述表示的基础上进行遍历的

两个输出结果。（4分） 2.对于下列二叉树（12分）

（1）请画出其对应的中序线索（thread）二叉树。（8分每

个线索一分）

（2）请将下列用于中序线索二叉树遍历的程序的空白部

分填上。（4分每空2分）

threaded_pointer insucc( threaded_pointer tree) {

threaded_pointer temp; temp = tree->right_child; if ( !tree->right_thread )

while(________)

temp = temp->left_child;

B．简单选择排序

C．快速排序

D．归并排序

} }

3.（8分）选取哈希函数H(k)=k mod 11, 用线性探测（linear probing）冲突解决策略(H(k)+i)%11. 试在0-10的哈希地址空间中对关键字序列(22,41,53,46,30,13,01,67)构造哈希表, 并求等概率情况下查找成功的平均查找长度。 得 分 评卷人

五、程序题（20分）

1．下面是将删除大顶堆(MAX HEAP)堆顶元素的算法，请将空白部分填上：（12分） element delete_max_heap(int *n) {

int parent,child; element item, temp; if (HEAP_EMPTY(*n)) {

fprintf (stderr, \"The heap is empty\\n\"); exit (1); }

item = heap[1]; temp = heap[________]; parent = 1; child = 2;

while (child <=*n) {

if (child < *n) && (heap[child].key< heap[child+1].key) ________;

if (temp.key >= heap[child].key) break;

第 2 页 共 3 页

return temp; }

heap[parent] =________; parent = child; child* = 2; }

heap [parent] = temp; return item; }

2．编写计算二叉树中叶节点个数的递归函数（8分）。

第 3 页 共 3 页