棵。
A）132 B）154 C）429 D）前面均不正确
（10）对n(n>=2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。
A）该树一定是一棵完全二叉树 B）树中一定没有度为1的结点
C）树中两个权值最小的结点一定是兄弟结点
D）树中任一非叶结点的权值一定不小于下一任一结点的权值 二、（本题8分）
斐波那契数列Fn定义如下：
F0=0，F1=1，Fn=Fn-1+Fn-2
请就此斐波那契数列，回答下列问题：
（1）在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，…，F1，F0精确计算多少次？ （2）若用有关大O表示法，试给出递归计算Fn时递归函数的时间复杂度是多少？ 三、（本题8分）
证明：如果一棵二叉树的后序序列是u1,u2,…,un，中序序列是up1,up2,…,upn，则由序列1,2,…,n可通过一个栈得到序列p1,p2,…,pn。
四、（本题8分）
如下图所示为5个乡镇之间的交通图，乡镇之间道路的长度如图中边上所注。现在要在这5个乡镇中选择一个乡镇建立一个消防站，问这个消防站应建在哪个乡镇，才能使离消防站最远的乡镇到消防站的路程最短。试回答解决上述问题应采用什么算法，并写出应用该算法解答上述问题的每一步计算结果。
135649412263
五、（本题8分）
证明一个深度为n的AVL树中的最少结点数为：Nn=Fn+2-1 (n≥0) 其中，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分）
N2个度为2的结点，Nm个度为m已知一棵度为m的树中有N1个度为1的结点，…，
的结点。试问该树中有多少个叶子结点？（北方名校经典试题）
十、（本题15分）
试用递归法编写输出从n个数中挑选 k个进行排列所得序列的算法。
模拟试题（七）参考答案
一、单项选择题（每小题 2 分，共20分） （1）参考答案：C）
（2）【分析】如下所示，三对角矩阵第1行和最后1行非零元素个数为2个，其余各行的非零元素个数是3个，所知a66,65前面共有2+3*64＝194个非零元素，a66,65本身是第 195个非零元。
?a11?a?21??A???????a12a22a32a23a33?a34?an?2,n?1?an?2,n?2an?1,nan?2,n?1an?1,n?1an,n?1?????? ??an?1,n?ann??参考答案：B）
（3）【分析】在哈夫曼树的非叶结点中最多只有1个结点的度不为m，设非叶结点的个数为k，则其中有k-1个结点的度为m，设另1个结点的度为u，则2≤u≤m，设结点
总数为n总，则有如下关系：
n总-1=m(k-1)+u n总=k+n
① ②
将②代入①可得：k+n-1= m(k-1)+u，解得：k?(n?1)?(m?u)，由于2≤u≤m，
m?1所以可得0≤m-u＜m-1，所以可得：
n?1n?1?n?1?+1，可知k??≤k＜。 ?m?1m?1?m?1?参考答案：C）
（4）【分析】设顶点按拓扑排序序列为：v0,v1,…,vn-1，则对于邻接矩阵A，只有当i
参考答案：C）
（5）【分析】设另一棵子树的结点个数为n，所以有 m=n+k+1，可知n= m-k-l。 参考答案：C）
（6）【分析】因为K个关键字互为同义词，只有在存入第一个关键字的情况下不发生冲突，所以至少需进行1+2+…+K=K(K+1)/2次探测。
参考答案：D）
（7）【分析】由于每个非终端结点的平衡因子均为0，所以每个非终端结点必有左右两个孩子，且左子树的高度和右子树的高度相同，这样AVL树是满二叉树。高度为k的
k
满二叉树的结点数为2-l。
参考答案：D） （8）【分析】本题中只有直接插入排序利用前面有序的子序列这个性质，如用直接插入排序对本题只需将最后一个元素插入到前面99999个元素的有序子序列中即可，显然比较次数较少。
参考答案：A）
（9）【分析】具有n个结点有不同形态的树的数目和具有n-l个结点互不相似的二叉树的数目相同（将树转化为二叉树时，根结点右子树为空，所以除根结点而外只有左子树，其不相似的二叉树的等价于不相似的左子树）。具有n个结点互不相似的二又树的数目为
11n6，本题中应为C2C12?132。 nn?16?1参考答案：A）
（10）参考答案：A） 二、（本题8分） 【解答】
（1）设在计算Fn时，由Fn-1+Fn-2可知Fn-1要精确计算1次； 由Fn-1=Fn-2+Fn-3可知Fn=2Fn-2+Fn-3，Fn-2要精确计算2次；
由Fn-2=Fn-3+Fn-4可知Fn=3Fn-3+2Fn-4，Fn-3要精确计算3次，Fn=3Fn-3+2Fn-4公式中Fn-3
的系数为Fn-3要精确计算次数，而Fn-4的系数为Fn-2要精确计算次数，以此类推，设Fn-j的精确计算次为aj，则有：Fn=aj*Fn-j+aj-1*Fn-j-1。
Fn-j-1的精确计算次数为aj+1， 由Fn-j=Fn-j-1+Fn-j-2可知Fn=(aj+ aj-1)*Fn-j-1+aj*Fn-j-2 ，所以有：
aj+1=aj+aj-1
由于Fn-1要精确计算a1为1次，即a1=1，即可知Fn-1，Fn-2，…，F1，F0的精确计算次为：1，2，3，5，……，aj=aj-1+aj-2……
与斐波那契数列数列：
0，1，2，3，5，……，Fn=Fn-1+Fn-2…… 比较可知aj=Fj+1。
（2）由于Fn的计算最终要转化为F0与F1之和，其加法的计算次数为F0与F1的精确计算次数之和再减1之差，由于F0=Fn-n与F1=Fn-(n-1)，所以计算Fn时，加法计算次数为：
an+an-1-1=Fn+1+Fn-1
由于Fn=
11?5n11?5n1?5n()?()，可知时间复杂度为O(())。 22255三、（本题8分）
【解答】当n=1时，结论显然成立。
设n<=k时结论成立，当n=k+1时，设一棵二叉树的后序序列是u1,u2,…,un，中序序列是up1,up2,…,upn，可知un是二叉树的根结点，设pj?n，可知{up1,up2,…,upj?1}是左子树的结点集合，{upj?1,upj?2,…, upn}是右子树的结点集合，进一步可知：
（1）左子树的后序序列是u1,u2,…,uj?1，中序序列是up1,up2,…,upj?1，由归纳假设知序列1,2,…,j-1可以通过一个栈得序列p1,p2,…,pj?1。
（2）右子树的后序序列是uj,uj?1,…, un?1，中序序列是upj?1,upj?2,…, upn，设
??uj，u2??uj?1，…，un??j?un?1；u?p1??upj?1，u?p?2?upj?2，…，u?p?n?j?upn，则u1??pj?1?j?1，p2??pj?2?j?1，…，pn??j?pn?j?1，由归纳假设知序列1,2,…,n-jp1可以通过一个栈得序列p1??j，显然按同样的方式，j,j+1,…,n-1 可以通过一?，p2?，…，pn个栈得序列j?1?p1??j，也就是pj?1，pj?2，…，pn。 ?,…,j?1?pn?,j?1?p2