（9） 树的深度是多少？ （10） 树的度数是多少？
参考答案：
根结点是：a
叶子结点是：d i f j k l g的祖先：a c 树的深度：4 树的度数：3
27．以下面数据作为叶子结点的权值构造一Huffman树，画出该树并计算出其带权路径长度。
2，4，5，8 参考答案： 19
8 11
5 6
带权路径长度：WPL=(2+4)*3+5*2+8=36 2 4
28．给定关键字集合(45,28,52,20,10,35,40,70,30,75,63,32)，
（3） 从一棵空的二叉搜索树开始，按表中元素的次序构造一棵二叉搜索树。 （4） 画出从该二叉搜索树中删除关键码28和52后的结果。
参考答案： (1)
(2)
（评分标准：每个图3分）
29．试画出下面带权无向图的一棵最小生成树。 9 2 a
7 d 6 b 3 9 c 7 8 4
e 5 f
参考答案：
a 2 b 6 3 c d 4 f e 5 (对1根线得1分，全对得6分)
30．写出利用希尔排序对关键字序列 (40,24,80,39,43,18,20,10,90,70) 进行从小到大排序的每一趟结果。（假设gap取值分别为5、3、1）
参考答案：
Gap=5时 18, 20, 10, 39, 43, 40, 24, 80, 90, 70 Gap=3时 18, 20, 10, 24, 43, 40, 39, 80, 90, 70 Gap=1时 10, 18, 20, 24, 39, 40, 43, 70, 80, 90 ( 每对1行得2分)
31．设一散列表长为13，采用线性探查法解决冲突。散列函数h(key)=key。 （1）画出在空表中依次插入关键字25,20,36,15,41,52,29,72,67后的散列表。 （2）该散列表在等概率查找成功和不成功的平均查找长度。
参考答案： (1)散列表：（2分） 0 1 2 3 4 5 6 7 8 9 10 11 12
52 15 41 29 67 20 72 36 25
(2)ASLSUCC=(5*1+3*2+1*4)/9=5/3 （2分） ASLNSUCC=(2+1+5+4+3+2+1+3+2+1+2+1+3)/13=30/13 （2分）
八、 综合题（共14分）
32．试对下图所示的AOE网络回答下列问题：
（4） 这个工程最早可能在什么时间结束。（2分）
（5） 求每个活动的最早开始时间e()和最迟开始时间l().（8分） （6） 确定哪些活动是关键活动。（4分） 10
2 1 2 4 19 4 3 6 6 15 11 5 5
数据结构模拟试卷(三)
一、 单项选择题（每小题2分，共30分）
1．一个非空广义表的表头
A．一定是子表 B. 一定是原子
C．不能是子表 D. 可以是原子，也可以是子表
2．下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是
A．堆排序 B. 冒泡排序 C．直接选择排序 D. 快速排序
3．设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，
则出栈序列不可能是
A．23415 B. 15432 C．23145 D. 54132
4. 算法必须具备输入、输出和
A. 计算方法 B. 排序方法
C．解决问题的有限运算步骤 D. 程序设计方法
5．拓扑排序运算只能用于
A．带权有向图 B. 连通无向图 C．有向无环图 D. 无向图
6. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是
A. O(1) B. O(n) C. O(n2) D. O(nlogn)
7．在一个无向图中，所有顶点的度数之和等于图的边数的 倍
A．1/2 B. 1 C. 2 D. 4
8. 设二维数组A[0..m-1][0..n-1]按行优先顺序存储，则元素A[i][j]的地址为
A． LOC(A[0][0])+(i*m+j) B．LOC(A[0][0])+(i*n+j) C.
LOC(A[0][0])+[(i-1)*n+j-1] D. LOC(A[0][0])+[(i-1)*m+j-1]
9．单链表的存储密度
A．大于1 B. 等于1 C．小于1 D. 不能确定
10. 有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是
A. 访问第i个节点（1≤i≤n）
B. 在第i个节点后插入一个新节点（1≤i≤n） C. 删除第i个节点（1≤i≤n） D. 将n个节点从小到大排序
11. 循环队列SQ的存储空间是数组d[m]，队头、队尾指针分别是front和rear，则执行出队
后其头指针front值是 A．front=front+1 B. front=(front+1)%(m-1) C. front=(front-1)%m D. front=(front+1)%m
12．下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是
A．堆排序 B. 冒泡排序 C．直接选择排序 D. 快速排序
13. 若要惟一地确定一棵二叉树，只需知道该二叉树的
A．前序序列 B. 中序序列 C．前序和后序序列 D. 中序和后序序列
14．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是
A．希尔排序 B. 冒泡排序 C．插入排序 D. 选择排序
15．具有n个节点的完全二叉树的深度为
A．?log2(n+1)? -1 B. log2n+1 C. log2n D. ?log2n?
二、 填空题（每小题2分，共20分）
1．数据的逻辑结构分为两大类，它们是线性结构和 。