2013考研408真题答案.pdf

027141455最小的带权路径长度为(2+3)3+(4+5)2+(6+7)1=46。5.解析：根据后序线索二叉树的定义，X结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后序遍历的方式可知X结点的后序后继是其父结点，即其右线索指向的是父结点。为了更加形象，在解题的过程中可以画出如下草图。6.解析：在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树会发生变化，不完全相同。7.解析：邻接矩阵A为非对称矩阵，说明图是有向图，度为入度加出度之和。各顶点的度是矩阵中此结点对应的行（对应出度）和列（对应入度）的非零元素之和。8.解析：送分题。只要掌握DFS和BFS的遍历过程，便能轻易解决。逐个代入，手工模拟，选项D是深度优先遍历，而不是广度优先遍历。b9.解析：找出AOE网的全部关键路径为(b、d、c、g)、(b、d、e、h)和(b、f、h)。根据定义，只有关键路径上的活动时间同时减少时，才能缩短工期，即正确选项中的两条路径必须涵盖在所有关键路径之中。利用关键路径算法可求出图中的关键路径共有三条：(b、d、c、g)、(b、d、e、h)和(b、f、h)。由此可知，选项A和B中并不能包含(b、f、h)这条路径，选项C中，并不能087包含(b、d、c、g)和(b、d、e、h)这两条路径，只有C包含了所有的关键路径，因此只有加快f和d的进度才能缩短工期（建议考生在图中检验）。10.解析：对于5阶B树，根结点只有达到5个关键字时才能产生分裂，成为高度为2的B树，因此高度为2的5阶B树所含关键字的个数最少是5。11.解析：基数排序的第1趟排序是按照个位数字的大小来排序的，第2趟排序是按照十位数字的大小进行排序的，排序的过程如下图所示。1回-1回-00可91回114-2022eo分配：0血2回4120收集：-020-91四-12214-00719eoe1e2阿2阿分配：咖卤函画收集：-00710-9四14-m网-20-2四12.解析：基准程序的CPI=20.5+30.2+40.1+50.2=3。计算机的主频为1.2GHz,即1200MHz,故该机器的MPS=1200/3=400。13.解析：IEEE754单精度浮点数格式为C6400000H,二进制格式为11000110010000000000000000000000,转换为标准的格式为：阶码尾数1000110010000000000000000000000数符=1表示负数：阶码值为10001100-01111111=00001101=13：尾数值为1.5（注意其有隐含位，要加1)。因此，浮点数的值为-1.523。14.解析：x*2,将x算术左移一位为11101000；y/2,将y算术右移一位为11011000，均无溢出或丢失精度。补码相加为11101000+11011000=11000000，亦无溢出。15.解析：设校验位的位数为k,数据位的位数为n,海明码能纠正一位错应满足下述关系：2*+k+1。n=8,当k-4时，24(=168+4+1(13)，符合要求，故校验位至少是4位。16.解析：按字节编址，页面大小为4KB,页内地址共12位。地址空间大小为4GB,虚拟地址共32位，前20位为页号。虚拟地址为03FFF180H,故页号为03FFFH,页内地址为180H。查找页标记08803FFH所对应的页表项，页框号为0153H,页框号与页内地址拼接即为物理地址0153180H。17.解析：根据变址寻址的方法，变址寄存器的内容(1000H)与形式地址的内容(2000H)相加，得到操作数的实际地址(3000H),根据实际地址访问内存，获取操作数4000H。变址寄存器形式地址1000H2000H地址内容1000H2000H3000H3000H3000H4000日18.解析：采用4级流水执行100条指令，在执行过程中共用4+(100-1)=103个时钟周期。CPU的主频是1.03GHz,也就是说每秒钟有1.03G个时钟周期。流水线的吞吐率为1.03G100/103=1.0109条指令秒。时钟99100时钟399100时钟2999100时钟129910010019.解析：USB是一种连接外部设备的I/O总线标准，属于设备总线，是设备和设备控制器之间的接口。而PCI、AGP、PCI-E作为计算机系统的局部总线标准，通常用来连接主存、网卡、视频卡等。20.解析：RAD0方案是无冗余和无校验的磁盘阵列，而RAD15方案均是加入了冗余（镜像）或校验的磁盘阵列。条带化技术就是一种自动地将V0的负载均衡到多个物理磁盘上的技术，条带化技术就是将一块连续的数据分成很多小部分并把它们分别存储到不同磁盘上去。这就能使多个进程同时访问数据的多个不同部分而不会造成磁盘冲突，而且在需要对这种数据进行顺序访问的时候可以获得最大程度上的IVO并行能力，从而获得非常好的性能。故能够提高RAD可靠性的措施主要是对磁盘进行镜像处理和奇偶校验，其余选项不符合条件。21.解析：磁盘转速是10000转/分，转一圈的时间为6ms,因此平均查询扇区的时间为3ms,平均寻道时间为6ms,读取4KB扇区信息的时间为4KB/(20MB/s)=0.2ms,磁盘控制器延迟为0.2ms,总时间为3+6+0.2+0.2-9.4ms。22.解析：中断处理方式：在I/O设备输入每个数据的过程中，由于无需CPU干预，因而可使CPU与/O设备并行工作。仅当输完一个数据时，才需CPU花费极短的时间去做些中断处理。因此中断申请使用的是CPU处理时间，发生的时间是在一条指令执行结束之后，数据是在软件的控制下完成传送的。而DMA方式与之不同。DMA方式：数据传输的基本单位是数据块，即在CPU与IVO设备之间，每次传送至少一个数据块；DMA方式每次申请的是总线的使用权，所传送的数据是从设备直接送入内存的，或者相反：仅在传送一个或多个数据块的开始和结束时，才需CPU干预，089