2018年北京市培养单位高能物理研究所408计算机学科专业基础综合之计算机组成原理考研强化五套模拟题
● 摘要
一、选择题
1． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。
A. 递归次数与初始数据的排列次序无关
B. 每次划分后，先处理较长的分区可以减少递归次数
C. 每次划分后，先处理较短的分区可以减少递归次数
D. 递归次数与每次划分后得到的分区的处理顺序无关
【答案】D
【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深度一致。例如：待排序列{48，62，35，77，55，14，35，98），采用快速排序方法，其对应递归调用过程的二叉树如下图所示。
在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。
2． 下列关于最小生成树的叙述中，正确的是（ ）。
Ⅰ. 最小生成树的代价唯一Ⅱ. 所有权值最小的边一定会出现在所有的最小生成树中Ⅲ. 使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树一定相同Ⅳ. 使用普里姆算法和克鲁斯卡尔（Kruskal ）算法得到的最小生成树总不相同
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅲ
D. 仅Ⅱ、Ⅳ
【答案】A 。
【解析】当图中存在相同权值的边时，其最小生成树可能是不唯一的，但最小生成树的代价一定是相同的，所以说法Ⅰ正确。从n 个顶点的连通图中选取n-1条权值最小的边可能构成回路，所以说法Ⅱ错误。当某个顶点有权值相同的边，使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树并不一定相同，所以说法Ⅲ错误。当最小生成树不唯一时，使用普里姆算法和克鲁斯卡尔（Kruskal ）算法得到的最小生成树可能相同，也可能不同，所以说法Ⅳ错误。由此可得出正确答案。
3． 系统总线中控制线的功能是_____。
A. 提供主存、
B. 提供数据信息
C. 提供时序信号
D. 提供主存、
【答案】A
【解析】控制线用来指明数据传送的方向（存储器读、存储器写、I/O读、I/O写）。
4． 下列选项中，对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA
B.CDMA
C.CSMA/CD
D.CSMA/CA
【答案】D
【解析】可采用排除法。CDMA 是码分多址复用，是物理层的内容；CSMA/CD即带冲突检测的载波监听多路访问，接收方并不需要确认；CSMA/CD是CSMA 的加强版，故CSMA 也无确定；CSMA/CD是802.11中的协议，其利用ACK 信号来避免冲突的发生，也就是说，只有当客户端收到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址，因此答案是D 。
5． 下列选项中，不属于网络体系结构中所描述的内容是（ ）。
A. 网络的层次
B. 每一层使用的协议
C. 协议的内部实现细节
D. 每一层必须完成的功能
【答案】C
【解析】体系结构仅规定协议的功能和消息格式，但对具体的实现细节由具体设备厂商来确定，对于网络的层次，以及每一个层次的协议及其功能都是网络体系结构所要描述的内容，因此答案为选项C 。
6． 总线共享cache 结构的缺点是（ ）。
A. 结构简单
接口设备的控制信号和响应信号 接口设备的响应信号
B. 通信速度高
C. 可扩展性较差
D. 数据传输并行度高
【答案】C
7． 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。
【答案】D
【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息，解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b ; 结点b 无左子树，左链域指向其前驱结点山结点c 无左子树，左链域指向其前驱结点b ，无右子树，右链域指向其后继结点a 。所以正确选项为D 。
8． 下列各种操作的时间中，不属于活动头硬盘的存取访问时间的是（ ）。
A. 寻道时间
B. 旋转延迟时间
C. 定位时间
D. 传送时间
【答案】C
9． 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz ，则总线带宽是（ ）。
A.10MB/S
B.20MB/S
C.40MB/S
D.80MB/S
【答案】B
【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送。总线时钟频率为