1、计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解。请见：网学天地(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分)K
2、603P03%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)算法的基本设计思想如下
3、：(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-(2te2722i
4、f(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)/若元素个数为奇数个
5、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路归并的思想，程序见表
6、后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:2696670126return Ai-1;elsej+:if(k=n)return Bj-1;若在算法的基本设计思想描述中因文字表达没有非常清晰地反映出算法思路，但在算法实现中能够清晰地看出算法
7、思想且正确的，可参照的标准给分若算法的基本设计思想描述或算法实现中部分正确，可参照中各种情况的相应给分标准酌情给分。若考生所估计的时间复杂度及空间复杂度与考生所实现的算法。藏，各给1分。参考答案中只给出了使用C语言的版本，使用小ava语言的答案视同使用C语言。43.【答案要点】5(1)134=128+6=10000110B,所以x的规器数为10000的，故R1的内容为86H。(1分)246=255-9=11110110B,所以y的机器数为1101108xy=10000110+00001010=(0)10010000,括弧中的0为加法器的进位故R5的内容为90泊.(1分)x+y=10000110
8、+11110110=(1)01111100,括弧中的1为加法器的进位故R6的内容为7CH。(1分)【评分说明】“R1的内容”也可表综为“(2)m的机器数与x的机器数相同皆羧86H=10000110B,解释为带符号整数m(用补码表示)时，其值为11010B=122。(芬)mn的机器数与y的机器数相同，皆为90H=10010000B,解释为带符号整数k1(用补码表示)时，其值为-110000B=112。(1分)(3)能。(1分)n位加法器实现的是模2”无符号整数加法运算。对于无符号整数a和b、a+b可以直接用加法器实现，而a-b可用a+b的补数实现，即a-b=a+-b补(mod2),所以n位无符号
9、整数加/减运算都可在n位加法器中实现。（1分)由于带符号整数用补码表示，补码加/减运算公式为：a+b#a+b)#（mod2)、a-b)a+-b#(mod2),所以n位带符号整数加/减法运算都可在n位加法器中实现。【评分说明】理由部分基本正确，即可给分。(4)带符号整数加/减运算的溢出判断规则为：若加法器的两个输入端（加数)的符号相同，且不同于输出端（和）的符号，则结果溢出。（或加法器完成加法操作时，若次高位的进位和最高位的进位不同，则结果溢出)(2分)最后一条语句执行时会发生溢出。因为10000110+11110110=(1)01111100，括弧中的1为加法器的进位，根据上述滋出判断规则，可
10、知结果溢出。(1分)【评分说明】正确说明其中一种溢出判断规则给2分，若给出的说明是变形补码溢出判断规则且正计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解。请见：网学天地(www.e-);咨询QQ:2696670126V(fu11):磁说P(service);/等特叫号获取服务：Process clerk(While(true)克言之比。裂P(fu11):v(epty）;V(service);/叫号为顾客服务：1【评分说明】能正确给出互斥信号量定义、含义积翻值，给)分。能正确给出3个同步信号量定义，含和初值，给2营业员进程描述正确的，给2分。)顾客进程描述中，互斥描述确的，给
11、1分，铜步描述正确的，给2分：共3分。其他正确解答，参照一的稀推给分。46.【答案要点】(1)在磁盘中连续存放（采取连续结构磁盘寻道时间更短，文件随机访问效率更高：(2分)在FCB中加队的字段为或者。(1分)(2)将所有FCB集中存放，文件数据集中存放。(2分)这样在随机查找文件名时，只需访问FCB对应的块辱可减沙碳头移动和磁盘VO访问次数。(2分)47.【答案要点】(1)由题47乃图可知，该数据顿所封装的P分组的目的地址就是Wb服务器的P地址，即64.170.98.32(40aa6220H):（1分)该数据帧的目的MAC地址就是该主机的默认网关MAC地址，即00-21-27-21-51-ee
12、。(1分)(2)该主机在构造题47b图的数据帧时，使用ARP协议确定目的MAC地址：（1分)因为ARP协议请求报文需要进行广播，所以封装ARP协议请求报文的以太网帧的目的MAC地址是ff-ff任f-ff。（1分)(3)根据持续的非流水线方式HTTP1.1协议的工作原理，每个RTT传输一个对象，共需要传输6个对象(1个Html页面和5个PEG小图像)，所以共需要6个RTT。(2分)【评分说明】若考生解答时将TCP连接建立过程的1个RTT时间计算进来，即7个RTT,给1分。(4)该帧所封装的P分组经过路由器R转发时，需要修改P分组头中的字段有：源P地址、TTL和头部校验和。【评分说明】若考生解答时将所有的P头中的字段进行罗列，不给分，其他情况酌情给分。
