武汉大学计算机学院
2009年－20010学年第一学期“数据结构”考试试题（A）
姓名
学号(序号)_ 学校
要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和序号。
一、单项选择题（每小题2分，共计20分）
1. 下列说法中，不正确的是 。 A.数据元素是数据的基本单位 B.数据项是数据中不可分割的最小可标识单位 C.数据可由若干个数据元素构成 D.数据项可由若干个数据元素构成
2. 对于一个线性表，既要求能够较快地进行节点插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用 存储结构。
A.顺序 B.链式 C.散列 D.索引
3. 如果以链表作为栈的存储结构，则退链栈操作时 。 A.必须判断链栈是否满 B.判断链栈元素的类型 C.必须判断链栈是否空 D.对链栈不作任何判断
4. 设循环队列中数组的下标是0～N-1，其头尾指针分别为f和r，则其元素个数为 。
A.r-f B.r-f-1 C.(r-f)％N+1 D.(r-f+N)％N
5. 设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址是 。
A.1000 B.860 C.1140 D.1200
6..一个无向图中有16条边，度为4的顶点有3个，度为3的顶点有4个，其余顶点的度均小于3，则该图至少有 个顶点。
A.10 B.11 C.12 D.13
7. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的 算法。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历
8. 一个有向图G的邻接表存储如图1所示，现按深度优先搜索遍历，从顶点0出发，所得到的顶点序列是 。
0 1 2 3 4 v0 v1 v2 v3 v4 ∧ 1 2 4 2 4 ∧ 3 ∧ 3 ∧
图1 有向图G的邻接表
A.0,1,2,3,4 B.0,1,2,4,3 C.0,1,3,4,2 D.0,1,4,2,3
9. 在含有27个节点的二叉排序树上，查找关键字为35的节点，则依次比较的关键字有可能是 。
A.28,36,18,46,35 B.18,36,28,46,35 C.46,28,18,36,35 D.46,36,18,28,35
10.对关键字序列{15,9,7,8,20,-1,4}进行排序，进行一趟排序后数据序列变为{9,15,7,8,20,-1,4}，则采用的是 算法。
A.简单选择排序 B.冒泡排序 C.直接插入排序 D.堆排序
二、填空题（每小题2分，共计10分）
1. 中缀表达式(2+2*3)*2+6*3/2的后缀表达式是 。
2. 在一棵完全二叉树中，节点个数为n，则编号最大的分支节点的编号为 。 3. 具有n个节点的二叉树采用二叉链存储结构，共有 个空指针域。
4. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头节点的个数为 ① ，邻接表中边表节点的个数为 ② 。
5. 具有5层节点的AVL树至少有 个节点。
三、问答题（每小题10分，共计40分）
1. 已知一棵完全二叉树有50个叶子节点，则该二叉树的总节点数至少应有多少个？需给出推导过程。
2. 对于图2所示的带权有向图，采用狄克斯特拉算法求从顶点0到其他顶点的最短路径和长度，要求给出求解过程（每个步骤的S、disp和path）。
2 0 6 9 4 3 1 2 1 2 2 7 3 图2 一个有向图
3. 设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77}，其哈希函数为：
H(key)=key % 13
采用开放地址法的线性探查法解决冲突，试在0～18的哈希地址空间中对该关键字序列构造哈希表，并求成功和不成功情况下的平均查找长度。
4. 有一组关键字序列{5,8,11,13,34,25,6,19,9,7} 。
（1）将其调整成大根堆，给出大根堆序列。（5分）
（2）采用堆排序实现递增排序，给出第1趟～第9趟的结果。（5分） 本题只需直接给出结果。
四、算法设计题（每小题15分，共计30分）
1. 设计一个算法void reverse(LinkList *&L)，将一个带头节点的循环单链表L（至少含有两个以上节点）中所有节点逆置。
2. 假设二叉树采用二叉链存储结构存储，其中所有节点值均为正整数，设计一个算法int max(BTNode *b)，用于计算二叉树b中的最大节点值并返回该最大值。
“数据结构”考试试题（A）参考答案
一、单项选择题（每小题2分，共20分）
1. D 6..B
2. B 7. D
3. C 8. B
4. D 9. D
5. A 10.C
二、填空题（5×2＝10分）
1. 2 3 * + 2 * 6 3 * 2 / + 2. ?n/2?或n/2。 3. n+1
4. ①n ②2e。 5. 12
三、问答题（每小题10分，共40分）
1. 设度为0、1、2的节点个数及总节点数分别为n0、n1、n2和n，则有： n0=50
n=n0+n1+n2 n-1=n1+2×n2
由以上3式可得：n2=49。 故：n-1=n1+2×49
n=n1+99
所以当n1=0时，n最少，所以n至少有99个节点。 评分说明：只有正确结果，给5分。 2. 对于图2，对应的邻接矩阵如下：
?069?2???012???????02?? ?????0?????3?70???在求最短路径时，S（存放顶点集），dist[]（存放最短路径长度）和path[]（存放最短路径）的变化如下：
S dist[] path[]
0 1 2 3 4 0 1 2 3 4 {0} {0, 4} {0, 1 ,4} {0,1,2,4} {0,1,2,3,4} 0 0 0 0 0 6 5 5 5 5 9 9 6 6 6 ∞ 9 7 7 7 2 2 2 2 2
0 0 0 0 0 0 4 4 4 4 0 0 1 1 1 -1 4 1 1 1 0 0 0 0 0 最后得到的结果如下：
顶点0到顶点1的最短距离为5，最短路径为：1?4?0（以P[]最后值为依据，P[1]=4，故有1?4，P[4]=0，故有4?0。假定P[]从下标0开始，以下求路径过程相同）；
顶点0到顶点2的最短距离为6，最短路径为：2?1?4?0； 顶点0到顶点3的最短距离为7，最短路径为：3?1?4?0； 顶点0到顶点4的最短距离为2，最短路径为：4?0。 3. 依题意，m=19，线性探查法计算下一地址计算公式为：
d1=H(key)
dj+1=(dj+1) % m; j=1, 2, ... 其计算函数如下：
H(19)=19 mod 13=6 H(01)=01 mod 13=1 H(23)=23 mod 13=10 H(14)=14 mod 13=1 H(14)=(1+1) mod 19 =2 H(55)=55 mod 13=3 H(20)=20 mod 13=7 H(84)=84 mod 13=6 H(84)=(6+1) mod 19=7 H(84)=(7+1) mod 19=8 H(27)=27 mod 13=1 H(27)=(1+1) mod 19=2 H(27)=(2+1) mod 19=3 H(27)=(3+1) mod 19=4 H(68)=68 mod 13=3 H(68)=(3+1) mod 19=4 H(68)=(4+1) mod 19=5 H(11)=11 mod 13=11 H(10)=10 mod 13=10 H(10)=(11+1) mod 19=12 H(77)=77 mod 13=12 H(77)=(12+1) mod 19=13
冲突
冲突 仍冲突
H(10)=(10+1) mod 19=11
冲突 仍冲突
冲突 冲突 仍冲突
冲突 仍冲突
冲突
因此，构建的哈希表如表1所示。
表1 哈希表
下标 k 探查次数 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 23 11 10 77 1 1 3 2 01 14 55 27 68 19 20 84 1 2 1 4 3 1 1 3
苏州大学研究生试卷2010数据结构A
