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

一、填空题

1． 阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】

【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。

2． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。

【答案】稳定

3． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。

【答案】15

2n

【解析】当时，100n2>2n，而，时，100n ＜2

4． 在循环队列中，队列长度为n ，存储位置从0到，n ﹣1编号，以rear 指示实际的队尾元素，

现要在此队列中插入一个新元素，新元素的位置是_____。

【答案】

5． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。

【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ；

6． 二进制地址为011011110000, 大小为

【答案】011011110100；011011100000

第 2 页，共 43 页

和块的伙伴地址分别为:_____

【解析】011011110000是块的起始地址，大小分别为算公式如下:

和其伙伴块的起始地址计

当大小为4时，起始地址为011011110000+0100。当大小为16时，起始地址为:011011110000-010000。

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

a 中存放待排序的关键字

【答案】

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

8． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。

【答案】O(1)；O(n)；O(1)；O(1)

【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，

第 3 页，共 43 页

必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。

9． 外排序的基本操作过程是_____和_____。

【答案】生成有序归并段(顺串) ；归并

10．属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

二、判断题

11．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第k ﹣1层具有的最多结点数为余下的

【答案】 √

【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为k ﹣1层全满时，此时从根结点到第k ﹣1层具有最大的结点数为

12．2，n ，a 2，a n

若…，…，桟的输入序列是1，输出序列是a 1，（ ）

【答案】 ×

【解析】出找序列不一定满足a 1＞a i+1... ＞a n ，比如1进栈，然后出找，a 1＝1。

13．堆肯定是一棵平衡二叉树。（ ）

【答案】×

【解析】堆是n 个元素的序列，排序树，更不会是平衡二叉树。

可以看成是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉

14．直接访问文件也能顺序访问，只是一般效率不高。（ ）

【答案】×

【解析】直接访问文件不能进行顺序访问，只能按关键字随机存取。在ISAM 文件上检索记录时，先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至找到为止。

15．广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）

【答案】 ×

【解析】广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是

第 4 页，共 43 页

个结点在第k 层的任一位置上。（ ）

则有:。

。