当前位置：问答库＞考研试题

一、填空题

1． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。

【答案】

或

【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。

2． 在哈希函数中，P 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

3． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。

【答案】

【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。

4． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。

【答案】逻辑特性；在计算机内部如何表示和实现；数学特性

5． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

6． 高度为h 的堆中，最多有_____元素，最少有_____个元素。

【答案】

当最后一层只有

【解析】当这个堆构成的是满二叉树时，元素的个数最多，

元素个数为一个元素时，此时堆的元素个数最少，元素个数为

7． 数组的存储结构采用_____存储方式。

【答案】顺序存储结构

【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。

8． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。

【答案】

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：

根据上述公式起始地址就为488。

9． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

【答案】

【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

10．分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为

11．在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））

【答案】归并；堆

12．在一棵m

阶的个数是_____。

【答案】

【解析】m

阶树除根结点和叶子结点外，结点中关键字个数最多是最少

13．在循环队列中，队列长度为n ，存储位置从0到，编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。

【答案】

14．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; （10，7，-9，0，47，23，1，8，98，36）

15．如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。

【答案】69

【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。

树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的

关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字

二、算法设计题

16．结点类型和存储结构如下：

试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。

【答案】算法如下：