2017年浙江大学控制科学与工程学院408计算机学科专业基础综合之计算机组成原理考研导师圈点必考题汇编
● 摘要
一、选择题
1． 下列表述中，微指令结构设计不追求的目标是（ ）。
A. 提高微程序的执行速度 B. 提高微程序设计的灵活性 C. 缩短微指令的长度 D. 增大控制存储器的容量 【答案】D
2． 已知序列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。
3． 对（ ）。
个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是
A. 该树一定是一棵完全二叉树 B. 树中一定没有度为1的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值 【答案】A
【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，选项A 错误；哈夫曼树中没有度为1的结点，选项B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P 的左右子树根结点处于同一层的结点中，若存在权值大于结点P 权值的结点Q ，那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。
4． 以下描述中，不正确的是（ ）。
A. 根据Amdahl 定理，程序的加速比决定于串行部分的性能 B. 多核处理机上运行的每个线程都具有完整的硬件执行环境 C. 按计算内核的对等与否，CMP 可分为同构多核和异构多核两种 D. 线程的切换比进程的切换代价大 【答案】D
5． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（ ）。
A.12 B.20 C.32 D.33
【答案】B 。
【解析】本题题目的实际问题是，具有6层结点的平衡二叉树含有最少的结点数是多少。表示深度为h 的平衡二叉树中含有的最少结点数，有
由此可得
对应的平衡二叉树如下图所示。
6． 下列关于无向连通图特性的叙述中，正确的是（ ）。
I. 所有的顶点的度之和为偶数 II. 边数大于顶点个数减1 III. 至少有一个顶点的度为1 A. 只有I B. 只有II C.I 和II D.I 和III 【答案】A
【解析】在图中，顶点的度
之和与边的数目满足关系式：
（n 为图的
，因此，I 项正确。对于II 、III 项中的特性不是一般无向连通图的特性，总结点数，e 为总边数）
可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。
7． 循环两列放在一维数组
中，endl 指向队头元素，end2指向队尾元素的后一个位置。
个元素。初始时为空，下列判断
假设队列两端均可进行入队和出队操作，队列中最多能容纳队空和队满的条件中，正确的是（ ）
A. 队空
：B. 队空：C. 队空：D. 队空：【答案】A
队满：队满
：
队满
：队满：