数据结构与算法分析试卷.pdf

北京工业大学计算机学院2004级

2005─2006（第二学期）

《数据结构与算法》期末考试卷

考试形式：“A4一纸开卷”时间2006年6月16日8:00~9:35

班级学号姓名

卷面作业
题号一二三四五总分
总分上机

分数101045152070%30%100

注意：不能拆卷!卷面不整洁最多可以扣3分.

一、单项选择题（10分）

1．算法的渐进时间复杂度是指（）。
A．算法程序执行的绝对时间
B．算法中执行语句的总条数
C．算法最深层循环语句中原操作重复执行的次数
D．随着问题规模的增大，算法执行时间的增长趋势

2．三个元素X、Y和Z顺序进栈，若进栈过程中允许退栈，不可能得到的退栈排
列是（）。
A．XYZB．YZX
C．ZXYD．ZYX

3．利用折半查找在有序表(4，10，28，32，46，55，63，76，97)中查
找28，55和97时，所需进行的关键字和给定值的比较次数分别为（）。
A．3，3，4B．3，4，3
C．4，3，3D．4，4，3

4．对任一棵二叉树进行遍历，如果只看叶子结点的输出序列，则叶子的先序序列
和后序序列所对应的次序关系（）。
A．不确定B．相同
C．互为逆序D．不相同

9-1
5．下列排序算法中，其时间复杂度和记录的初始排列无关的是（）。
A．堆排序B．插入排序
C．快速排序D．起泡排序

二、填空题（10分）

（不写解答过程，将答案直接填写在试题的空上）

1．数据结构在计算机中的表示被称为。

2．包含t个非零元素、m行n列的稀疏矩阵，采用三元组表示法存储该矩阵，当t
值很小或与m•n等数量级时，快速转置算法在这两种条件下的时间复杂度分别
为。

3．使用循环队列对n个结点的满二叉树进行按层次的横向遍历，所开设的队空间大

小至少应为。

4．假设哈希表的表长为m，哈希函数为H(key)，若用二次探测再散列解决冲突，则

探查地址序列的形式表达为。

5．在插入排序、起泡排序、快速排序、堆排序和归并排序等五个排序方法中，适合

做“最低位优先”多关键字排序的有。

三、解答题（本大题共5小题，共45分）

1．森林转化为对应的二叉树后，对该二叉树进行先序遍历和中序遍历，结果为：
先序序列HDACBGFE
中序序列ADCBHFEG
请画出原来的森林。

9-2

2.对于给定的关键字序列：Sun，Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，
Sep，Oct，Nov，Dec，Moon。
（1）以字典序比较大小，画出该输入序列所创建的二叉排序树；
（2）写出查找关键字Moon的比较过程；
（3）画出按教科书的算法删除关键字Sun后的二叉排序树。

9-3
3.利用堆排序方法对一组关键字序列
（7，10，14，23，33，56，66，72，90）
只进行前两趟的非递减序排序，按要求完成下列问题：
（1）画出排序的“初始堆”，并统计建立初始堆所需要进行的比较次数；
（2）画出第一趟和的第二趟的堆排序结果。

建初始化堆比较次数：

第一趟结果

第二趟结果

9-4
4．已知一个图如下所示，其顶点按A、B、C、D、E、F、G顺序存放在邻接表的
顶点表中，请画出该图的完整邻接表，使得按此邻接表进行深度优先遍历时得到的顶
点序列为ACFGDEB，进行广度优先遍历时得到的顶点序列为ACBDFEG。

5．已知一个电文中只含‘A’,’B’,’C’,’D’,’E’,’F’,’G’七种字符，且每个字母在电文中出
现的频度依次为：0.15,0.05,0.20,0.28,0.12,0.11,0.09，按要求完成下列问题：
（1）按HuffnamCoding算法和所给的存储空间图示，画出构造Huffman树的存
储表示及Huffman编码（注意：为使编码无二义性，应保持左子树根的结点序号比．
右子树根的结点序号小．）。

HTweightparentlchildrchild
1

2

3

4

5

6

7

8

9
10

11
12

13

9-5
（2）若电文中的字母总数为1000，估算经哈夫曼编码后得到的电文总长：

四．算法阅读题（15分）

一个AOV网G的邻接矩阵如下图所示，阅读所给的算法（算法中的Q是一个循
环队列结构），并完成下面的两个问题。

StatusgraphXP（GraphG）{
FindInDegree(G,indegree);
InitQueue(Q);
for(i=0;i<G.vexnum;++i)
if(!ind