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

一、填空题

1． 当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

2． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】

【解析】哈夫曼树只有度为0和2的节点。

3． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____ (表示为n 的函数) 。

【答案】1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋…＋n) ＝n(n＋1)(n＋2)/6，即O(n)

【解析】当i ＝l 时，赋值语句就被执行了一次。当i ＝2时，赋值语句被执行了1＋2次。当i ＝3时，赋值语句被执行了1＋2＋3次。...... 可以推出赋值语句总共被执行了1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋... ＋n) ＝n(n＋1)(n＋2)/6次。

4． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树

【解析】二叉排序树(binary sort tree)或者是一棵空树，或者是具有下列性质的二叉树:①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

5． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。 【答案】

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

二、单项选择题

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

Ⅰ.LRU 算法

Ⅱ.FIFO 算法

Ⅲ.OPT 算法

A. 仅Ⅱ

B. 仅Ⅰ Ⅱ

C. 仅Ⅰ Ⅲ

D. 仅Ⅱ Ⅲ

【答案】A

【解析】Belady 现象只有FIFO 算法才会出现

7． 在无噪声情况下，若某通信链路的带宽为3kHz ，采用4个相位，每个相位具有4种振幅的QAM 调制技术，则该通信链路的最大数据传输速率是（ ）.

A.12kbps

B.24kbps

C.48kbps

D.96kbps

【答案】B

【解析】首先要根据信道有无噪声来确定是否采用奈奎斯特定理. 解题难点在于离散数值的确定，先确定调制技术的码元数，此处为4个相位乘以4种振幅，共16种，即该通信链路的最大数据传输速率＝2×3×log2(4×4) ＝6×4＝24kbps.

8． 为提高散列(Hash)表的查找效率, 可以采用的正确措施是（ ）。

Ⅰ. 增大装填(载) 因子

Ⅱ. 设计冲突(碰撞) 少的散列函数

Ⅲ. 处理冲突(碰撞) 时避免产生聚集(堆积) 现象

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅱ

D. 仅Ⅱ、Ⅲ

【答案】D

【解析】散列表的查找效率(比较次数) 取决于:散列函数、处理冲突的方法和散列表的装填因子α。α标志着散列表的装满程度, 通常情况下, α越小, 发生冲突的可能性越小; 反之, α越大, 表示已填入的记录越多, 再填入记录时, 发生冲突的可能性越大。因此选项Ⅰ错误, 越是增大装填因子, 发生冲突的可能性就越大, 查找效率也越低。选项Ⅱ正确。选项Ⅲ正确。采用合适的处理冲突的方

法避免产生聚集现象, 也将提高查找效率。例如, 用拉链法解决冲突时不存在聚集现象, 用线性探测法解决冲突时易引起聚集现象。

9． 下面关于串的叙述中，不正确的是（ ）。

A. 串是字符的有限序列

B. 空串是由空格构成的串

C. 模式匹配是串的一种重要运算

D. 串既可以采用顺序存储，也可以采用链式存储

【答案】B

【解析】空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。

10．稀疏矩阵一般的压缩存储方法有两种，即（ ）。

A. 二维数组和三维数组

B. 三元组和散列

C. 三元组和十字链表

D. 散列和十字链表

【答案】C

【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组(行标，列标，值) 。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。

11．下列选项中, 属于多级页表优点的是（ ）

A. 加快地址变换速度

B. 减少缺页中断次数

C. 减少页表项所占字节数

D. 减少页表所占的连续内存空间

【答案】D

【解析】多级页表避免了把所有的页表一直保存在内存中

12．b ，(c，d) ，(e，(f，g))) ， 广义表A ＝(a，则式子Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。

A.(g)

B.(d)

C.c

D.d

【答案】D

【解析】head 操作就是得到广义表中第一个的原子。tail 操作就是得到除第一个原子外剩下