数据结构期末复习题讲解.pdf

（1）若以1234作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输出受限双端队列
得到的输出序列是（）。

A）1234B）4132C）4231D）4213
（2）将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[298]中，A中元素a在B数组
66,65
中的位置k为（）（假设B[0]的位置是1）。A）198B）195C）197
D）198
（3）若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（）。
nn1n
A）n-1B）1C）D）1
mm1m1

（4）若一个有向图具有拓扑排序序列，并且顶点按拓扑排序序列编号，那么它的邻接矩阵必定为
（）。
A）对称矩阵B）稀疏矩阵C）三角矩阵D）一般矩阵
（5）设森林F对应的二叉树为有m个结点，此二叉树根的左子树的结点个数为k，则另一棵子树的结
点个数为（）。
A）m-k+1B）k+1C）m-k-1D）m-k
（6）假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（）
次探测。
A）K-1次B）K次C）K＋l次D）K(K+1)/2次
（7）一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。
A）2k-1-1B）2k-1C）2k-1+1D）2k-1
（8）如表r有100000个元素，前99999个元素递增有序，则采用（）方法比较次数较少。
A）直接插入排序B）快速排序C）归并排序D）选择排序
（9）如果只考虑有序树的情形，那么具有7个结点的不同形态的树共有（）棵。
A）132B）154C）429D）前面均不正确
（10）对n(n>=2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）。
A）该树一定是一棵完全二叉树
B）树中一定没有度为1的结点
C）树中两个权值最小的结点一定是兄弟结点
D）树中任一非叶结点的权值一定不小于下一任一结点的权值
二、（本题8分）
斐波那契数列Fn定义如下：
F=0，F=1，F=F+F
01nn-1n-2
请就此斐波那契数列，回答下列问题：
（1）在递归计算F的时候，需要对较小的F，F，…，F，F精确计算多少次？
nn-1n-210
（2）若用有关大O表示法，试给出递归计算Fn时递归函数的时间复杂度是多少？
三、（本题8分）

证明：如果一棵二叉树的后序序列是u,u,…,u，中序序列是u,u,…,u，则由序列1,2,…,n可通
12nppp
12n

过一个栈得到序列p,p,…,p。
12n
四、（本题8分）
如下图所示为5个乡镇之间的交通图，乡镇之间道路的长度如图中边上所注。现在要在这5个乡镇中选
择一个乡镇建立一个消防站，问这个消防站应建在哪个乡镇，才能使离消防站最远的乡镇到消防站的路程最

短。试回答解决上述问题应采用什么算法，并写出应用该算法解答上述问题的每一步计算结果。

112
2
3

596

6
43
4

五、（本题8分）
证明一个深度为n的AVL树中的最少结点数为：Nn=F-1(n≥0)
n+2
其中，Fi为Fibonacci数列的第i项。
六、（本题8分）
简单回答有关AVL树的问题：（北方名校经典试题）
（1）在有n个结点的AVL树中，为结点增加一个存放结点高度的数据成员，那么每一个结点需要增加
多少个字位（bit）？
（2）若每一个结点中的高度计数器有8bit，那么这样的AVL树可以有多少层？最少有多少个关键字？
七、（本题8分）
设有12个数据{25，40，33，47，12，66，72，87，94，22，5，58}，它们存储在散列表中，利用线性探测再
散列解决冲突，要求插入新数据的平均查找次数不超过3次。
（1）该散列表的大小m应设计多大？
（2）试为该散列表设计相应的散列函数。
（3）顺次将各个数据散列到表中。
（4）计算查找成功的平均查找次数。
八、（本题8分）

已知某电文中共出现了10种不同的字母，每个字母出现的频率分别为A：8，B：5，C：3，D：2，E：
7，F：23，G：9，H：11，I：2，J：35，现在对这段电文用三进制进行编码（即码字由0，l，2组成），问
电文编码总长度至少有多少位？请画出相应的图。
九、（本题9分）
已知一棵度为m的树中有N个度为1的结点，N个度为2的结点，…，N个度为m的结点。试问该
12m
树中有多少个叶子结点？（北方名校经典试题）
十、（本题15分）
试用递归法编写输出从n个数中挑选k个进行排列所得序列的算法。

模拟试题（七）参考答案

一、单项选择题（每小题2分，共20分）
（1）参考答案：C）
（2）【分析】如下所示，三对角矩阵第1行和最后1行非零元素个数为2个，其余各行的非零元素个数是3
个，所