2018年浙江大学控制科学与工程学院408计算机学科专业基础综合之计算机组成原理考研核心题库
● 摘要
一、选择题
1． 已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（ ）。
A.39
B.52
C.111
D.119
【答案】C
【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层。题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度。根据题意，一棵完全二叉树的第6层（设根为第1层）有8个叶结点，可知此二叉树的高度是6或7。题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7。由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是
性质1可知，题目中二叉树的第6层结点数是，又根据二叉树的个结点，已知有8个叶子结点，那么其余32-8=24个结点均为分支结点，这些结点在第7层上最多有48个子结点（即叶子结点）。所以此 二叉树的结点数最多可达
2． 从以下有关的描述中，选择正确答案。（ ）
A. 采用
C.
D. 技术后，计算机的体系结构又恢复到早期的比较简单的情况。 是从原来系统的指令系统中挑选一部分实现的。 的主要目标是减少指令数。 设有乘、除法指令和浮点运算指令。
指令系统的控制器采用组合逻辑控制，计算机体系结构更复杂了；B 项
，指令系统上的改进，除精简了指令集，中增加了通用寄存器，采用了
中像乘、除法和浮点数运算等复杂指令的功能由频度B. 为了实现兼容，
新设计的【答案】C 【解析】A 项，指令系统是在流水线技术，优化了编译程序。D 项，
高的简单指令的组合来实现。
3． 使用浏览器访问某大学Web 网站主页时，不可能使用的协议是（ ）
A.PPP
B.ARP
C.UDP
D.SMTP
【答案】D
【解析】SMTP 是简单邮件传输协议，访问主页时并不涉及邮件相关协议。
4． 用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9, 1, 4, 13, 7, 8, 20, 23, 15，则该趟排序采用的增量（间隔）可能是（ ）
A.2
B.3
C.4
D.5
【答案】B
【解析】对于A , 增量为2, 那么9, 4, 7, 20，15是一组，而它们是无序的，所以A 错误对于C ，増量为4, 那么9, 7，15是一组，而它们是无序的，所以C 错误
对于D ，增量为5, 那么9, 8是一组，降序，1，20是一组，而它们是升序，所以D 也错误。对于B ，分为3组：9, 13, 20; 1，7, 23; 4, 8, 15都是升序有序，所以B 正确
5． 某同步总线的时钟频率为100MHz , 宽度为32位，±也址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输128位数据所需要的时间至少是（ ）.
A.20ns
B.40ns
C.50ns
D.80ns
【答案】C 。
【解析】总线的时钟频率为100MHz ，贝U 时钟周期为10ns 。数据是128位，总线宽度是32位，所以需要4个时钟周期，而传输地址还需要一个周期，所以传输一个128位的数据至少需要5个时钟周期，所以至少需要
6． 某系统有n 台互斥使用的同类设备，3个并发进程需要3, 4, 5台设备，可确保系统不发生死锁的设备数n 最小为（ ）
A.9
B.10
C.11
D.12
【答案】B
【解析】2+3+4+1=10
7． （ ）对计算机的产生有重要影响。
A. 牛顿、维纳、图灵
B. 莱布尼兹、布尔、图灵
C. 巴贝奇、维纳、麦克斯韦
D. 莱布尼兹、布尔、克雷
【答案】B
8． FTP 客户和服务器间传递FTP 命令时，使用的连接是（ ）。
A. 建立在TCP 之上的控制连接
B. 建立在TCP 之上的数据连接
C. 建立在UDP 之上的控制连接
D. 建立在UDP 之上的数据连接
【答案】A
【解析】对于FTP ，为了保证可靠性，选择TCP 。FTP 应用需要建立两条TCP 连接：一条为控制连接，另一条为数据连接。FTP 服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII 形式表示的。
9． 设栈S 和队列Q 的初始状态均为空，元素a ，b ，c ，d ，e ，f ，g 依次进入栈S 。若每个元素出栈后立即进入队列Q ，且7个元素出队的顺序是b ，d ，c ，f ，e ，a ，g ，则栈S 的容量至少是（ ）。
A.1
B.2
C.3
D.4
【答案】C
【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序。在本题中，每个元素出栈S 后立即进入队列Q ，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序。根据出栈顺序可以分析各个元素进出栈的过程：第一个出栈元素为b ，表明栈内还有元素a ，b 出栈前的深度为2; 第二个出栈元素为d ，找内元素为a 和c ，d 出栈前的深度为3; c 出找后，剩余元素为a ，c 出栈前的深度为2; f 出栈后，剩余元素为a 和e ，f 出栈前的深度为3; e 出栈后，剩余元素为a ，e 出栈前的深度为2; a 出栈后，无剩余元素，a 出栈前的深度为1; g 出栈后，无剩余元素，g 出栈前的深度为:L 所以栈容量至少是3。
10．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
Ⅰ. 简单选择排序Ⅱ. 希尔排序Ⅲ. 快速排序Ⅳ. 堆排Ⅴ. 二路归并排序
A. 仅Ⅰ、Ⅲ、Ⅳ
B. 仅Ⅰ、Ⅱ、Ⅲ
C. 仅Ⅱ、Ⅲ、IV
D. 仅Ⅲ、Ⅳ、Ⅴ