2016考研408真题答案.pdf

2016年计算机学科专业基础综合试题参考答案一、单项选择题1.D2.D3.C4.B5.c6.D7.心8.B9.B10.A11.D12.C13.D14.A15.C16.c17.C18.B19.B20.A21.A22.A23.A24.B25.C26.A27.B28.D29.A30.31.D32.A33.C34.C35.D36.B37.B38.D39.c40.1.解析：根据存储状态，单链表的结构如下图所示：1008H1000H1010H1004H100CHaebd1014Lf其中“链接地址”是指结点next所指的内存地址。当结点f插入后，a指向f,f指向e,e指向b。显然a、e和f的“链接地址”分别是f、b和e的内存地址，即1014H、1004H和1010H.2.解析：此类题的思路万变不离其宗，无论是链表的插入还是删除都必须保证不断链。3.解析：在确保队列先进先出原则的前提下。根据题意具体分析：入队顺序为8、4、2、5、3、9、1、6、7,出队顺序为19。入口和出口之间有多个队列(n条轨道)，且每个队列（轨道）可容纳多个元素（多列列车）。如此分析：显然先入队的元素必须小于后入队的元素（否则，如果8和4入同一队列，8在前4在后，那么出队时只能是8在前4在后)，这样8入队列1,4入队列2,2入队列3,5入队列2（按照前面的原则“大的元素在小的元素后面”也可以将5入队列3，但这时剩下的元素3就必须放到一个新的队列里面，无法确保“至少”，本应该是将5入队列2，再将3入队列3，不增加新队列的情况下，可以满足题意“至少”的要求)，3入队列3,9入队列1，这时共占了3个队列，后面还有元素1，直接再占用一个新的队列4,1从队列4出队后，剩下的元素6和7或者入队到队列2或者入队到队列3（为简单起见我们不妨设个队列的序号分别为1、2、),这样就可以满足题目的要求。综上，共占用了4个队列。当然还有其他的入队出队的情况，请考生们自己推演。但要确保满足：队列中后面的元素大于前面的元素；确保占用最少（即满足题目中的“至少”）的队列。4.解析：三对角矩阵如下图所示：028a11a1,2a21a2,2a230a32a338340an-1.-2an-1.n-1 an-1.nann-1采用压缩存储，将3条对角线上的元素按行优先方式存放在一维数组B中，且a1,!存放于BO中，其存储形式如下所示：a1a12a21a22a23an-lnann1可以计算矩阵A中3条对角线上的元素a,(1i,jn,ij1)在一维数组B中存放的下标为k=2i+j-3。解法一：针对该题，仅需将数字逐一带到公式里面即可：k=2*30+30-3=87,结果为87。解法二：观察上图的三对角矩阵不难发现，第一行有两个元素，剩下的在元素m30,30所在行之前的28行（注意下标1i100、1j100）中每行都有3个元素，而m30,30之前仅有一个元素m30,29,那么不难发现元素m30,30在数组N中的下标是：2+28*3+2-1=87。【注意】矩阵和数组的下标是从0或1开始的（如矩阵可能从ao.o或a1,1开始，数组可能从B0或B1开始)，这时就需要适时调整计算方法（这个方法无非是针对上面提到的公式k=2*i+j3多计算1或少计算1的问题)。5.解析：解法一：树有一个很重要的性质：在个结点的树中有n-1条边，“那么对于每棵树，其结点数比边数多1”。题中的森林中的结点数比边数多10（即25-15=10），显然共有10棵树。解法二：若考生再仔细分析发现，此题也是考察图的某些方面的性质：生成树和生成森林。此时对于图的生成树有一个重要的性质：若图中顶点数为，则它的生成树含有-1条边。对比解法一中树的性质，不难发现两种解法都利用到了“树中结点数比边数多1”的性质，接下来的分析如解法一。6.解析：对于本题，只需按深度优先遍历的策略进行遍历即可。对于选项A:先访问V,然后访问与V1邻接且未被访问的任一顶点（满足的有V2、V3和Vs),此时访问V5,然后从V出发，访问与V邻接且未被访问的任一顶点（满足的只有V4),然后从V4出发，访问与V4邻接且未被访问的任一顶点（满足的只有V3),然后从V3出发，访问与V3邻接且未被访问的任一顶点（满足的只有V2),结束遍历。选项B和C的分析方法与选项A相同，不再赘述。对于选项D,首先访问V1,然后从V1出发，访问与V1邻接且未被访问的任一顶点（满足的有V2、V3和V5),然后从V2出发，访问与V2邻接且未被访问的任一顶点（满足的只有V5),按规则本应该访问V5,但选项D却访问V3,D错误。7.解析：根据拓扑排序的规则，输出每个顶点的同时还要删除以它为起点的边，这样对各顶点和边都要进行遍历，故拓扑排序的时间复杂度为On+e)。8.解析：根据Dijkstra算法，从顶点1到其余各顶点的最短路径如下表所示：。029顶点第1趟第2趟第3趟第4趟第5趟2心5V1+V2V1*V23VI-V2-V3c411之V1Vs+V4V1*VsV4VI-Vs-V4VIV5V44V1-V5969V1V5V6V1VsV6V1V5*V6集合S1,531,5,21,5,2,31,5,2,3,61,5,2,3,6,49.解析：送分题。该程序采用跳跃式的顺利查找法查找升序数组中的x,显然是x越靠前，比较次数才会越少。10.解析：由于B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，可以进行顺序查找，而B树不支持顺序查找（只支持多路查找）。11.解析：外部排序指待排序文件较大，内存一次性放不下，需存放在外部介质中。外部排序通常采用归并排序法。选项A、B、C都是内部排序的方法。12.解析：翻译程序是指把高级语言源程序转换成机器语言程序（目标代码）的软件。翻译程序有两种：一种是编译程序，它将高级语言源程序一次全部翻译成目标程序，每次执行程序时，只要执行目标程序，因此，只要源程序不变，就无须重新编译。另一种是解释程序，它将源程序的一条语句翻译成对应的机器目标代码，并立即执行，然后翻译下一条源程序语句并执行，直至所有源程序语句全部被翻译并执行完。所以解释程序的执行过程是翻译一句执行一句，并且不会生成目标程序。汇编程序也是一种语言翻译程序，它把汇编语言源程序翻译为机器语言程序。汇编语言是一种面向机器的低级语言，是机器语言的符号表示，与机器语言一一对应。13.解析：结合题干及选项可知，shot为16位。因C语言中的数据在内存中为补码表示形式，si对应的补码二进制表示为：1000000000000001B,最前面的一位“1”为符号位，表示负数，即-32767。由signed型转化为等长unsigned型数据时，符号位成为数据的一部分，也就是说，负数转化为无符号数（即正数），其数值将发生变化。Usi对应的补码二进制表示与$i的表示相同，但表示正数，为32769。14.解析：大端方式：一个字中的高位字节(Byte)存放在内存中这个字区域的低地址处。小端方式：一个字中的低位字节(Byt)存放在内存中这个字区域的低地址处。依此分析，各字节的存储分配如下表所示：。030选择遇到的第一个帧（AO,M=0)用于替换。2)如果第1)步失败，则重新扫描，查找(AO,M=1)的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中，对每个跳过的帧，把它的使用位设置成0。3)如果第2)步失败，指针将回到它的最初位置，并且集合中所有帧的使用位均为0。重复第1步，并且如果有必要，重复第2步。这样将可以找到供替换的帧。从而，该算法淘汰页的次序为(0,0)，(0,1)，（1,0)，(1,1)，即A正确。27.解析：当进程退出临界区时置1ock为FALSE,会负责唤醒处于就绪状态的进程，A错误。若等待进入临界区的进程会一直停留在执行while(TSL(&lock)的循环中，不会主动放弃CPU,B正确。让权等待，即当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。通过B选项的分析中发现上述伪代码并不满足“让权等待”的同步准则，C错误。若while(TSL(&lock)在关中断状态下执行，当TSL(&lock)一直为true时，不再开中断，则系统可能会因此终止，D错误。28.解析：分段系统的逻辑地址A到物理地址E之间的地址变换过程如下：越界控制寄存器段号S位移量W段表始址F段表长度M2100逻辑地址A段号段长C基址b01KB6KB16004KB8292物理地址E25008KB320092008KB=82928692主存从逻辑地址A中取出前几位为段号S,后几位为段内偏移量W,注意段式存储管理的题目中，逻辑地址一般以二进制给出，而在页式存储管理中，逻辑地址一般以十进制给出，各位读者要具体问题具体分析。比较段号S和段表长度M,若SM,则产生越界异常，否则继续执行。段表中段号S对应的段表项地址=段表起始地址+段号S段表项长度，取出该段表项的前几位得到段长C。若段内偏移量C,则产生越界异常，否则继续执行。从这句话我们可以看出，段表项实际上只有两部分，前几位是段长，后几位是起始地址。取出段表项中该段的起始地址b,计算E-b+W,用得到的物理地址E去访问内存。题目中段号为2的段长为300，小于段内地址为400，故发生越界异常，D正确。29.解析：在任一时刻t,都存在一个集合，它包含所有最近k次（该题窗口大小为6）内存访问所访问过的页面。这个集合wk,)就是工作集。该题中最近6次访问的页面分别为：6、0、3、2、3、2，再去除重复的页面，形成的工作集为6,0,3,2。30.解析：P1中对a进行赋值，并不影响最终的结果，故a=1与a=2不需要互斥执行；a-x与b=x执行先后不影响与b的结果，无需互斥执行；x+=1与x+=2执行先后会影响x的结果，需要互斥执。033