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

一、填空题

1． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。

【答案】O(m＋n)

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

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

【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。

3． 对n 个记录的表

【答案】n (n－1) /2

【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要。

4． 设数组数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么

(1)存放该数组至少需要的单元数是_____；

(2)存放数组的第8列的所有元素至少需要的单元数_____；

(3)数组按列存储时，元素A[5，8]的起始地址是_____。

【答案】270；27；2204

【解析】数组的元素个数为9*10＝90，因为每个元素占内存48个二进制位，即6个字节。故总需要90*6＝540个字节，因为主内存字长为16位，即2个字节，所以至少需要540/2＝270个单元数。第8列有9个元素，共占9*6＝54个字节，因此至少需要54/2＝27个单元数。由题知，每个元素占3个单元。按列存储时，A[5，8]的起始地址为2000＋[(8﹣1)*9＋(5﹣0)]*3＝2204。

5． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，

进行简单选择排序，所需进行的关键字间的比较次数为_____。

关键字最多。

6． 一个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

7． 设二维数组A 的行和列的下标范围分别为[0:8]和[0:10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_____。

【答案】A[2][3]

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*i＋j ＋l ﹣l)*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。

8． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。

【答案】集合；线性结构；树形结构；图状结构(网状结构)

9． 高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】

。当最后一层只有【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为

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

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

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

11．下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空:

(_____i)；

＝

_____.

_____

【答案】a ＋l ；n%10

【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

12．在哈希函数中，p 值最好取_____。

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

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

二、单项选择题

13．下列选项中, 用于提高RAID 可靠性的措施有（ ）

Ⅰ. 磁盘镜像

Ⅱ. 条带化

Ⅲ. 奇偶校验

Ⅳ. 增加Cache 机制

A. 仅Ⅰ、Ⅱ

B. 仅Ⅰ、Ⅲ

C. 仅Ⅰ、Ⅲ和Ⅳ

D. 仅Ⅱ、Ⅲ和Ⅳ

【答案】B

【解析】能够提高RAID 可靠性的措施主要是对磁盘进行镜像处理和进行奇偶校验。其余选项不符合条件。

14．下列哪一种图的邻接矩阵是对称矩阵？（ ）

A. 有向图

B. 无向图

C.AOV 网

D.AOE 网

【答案】B

【解析】邻接矩阵存储，就是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间关系的二维数组称为邻接矩阵。因为无向图中边是没有方向的，

所以

，所以无向图的邻接矩阵是对称矩阵。

15．采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。

A. 数据元素过多

B. 负载因子过大

C. 哈希函数选择不当

D. 解决冲突的算法选择不好

【答案】D