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

一、单项选择题

1． 已知串

A.0123

B.1123

C.1231

D.1211

【答案】A

【解析】KMP 算法的next 数组建立的原则

其Next 数组值为（ ）。

2． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列, 能属于同一棵哈夫曼树的是（ ）。

A.24, 10, 5和24, 10, 7

B.24, 10, 5和24, 12, 7

C.24, 10, 10和24, 14, 11

D.24, 10, 5和24, 14, 6

【答案】D

【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中, 第二个被访问的两个结点的权值要么相等, 要么和为根节点的权值, 故B 项错误。同理, 通过第三个被访问的节点排除A 项。C 项, 由两条路径可推出三个叶子节点的权值分别是:3、10和11, 而根据哈夫曼树的定义可知, 权值为3的节点应该和权值为10的结点结合, 故C 项错误。D 项, 反推出有四个叶子节点, 权值分别为:5、5、6和8, 满足哈夫曼树的条件。

3． 下列给出的指令系统特点中, 有利于实现指令流水线的是（ ）。

Ⅰ. 指令格式规整且长度一致

Ⅱ. 指令和数据按边界对齐存放

Ⅲ. 只有Load/Store指令才能对操作数进行存储访问

A. 仅Ⅰ、Ⅱ

B. 仅Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

【答案】D

【解析】特点Ⅰ和Ⅲ都是RISC 机的特征, 而特点Ⅱ则有利于指令和数据的存放, 所以以上三个特点都有利于实现指令流水线。

4． 执行完下列语句段后，f 值为（ ）。

A.2

B.4

C.8

D. 无限递归

【答案】B

【解析】该程序使用了递归调用，由题知，:f(0)＝2；f(l)＝l*f(0)＝2；f(2)＝2*f(l)＝4；所以结果为4。

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

Ⅰ. 增大装填(载) 因子

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

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

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅱ

D. 仅Ⅱ、Ⅲ

【答案】D

【解析】散列表的查找效率(比较次数) 取决于:散列函数、处理冲突的方法和散列表的装填因子α。α标志着散列表的装满程度, 通常情况下, α越小, 发生冲突的可能性越小; 反之, α越大, 表示已填入的记录越多, 再填入记录时, 发生冲突的可能性越大。因此选项Ⅰ错误, 越是增大装填因子, 发生冲突的可能性就越大, 查找效率也越低。选项Ⅱ正确。选项Ⅲ正确。采用合适的处理冲突的方法避免产生聚集现象, 也将提高查找效率。例如, 用拉链法解决冲突时不存在聚集现象, 用线性探测法解决冲突时易引起聚集现象。

6． 下列选项中会导致进程从执行态变为就绪态的事件是（ ）。

A. 执行P(wait)操作

B. 申请内存失败

C. 启动设备

D. 被高优先级进程抢占

【答案】D

【解析】D 项, 被高优先级进程抢占, 进程会由执行态变为就绪态。ABC 三项, 程序由于缺少资源而由执行态转为阻塞态。

7． 将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是（ ）.

(1)父子关系

(2)兄弟关系

(3)U的父结点与V 的父结点是兄弟关系

A. 只有(1)

B.(1)和(2)

C.(1)和(3)

d.(1)、(2)和(3)

【答案】B

【解析】首先，在二叉树中，若结点U 是结点v 的父结点的父结点，那么u 和v 的关系有如下4种情况：

接下来，根据森林与二叉树的转换规则，将这4种情况还原成森林中结点的关系. 其中： 情况(1)，在原来的森林中u 是v 的父结点的父结点；

情况(2)，在森林中u 是v 的父结点；

情况(3)，在森林中u 是v 的父结点的兄弟；

情况(4)，在森林中u 与v 是兄弟关系.

由此可知，题目中的(1)、(2)是正确的.

8． 在采用中断方式控制打印输出的情况下, CPU 和打印控制接口中的

息不可能是（ ）。

A. 打印字符

B. 主存地址

C. 设备状态

D. 控制命令

【答案】B

端口之间交换的信