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

一、填空题

1． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

2． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，

【答案】比较；移动

3． 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。

【答案】

【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，

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

【答案】起泡；快速

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

5． 设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：_____;

【答案】

6． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

7． 二进制地址为011011110000，大小为

【答案】011011110100；011011100000

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

其伙伴块的起始地址计算公

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

当大小为4时，起始地址

为

8． 建立索引文件的目的是_____。

【答案】提高查找速度

9． 在哈希函数

中，P 值最好取_____。

当大小为16时，起始地址为

：

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

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

10．己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。

【答案】2；4；3

【解析】二分法查找元素次数列表

查

找100是找到115就停止了。

二、选择题

11．组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。

A. B. C. D.

【答案】B

【解析】因组与组之间已有序，故将

个组分别排序即可，基于比较的排序方法每组的时

间下界为

0全部时间下界为

12．有六个元素6, 5, 4, 3, 2, 1顺序入栈，下列不是合法的出栈序列的是（ ）。

A.543612

B.453126 C.346521 D.234156 【答案】C

【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出找。

13．采用指令Cache 与数据Cache 分离的主要目的是（ ）

A. 减低Cache 的缺失损失 B. 提高Cache 的命中率 C. 减低CPU 平均访问时间 D. 减少指令流水线资源冲突 【答案】D

【解析】指令流水线不会断流，预取过来的都是指令

14．某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a , b , c , d , e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（ ）。

A.b ，a , c , d ，e B.d ，b , a , c ，e C.d ，b , c , a ，e D.e ，c ，b , a ，d 【答案】C

【解析】根据题意，队列两端都可以输入数据元素，但是只能在一端输出数据元素，这种队列为输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队，从而得出不可能的情况。

假设L 代表从左端入队，R 代表从右端入队，出队都是从左端L 出。四个选项所给序列的进队操作序列分别为：

选项 A. aL （或 aR ）, bL, cR, dR, eR 选项 B. aL （或 aR ）, bL, cR，dL , eR 选项C. 不可能出现 选项 D. aL （或 aR ）, bL, cL, dR, eL

15．设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。

【答案】A

【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是