全国硕士研究生入学统一考试计算机科学与技术学科联考

PAGEPAGE19计算机科学与技术学科联考计算机学科专业基础综合试题1～40280求整数n(n≥0)intfact(intn){if(n<=1)return1;returnn*fact(n-1);}A.O(log2n) B.O(n) C.(nlog2n) D.O(n2)‘+’‘-’‘*’‘/’‘(’和‘)’a+b-a*((cd)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+A.5 B.7 C.8 D.11a,e,b,d,c，后序遍历序列为b,c,d,e,aA.只有e B.有eb C.有、c D.无确定平二树高为6，且有叶点平衡子为1，该衡二树结总为A.10 B.20 C.32 D.33neA.O(n) B.O(e) C.O(n+e) D.O(n*e)A.存，唯一 B.，且唯一C.在可不一 D.无确定否在（Dijkstra）abcA.d,e,f B.e,d,f C.f,d,e D.f,e,d用普里姆（Prim）（Kruskal）A.仅I B.仅II C.仅、III D.仅、3阶B78BA.60 B.60,62 C.62,65 D.65I.简单选排序 希排序 快速排序 IV排序 二归排序A.仅、、IV B.仅、III、VC.仅II、、IV D.仅、IV、VA.排的趟数 B.素移次数C.用助间数量 D.元之的较数A10090CPUCPU50%，I/O速度不变，则运行基准程序AA.55秒 B.60秒 C.65秒 D.70秒intshort3216位，执行下列Cunsignedshortx=65530;unsignedinty=x;得到y的机器数为A.00007FFA B.0000C.FFFF7FFA D.FFFAfloat即IEEE754）A.2126-2103 B.2127-2104 C.2127-2103 D.2128-2104int和short3216，并且数据按边界对齐存储。某Cstruct{int a;charb;short }record;record.a=273;若record变量的首地址为0Xc008，则低至0Xc008中内容及record.c的地址分别为A.0x00、0xC00D B.0x00、0xC00EC.0x110xC00D D.0x11、0xC00E（FlashMemory）MOSCache4Cache1个字。若Cache2路组相联映射方式和LRU0,4,8,2,0,6,8,6,4,8时，命中CacheA.1 B.2 C.3 D.433573、12、56A.5位 B.6位 C.15位 D.33位100MHz32/（）“128A.20ns B.40ns C.50ns D.20．下列关于USB221．下列选项中，在I/O总线的数据线上传输的信息包括I.接口的令字 接口状态字 中断类号A.仅、II B.仅、III C.仅、III D.I、II、22．应部断过中，断指完的作，保断外还括I.关中断 保存用存的容 形成中服序入地送PCA.仅、II B.仅、III C.仅、III D.I、II、23．列项，可在用态生事是A.系调用 B.部断 C.程换 D.缺页A.程计器 B.序态存器C.用据存器 D.用址器A.虚存只基连分配术 B.虚拟储能于连分配术C.拟储量受容量限制 D.虚拟储量受存量的制5P0P1P2P3P4R1、R2、R318、622。T0进程已分配资源资源最大需求R1R2R3R1R2R3P03235510P1403536P24054011P3204425P4314424A.P0,P2,P4,P1,P3 B.P1,P0,P3,P4,P2C.P2，P1，P0，P3，P4 D.P3,P4,P2,P1,P0readread系统调用会导致CPUreadA.仅、II B.仅、III C.仅、III D.I、II和III一个多道批处理系统中仅有P1和P2P2比P15ms到达，它的计算和P160ms，I/O80ms20msP2120ms，I/O40ms40ms若不考虑调度和切换时间，则完成两个作业需要的时间最少是A.240ms B.260ms C.340ms D.360msA.重排求序 B.在个上设多分区C.读滞写 D.优文理的布TCP/IPICMPA.PPP B.IP C.UDP D.TCPA.机特性 B.功能性 C.特性 D.气35．太的MAC提供是A.无接不靠服务 B.连接可的务C.连的靠服务 D.连接不靠服务NB传输数据数据传输速率为16kbp270ms128~512A.5 B.4 C.3 D.2IPIPIPIPIPIPA.仅、IV B.仅、、III C.仅、、IV D.I、、III、38．ARP议功是A.根据址询MAC地址 B.据MAC址询IPC.据名询IP地址 D.据IP址域名180.80.77.55255.255.252.0A.180.80.76.0 B.180.80.76.255 C.180.80.77.255 D.180.80.79.25512A.SMTP、SMTP、SMTP B.POP3SMTPPOP3C.POP3、SMTP、SMTP D.SMTP、SMTPPOP341～477041.（106ABCDE1035405060200561个升序表，并在最坏情况下比较的总次数达到最小。n（n≥2）42.（13分）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。oldastr1oldastr2gnieb^pgnieb^设str1和str2分别指向个单所单表头点，表点构为 ，设计个间可能效算出由s1和s2指两链共同缀起位（中符i所结的置要：C或C++JAVA43.（11）假设某计算机的CPU80MHz，CPI41.5次，主存与Cache16B，Cache99%32MIPS数是多少？平均每秒Cache缺失的次数是多少？在不考虑DMACPUCache0.0005%CPU4KBDMA32位，则磁盘接口平均每秒发出的DMACPU和DMA41/450ns，则主存能提供的最大带宽是多少？44.（12）16Cache和指令Cache44部分指令格式，其中RsRdmem表示存储单元地址，（x）xx的内容。题44表指令系统中部分指令格式名称指令的汇编格式指令功能加法指令ADD Rs，Rd(Rs)+(Rd)->Rd算术/逻辑左移SHL Rd2*(Rd)->Rd算术右移SHR Rd(Rd)/2->Rd取数指令LOAD Rd，mem(mem)->Rd存数指令STORE Rs，memRs->(mem)该计算机采用5段流水方式执行指令，各流水段分别是取指（IF）、译码/读寄存器（ID）、执行/计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB），流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。intx，存放在寄存器R1“SHLR1”44x=a+b，x、abint[x]、[a]和[b]44I1LOADR1，[a]I2LOADR2，[b]I3ADDR1，R2I4STORER2，[x]444I3IDI4IFx=x*2+a，xaunsignedint4445.(7分)某请求分页系统的页面置换策略如下：0532、1521、41。进程P<><1,1><3,2><0,4><0,6><0,13><2,14><0,4>46（8分41B240B512B0~7<>504分H192.168.0.8SIP211.68.71.80H与S使用TCP通信时，在H上捕获的其中5个IP分组如题47-a表所示。题47-a表编号IP分组的前40字节内容（十六进制）145000030 019b4000 80061de8 c0a80008 d34447500bd91388 846b41c5 00000000 70024380 5db00000243000030 00004000 31066e83 d3444750 c0a8000813880bd9 e0599fef 846b41c6 701216d0 37e10000345000028 019c4000 80061def c0a80008 d34447500bd91388 846b41c6 e0599ff0 50f04380 2b320000445000038 019d4000 80061dde c0a80008 d34447500bd91388 846b41c6 e0599ff0 50184380 e6550000545000028 684000 3106067a d3444750 c0a8000813880bd9 e0599ff0 846b41d6 501016d0 57d20000回答下列问题。47-aIPHTCP47-aIP分组，分析S47-aIPS4047-bIPH少个路由器？

题47-b表来自S的分组45000028 684000 4006ecad d3444750 ca7601061388a108 e0599ff0 846b41d6 501016d0 b7d60000注：IP分组头和TCP段头结构分别如题47-a图，题47-b图所示。题47-a图 组结构题47-b图TCP段头结构计算机专业基础综合试题参考答案一、单项选择题：每小题2分，共80分。1-5BAABC 6-10CCADA 11-15DDBDD 16-20ACCCD21-25DBCBB 26-30ADABC 31-35ABBCA 36-40BCADD二、综合应用题：41~47小题，共70分。5X-5，XNX这样，最坏情况下比较的总次数为：N=(10+35)×4+(40+50+60)×3+200−5=825（2）N（N≥2）个不等长升序表的合并策略：N理由：NN-1X-N+1，XNkk① L1，L2；② L1，L2L=|L1-L2|；③ L④ LinkListSearch_First_Common(LinkListL1,LinkListL2){//本算法实现线性时间内找到两个单链表的第一个公共结点intlen1=Length(L1);,len2=Length(L2);LinkListlongList,shortlist;//LinkListSearch_First_Common(LinkListL1,LinkListL2){//本算法实现线性时间内找到两个单链表的第一个公共结点intlen1=Length(L1);,len2=Length(L2);LinkListlongList,shortlist;//分别指向较长和较短的链表if(len1>len2){longList=L1->next;shortlist=L2->next;L=len1-len2;//表长之差}else{longList=L2->next;shortlist=L1->next;L=len2-len1;//表长之差}While(L--)longList=longList->next;while(longList!=NULL){if(longList==shortList)//同步寻找共同结点returnlongList;else{longList=longList->next;shortlist=shortlist->next;}}//whilereturnNULL;}算法的时间复杂度为O(len1+len2)，空间复杂度为O(1)。MIPS=CPU主频6/CPI=80M/4=201.5次,Cache99%Cache=0M1.1=30000（次；）在不使用DMA传送的情况下，所有主存的存取操作都需要经过CPU，所以主存带宽至少应为。由于页式虚拟存储方式的页表始终位于内存，则产生缺页异常的只能是指令的访存。每秒产生缺页中断20M/s×1.5×0.0005%=150次。因此平均每秒发出的DMA请求次数至少是150×4KB/4B=150K次。优先响应DMADMA通常连接高速44×4B/50ns=320MB/s。（1）x的机器码为[x]补=111111011111B，即指令执行前（R1）=FDFFH，右移1位后位1111111011111111B，即指令执行后（R1）=FEFFH。4+（5-1）=8I3IDI3I1I2I1I2I3读寄存器内容，所以I3的ID段被阻塞。I4的IF段被阻塞的原因：因为I4的前一条指令I3在ID段被阻塞，所以I4的IF段被阻塞。2*xx=x*2+aI1LOADR1，[x]I2