2011年联考《408计算机学科专业基础综合》真题答案.pdf

计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解。请见：网学天地(www.e-);咨询QQ:2696670126绝密启用前2011年全国硕士研究生几学统一考试计骨机科学与技术学科联考计算机学科专业基础综合试题答案及评分参考一、单项选择题：每小题2分，共80分。1.A2.B3.B5.C6.D7.A8.10.A11.B12.D13.A15.D16.A17.C18.D1920.C21.D22.C23.E2425.D26.B27.DA30.C31.B32.CB35.B36.D37.D39.C40.B二、综合应用题：4147小0分41.【答案要点】(1)图G的邻接矩阵A如下：(2分)K603P03%030(2)图G如下：(2分)4【评分说明】考生画出的图G与上图同构，给2分。若考生画出的图G部分正确，可酌情给分。(3)下图中粗线箭头所标识的4个活动组成图G的关键路径。(3分)计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解。请见：网学天地(www.e-);咨询QQ:2696670126图G的关键路径的长度为16。(1分)【评分说明】若考生给出的答案(1)或答案(2)不完全正确，但所画的图是含6个顶点、7条边的有向无环图，且所求得的关键路径及路径长度与考生所画的图吻合，则按(3)的标准给分。部分正确，可酌情给分。42.【答案要点】(1)算法的基本设计思想如下：(5分)分别求两个升序序列A、B的中位数，设为a和b。若a=b财或b即为所求的中位数：否则，舍弃a、b中较小者所在序列之较小一半，同时啥弃较大者所在忘列之较大一半，要求两次舍弃的元素个数相同。在保留的两个升序序列中，重复述过稀直到两个序列中均只含一个元素时为止，则较小者即为所求的中位数。(2)算法实现如下：(8分)int Search(int Al,int B,int n)(即为序的长度1int s1,el,midl,s2,e2,mid2s1=0;e1=n-17s2-1;e2=n-1wh11e(s11=e1f1s2182w叭w.一Stmidl=(s1+e1)/2:mid2-(2te2722if(Amid1)-=Bmid2)return Aimidif(Amid1Bmid2)/分别考虑奇数和偶数，保特两个子数组元素个数相等1f(s1+e1)号2=0)/若元素个数为奇数个sl=mid1;/舍弃A中间点以前的部分且保留中间点e2-mid2:/舍弃B中间点以后的部分且保留中间点else1/若元素个数为偶数个sl=midi+l;/舍弃A中间点及中间点以前部分e2-mid2;/舍弃B中间点以后部分且保留中间点计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解。请见：网学天地(www.e-);咨询QQ:2696670126else1f(s1+e1)号2=0)/若元素个数为奇数个el=mid1;/舍弃A中间点以后部分且保留中间点s2=mid2;/舍弃B中间点以前部分且保留中间点else/若元素个数为偶数个e1=mid1+1;/舍弃A中间点以后部分且保留中间点s2=mid2;/舍弃B中间点及中间点以前的部分return(As1】Bs2？As1】:Bs2:(3)上述所给算法的时间、空间复杂度纷别是010g0霜O(1)。(2分)【评分说明】考生设计的算法满足题目的能要求自症确刘(1)、(2)根据所实现算法的效率给分，细则见下表。时间空间复杂度复杂度出得分得分说明0(1ogn）0(1)5O(logzn)O(l0gan)57如采用递归算法0(n)7如采用2路归并的思想，程序见表后0(n)o()5如采用2路归并的思想，但使用了辅助数组其他其他3如对所有元素进行排序后再查找中位数/采用2路归并的思想实现如下：int M search(int A,int B,int n)int i,j,k;1=j=k=0:while(in&jn)k+;iE(A1Bj)i+:if(k=n)计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解。请见：网学天地(www.e-);咨询QQ:2696670126确，可给1分。只要说明最后一条语句溢出就给1分。44.【答案要点】(1)虚拟地址为24位，其中高12位为虚页号。(1分)物理地址为20位，其中高8位为物理页号。(1分)(2)20位物理地址中，最低5位为块内地址，中间3位为Cache行号，高12位为标志【评分说明】每答对一个字段给1分。(3).在主存中。(1分)虚拟地址001C60H000000000001110001100000B,故虚页号为000000000001B,查看000000000001B=001H处的页表项，由于对应的有效位为1，故虚拟地址001C60H所在的页面在主存中。(1分)页表001H处的页框号（物理页号）为04H=00000100B与页内偏移110001100000B拼接成物理地址：00000100110001100000B=04C60H。1分Q对于物理地址00000100110001100000B,所在主存块只可能映射到Cache第3行（即第011B行)；由于该行的有效位=1、标记（值为103H)04CF(物理地址高12位），故访问该地址时Cache不命中。(2分)【评分说明】仅指出正确的Cache行号给l分。(4)虚拟地址024BACH-00000010010011010100B,故虚页号为000000100100B。由于TLB只有8/4-=2个组，故虚页号中高位为TL及标花，最低1位为TLB组号，它们的值分别为00000010010B(即012和0B,因此该虚拟地址所对应的物理页面只可能映射到TLB第0组。(1分)由于组0中存在有效位、标说012H的黄，所以访间TLB命中，即虚拟地址024BACH所在的页面在主存中。(1分叭45.【答案要点】(1)互斥资源：取景机（一次仅允许一位顾客领号），设一个互斥信号量mutex。(2)同步问题顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客为其服务。有无空座位决定了顾客等待否，有无顾客决定了营业员是否提供服务，故设置信号量empty和full来实现这个同步关系。另外，顾客获得空座位后，需要等待叫号和被服务。这样，顾客和营业员之间也存在同步关系，定义信号量service来控制这个同步。Semaphore mutex=l;/管理取号机的互斥信号量，初值为1，表示取号机空闲Semaphore empty-10;/表示空余座位数量的资源信号量，初值为10Semaphore.full=0;1/表示已占座位数量的资源信号量，初值为0Semaphore service=0;/等待叫号Process顾客1()P(empty);P(mutex)从取号机上取号，V(mutex);