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

一、填空题

1． 数据结构中评价算法的两个重要指标是_____。

【答案】算法的时间复杂度和空间复杂度

2． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。

【答案】

【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为。

3． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。

【答案】（ ）；(（ ）) ；2；2

【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

4． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。

【答案】度；出度

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

检索和_____检索。

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

6． 以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。

【答案】

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

【答案】P ﹣＞next! ＝NULL

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

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

a 中存放待排序的关键字

【答案】

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

以达到整个序列有序。

9． VSAM 系统是由_____、_____、_____构成的。

【答案】索引集；顺序集；数据集

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

【答案】比较；移动

二、单项选择题

11．算法的计算量的大小称为计算的（ ）。

A. 效率 B. 复杂性 C. 现实性 D. 难度 【答案】B

【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。

12．下列排序算法中，占用辅助空间最多的是（ ）。

A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 【答案】A

【解析】归并排序的辅助空间为O(n)，快速排序所占用的辅助空间为

，堆排序所占

用的辅助空间为O(1)。

13．在页式存储管理系统中, 采用某些页面置换算法, 会出现Belady 异常现象, 即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中, 可能出现Belady 异常现象的是（ ）

Ⅰ.LRU 算法 Ⅱ.FIFO 算法 Ⅲ.OPT 算法 A. 仅Ⅱ B. 仅Ⅰ Ⅱ