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

一、单项选择题

1． 下列关于IP 路由器功能的描述中, 正确的是（ ）。

Ⅰ. 运行路由协议, 设置路由表;

Ⅱ. 监测到拥塞时, 合理丢弃IP 分组;

Ⅲ. 对收到的IP 分组头进行差错校验, 确保传输的IP 分组不丢失;

Ⅳ. 根据收到的IP 分组的目的IP 地址, 将其转发到合适的输出线路上。

A. 仅Ⅲ、Ⅳ

B. 仅Ⅰ、Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅱ、Ⅳ

D. Ⅰ、Ⅱ、Ⅲ、Ⅳ

【答案】C 。

【解析】路由器的主要功能是路由和转发, 因此Ⅰ和Ⅳ是正确的, 而针对Ⅱ和Ⅲ, 可以从ICMP 协议的差错控制出发, 注意检测到拥塞时, 合理丢弃IP 分组, 并回传ICMP 源抑制报文, Ⅱ是正确的, 而Ⅲ对收到的IP 分组头进行差错校验, 确保传输的IP 分组不丢失, 差错校验是正确的, 但网络层不

保证IP 分组不丢失, 也就是不可靠的, 因此Ⅲ的说法错误, 正确的说法仅Ⅰ、Ⅱ、Ⅳ, 因此答案是C 。

2． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。

A.4

B.5

C.6

D.7

【答案】C

【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个(n＞0) 结点的完全二叉树的高度为或由完全二叉树类推到完全三叉树可知，n 个结点的完全三叉树的高度为

或》

3． 下列关于最小生成树的叙述中, 正确的是（ ）。

Ⅰ. 最小生成树的代价唯一

Ⅱ. 所有权值最小的边一定会出现在所有的最小生成树中

Ⅲ. 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同

IV. 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树总不相同

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅲ

D. 仅Ⅱ、Ⅳ

【答案】A 。

【解析】当图中存在相同权值的边时, 其最小生成树可能是不唯一的, 但最小生成树的代价一定是相同的, 所以说法Ⅰ正确。从n 个顶点的连通图中选取n-1条权值最小的边可能构成回路, 所以说法Ⅱ错误。

当某个顶点有权值相同的边, 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树并不一定相同, 所以说法Ⅲ错误。当最小生成树不唯一时, 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树可能相同, 也可能不同, 所以说法Ⅳ错误。由此可得出正确答案。

4． 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear ，front 的值分别为多少？（ ）

A.1和5

B.2和4

C.4和2

D.5和1

【答案】B

【解析】入队操作的主要步骤:rear ＝(rear+1)%6，加入一个后，rear ＝(0+1)%6＝1，再加入一个后，rear ＝(1+1)%6＝2。出队操作的主要步骤:front ＝(front+1)%6。删除一个后，front ＝(3+1)%6＝4。

5． 本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是（ ）.

A. 命令解释程序

B. 中断处理程序

C. 系统调用服务程序

D. 用户登录程序

【答案】B

【解析】外部设备在与计算机连接时有多种方式，中断技术就是一种常用方式. 其工作原理是:利用处理机中断信号线，外部设备在需要服务的时候将该线设置为有效，计算机若同意接受中断则会停止当前进程的运行，转而服务发出中断的物理设备(注意与陷阱，即软中断有区别），那么对不同外部设备进行服务的程序代码是不同的，如何找到这些代码呢? 这就要借助中断向量，中断向量一般是由硬件根据中断的类型(不同外设不同）计算所得，或计算机系统在开机配置时所配置的. 处理机取得中断向量，其实就是一个物理地址，该地址下存放的是为此中断服务的代码的起始地址. 所以，当键盘按下的时候，键盘控制器获得该操作动作，先将键盘扫描码读入键盘缓冲区，

再向处理机发出键盘中断，适当的时候(一条指令的末尾或一条原语结束）处理机会响应中断，调用指定服务程序将键盘缓冲区中的键盘扫描码输入到登录进程中去. 如此，最先响应键盘的必然是中断处理程序. 本题中，像命令解释器(例如cmd 窗口）、系统调用服务和用户登录程序都在中断处理程序后面.

6． 单处理机系统中，可并行的是（ ）.

(1)进程与进程

(2)处理机与设备

(3)处理机与通道

(4)设备与设备

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

B. (1)、(2)和(4)

C. (1)、(3)和(4)

D. (2)、(3)和(4)

【答案】D

【解析】注意区分并发和并行. 在单处理机系统中，进程只能并发. 微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的. 通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行. 显然，设备和设备之间也是可以并行的.

7． 已知小根堆为8, 15, 10, 21, 34, 16, 12, 删除关键字8之后需重建堆, 在此过程中, 关键字之间的比较数是（ ）。

A.1

B.2

C.3

D.4

【答案】C

【解析】堆排序中, 依次输出堆顶的最小值, 然后重新调整堆, 如此反复执行, 便得到一个有序序列。本题中, 删除堆顶元素8后将最后一个元素12置于堆顶, 然后调整堆:首先与15比较, 12小于15, 所以不用交换; 然后与10比较, 因为10小于12, 所以交换10和12的位置; 调整后12再与16比较, 12小于16, 调整堆过程结束。因此12共与15、10、16进行了三次比较。

8． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。

A. B.

C. O (n) D.

【答案】A

【解析】在内部排序中，最坏情况下的时间复杂度为

。