（ ）。
A）快速排序 B）堆排序 C）归并排序 D）直接插入排序
（8）在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。（北方名校经典试题）
A）直接插入排序 B）起泡排序 C）简单选择排序D）基数排序 （9）一棵有124个叶结点的完全二叉树，最多有（ ）个结点。
A）247 B）248 C）249 D）250
（10）一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用 ( )方法。
A）快速排序 B）堆排序 C）插入排序 D）二路归并排序 二、（本题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)（其中ai 八、（本题8分） （1）设T是具有n个内结点的判断二叉树，I是它的内路径长度，E是它的外路径长度，试利用归纳法证明 E＝I＋2n，n＞0。 （2）利用（1）的结果，试说明，成功查找的平均比较次数s与不成功查找的平均比较次数u之间的关系，可用公式s?(1?1n)u?1，n＞0表示。 提示：判断二叉树只有度为0或度为2的结点；判断二叉树成功查找的比较次数为内路径长度与内结点数之和，不成功查找的比较次数为外路径长度。 九、（本题9分） 一个深度为h的满m叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点有m棵非空子树。问： （1）第k层有多少个结点？（k≤h） （2）整棵树有多少个结点？ （3）若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，编号为i的结点的双亲结点的编号是什么？编号为i的结点的第j个孩子结点（若存在）的编号是什么？ 十、（本题15分） 设散列表的关键字取值范围为0 ~ m-1，n为对散列表的最大插入次数，设计散列表，允许使用以O(m+n)空间，要求查找、插入和删除算法的时间复杂度都是O(1)。 模拟试题（八）参考答案 一、单项选择题（每小题 2 分，共20分） （1）参考答案：B） （2）【分析】存储位置=n+(n-1)+…+(n-i+2)+i-j=(i-1)(2n-i+2)/2+j-i。 参考答案：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× (k-1)＜kh，从而：h-1≤logk(n×(k-1))＜h，进而：h??logk(n?(k?1))??1 即有：kh-1≤n× 所以：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）中结点②的后继是结点③。 五、（本题8分） 【解答】树的查找路径是从根结点开始到所要查找的结点的路径，最大不会超过B-树的深度。在B树中，除根结点外所有非终端结点都含有??m?棵子树，所以有n个关键字的B-树的最大深度为根结点具有两棵子??2?树，其余非终端点有??m?棵子树，设最大路径长度是x，由于叶子结点表示查找不成功，叶子结点不含关键?2??字，可知B-树的深度为x+1， 第1层共有1个结点，含1个关键字； 第2层共有2个结点，含2(??m?-1)个关键字； ?2?? 第3层共有2?…… ?m??m??m?2(-1)个关键字； 个结点，含?????222??????x?2?m?第x层共有2 ?2????m?个结点，含2 ?2???x?2( ?m?-1)个关键字； ???2??m??m?(-1)＝2??2??2????x?1故，共含有的关键个数为： ?m??m??m??m?1+2(-1)+2(-1)+…+2 ???2??2???2????2????x?2?1 ?m?由此可得：n?2?2???x?1?1，解得：x?1?log?m?(?2???n?1)，这就是具有n个关键宇的B一树的查2找的最大路径长度。 六、（本题8分） 【解答】折半查找对应的判定树如下图所示。查找不成功的对应于外部结点。查找不成功所走的路径是从根结点到每个外部结点（图中方块结点），和给定值进行比较的关键字个数等于该路径上内部结点个数。 在不成功情况下，一共比较的次数为3*3+4*10=49次。 平均查找长度为49/13≈3.77 七、（本题8分） 【解答】对于a来说，在S2中总可找到离a最近的祖先结点d，这时a 八、（本题8分） 【解答】 （1）证明：n=1时显然成立，设n=k时成立，即Ek=Ik＋2k，当n=k+1时，设所增加的结点的路径长度为Dk，则有： Ik+1=Ik+Dk Ek+1=Ek-Dk+2(Dk+1)=Ek+Dk+2=Ik+2k+Dk+2=Ik+1+2(k+1)=Ik+1+2n 结论也成立。 （2）根据二叉树性质：度为0的结点数=度为2的结点数+1，所以外结点数=n＋l。 s=查找成功总的比较次数/内结点数=(I+n)/n ① u=查找失败总的比较次数/外结点数=E/(n+1)=(I+2n)/(n+1) ② 由①得：I=ns-n，由②得：I=(n+1)u-2n，所以可得：ns-n=(n+1)u-2n，进一步得：s?(1?1n)u?1。
相关推荐：
loading