2017年安徽省合肥物质科学研究院408计算机学科专业基础综合之计算机组成原理考研导师圈点必考题汇编
● 摘要
一、选择题
1． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。
A.0（n ） B.0（e ） C.0（n+e） D.O （nxe ） 【答案】C 。
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间
为
，其中n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为0（e ）
其中e 为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O （n+e）。即可得出正确答案。
2． 在OSI 参考摸型中，下列功能需由应用层的相邻层实现的是（ ）
A. 对话管理 B. 数据格式转换 C. 路由选择 D. 可靠数据传输 【答案】B
【解析】应用层的相邻层即为表示层，表示层负责管理数据的压缩、加密与解密、格式装换等，故答案为B 。
3． 若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y ，则X 的右线索指向的是 （ ）
A.X 的父结点
B. 以Y 为根的子树的最左下结点 C.X 的左兄弟结点Y
D. 以Y 为根的子树的最右下结点 【答案】A
【解析】根据后续线索二叉树的定义，X 结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后续遍历的方式可知X 结点的后继是其父结点，即其右线索指向的是父结点。
4． 在cache 的地址映射中，若主存中的任意一块均可映射到cache 内的任意一块的位置上，贝!J 这种方法称为（ ）。
A. 全相联映射 B. 直接映射 C. 组相联映射 D. 混合映射 【答案】A
5． 单级中断系统中，中断服务程序内的执行顺序是（ ）。
I 保护现场；II 开中断；III 关中断；IV 保存断点；V 中断事件处理；VI 恢复现场；VII 中断返回
A.I →V →VI →II →VI B.III →I →V →VII C.Ill →IV →V →VI →VII D.IV →I →V →VI →VII 【答案】A
【解析】程序中断有单级中断和多级中断之分，单级中断在CPU 执行中断服务程序的过程中不能被打断，即不允许中断嵌套。保存断点与关中断的任务是由硬件（中断隐指令）完成的，所以在单级中断系统中，中断服务程序内应完成的任务有：①保存现场；②中断事件处理；③恢复现场；④开中断；⑤中断返回。
6． 求整数阶乘的算法如下，其时间复杂度是（ ）。
A. B.0（n ）
C.
D. 【答案】B
【解析】设fact （n ）的运行时间函数是T （n ）。
该函数中语句①的运行时间是0（1）, 语句②的运行时间是T （n-1）+0（1）, 其中O （1）为乘法运算的时间。
因此，当
T -0; 当n ＞l 时，时，（n ）（1）
则，
即fact （n ）的时间复杂度为O （n ）。
7． 数据总线的宽度由总线的（ ）定义。
A. 物理特性 B. 功能特性 C. 电气特性 D. 时间特性 【答案】B
8． 下列说法中不正确的是（ ）。
A. 任何可以由软件实现的操作也可以由硬件来实现 B. 固件就功能而言类似于软件，而从形态来说又类似于硬件
C. 在计算机系统的层次结构中，微程序属于硬件级，其他四级都是软件级 D. 直接面向高级语言的机器目前已经实现 【答案】D
9． —个进程的读磁区操作完成后，操作系统针对该进程必做的是（ ）
A. 修改进程状态为就绪态 B. 降低进程优先级 C. 进程分配用户内存空间 D. 增加进程的时间片大小 【答案】A
【解析】进程等待的FO 操作完成便会从等待状态转移到就绪状态。
10．CPU 对通道的请求形式是（ ）。
A. 自陷 B. 中断 C. 通道命令 D.I/O指令 【答案】D
二、简答题
11．在虚存实现过程中，有些页面会在内存与外存之间被频繁地换入和换出，使系统效率急剧下降。这种现 象称为颠簸。请解释产生颠簸的原因，并说明防止颠簸的办法。
【答案】产生颠簸的原因主要有： （1）分配的页面数太少；