2017年北京大学地球与空间科学学院408计算机学科专业基础综合之计算机组成原理考研导师圈点必考题汇编
● 摘要
一、选择题
1． 引入多道程序的目的在于（ ）。
A. 充分利用
减少
等待时间
B. 提高实时响应速度
C. 有利于代码共享，减少主辅存信息交换量 D. 充分利用存储器 【答案】A
【解析】多道程序设计的主要优点是通过将用户的
请求和
请求重叠起来的办法来有效
地使用和外设。它设法让总有事情可做，以此来提高和外设的利用率。
2． 若磁盘转速为7200转/分，平均寻道时间为8ms , 每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是（ ）。
A.8.1ms B.12.2ms C.16.3ms D.20.5ms 【答案】B
【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms ，平均等待时间与磁盘转速有关，
为
因此总的时间为：
3． 为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。
A. 顺序存储 B. 散列存储 C. 链式存储 D. 索引存储 【答案】A
【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。
4． 已知一个长度为16的顺序表L ，其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多是（ ）。
A.4 B.5
第 2 页，共 74 页
磁盘的存取一个扇区的时间
为
C.6 D.7
【答案】B
【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为题中，n=16，故比较次数最多为5。
5． 在OSI 参考模型中，自下而上第一个提供端到端服务的层次是（ ）。
A. 数据链路层 B. 传输层 C. 会话层 D. 应用层 【答案】B
【解析】题目中指明了这一层能够实现端到端传输，也就是端系统到端系统的传输，数据链路层主要负责传输路径上相邻结点间的数据交付，这些结点包括了交换机和路由器等数据通信设备，这些设备不能被称为端系统，因此数据链路层不满足题意。题目中指明了这一层能够实现传输，会话层只是在两个应用进程之间建立会话而已，应用层只是提供应用进程之间通信的规范， 都不涉及传输。所以本题答案应该是B 项。在OSI 模型中网络层提供的是主机到主机的通信服务。
6． 有向带权图如图所示，若采用迪杰斯特拉（Dijkstra ）算法求从源点a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b ，第二条最短路径的目标顶点是c ，后续得到的其余各最短路径的目标顶点依次是（ ）。
在本
图 有向带权图
A.d , e , f B.e , d , f C.f , d , e D.f , e , d 【答案】C 。
【解析】本题主要考查Dijkstra 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstra 算法过程中各步的状态表，故后续目标顶点依次为f ，d ，e 。
第 3 页，共 74 页
7． 在一株高度为2的5阶B 树中，所含关键字的个数最少是（ ）
A.5 B.7 C.8 D.14
【答案】A
【解析】根据B 树的定义可知，跟结点最少含有
个关键字，高度为2的阶B
树最少有（5-1）+1=5个关键字，其中根节点含有（5-1）个关键字，第2层结点含有1关键字。
8． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（ ）。
A.1, 2, 3, 4 B.2, 3, 4, 1 C.3, 2, 4, 1 D.4, 3, 2, 1 【答案】C
【解析】题目中的二叉树的先序序列和后序序列正好相反，这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。
从左至右，这8棵二叉树的中序序列分别为： （1）4, 3, 2, 1, （2）3, 4, 2, 1 （3）2, 4, 3, 1 （4）2, 3, 4, 1
第 4 页，共 74 页