（1）若以1234作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列是（ ）。
A）1234 B）4132 C）4231 D）4213
（2）将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[298]中，A中元素a66,65在B数组
B）195 C）197中的位置k为（ ）（假设B[0]的位置是1）。 A）198
D）198
（3）若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。
A）n-1
B）
?n??1 ???m?C）
?n?1?
???m?1?D）
?n??1 ???m?1?（4）若一个有向图具有拓扑排序序列，并且顶点按拓扑排序序列编号，那么它的邻接矩阵必定为
（ ）。
A）对称矩阵 B）稀疏矩阵 C）三角矩阵 D）一般矩阵
（5）设森林 F对应的二叉树为有 m个结点，此二叉树根的左子树的结点个数为k，则另一棵子树的结点个数为（ ）。
A）m-k+1 B）k+1 C）m-k-1 D）m-k （6）假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（ ）次探测。
A）K-1次 B）K次 C）K＋l次 D）K(K+1)/2次
（7）一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ ）个结点。
A）2k-1-1 B）2k-1 C）2k-1+1 D）2k-1
（8）如表r有100000个元素，前99999个元素递增有序，则采用（ ）方法比较次数较少。
A）直接插入排序 B）快速排序 C）归并排序 D）选择排序 （9）如果只考虑有序树的情形，那么具有7个结点的不同形态的树共有（ ）棵。
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，中序序列是up,up,…,up，则由序列1,2,…,n可通
12n过一个栈得到序列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分）
已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，…，Nm个度为m的结点。试问该树中有多少个叶子结点？（北方名校经典试题）
十、（本题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???????
a23a33?a34?an?2,n?1?an?2,n?2an?1,nan?2,n?1an?1,n?1an,n?1????? ???an?1,n?ann??a12a22a32参考答案：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，所以可得0≤m-u
m?1＜m-1，所以可得：
n?1n?1?n?1?+1，可知k?≤k＜。
??m?1m?1m?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的满二叉树的结点数为2k-l。
参考答案：D）
（8）【分析】本题中只有直接插入排序利用前面有序的子序列这个性质，如用直接插入排序对本题只需将最后一个元素插入到前面99999个元素的有序子序列中即可，显然比较次数较少。
参考答案：A）
（9）【分析】具有n个结点有不同形态的树的数目和具有n-l个结点互不相似的二叉树的数目相同（将树转化为二叉树时，根结点右子树为空，所以除根结点而外只有左子树，其不相似的二叉树的等价于不相似的左子树）。具有n个结点互不相似的二又树的数目为
参考答案：A）
（10）参考答案：A） 二、（本题8分） 【解答】
11n6C2C12?132。 n，本题中应为n?16?1
（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=aj*Fn-j+aj-1*Fn-j-1。 计算次数，而Fn-4的系数为Fn-2要精确计算次数，以此类推，设Fn-j的精确计算次为aj，则有：
由Fn-j=Fn-j-1+Fn-j-2可知Fn=(aj+ aj-1)*Fn-j-1+aj*Fn-j-2 ，Fn-j-1的精确计算次数为aj+1，所以有：
aj+1=aj+aj-1
Fn-2，F1，F0的精确计算次为：1，2，3，5，由于Fn-1要精确计算a1为1次，即a1=1，即可知Fn-1，…，……，
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，中序序列是up,up,…,up，
12n
{up,up,…, up}可知un是二叉树的根结点，设pj?n，可知{up,up,…,up}是左子树的结点集合，
12nj?1j?1j?2是右子树的结点集合，进一步可知：
（1）左子树的后序序列是u1,u2,…,uj?1，中序序列是up,up,…,up，由归纳假设知序列1,2,…,j-1
12j?1可以通过一个栈得序列p1,p2,…,pj?1。
（2）右子树的后序序列是uj,uj?1,…, un?1，中序序列是up,up,…, up，设u1…，??uj，??uj?1，u2nj?1j?2??j?un?1；u?p1??pj?1?j?1，p2??pj?2?j?1，…，un?upj?2，…，u?p?n?j?upn，则p1??upj?1，u?p?2?，p2?，…，pn??j?pn?j?1，由归纳假设知序列1,2,…,n-j可以通过一个栈得序列p1??j，显然按同样的pn 方式，j,j+1,…,n-1 可以通过一个栈得序列j?1?p1?,j?1?p2?,…,j?1?pn??j，也就是pj?1，pj?2，…，pn。
由（1）（2）及pj?n可知由1,2,…,n可通过一个栈得到序列p1,p2,…,pn。由数学归纳法可知本题结论成立。
四、（本题8分）
相关推荐：
loading