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

一、单项选择题

1． 在有向图G 的拓扑序列中，若顶点在顶点之前，则下列情形不可能出现的是（ ）。

A.G 中有弧

C.G 中没有弧

【答案】D

【解析】若想实现图的一个拓扑排序，需要满足的一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从到的路径，则在拓扑序列中不可能在前。

2． 某CPU 主频为, 采用4级指令流水线, 每个段的执行需要1个时钟周期。假定CPU 执行了100条指令, 在其执行过程中没有发生任何流水线阻塞, 此时流水线的吞吐率为（ ） A.

B.

C.

D.

【答案】C

【解析】采用4级流水线执行100条指令, 在执行过程中共用

CPU 的主频是, 也就是说每秒钟有

条指令/秒,

故答案为C 。

3． 一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。

A.107

B.108

C.214

D.215

【答案】B

【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有n0＝n2＋+l，所以215＝n0＋n2＝2*n2＋l ，n2＝107，n0＝108。也就是说若对其进行哈夫曼编码，共能得到108个码字。

第 2 页，共 48 页 B.G 中有一条从到的路径 D.G 中有一条从到的路径 条指令/秒 条指令/秒 条指令/秒 条指令/秒 个时钟周期。 个时钟周期。流水线的吞吐率为

4． 求整数阶乘的算法如下, 其时间复杂度是（ ）。

A.

B.0(n) C. 2D.O(n)

【答案】B 。

【解析】设fact(n)的运行时间函数是T(n)。

该函数中语句①的运行时间是0(1), 语句②的运行时间是

算的时间。

因此, 当

则,

时

, ; 。

即fact(n)的时间复杂度为O(n)。

当11>1时, , 其中O(1)为乘法运

第 3 页，共 48 页

通过上表可以看出, 显然转换过程中同时保存在栈中的操作符的最大个数是5。

5． 某计算机系统中有8台打印机，由K 个进程竞争使用，每个进程最多需要3台打印机. 该系统可能会发生死锁的K 最小值是（ ）.

A.2

B.3

C.4

D.5

【答案】C

【解析】死锁的抽屉原理一般描述是：将5个苹果放进4个抽屉，那么，必然有1个抽屉中至少有2个苹果. 计算机系统的资源分配充分体现了这一原理. 考察进程运行的特点，只要有一个进程能够运行，则运行结束后必然会归还资源，其余的进程也就会得到满足从而可以执行(这里考虑的资源主要是可重用的资源，不可重用的资源会消失，就不可用上述方法分析). 所以最少需要4个进程竞争使用，每个进程占用2台打印机，此时会产生死锁.

6． 下列序列中，（ ）是执行第一趟快速排序后所得的序列。 A. B. C. D.

【答案】C

【解析】快速排序将数据划分成两部分，其中一部分关键字比另一部分关键字小。

第 4 页，共 48 页