2009考研408真题答案.pdf

5.解析：完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了82=16个叶结点，故完全二叉树的结点个数最多为(2？-1)-16=111个结点。6.解析：森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。情形I:若结点v是结点u的第二个孩子结点，在转换时，结点v就变成结点u第一个孩子的右孩子，符合要求。情形：结点u和v是兄弟结点的关系，但二者之中还有一个兄弟结点k,则转换后，结点V就变为结点k的右孩子，而结点k则是结点山的右孩子，符合要求。OO图1图情形：若结点的父结点与v的父结点是兄弟关系，则转换后，结点u和v分别在两者最左父结点的两棵子树中，不可能出现在同一条路径中。233图【逆向法】由题意可知u是的父结点的父结点，如下图所示有4种情况：(1)(4)根据树与二叉树的转换规则，将这4种情况转换成树种结点的关系。(1)在原来的树中u是的父结点的父结点：(2)在树中u是v的父结点；(3)在树中u是v的父结点的兄弟；(4)在树中u与v是兄弟关系。由此可知I和正确。7.解析：每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次（出度和入度），故所有顶点的度之和为边数的两倍，I正确。n个顶点、n-1条边可以构成无向连通图，比如树，错误。顶点数为N(N21)的无向完全图中不存在度为1的顶点，错误。8.解析：选项A、B和C都是B-树的特点，而选项D则是B+树的特点。注意区别B-树和B+树各自163的特点。9.解析：根据关键字序列得到的小顶堆的二叉树形式如下图所示。回)(2)(3)插入关键字3时，先将其放在小顶堆的末端，如图(2)所示。再将该关键字向上进行调整，得到的结果如图(3)所示。所以，调整后的小顶堆序列为3,5,12,8,28,20,15,22,19。10.解析：解答本题需要对各种排序算法的特点极为清楚。对于冒泡排序和选择排序，每一趟都能确定一个元素的最终位置，而题目中，前2个元素和后2个元素均不是最小或最大的2个元素并按序排列。选项D中的2路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。插入排序在每趟排序后能确定前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特征。11.解析：虽然指令和数据都是以二进制形式存放在存储器中，但CPU可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，在执行阶段取出的是数据。本题容易误选A,需要清楚的是，CPU只有在确定取出的是指令之后，才会将其操作码送去译码，因此，不可能依据译码的结果来区分指令和数据。12.解析：C语言中的整型数据为补码形式，it为32位，shot为l6位，故x、y转换成十六进制为O000007FH、FFF7H。执行z=x+y时，由于x是imt型，y为shot型，需将短字长数据转换成长字长数据，称之为“符号扩展”。由于y的符号位为1，故在y的前面添加16个1，即可将y上升为int型，其十六进制形式为FFFFFFF7H。最后执行加法，即O000007FH+FFFFFFF7H=00000076H,其中最高位的进位1自然丢弃。故选D。【排除法】对于x的值，4个选项都一样，无需计算；zx+y127-9=1180,前4个字节必然全O,排除BC;只需算出y9的值即可，其十六进制形式为FFF7H,排除A。【提示】解题时，应先排除明显错误的选项，然后再推敲剩下的选项。13.解析：X的浮点数格式为00,111：00,11101（分号前为阶码，分号后为尾数），Y的浮点数格式为00,101;00,10100。然后根据浮点数的加法步骤进行运算。第一步：对阶。X、Y阶码相减，即00,111-00,101=00,111+11,0111=00,010，可知X的阶码比Y的价码大2（这一步可直接目测）。根据小阶向大阶看齐的原则，将Y的阶码加2，尾数右移2位，将Y变为00,11100,00101。第二步：尾数相加。即00,11101+00,0010101,00010，尾数相加结果符号位为01，故需右规。第三步：规格化。将尾数右移1位，阶码加1，得X+Y为01,000：00,10001。164命中率-Cache命中次数/总访问次数。需要注意的是看清题，题中说明的是缺失50次，而不是命中50次，仔细审题是做对题的第一步。22.解析：外部中断指的是CPU执行指令以外的事件产生的中断，通常是指来自CPU与内存以外的中断。A中键盘输入属于外部事件，每次键盘输入CPU都需要执行中断以读入输入数据，所以能引起外部中断。B中除数为0属于异常，也就是内中断，发生在CPU内部。C中浮点运算下溢将按机器零处理，不会产生中断。而D访存缺页属于CPU执行指令时产生的中断，也不属于外部中断。所以能产生外部中断的只能是输入设备键盘。23.解析：在单处理机系统（不包含多核的情况）中，同一时刻只能有一个进程占用处理机，因此进程之间不能并行执行。通道是独立于CPU的控制输入输出的设备，两者可以并行，显然，设备与设备之间也是可以并行的。24.解析：在高响应比优先调度算法中，选出响应比最高的进程投入执行，响应比R定义如下：响应比R=(等待时间+执行时间)/执行时间。它综合考虑了每个进程的等待时间和执行时间，对于同时到达的长进程和短进程，短进程会优先执行，以提高系统吞吐量：而长进程的响应比可以随等待时间的增加而提高，不会产生进程无法调度的情况25.解析：这种题用到组合数学中鸽巢原理的思想。考虑最极端情况，因为每个进程最多需要3台打印机，如果每个进程已经占有了2台打印机，那么只要还有多的打印机，总能满足一个进程达到3台的条件，然后顺利执行，所以将8台打印机分给K个进程，每个进程有2台打印机，这个情况就是极端情况，K为4。26.解析：每个进程都拥有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界，因此需要进行界地址保护，即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断。27.解析：分段存储管理的逻辑地址分为段号和位移量两部分，段内位移的最大值就是最大段长。地址长度为32位，段号占8位，则位移量占32-8=24位，故最大段长为224B。28.解析：文件的物理结构包括连续、链式、索引三种，其中链式结构不能实现随机访问，连续结构的文件不易于扩展。因此随机访问且易于扩展是索引结构的特性。29.解析：SCAN算法类似电梯的工作原理。首先，当磁头从105道向序号增加的方向移动时，便会按照从小到大的顺序服务所有大于105的磁道号(110,170,180,195)：往回移动时又会按照从大到小的顺序进行服务(68,45,35,12)。30.解析：为了实现“按名存取”，在文件系统中为每个文件设置用于描述和控制文件的数据结构，称之为文件控制块(FCB)。在文件控制块中，通常包含以下三类信息，即基本信息、存取控制信息及使用信息。31.解析：166建立符号链接时，引用计数值直接复制：建立硬链接时，引用计数值加1。删除文件时，删除操作对于符号链接是不可见的，这并不影响文件系统，当以后再通过符号链接访问时，发现文件不存在，直接删除符号链接；但对于硬链接则不可以直接删除，引用计数值减1，若值不为0，则不能删除此文件，因为还有其他硬链接指向此文件。当建立F2时，F1和F2的引用计数值都为1。当再建立F3时，F1和F3的引用计数值就都变成了2。当后来删除F1时，F3的引用计数值为2-1=1，F2的引用计数值一直不变。32.解析：设备管理具有设备独立性的特点，操作系统以系统调用方式来请求某类设备时，使用的是逻辑设备名。而在程序实际执行时，将逻辑设备名转换为对应的物理设备名。33.解析：传输层提供应用进程间的逻辑通信（通过端口号），即端到端的通信。而数据链路层负责相邻结点之间的通信，这个结点包括了交换机和路由器等数据通信设备，这些设备不能称为端系统。网络层负责主机到主机的逻辑通信。因此选B。34.解析：采用4个相位，每个相位有4种幅度的QAM调制方法，每个信号可以有16种变化，传输4bit的数据。根据奈奎斯特定理，信息的最大传输速率为23k4-24kbps。35.解析：在后退N帧协议中，当接收方检测到某个帧出错后，则简单地丢弃该帧及其后所有的后续帧，发送方超时后需重传该数据帧及其后续的所有帧。这里应注意，连续ARQ协议中，接收方一般采用累积确认的方式，即接收方对按序到达的最后一个分组发送确认，因此本题中收到3的确认帧就表示编号为0、1、2、3的帧已接收，而此时发送方未收到1号帧的确认只能代表确认帧在返回的过程中丢失了，而不代表1号帧未到达接收方。因此需要重传的帧为编号是4、5、6、7的帧。36.解析：交换机实质上是一个多端口网桥，工作在数据链路层，数据链路层使用物理地址进行转发而转发到目的地通常是使用目的地址。因此PDU地址是目的物理地址。37.解析：若最短帧长减少，而数据传输速率不变，则需要使冲突域的最大距离变短来实现碰撞窗口的减少。碰撞窗口是指网络中收发结点间的往返时延，因此假设需要减少的最小距离为S,则可以得到如下公式（注意单位的转换）：减少的往返时延=减少的发送时延，即2s/(210)=800/(110)。即，由于帧长减少而缩短的发送时延，应等于由于距离减少而缩短的传播时延的2倍。可得s=80,即最远的两个站点之间的距离最少需要减少80m。【注意】CSMA/CD的碰撞窗口=2倍传播时延，报文发送时间碰撞窗口。38.解析：返回的确认序列号是接收端期待收到对方下一个报文段数据部分的第一个字节的序号，因此乙在正确接收到两个段后，返回给甲的确认序列号是200+300+500=1000。39解析：在发生超时后，慢开始门限ssthresh变为16KB/2=8KB,拥塞窗口变为1KB。在接下来的3个RTT内，执行慢开始算法，拥塞窗口大小依次为2KB、4KB、8KB,由于慢开始门限ssthresh为8KB,因此之后转而执行拥塞避免算法，即拥塞窗口开始“加法增大”。因此第4个RTT结束167: