20.在系统总线的数据线上,不.可能传输的是

解析：【答案解析】由权值为 9、2、5、7 的四个叶子构造的哈夫曼树可如下图所示。该树的带权路径长度=9×1+7×2+2×3+5×3=44。【归纳总结】对哈夫曼树特征的总结：（1）用 n 个权值（对应 n 个叶子结点）构造哈夫曼树，共需要 n-1 次合并，即哈夫曼树中非叶子结点的总数为 n-1，总结点个数为 2n-1。（2）哈夫曼树中没有度为 1 的结点，因为非叶子结点都是通过两个结点合并而来。但是，没有度为 1 的二叉树并不一定是哈夫曼树。（3）用 n 个权值（对应 n 个叶子结点）构造的哈夫曼树，形态并不是唯一的。建立哈夫曼树的过程中有以下三种常见的错误：（1）在合并中不是选取根结点权值最小的两棵二叉树（包括已合并的和未合并的），而 是选取未合并的根结点权值最小的一棵二叉树与已经合并的二叉树合并。（2）每次都是在未合并的二叉树中选取根结点的权值最小的两棵子树。（3）有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树， 但那只是巧合，没有规律性，而没有规律性的解法不利于用计算机进行处理。

1.下列函数的时间复杂度是

28.某虚拟存储系统当前内存的分配情况如下表所示,当前时间为 65000 当采用先进先出（FIFO）页面置换算法时，淘汰的页面其页号是

解析：【答案解析】本题考查的是虚拟存储管理的基本概念以及页面置换的基本概念。虚存管 理中，先进先出（FIFO）页面置换算法是选择最早进入内存的页面进行置换。考察表中调入 内存时间，最小者为最早调入内存，其他均无需考虑，故本题正确答案为 A。

解析：【答案解析】能够提高 IO 性能的主要方法是：增加缓冲区，匹配不同速度的外设；采用异步 IO 技术，减少进程阻塞时间；应用 DMA 和通道技术，增加 CPU 与 IO 的并发度；应用虚拟设备技术，提高独占设备的利用率。多处理器并不能提高 IO 性能，多级存储也是，设备独立层为用户使用 IO 提供了方便性，对 IO 性能无益。因此正确答案为 A。

解析：【答案解析】程序中断的实质是程序切换,由现行程序切换到中断服务程序,再由中断服务程 序返回到现行程序。所以中断只是暂停正在运行的程序,而不会暂停 CPU 的运行,也不会暂停对内存的访问。【归纳总结】程序中断是指计算机执行现行程序的过程中,出现某些急需处理的异常情况和 特殊请求,CPU 暂时中止现行程序,而转去对随机发生的更紧迫的事件进行处理,在处理完毕后,CPU 将自动返回原来的程序继续执行。【解题技巧】此题容易误选 D,其错误在于中断不仅用于 I/O 设备的输入输出,还用于对计算机内部的故障和错误的进行处理。