北京师范大学2011～2012学年第 1 学期期末考试试卷（A卷） 课程名称： 数据结构 任课教师姓名： 刘玉铭 卷面总分： 100 分 考试时长： 100 分钟 考试类别：闭卷 院（系）： 数学科学学院 专 业： 年级： 2010 姓 名： 学 号：
题号 第一题 第二题 第三题 第四题 总分 得分
阅卷教师（签字）：
一、 单项选择题（每题2分，共10题20分） 题号 1 2 3 4 5 6 7 8 9 10 答案 A B B B B D D C C A
1．以下那一个术语与数据的存储结构无关？ 。 A．栈 B．哈希表 C．线索树 D．双向链表
2．链表不具有的特点是 。 A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性表长度成正比
3．算术表达式a+b*（c+d/e）转为后缀表达式后为 。 A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++
4．二维数组A[10][20]采用列优先的存储方法,若每个元素占2个存储单元，设A[0][0]的地址为100，则元素A[7][6]的存储地址为 。 A．232 B．234 C．390 D．392
装 订 线 5．若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点，则度为0 的结点个数是 。 A．9 B．11 C．15 D．不确定
6．一棵二叉树中序序列为FEABDC，后序序列为FBADCE，则层序序列为 。 A. ABCDEF B. EFCDBA C. FECDAB D. EFCDAB
7．在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是 。 A．G 中有弧 B．G 中有一条从Vi 到Vj 的路径 C．G 中没有弧 D．G 中有一条从Vj 到Vi 的路径
8． 对于二叉排序树，下面的说法 是正确的。 A．二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合 B．对二叉排序树进行层序遍历可得到有序序列 C．用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大 D．在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/2
9．一组记录的关键字为{47、75、55、30、42、90}，则用快速排序方法并以第一个记录为支点得到的第一次划分结果是 。 A. 30,42,47,55,75,90 B. 42,30,47,75,55,90 C. 42,30,47,55,75,90 D. 42,30,47,90,55,75
10． 下述文件中适合于磁带存储的是 。 A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件
二、 判断（每题1分，共10题10分） 题号 1 2 3 4 5 6 7 8 9 10 答案 × √ √ × × √ × √ × √
1．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。----( ) 2．KMP 算法的特点是在模式匹配时指示主串的指针不会变小。------------( ) 3．若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1. ---( ) 4．数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。---------------------------------------------------------( ) 5．若一个广义表的表头为空表，则此广义表亦为空表。-------------------( ) 6．完全二叉树中，若一个结点没有左孩子，则它必是树叶。---------------( ) 7．一个有向图的邻接表和逆邻接表中结点的个数可能不等。---------------( ) 8．AOE 网一定是有向无环图。-----------------------------------------( ) 9．对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。---( ) 10． 倒排文件与多重表文件的次关键字索引结构是不同的。-------------( )
三、 填空题（每题2分，共10题20分） 1．带头结点的双循环链表L 中只有一个元素结点的条件是： L->next->next==L 。 2．已知链队列的头尾指针分别是f 和r，则将s指向的结点入队的操作是 r->next=s；r=s 。 3．广义表A((( ),(a,(b),c)))，head(tail(head(tail(head(A))))等于 (b) 。 4．高度为5 的完全二叉树至少有 8 个叶子结点 5．一棵树T中，包括一个度为1的结点，两个度为2 的结点，三个度为3 的结点，四个度为4 的结点和若干叶子结点，则T 的叶结点数为 1+2*1+3*2+4*3 = 21 。 6．求图的最小生成树有两种算法中， prim 算法适合于求稠密图的最小生成树。 7．具有10 个关键字的有序表，折半查找的平均查找长度 2.9 。 8．高度为7的平衡二叉树的结点数至少有 33 个。 9．在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是 m-1 。 10． 对n个记录进行简单选择排序，所需进行的关键字间的比较次数为 1+2+3+…+(n-1) = n(n-1)/2 。 四、 简答题（每题5分，共10题50分） 1．画出广义表（a，（b，c，d），e）的存储结构图（采用头尾指针的链表结构，标志1表示表结点，标志0表示原子结点）
2．画出下列由三棵树组成的森林转换为二叉树。
a
b c d e f g
h i j k
l
1 1 1 1 1 1 0 a 0 b 0 c 0 d 0 e
a b c d e f g
h i j k l 3． 给定一组叶子的权值分别为：8、6、3、2、7、24，填写下表构造一棵赫夫曼树，并画出该赫夫曼树(同一层的左子树根权值小于右子树根权值) HT： weight parent lchild rchild 1 8 9 0 0 2 6 8 0 0 3 3 7 0 0 4 2 7 0 0 5 7 9 0 0 6 24 11 0 0 7 5 8 4 3 8 11 10 7 8 9 15 10 5 1 10 26 11 8 9 11 50 0 6 10
4． 已知某图的邻接表 （1）．画出此邻接表对应的图； （2）．写出由v1 开始的深度优先遍历的序列； （3）．画出由v1 开始的深度优先的生成树；
v1 开始深度优先遍历的序列:v1-v2-v5-v3-v4-v6 V1 V2 V3 V4 V5 V6
生成树 V1 V2 V3 V4 V5 V6 图
6 24 3 2 7 8 5 11 15 26 50 5． 画出带权无向图的一棵最小生成树。 6． 按Dijkstra算法计算从顶点A到其它各个顶点的最短路径和最短路径长度。（写出每一步计算得到的最短路径和相应的路径长度）
源点 A V(i) 路径 终点 B C D E
i=1 路径 路径长度 AB 3 AC 20 AE
45 B AB
i=2 路径 路径长度 ABC 18 ABE
43 C ABC
i=2 路径 路径长度 ABCD 38 ABE
43 D ABCD
i=4 路径 路径长度 ABE
43 E ABE
1 2 4 5 3 6 18
16 11 5
6
1 2
4 3 6
16 11 5
6 1 2
3 6
16 5
6
1 2 3
16
5
1 2 16 1
1 2
4 5 3 6 33 18 14
19
16 21 11 8 5
6 7．由字符序列(t, d, e, s, u, g,)建立一棵平衡的二叉排序树(画出主要过程)。
8．已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。
请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。
关键字 25 16 38 47 79 82 51 39 89 151 231
哈希值 3 5 5 3 2 5 7 6 1 8 0
哈希地址 0 1 2 3 4 5 6 7 8 9 10 11 关键字 231 89 79 25 47 16 38 82 51 39 151 比较次数 1 1 1 1 2 1 2 3 2 4 3
等概率情况下查找成功时的平均查找长度：（1+1+1+1+2+1+2+3+2+4+3）/11=21/11
t t
d t d e t d e
t d
e
s t d
e
s u t d e s u g
t d e s u g