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

一、填空题

1． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。

【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储

2． 在一棵m 阶的个数是_____。

【答案】

最少

【解析】m 阶树除根结点和叶子结点外，结点中关键字个数最多是

3． 循环队列的引入，目的是为了克服_____。

【答案】假溢出时大量移动数据元素

【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。

4． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

5． 完善算法：求KMP 算法.next 数组。

END ； 【答案】

6． 线性表

【答案】（n －1）/2

【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平

第 2 页，共 53 页

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

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

用数组表示，假定删除表中任一元素的概率相同，则删除一个元素

平均需要移动元素的个数是_____。

均次数为

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

【答案】

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

8． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。

【答案】要加“虚结点”。

设编号为

和

的结点在顺序存储中的下标为

和

。

9． 在单链表中设置头结点的作用是_____。

【答案】方便运算

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

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

11．对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4; 2

12．在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

，

则结点

和

在同一层上的条件是

【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，

第 3 页，共 53 页

13．已

求REPLACE （S ，V , m ）=_____。

知

【答案】

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

【答案】 15．假定查找有序表

【答案】37/12

【解析】折半查找时每个的次数如表所示：

表

平均查找次数为

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____

二、选择题

16．—

组记录的关键码为

准得到的一次划分结果为（ ）。

【答案】C

【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。

第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为

则利用快速排序的方法，以第一个记录为基

一次划分结束。

17．设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，放于

中，那么第i 行的对角元素

存放于B 中（ ）处。

【答案】A

【解析】

中列标不大于行标，

又

存放在

中，

所以

存

存放的位置为

第 4 页，共 53 页