2018年北京大学地球与空间科学学院408计算机学科专业基础综合之计算机组成原理考研强化五套模拟题
● 摘要
一、选择题
1． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是（ ）。
A.24, 10, 5和24, 10, 7
B.24, 10, 5和24, 12, 7
C.24, 10, 10和24, 14, 11
D.24, 10, 5和24, 14, 6
【答案】D
【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中，第二个被访问的两个结点的权值要么相等，要么和为根节点的权值，故B 项错误。同理，通过第三个被访问的节点排除A 项。C 项，由两条路径可推出三个叶子节点的权值分别是：3、10和11，而根据哈夫曼树的定义可知，权值为3的节点应该和权值为10的结点结合，故C 项错误。D 项，反推出有四个叶子节点，权值分别为：5、5、6和8，满足哈夫曼树的条件。
2． 以下描述中，不正确的是（ ）。
A. 根据Amdahl 定理，程序的加速比决定于串行部分的性能
B. 多核处理机上运行的每个线程都具有完整的硬件执行环境
C. 按计算内核的对等与否，CMP 可分为同构多核和异构多核两种
D. 线程的切换比进程的切换代价大
【答案】D
3． 已知序列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。
4． 下溢指的是（ ）。
A. 运算结果的绝对值小于机器所能表示的最小绝对值
B. 运算的结果小于机器所能表示的最小负数
C. 运算的结果小于机器所能表示的最小正数
D. 运算结果的最低有效位产生的错误
【答案】B
5． 元素a ，b , c ，d ，e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（ ）。
A.3
B.4
C.5
D.6
【答案】B
【解析】d 首先出栈后的状态如下图所示。
此时可有以下4种操作：
（1）e 进钱后出栈，出梭序列为decba 。
（2）c 出枝，e 进栈后出栈，出栈序列为dceba 。
（3）cb 出栈，e 进枝后出栈，出栈序列为dcbea 。
（4）cba 出枝，e 进枝后出栈，出栈序列为dcbae 。
6． 下列介质访问控制方法中，可能发生冲突的是（ ）
A.CDMA
B.CSMA
C.TDMAC
D.FDMA
【答案】B
【解析】介质访向控制协议中能够发生冲突的是CSMA 协议，答案为B 。
7． 在下图所示的采用“存储一转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbps ，，，分组大小为1000B 其中分组头大小20B 若主机H1向主机H2发送一个大小为980000B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是（ ）。
A.80ms
B.80.08ms
C.80.16ms
D.80.24ms
【答案】C
【解析】由题设可知，分组携带的数据长度为980B ，文件长度为980000B ，需拆分为1000个分组，加上头部后，每个分组大小为1000B ，总共需要传送的数据量大小为1MB 。由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过分组交换机。当t=lM×8/100Mbps=80ms时，HI 发送完最后一个比特；到达目的地，最后一个分组，需经过两个分组交换机的转发，每次转发的时间为t0=lK×8/100MbpS=0.08ms，所以，在不考虑分组拆装时间和传播延时的情况下，
当时，H2接受完文件，即所需的时间至少为80.16ms 。
8． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。
A.0（n ）
B.0（e ）
C.0（n+e）
D.O （nxe ）
【答案】C 。