考研专业课资料、辅导、答疑一站式服务平台
第 6 页，共 62 页 子树构造一棵新的二叉树,C 正确;哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和,其权值不小于其左右子树根结点的权值,在与结点P 的左右子树根结点处于同一层的结点中,若存在权值大于结点P 权值的结点Q ,那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树,由此可知,哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。
14．用直接插入排序方法对下面4个序列进行排序(由小到大)，元素比较次数最少的是（ ）。
A.94，32，40，90，80，46，21，69
B.32，40，21，46，69，94，90，80
C.21，32，46，40，80，69，90，94
D.90，69，80，46，21，32，94，40
【答案】C
15．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A.直接插入排序
B.起泡排序
C.基数排序
D.快速排序
【答案】C
【解析】C 项,基数排序是采用分配和收集实现的,不需要进行关键字的比较。ABD 三项都依赖关键字的比较,不同的初始排列次序下元素移动的次数有很大变化,最好情况元素正序,则不用移动,最坏情况元素反序,则需要移动次(n 为元素个数)。
16．某CPU 主频为,采用4级指令流水线,每个段的执行需要1个时钟周期。假定CPU 执行了100条指令,在其执行过程中没有发生任何流水线阻塞,此时流水线的吞吐率为（ ） A.
条指令/秒 B.
条指令/秒 C.
条指令/秒 D.
条指令/秒 【答案】C
【解析】采用4级流水线执行100条指令,在执行过程中共用
个时钟周期。 CPU 的主频是,也就是说每秒钟有
个时钟周期。流水线的吞吐率为
条指令/秒,
故答案为C 。
17．在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0(n)