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

一、单项选择题

1． 若无向图

是（ ）。

A.6

B.15

C.16

D.21

【答案】C

【解析】要保证无向图G 在任何情况下都是连通的, 即任意变动图G 中的边, G 始终保持连通。首先需要图G 的任意6个结点构成完全连通子图

再添加一条边将第7个结点与, 需条边, 然后连接起来, 共需16条边。本题非常容易错误地选择选项A , 主要原中含7个顶点, 则保证图G 在任何情况下都是连通的, 则需要的边数最少因是对“保证图G 在任何情况下都是连通的”的理解, 分析选项A , 在图G 中, 具有7个顶点6条边并不能保证其一定是连通图, 即有n-1条边的图不一定是连通图。分析选项D , 图G 有7个顶点21条边, 那么图G 一定是无向完全图, 无向完全图能保证其在任何情况下都是连通的, 但是这不符合题目中所需边数最少的要求。

2． 对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。

A. 每次分区后，先处理较短的部分

B. 每次分区后，先处理较长的部分

C. 与算法每次分区后的处理顺序无关

D. 以上三者都不对

【答案】A

【解析】令递归函数为f ，第一次进行递归函数认为递归深度为1，以后从深度为n 的递归函数f 中再调用递归函数f ，此时深度为n+1。整个f 的最大深度为递归深度。

3． 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。 A. B. | C. D.

【答案】C

【解析】因为该序列中的结点己经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为O(N)。对于采用归并法，它是一种稳定的排序方法，它

的时间复杂度为。对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，此时的时间复杂度为。

4． 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz ，则总线带宽是（ ）.

A.10MB/s

B.20MB/S

C.40MB/S

D.80MB/S

【答案】B

【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送. 总线时钟频率为10MHz ，时钟周期为，总线周期占用2个时钟周期，为＝一个总线周期中并行传输4字节信息，则总线带宽是＝20MB/s.

5． 下列选项中, 不可能在用户态发生的事件是（ ）。

A. 系统调用

B. 外部中断

C. 进程切换

D. 缺页

【答案】C 。

【解析】我们在学习操作系统中知道, 任何一个进程在现代操作系统中为了共享和保护, 设定了用户态和内核态(可以通过设置软、硬件标志位来实现) , 在用户态运行用户的程序, 在内核运行系统的程序。所以, 从选项来看, 系统调用可以在任何态发生, 用户可以发起系统调用, 系统也可以; 外部中断是不可控的, 也会在任何时刻发生, 缺页的发生也是不可控的, 可以发生在用户代码之间; 而进程切换却不会在用户态发生。我们可以考虑一下情形, 进程切换是在什么时候发生的, 进程切换前必定运行的是进程调度, 只有进程调度选择了下一次被调度的进程, 进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制分离的设计思想。所以, 进程切换必定不会在用户态发生(所谓发生指其起始的源头时刻) , 必定是在内核态(进程调度) 发生的。

6． 假定一台计算机的显示存储器用DRAM 芯片实现, 若要求显示分辨率为1600x1200, 颜色深度

为24位, 帧频为85Hz , 显存总带宽的50%用来刷新屏幕, 则需要的显存总带宽至少约为（ ）。

A.245Mbps

B.979Mbps

C.1958Mbps

D.7834Mbps

【答案】D

【解析】显存的容量＝分辨率×色深，带宽＝分辨率×色深×帧频，考虑到

的时间用来刷新屏幕，故显存总带宽应加倍. 所以需要的显存总带宽至少约为:1600×l200×24×85×2＝7834Mbps.

7． n 个结点的线索二叉树上含有的线索数为（ ）。

A.2n

B.n ﹣1

C.n ＋1

D.n

【答案】C

【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n ＋1个空链域。

8． 某计算机采用微程序控制器, 共有32条指令, 公共的取指令微程序包含2条微程序, 各指令对应的微程序平均由4条微指令组成, 采用断定法(下址字段法) 确定下条微指令的地址, 则微指令中下址字段的位数至少是:（ ）

A.5

B.6

C.8

D.9

【答案】C 【解析】, ,

所以至少需要8位才能表示完130个地址。

9． 对同一待排序列分别进行折半插入排序和直接插入排序, 两者之间可能的不同之处是 （ ）。

A. 排序的总趟数

B. 元素的移动次数

C. 使用辅助空间的数量

D. 元素之间的比较次数

【答案】D 。

【解析】折半插入排序所需附加存储空间和直接插入排序相同, 从时间上比较, 折半插入排序仅减少了关键字间的比较次数, 而记录的移动次数不变。折半插入排序的时间复杂度仍为, 所以两者之间的不同只可能是元素之间的比较次数。

10．假定用若干个位的芯片组成一个8K ×8位的存储器, 则地址0B1FH 所在芯片的最小地址是（ ）。

A.0000H

B.0600H

C.0700H

D.0800H

【答案】D

【解析】由若干芯片构成存储器, 采用字和位同时扩展方法。8片

组2个芯片, 各组芯片的地址分配分别为:

第1组, ; 第2组, ;

位的芯片分成4组, 每