2010考研408真题答案.pdf

调整后，关键字37所在结点的左、右子结点中保存的关键字分别是24、53。5.解析：设树中度为i(=0,1,2,3,4)的结点数分别为N,树中结点总数为N,则树中各结点的度之和等于N-1,即N=1+N,+2N2+3N3+4N4=No+N1+N2+N3+N4,根据题设中的数据，即可得到No82,即树T的叶结点的个数是82。6.解析：哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为1的结点，B正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左、右子树构造一棵新的二叉树，C正确：哈夫曼树中任一非叶结点P的权值为其左、右子树根结点权值之和，其权值不小于其左、右子树根结点的权值，在与结点P的左、右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q,那么结点Q的兄弟结点中权值较小的一个应该与结点P作为左、右子树构造新的二叉树。综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。7.解析：要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通，首先需要G的任意6个结点构成完全连通子图G1,需n(n-1)/2=6(6-1)/2=15条边，然后再添一条边将第7个结点与G1连接起来，共需16条边。8.解析：拓扑排序的过程如下图所示。a输出e一又输出b输出b输出e输出c)输出c输出c输出e又输出d,得到aebed输出d得到abecd输出d,得到abced可以得到3个不同的拓扑序列，分别为：abced、.abecd、aebcd。9.解析：折半查找法在查找成功时进行的关键字比较次数最多为1og2+1,即判定树的高度；折半查找法在查找不成功时进行的关键字比较次数最多为1og2+1。题中n=16,因此最多比较1og216+1=5次。也可以画出草图求解。思考：若本题题干改为求最少的比较次数呢？10.解析：快递排序的递归次数与元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少：如果划分后分区不平衡，则递归次数多。但快速排序的递归次数与分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。145此外，可以形象地把快速排序的递归调用过程用一个二叉树描述，先处理较长或较短分区，可以想象为交换某一递归结点处的左右子树，这并不会影响树中的分支数。11.解析：题中所给的三趟排序过程中，每一趟排序是从前往后依次比较，使最大值“沉底”，符合冒泡排序的特点。看第一趟可知仅有88被移到最后。如果是希尔排序，则12,88,10应变为10,12,88。因此排除希尔排序。如果是归并排序，则长度为2的子序列是有序的。因此可排除归并排序。如果是基数排序，则16,5,10应变为10,5,16。因此排除基数排序。提示：对于此类题，先看备选项的排序算法有什么特征，再看题目中的排序过程是否符合这一特征，从而得出答案。一般先从选项中的简单排序方法（插入排序、起泡排序、选择排序）开始判断，若简单排序方法不符合，再判断排序方法（希尔排序、快速排序、堆排序、归并排序）。12.解析：CPU时钟频率（主频）越高，完成指令的一个执行步骤所用的时间就越短，执行指令的速度越快，I正确。数据通路的功能是实现CPU内部的运算器和寄存器以及寄存器之间的数据交换，优化数据通路结构，可以有效提高计算机系统的吞吐量，从而加快程序的执行，正确。计算机程序需要先转化成机器指令序列才能最终得到执行，通过对程序进行编译优化可以得到更优的指令序列，从而使得程序的执行时间也越短，正确。【另解】定量分析：CPU执行时间=（程序指令条数*每条指令时钟周期数）/时钟频率。提高时钟频率显然可以缩短CPU执行时间；编译优化可能减少程序的指令数或优化指令结构：优化数据通路结构可能减少时钟周期，即提高时钟频率，故选D。13.解析：本题的真正意图是考查补码的表示范围，而不是补码的乘法运算。若采用补码乘法规则计算出4个选项，是费力不讨好的做法，而且极容易出错。8位补码所能表示的整数范围为-128+127。将4个数全部转换为十进制：r1-2,r2=-14,r3=-112,r4=-8,得r2r3=1568,远超出了表示范围，发生溢出。【提示】解题时，尤其是对于这种看似很复杂的题，不要轻易动笔，要弄清题目考查的真正意图，而尽可能地“走捷径”，以免绕进命题者设计的死胡同。14.解析：题中三种数据类型的精度从低到高为int-oat-double,从低到高的转换通常可以保持其值不变，I和正确，而从高到低的转换可能会有数据的舍入，从而损失精度。对于，先将oat型的f转换为t型，小数点后的数位丢失，故其结果不为真。对于IV,初看似乎没有问题，但浮点运算d+f时需要对阶，对阶后f的尾数有效位被舍去而变为0，故d+f仍然为d,再减去d后结果为0，故V结果不为真。此外，根据不同类型数据混合运算的“类型提升”原则，在IV中，等号左端的类型为double型，结果不为真。15.解析：用2K4位的芯片组成一个8K8位存储器，共需8片2K4位的芯片，分为4组，每组由2片2K4位的芯片并联组成2K8位的芯片，各组芯片的地址分配如下：第一组(2个芯片并联)：0000H07FFH。第二组(2个芯片并联)：0800HOFFFH。146第三组(2个芯片并联)：1000H17FFH。第四组(2个芯片并联)：1800H1FFFH。地址0B1FH所在的芯片属于第二组，故其所在芯片的最小地址为0800H16.解析：RAM(分为DRAM和SRAM)断电后会失去信息，而ROM断电后不会丢失信息，它们都采用随机存取方式（注意，采用随机存取方式的存储器并不一定就是随机存储器）。Cache一般采用高速的SRAM制成，而ROM只可读，不能用作Cache,I错误。DRAM需要定期刷新，而ROM不需要刷新，故IV错误。17.解析：Cache中存放的是主存的一部分副本，TLB(快表)中存放的是Pagc(页表)的一部分副本。在同时具有虚拟页式存储器（有TLB)和Cache的系统中，CPU发出访存命令，先查找对应的Cache块。I)若Cache命中，则说明所需内容在Cache内，其所在页面必然已调入主存，因此Page必然命中，但TLB不一定命中；2)若Cache不命中，并不能说明所需内容未调入主存，和TLB、Page命中与否没有联系。但若TLB命中，Page也必然命中；而当Page命中，TLB则未必命中，故D不可能发生。主存、Cache、TLB和Page的关系如下图所示。主存PageTLBCache【提示】本题看似既涉及虚拟存储器又涉及Cache,实际上这里并不需要考虑Cache命中与否。因为一旦缺页，说明信息不在主存，那么TLB中就一定没有该页表项，所以不存在TLB命中、Page缺失的情况，也根本谈不上访问Cache是否命中。18.解析：读者首先必须明白“汇编语言程序员可见”的含义，即汇编语言程序员通过汇编程序可以对某个寄存器进行访问。汇编程序员可以通过指定待执行指令的地址来设置PC的值，如转移指令、子程序调用指令等。而IR、MAR、MDR是CPU的内部工作寄存器，程序员无法直接获取和设置它们的值，也无法直接对它们进行其他操作，所以对程序员不可见。【提示】指令寄存器R中的内容总是根据PC所取出的指令代码。在CPU的专用寄存器中，只有PC和PSWR是汇编程序员可见的。19.解析：采用流水线方式，相邻或相近的两条指令可能会因为存在某种关联，后一条指令不能按照原指定的时钟周期运行，从而使流水线断流。有三种相关可能引起指令流水线阻塞：结构相关，又称资源相关；数据相关：控制相关，主要由转移指令引起。而数据旁路技术，其主要思想是不必待某条指令的执行结果送回到寄存器，再从寄存器中取出该结果，作为下一条指令的源操作数，而是直接将执行结果送到其他指令所需要的地方，这样可以使流水线不发生停顿。20.解析：典型的总线标准有：ISA、EISA、VESA、PCI、PCI-Express、AGP、USB、RS-232C等。A中的CRT是纯平显示器：B中的CPI是每条指令的时钟周期数；C中的RAM是半导体随机存储器、MPS是每秒执行多少百万条指令数。21.解析：147在单级（或单重）中断系统中，不允许中断嵌套。中断处理过程为：关中断；保存断点：识别中断源；保存现场：中断事件处理；恢复现场：开中断；中断返回。其中，由硬件完成，由中断服务程序完成，故选A。【排除法】选项B、C、D的第一个任务（保存断点或关中断）都是由中断隐指令完成的，即由硬件直接执行，与中断服务程序无关。22.解析：刷新所需带宽=分辨率色深帧频-1600120024bit85Hz-3916.8Mb/s,/显存总带宽的50%用来刷屏，于是需要的显存总带宽为3916.8Mb/s0.5=7833.6Mb/s7834Mb/s。23.解析：操作系统提供的接口主要有两类：命令接口和系统调用。系统调用是能完成特定功能的子程序，当应用程序请求操作系统提供某种服务时，便调用具有相应功能的系统调用。库函数则是高级语言中提供的与系统调用对应的函数（也有些库函数与系统调用无关），目的是隐藏访管指令的细节，使系统调用更为方便、抽象。但要注意，库函数属于用户程序而非系统调用，是系统调用的上层。下图是Liux中的分层关系。用户接口用户库函数接口标准系统程序实用程序系统程序：汇编、编译、编辑、Shel系统调用接口标准库函数标准函数：打开、关闭、读、写、创建、撤销操作系统系统调用：进程管理、存储管理、文件管理、设备管理24.解析：引起进程创建的事件有：用户登录、作业调度、提供服务、应用请求等。I.用户登录成功后，系统要为此创建一个用户管理的进程，包括用户桌面、环境等。所有的用户进程会在该进程下创建和管理。.设备分配是通过在系统中设置相应的数据结构实现的，不需要创建进程。.启动程序执行是典型的引起创建进程的事件。25.解析：信号量表示相关资源的当前可用数量。当信号量K0时，表示还有K个相关资源可用，所以该资源的可用个数是1。而当信号量K0时，表示有K个进程在等待该资源。由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。26.解析：进程时间片用完，可降低其优先级以让别的进程被调度进入执行状态。B选项中进程刚完成I/O,进入就绪队列等待被处理机调度，为了让其尽快处理IVO结果，故应提高优先权。C选项中进程长期处于就绪队列，为不至于产生饥饿现象，也应适当提高优先级。D选项中进程的优先级不应该在此时降低，而应在时间片用完后再降低。27.解析：这是皮特森算法的实际实现，保证进入临界区的进程合理安全。该算法为了防止两个进程为进入临界区而无限期等待，设置变量um,表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置u标志，不允许另一个进程进入，这时，再同时检测另一个进程状态标志和不148允许进入表示，这样可以保证当两个进程同时要求进入临界区时只允许一个进程进入临界区。保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入。先到先入，后到等待，从而完成临界区访问的要求。其实这里可以想象为两个人进门，每个人进门前都会和对方客套一句“你走先”。如果进门时没别人，就当和空气说句废话，然后大步登门入室；如果两人同时进门，就互相请先，但各自只客套一次，所以先客套的人请完对方，就等着对方请自己，然后光明正大地进门。28.解析：最佳适配算法是指每次为作业分配内存空间时，总是找到能满足空间大小需要的最小的空闲分区给作业，可以产生最小的内存空闲分区，如图3-2所示。6MB15MB15MB15MB15MB9MB55MB30MB30MB30MB30MB40MB8MB10MB10MB8MB2MB2MB初始分配分配释放分配分配15MB30MB15MB8MB6MB29.解析：页大小为2B,页表项大小为2B,故一页可以存放2”个页表项，逻辑地址空间大小为26页，即共需216个页表项，则需要2162=2=128个页面保存页表项，即页目录表中包含表项的个数至少是128。30.解析：每个磁盘索引块和磁盘数据块大小均为256B,每个磁盘索引块有256/4=64个地址项。因此，4个直接地址索引指向的数据块大小为4256B:2个一级间接索引包含的直接地址索引数为2(256/4),即其指向的数据块大小为2(256/4)256B。1个二级间接索引所包含的直接地址索引数为(256/4)(256/4)，即其所指向的数据块大小为(256/4)(256/4)256B。即7个地址项所指向的数据块总大小为4256+2(256/4)256+(256/4)(256/4)256=1082368B=1057KB。31.解析：当一个文件系统含有多级目录时，每访问一个文件，都要使用从树根开始到树叶为止、包括各中间结点名的全路径名。当前目录又称工作目录，进程对各个文件的访问都相对于当前目录进行，而不需要从根目录一层一层的检索，加快了文件的检索速度。选项AB都与相对目录无关：选项D,文件的读/写速度取决于磁盘的性能。32.解析：键盘是典型的通过中断/O方式工作的外设，当用户输入信息时，计算机响应中断并通过中断处理程序获得输入信息。33.解析计算机网络的各层及其协议的集合称为体系结构，分层就涉及到对各层功能的划分，因此A、B、D正确。体系结构是抽象的，它不包括各层协议的具体实现细节。计算机网络中在讲解网络层次时，仅有讲各层的协议和功能，而内部实现细节则没有提及。内部实现细节是由具体设备厂家来确定的。149