}
}
}
exchange(list[outlen+1],list[i]);
*模拟试题（八）
注：本套试题选作
一、单项选择题（每小题 2 分，共20分） （1）一个 n*n的带状矩阵A=[aij]如下：
?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??将带状区域中的元素aij（|i-j|≤1）按行序为主序存储在一维数组B[3n-2]中，元素aij
在B中的存储位置是（ ）。
A）i+2j-2 B）2i+j-3 C）3i-j D）i+j+1 （2）一n×n的三角矩阵A=[aij]如下：
?a11?????a12?a1n? a22?a2n?????ann?将三角矩阵中元素aij(i≤j)按行序为主序的顺序存储在一维数组B[1..n(n+1)/2]中，则aij在B中的位置是（ ）。
A）(i-1)(2n+i)/2+i-j+1 B）(i-1)(2n-i+2)/2+j-i+1 C）(i-1)(2n-i)/2+j-i D）(i-1)(2n-i+2)/2+j-i
（3）设有一棵度为3的树，其叶结点数为n0，度为1的结点数为n1，度为2的结点数为n2，度为3的结点数为n3，则n0与n1，n2，n3满足关系（ ）。
A）n0=n2+1 B）n0=n1+2n3+1 C）n0=n2+n3+1 D）n0=n1+n2+n3 （4）G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。
A）6 B）7 C）8 D）9
（5）设图G用邻结表存储，则拓扑排序的时间复杂度为（ ）。
A）O(n) B）O(n+e) C）O(n2) D）O(n×e) （6）用n个键值构造一棵二叉排序树，最低高度为（ ）。
A）n B）n C）nlog2n D）?log2n??1
2（7）若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A）快速排序 B）堆排序 C）归并排序 D）直接插入排序 （8）在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。（北方名校经典试题）
A）直接插入排序 B）起泡排序 C）简单选择排序D）基数排序 （9）一棵有124个叶结点的完全二叉树，最多有（ ）个结点。
A）247 B）248 C）249 D）250
（10）一个序列中有10000
个元素，若只想得到其中前10个最小元素，最
好采用 ( )方法。
B）堆排序 D）二路归并排序
A）快速排序 C）插入排序
二、（本题8分）
要借助栈由输入序列是输入1,2,3,?,n得到的输出序列为p1,p2,p3,?,pn(此输出序列是输入序列经过栈操作后的某个排列)，则在输出序列中不可能出现当i 三、（本题8分） 已知某一完全k叉树只有度为k的结点及叶结点，设叶结点数为n0，试求它的树高h。（南方名校经典试题） 四、（本题8分） 试讨论怎样在一棵中序线索二叉树上查找给定结点x在后序序列中的后继。 五、（本题8分） 具有n个关键字的B一树的查找的最大路径长度是多少？ 六、（本题8分） 对长度为12的有序表(a1，a2，?，a12)（其中aia12以及ai 图 判定树示意图 在不成功情况下，一共比较的次数为3*3+4*10=49次。 平均查找长度为49/13≈3.77 八、（本题8分） （1）设T是具有n个内结点的判断二叉树，I是它的内路径长度，E是它的外路径长度，试利用归纳法证明 E＝I＋2n，n＞0。 （2）利用（1）的结果，试说明，成功查找的平均比较次数s与不成功查找的平均比较次数u之间的关系，可用公式s?(1?1)u?1，n＞0表示。 n提示：判断二叉树只有度为0或度为2的结点；判断二叉树成功查找的比较次数为内路径 长度与内结点数之和，不成功查找的比较次数为外路径长度。 九、（本题9分） 一个深度为h的满m叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点有m棵非空子树。问： （1）第k层有多少个结点？（k≤h） （2）整棵树有多少个结点？ （3）若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，编号为i的结点的双亲结点的编号是什么？编号为i的结点的第j个孩子结点（若存在）的编号是什么？ 十、（本题15分） 设符号表T中的标识符（关键字）x满足：l≤x≤m，n为对T表的最大插入次数，设计符号表T的表示结构，允许使用以O(m+n)空间，并写出T的初始化、查找、插入和删除算法，要求它们的时间复杂度都是O(1)。 模拟试题（八）参考答案 一、单项选择题（每小题 2 分，共20分） （1）参考答案：B） （2）【分析】存储位置=n+(n-1)+…+(n-i+2)+i-j+1=(i-1)(2n-i+2)/2+j-i+1。 参考答案：B） （3）【分析】用n表示结点总数，则有：n= n0+n1+n2+n3； 由于除根结点而外，结点与分支一一对应，而分支数= n1+2n2+3n3，即有：n-1= n1+2n2+3n3。 由上面两式可得：n0=n1+2n3+1 参考答案：B） （4）【分析】本题中由于是非连图，至少有一个顶点与其他顶点不连，这个顶点是孤立点，其他顶点可组成一个连通图，由于8个顶点的完全图共有28条边，所以具体28个顶点的连通图的顶点个数至少为8，这样非连通图至少有9个顶点。 参考答案：D） （5）【分析】对于有n个顶点e条边的有向图，建立各顶点的入度时间复杂度为O(e)，建立入度为零的栈的时间复杂度为O(n)，在拓扑排序过程中，最多每个顶点进一次栈，入度减1的操作最多总共执行e次，可知总的时间复杂度为O(n+e) 参考答案：B） （6）【分析】当用n个键值构造一棵二叉排序树是一棵完全二叉树时，高度最低，此时高度为?log2n??1。 参考答案：D） （7）【分析】快速排序和堆排序都是不稳定的，应排除；归并排序稳定，时间复杂度O(nlogn)，满足条件；直接插入排序，时间复杂度为O(n2)，排除。 参考答案：C） （8）【分析】对直接插入排序而言，算法时间复杂度为O(n2)，但若待排记录序列为“正序”时，其时间复杂度可提高至O(n)。若待排记录序列按关键字“基本有序”，直接 插入排序的效率就可大大提高，此外由于直接插入排序算法简单，在n值很小时效率也高。 参考答案：A） （9）【分析】完全二叉树中度为1的结点最多只有1个，由二叉树的度和结点的关系： n=n0+n1+n2 (1) n=n1+2n2+1 (2) 由2(1)-(2)得，n=2n0+n1-1=247+n1≤248，所以本题应选择B）。 参考答案：A） （10）参考答案：B） 二、（本题8分） 【解答】设pj 三、（本题8分） 【解答】设度为k的结点数为nk，结点总数为n，则有如下关系： n= nk+n0 ① 又由于树中只有n-1条边，所以： n-1=k×nk ② 由①与②可得：nk=(n0-1) / (k-1)，进而有n= k?n0?1 k?1(k-1)≤kh-1 对于k叉完全树有如下关系：kh-1-1＜n× kh-1≤n×(k-1)＜kh，h-1≤logk(n×(k-1))＜h，即有：从而：进而：h??logk(n?(k?1))??1 所以：h=?logk(k?n0?1)??1 四、（本题8分） 【解答】由于后序遍历二叉树需要知道的关键是访问当前结点的双亲结点，需要由中序线索树才能得到当前结点的双亲，中序线索树有如下性质： ? 若x是parent的左孩子，则parent是x的最右子孙的右线索； ? 若x是parent的右孩子，则parent是x的最左子孙的左线索。 用以上性质能找到x的双亲结点parent。 若x是parent的右孩子，则parent结点就是x的后序序列的后继结点；如下图（1）中结点①的后继是结点②。 若x是parent的左孩子，则： 如果parent的右指针域为线索的话，那么parent就是x的后序序列的后继结点，如下图（2）中结点②的后继是结点③。 否则 parent右子树中最左边第一个左右孩子均为线索的结点，就是 x的后序序列的后继结点。如下图（3）中结点②的后继是结点③。 图 给定结点x在后序序列中的后继示意图 五、（本题8分） 【解答】树的查找路径是从根结点开始到所要查找的结点的路径，最大不会超过B-树的深度。在B树中，除根结点外所有非终端结点都含有??棵子树，所以有n个关键 ?2?字的B-树的最大深度为根结点具有两棵子树，其余非终端点有??m??m??棵子树，设最大路径2??