福州大学《863数据结构与程序设计》考研模拟题2答案.doc

模拟卷二参考答案 单项选择题 1．A。考查时间复杂度的计算。 在程序中，执行频率最高的语句为“x=2*x”。设该语句共执行了t次，则，2t+1=n/2，故t=log2(n/2)-1=log2n-2，得T(n)=O(log2n)。 2．B。考查出栈序列。 出栈顺序必为d_c_b_a_，e的顺序不定，在任一个“_”上都有可能。 3．B。考查循环队列的性质。 入队时由于要执行(rear+1)%n操作，所以如果入队后指针指向0，则rear初值为n-1，而由于第一个元素在A[0]中，插入操作只改变rear指针，所以front为0不变。 4．C。考查完全二叉树的性质。 根据完全二叉树的性质，最后一个分支结点的序号为 ?768/2? =384，故叶子结点的个数为768-384=384。 5．C。考查二叉树的遍历算法。 前序序列为LRN，后序序列为NLR，由于前序序列和后序序列刚好相反，故不可能存在一个结点同时存在左右孩子，即二叉树的高度为4。1为根结点，由于根结点只能有左孩子（或右孩子），因此，在中序序列中，1或在序列首或在序列尾，ABCD皆满足要求。仅考虑以1的孩子结点2为根结点的子树，它也只能有左孩子（或右孩子），因此，在中序序列中，2或在序列首或序列尾，ABD皆满足要求。 6．D。考查树和二叉树的转换。 树转换为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数=分支结点数+1=2011-116+1=1896。通常本题应采用特殊法解，设题意中的树是如下图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子，故无右孩子的结点个数=2011-115=1896。 7．A。考查二叉排序树的查找过程。 在二叉排序树中，左子树结点值小于根结点，右子树结点值大于根结点。在选项A中，当查找到91后再向24查找，说明这一条路径（左子树）之后查找的数都要比91小，而后面却查找到了94，因此错误。 8．C。考查图的基本概念。 回路对应于路径，简单回路对应于简单路径，故Ⅰ错误；稀疏图是边比较少的情况，此时用邻接矩阵必将浪费大量的空间，应该选用邻接表，故Ⅱ错误。存在回路的图不存在拓扑序列，故Ⅲ正确。 9．D。考查散列表的性质。 Hash表的查找效率取决于：哈希函数、处理冲突的方法和装填因子。显然，冲突的产生概率与装填因子（即表中记录数与表长之比）的大小成正比，Ⅰ错误。冲突是不可避免的， 但处理冲突的方法应避免非同义词之间地址的争夺，Ⅲ正确。 10．A。考查排序的基本特点。 对绝大部分内部排序而言，只适用于顺序存储结构。快速排序在排序的过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。 11．B。考查堆的调整。 首先18 与10 比较，交换位置，再与25 比较，不交换位置。共比较了2 次，调整的过程如下图所示。 12.B。考查拓扑排序序列。 图B-2中有3个不同的拓扑排序序列，分别为abced、abecd、aebcd。 13．B。考查折半查找的过程。 具有n个结点的判定树的高度为 ?log2n? +1，长度为16，高度为5，所以最多比较5次。 14．D。考查快速排序。 递归次数与各元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少；如果划分后分区不平衡，则递归次数多。递归次数与处理顺序无关。 15．A。考查各种排序算法的过程。 看第一趟可知仅有88被移到最后。 如果是希尔排序，则12，88，10应变为10，12，88。因此排除希尔排序。 如果是归并排序，则长度为2的子序列是有序的。因此可排除归并排序。 如果是基数排序，则16，5，10应变为10，5，16。因此排除基数排序。 可以看到，每一趟都有一个元素移到其最终位置，符合冒泡排序特点。 16-20．C D B C C 21-25．A A D D B 26-30．A B B B C 二、填空题（前14个空，每空1分，后3个空，每空2分，共20分） 1． 抽象 实例 2． this指针 3． E D、F A、B、C、D、E D、F 4． virtual 5． 静态多态性 动态多态性 6. 抽象类 7. friend void fun(A a) 8. 继承 组合或模板 9. 在对象被系