2018年浙江大学建筑工程学院408计算机学科专业基础综合之计算机组成原理考研核心题库
● 摘要
一、选择题
1． 将森林F 转换为对应的二叉树T ，F 中叶结点的个数等于（ ）
A.T 中叶结点的个数 B.T 中度为1的结点个数 C.T 中左孩子指针为空的结点个数 D.T 中右孩子指针为空的结点个数 【答案】C
【解析】森林转化为对应的二叉树是‘孩子-兄弟’存储的，即左孩子指针指向当前节点的孩子节点，右孩子指针指向当前节点的兄弟节点，所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C
2． 设有向图G=（V ，E ）, 顶点集V={V0, V1，V2, V3},
边集
，若从顶点V0开始对图进行深度优先遍历则可能得
到的不同遍历序列个数是（ ）。
A.2 B.3 C.4 D.5
【答案】D
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可能得到的不同遍历序列分别是：
3． 若某数X 的真值为码。
A. 原 B. 补 C. 反 D. 移 【答案】B
第 2 页，共 27 页
在计算机中该数表示为则该数所用的编码方法是（ ）
4． 早期微型机中，不常用的
A. 程序查询方式 B. 中断方式 C.DMA 方式 D. 通道方式 【答案】D
信息交换方式是（ ）。
5． 已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18, 将其再调整为大根堆，调整过程中元素之间进行的比较次数是（ ）。
A.1 B.2 C.4 D.5
【答案】B
【解析】对堆插入或删除一个元素，有可能不满足堆的性质，堆被破坏，需要调整为新堆。 （1）为原堆， （2）为插入18后， （3）比较10与18, 交换后，
（4）比较25与18, 不交换，即为调整后的新的大根堆。 因此调整过程中元素之间进行的比较次数为2。
6． 两台主机之间的数据链路层采用后退N 帧协议（GBN ）传输数据，数据传输速率为16kbps ，单向传播时延为270ms , 数据帧长度范围是128〜512字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为（ ）。
A.5 B.4 C.3 D.237
【答案】B 。
第 3 页，共 27 页
【解析】GBN 的工作原理如下图所示，本题求解的是发送一个帧到接收到这个帧的确认期间最多可以发送多少数据帧，要尽可能多发送帧，应以短的数据帧计算，注意帧的单位是字节，因
此首先计算出发送一帧的时间
这段时间总共可以发送
在此期间不重复，因此顿序号的比特数至少为4, 答案为
B
故发送一帧到收到确认为止的总时间为
；
为了保证发送帧序号和确认帧序号
7． 求整数
阶乘的算法如下，其时间复杂度是（ ）。
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 ）。
8． 活动头磁盘存储器的平均存取时间是指（ ）。
A. 最大找道时间加上最小找道时间 B. 平均找道时间
C. 平均找道时间加上平均等待时间
第 4 页，共 27 页
则，