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

一、单项选择题

1． 假设某计算机的存储系统由Cache 和主存组成. 某程序执行过程中访存1000次，其中访问Cache 缺失(未命中)50次，则Cache 的命中率是（ ）.

A.5% B.

C.50%

D.95%

【答案】D

【解析】Cache 的命中率H ＝N 1(N1＋N 2) ，其中N 1为访问Cache 的次数，N 2为访存主存的次数，程序总访存次数为N 1＋N 2，程序访存次数减去失效次数就是访问Cache 的次数队. 所以根据公式可得：H ＝(1000﹣50) /100＝95%.

2． 下列排序算法中，其中（ ）是稳定的。

A. 堆排序，起泡排序

B. 快速排序，堆排序

C. 直接选择排序，归并排序

D. 归并排序，起泡排序

【答案】D

3． n 个结点的完全有向图含有边的数目（ ）。

A.n*n

B.n(n+1)

C.n/2

D.n*(n－1)

【答案】D

【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有条边。如是有向图，需要在无向图的最多边的基础上乘以2，则为n(n－1) 。

4． 有关二叉树下列说法正确的是（ ）。

A. 二叉树的度为2

B. 一棵二叉树的度可以小于2

C. 二叉树中至少有一个结点的度为2

D. 二叉树中任何一个结点的度都为2

【答案】B

【解析】树的度＝MAX(结点1的度，结点2的度，结点3的度结点n 的度) 。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。

5． 冯•诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）.

A. 指令操作码的译码结果

B. 指令和数据的寻址方式

C. 指令周期的不同阶段

D. 指令和数据所在的存储单元

【答案】C

【解析】在冯•诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段(分析取数阶段、执行阶段) 取出的是数据. 所以，CPU 区分指令和数据的依据是指令周期的不同阶段.

6． 先序序列为a , b , c , d 的不同二叉树的个数是（ ）。

A.13

B.14

C.15

D.16

【答案】B

【解析】二叉树的先序遍历定义为:若二叉树为空, 则空操作; 否则, 访问根节点, 然后先序遍历左子树, 最后先序遍历右子树。本题中, 结点a 为二叉树的根节点, 左右子树的先序遍历可能存在下面四种情况:

①左子树为空, bcd 为右子树; ②b 为左子树, cd 为右子树; ③bc 为左子树, d 为右子树; ④bcd 为左子树, 右子树为空。

然后将左右子树继续分解, 如第①种情况的右子树先序遍历(bcd)可能有:

A. 左子树为空, 右子树为cd ;

b. 左子树为c , 右子树为d ;

c. 左子树为cd , 右子树为空。

按照这种方法继续分解左右子树, 直到不能再分解为止, 可得第①和④种情况各包含5种不同情况, 第②和③种情况各包含2种情况, 因此总共有14种不同的二叉树。

7． 某同步总线的时钟频率为100MHz , 宽度为32位, 地址/数据线复用, 每传输一个地址或数据占用一个时钟周期。若该总线支持突发(猝发) 传输方式, 则一次“主存写”总线事务传输128位数据所需要的时间至少是（ ）。

A.20ns

B.40ns

C.50ns

D.80ns

【答案】C 。

【解析】总线的时钟频率为100MHz , 则时钟周期为10ns 。数据是128位, 总线宽度是32位, 所以需要4个时钟周期, 而传输地址还需要一个周期, 所以传输一个128位的数据至少需要5个时钟周期, 所以至少需要。

8． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。

A.h ﹣＞next ＝s ；

B.s ﹣＞next ＝h ；

C.s ﹣＞next ＝h ；h ﹣＞next ＝s ；

D.s ﹣＞next ＝h ﹣next ；h ﹣＞next ＝s ；

【答案】D

【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。

9． 下列选项中, 满足短任务优先且不会发生饥饿现象的调度算法是（ ）。

A. 先来先服务

B. 高响应比优先

C. 时间片轮转

D. 非抢占式短任务优先

【答案】B

【解析】分析该题目可以看到, 本题所提到的问题是涉及短任务调度也就是属于作业调度, 因此首先排除时间片轮转算法; 因为作业调度算法中没有时间片轮转的算法。其次, 因为问题提到短任务, 则先来先服务的算法也可以排除了, 它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个？我们可以通过分析得到, 非抢占式短任务优先算法不能解决饥饿问题, 因为当一个系统短任务源源不断到达是, 长任务必然会得不到调度, 产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法, 并以高响应比值优先调度。这样, 无论短任务或长任务, 均可以得到调度, 而且, 较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有高响应比优先算法。