《2024计算机考研真题及答案解析.docx》由会员分享，可在线阅读，更多相关《2024计算机考研真题及答案解析.docx（24页珍藏版）》请在课桌文档上搜索。
1、2024年全国硕士探讨生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题（科目代码408）2024年全国硕士探讨生入学统一考试一计算机专业掷出综合试题一、单项选择题：第1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1 .求整数n(nN0)阶乘的算法如下，其时间困难度是intfact(intn)(if(n=1)return1;returnn*fact(n-l);)A.O(log2n)B.O(n)C.(nl0g2n)D.O(n2)2 .已知操作符包括中、，一、“、/、丫和将中缀表达式a+b-a*(cd)e-f)+g转换为等价的后缀表达式ab
2、+acd+ef-*-g+时，用栈来存放短暂还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是A.5B.7C.8D.113 .若一棵二叉树的前序遍历序列为a,e,b,d,a后序遍历序列为b,c,d,e,a,则根结点的孩子结点A.只有eB.有e、bC.有e、CD.无法确定4 .若平衡二叉树的高度为6,且全部非叶结点的平衡因子均为1,则该平衡二叉树的结点总数为A.1()B.20C.32D.335 .对有n个结点、e条边且运用邻接表存储的有向图进行广度优先遍历，其算法时间困难度是A.O(n)B.O(e)C.O(n+e)D.O(n*e)6 .若用邻接矩阵存储有向图
3、，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一D.无法确定是否存在7 .对如下有向带权图，若采纳迪杰斯特拉(DijkStra)算法求源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b,其次条最短路径的目标顶点是c,后续得到的其余各最短路径的目标顶点依次是A.d,e,fB.e,d,fC. f,d,eD.f,e,d8 .下列关于最小生成树的说法中，正确的是I .最小生成树树的代价唯一II .权值最小的边确定会出现在全部的最小生成树中III .用普里姆（Prim）算法从不同顶点起先得到的最小生成树确定相同IV .普里
4、姆算法和克鲁斯卡尔（KnISkaI）算法得到的最小生成树总不相同A.仅IB.仅IIC.仅I、IIID.仅ILIV9.设有一棵3阶B树，如下图所示。删除关键字78得到一棵新B树，其最右叶结点所含的关键字是A.60B.60,62C.62,65D.6510 .在内部排序过程中，对尚未确定最终位置的全部元素进行一遍处理称为-趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是I.简洁选择排序IL希尔排序IH.快速排序IV堆排序V.二路归并排序A.仅I.IILIVB.仅LIIkVC.仅ILIIkIVD.仅IILIV、V11 .对一待排序序列分别进行折半插入排序和干脆插入排序，两者
5、之间可能的不同之处是A.排序的总趟数B.元素的移动次数C.运用协助空间的数量D.元素之间的比较次数12 .假定基准程序A在某计算机上的运行时间为100秒，其中90秒为CPU时间，其余为I/O时间。若CPU速度提高50%,I/O速度不变，则运行基准程序A所耗费的时间是A.55秒B.60秒C.65秒D.7（）秒13 .假定编译器规定int和short类型长度占32位和16位，执行下列C语言语句unsignedshortx=65530;unsignedinty=x;得到y的机器数为A.00007FFAB.0000FFFAC.FFFF7FFAD.FFFFFFFA14 .float类型(即IEEE754
6、单精度浮点数格式)能表示的最大正整数是A.2126-2103B.2127-2104C.227-2O3D.228-2O415 .某计算机存储器按字节编址，采纳小端方式存放数据。假定编译器规定int和short型长度分别为32位和16位,并且数据按边界对齐存储。某C语言程序段如下：structinta;charb;shortc;record;record.a=273;若record变量的首地址为OXC(X)8,则低至OXCoo8中内容及record.c的地址分别为A.0x00.OxCOODB.Ox(X).OxCOOEC.Oxlk0xC00DD.OxIKOxCOOE16 .下列关于闪存(FIaShM
7、emory)的叙述中，错误的是A.信息可读可写，并且读、写速度一样快B.存储元由MOS管组成，是一种半导体存储器C.掉电后信息不丢失，是一种非易失性存储器D.采纳随机访问方式，可替代计算机外部存储器17 .假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块为1个字。若Cache的内容初始为空，采纳2路组相联映射方式和LRU替换算法。当访问的主存地址依次为(),4,8,2,0,6,8,6,4,8时，命中Cache的次数是A.1B.2C.3D.418 .某计算机的限制器采纳微程序限制方式，微指令中的操作限制字段采纳字段干脆编码法，共有33个微吩咐，构成5个互斥类，分别包含7、3
8、、12、5和6个微吩咐，则操作限制字段至少有A.5位B.6位C.15位D.33位19 .某同步总线的时钟频率为100MHz,宽度为32位，地址/数据线应用，每传送一次地址或者数据占用一个时钟周期。若该总线支持突发(猝发)传输方式，则一次“主存写”总线事务传输128位数据所须要的时间至少是A. 20nsB. 40nsC. 50nsD. 80ns20 .下列关于USB总线特性的描述中，错误的是4A.可实现外设的即插即用和热拔插B.可通过级联方式连接多台外设C.是一种通信总线，连接不同外设D.同时可传输2位数据，数据传输率高21 .下列选项中，在I/O总线的数据线上传输的信息包括I.I/O接口中的吩
9、咐字II.I/O接口中的状态字III.中断类型号A.仅 L IIB.仅 L IIIC.仅 H、InD. k Ik HI22 .响应外部中断的过程中，中断隐指令完成的操作，除爱护断点外，还包括I.关中断IL保存通用寄存器的内容III.形成中断服务程序入口地址并送PCA.仅 k IIB.仅 L IIIC.仅 Ik IIID. k Ik III23 .下列选项中，不行能在用户态发生的事务是A.系统调用B.外部中断C.进程切换D.缺页24 .中断处理和子程序调用都须要压栈以爱护现场，中断处理确定会保存而子程序调用不须要保存其内容的是A.程序计数器B.程序状态字寄存器C.通用数据寄存满D.通用地址寄存器
10、25 .下列关于虚拟存储器的叙述中，正确的是A.虚拟存储只能基于连续安排技术B.虚拟存储只能基于非连续安排技术C.虚拟存储容量只受外存容量的限制D.虚拟存储容量只受内存容量的限制26 .操作系的I/O子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口，其合理的层次组织排列依次是A.用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序B.用户级I/O软件、设备无关软件、中断处理程序、设备驱动程序C.用户级I/O软件、设备驱动程序、设备无关软件、中断处理程序D.用户级I/O软件、中断处理程序、设备无关软件、设备驱动程序27.假设5个进程PO、Pl、P2、P3、P4共享三类资源Rl、R
11、2、R3,这些资源总数分别为18、6、22。TO时刻的资源安排状况如下表所示，此时存在的一个平安序列是5进程已安排资源资源最大需求RlR2R3RlR2R3PO3235510Pl403536P24054011P3204425P4314424A.PO,P2,P4,P1,P3B.Pl,P0,P3,P4,P2C.P2,Pl,PO,P3,P4D.P3,P4,P2,Pl,PO28.若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是I.若该文件的数据不在内存，则该进程进入睡眠等待状态IL恳求read系统调用会导致CPU从用户态切换到核心态III.read系统调用的
12、参数应包含文件的名称A.仅I、IIB.仅I、IIIC.仅ILIIID.I、II和III29 .一个多道批处理系统中仅有Pl和P2两个作业，P2比Pl晚5ms到达，它的计算和I/O操作依次如下:P1：计算60ms,I/O80ms,计算20msP2：计算120ms,I/O40ms,计算40ms若不考虑调度和切换时间，则完成两个作业须要的时间最少是A.240msB.260msC.340msD.360ms30 .若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中错误的是A.在进程结束时能进行处理机调度B.创建新进程后能进行处理机调度C.在进程处于临界区时不能进行处理机调度D.在系统
13、调用完成并返回用户态时能进行处理机调度31 .下列关于进程和线程的叙述中，正确的是A.不管系统是否支持线程，进程都是资源安排的基本单位B.线程是资源安排的基本单位，进程是调度的基本单位C.系统级线程和用户级线程的切换都须要内核的支持D.同一进程中的各个线程拥有各自不同的地址空间32 .下列选项中，不能改善磁盘设备I/O性能的是2024年全国硕士探讨生入学统一考试一计算机专业掷出综合试题A.重排I/O恳求次序B.在一个磁盘上设置多个分区C.预读和滞后写D.优化文件物理的分布33 .在TCP/IP体系结构中，干脆为ICMP供应服务协议的是A.PPPB.IPC.UDPD.TCP34 .在物理层接口特
14、性中，用于描述完成每种功能的事务发生依次的是A.机械特性B.功能特性35.以太网的MAC协议供应的是A.无连接的不行靠的服务C.有连接的牢靠的服务C.过程特性D.电气特性B.无连接的牢靠的服务D.有连接的不行靠的服务36 .两台主机之间的数据链路层采纳后退N帧协议（GBN）传输数据数据传输速率为16kbps,单向传播时延为270ms,数据帧长度范围是128512字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序列的比特数至少为A.5B.4C.3D.2.下列关于IP路由器功能的描述中，正确的是1.运行路由协议，设备路由表IL监测到拥塞时，合理丢弃IP分组III .对收到的I
15、P分组头进行差错校验，确保传输的IP分组不丢失IV .依据收到的IP分组的目的IP地址，将其转发到合适的输出线路上A.仅IILIVB.RI、ILIIIC.仅I、ILIVD.I、ILIIkIV38. ARP协议的功能是A.依据IP地址查询MAC地址C依据域名查询IP地址B.依据MAC地址查询IP地址D.依据IP地址查询域名39 .某主机的IP地址为，子网掩码为。若该主机向其所在子网发送广播分组，则目的地址可以是40 .若用户I与用户2之间发送和接收电子邮件的过程如下图所示，则图中、阶段分别运用的应用层协议可以是用户1的用户2的B. POP3. SMTP、POP3D. SMTP、SMTP、POP3
16、A.SMTP、SMTP、SMTPCPOP3、SMTP、SMTP二、综合应用题：第4147题，共70分。请将答案写在答题纸指定位置上。41. (1()分)设有6个有序表A、B、C、D、E、F,分别含有1()、35、40、5()、60和2(X)个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏状况下比较的总次数达到最小。请问答下列问题。(1)给出完整的合并过程，并求出最坏状况下比较的总次数。(2)依据你的合并过程，描述n(n2)个不等长升序表的合并策略，并说明理由。42. （13分）假定采纳带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同
17、的后缀存储空间,例如，“loading”和“being”的存储映像如下图所示。StrIta-Rd算术/逻辑左移SHLRd2*(Rd)-Rd算术右移SHRRd(Rd)2-Rd取数指令LOADRd,mem(mem)-Rd存数指令STORERsmemRs-(mem)该计算机采纳5段流水方式执行指令，各流水段分别是取指（IF）、译码/读寄存器（ID）、执行/计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB）,流水线采纳”按序放射，按序完成”方式，没有采纳转发技术处理数据相关，并且同一寄存器的读和写操作不能在同个时钟周期内进行。请回答下列问题。（1）若int型变量X的值为-513,存放在寄存
18、器Rl中，则执行“SHLR1”后，Rl中的内容是多少？（用十六进制表示）（2）若在某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何堵塞，则执行这4条指令所需的时钟周期数为多少？（3）若高级语言程序中某赋值语句为x=a+b,x、a和b均为int型变量，它们的存储单元地址分别表示为x、a和b。该语句对应的指令序列及其在指令流中的执行过程如题44图所示。IlLOADRl,(al12LOADR2,lb13ADDRl,R214STORER2,时间田元123456789101112131411IFIDEXMWB12IFIDEXMWB13IFIDEXMW814IFIDEXMWB题44图指
19、令序列及其执行过程示意图则这4条指令执行过程中B的ID段和14的IF段被堵塞的缘由各是什么？（4）若高级语言程序中某赋值语句为x=x*2+a,X和a均为unsignedint类型变量，它们的存储单元地址分别表示为X、a,则执行这条语句至少须要多少个时钟周期？要求仿照题44图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。45. （7分）某恳求分页系统的页面置换策略如下：从0时刻起先扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽视不计）且在本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次安排之前不清空。当放发生缺页时，假如该页曾被运用过且还在空闲页链表中，则
20、重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。忽视其它进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页的页框号依次为32、15、21、41。进程P依次访问的虚拟页号，访问时刻为,、0请回答下列问题。（1）当虚拟页为时，对应的页框号是什么？（2）当虚拟页为VlJ时，对应的页框号是什么？说明理由。（3）当虚拟页为时，对应的页框号是什么？说明理由。（4）这种方法是否适合于时间局部性好的程序？说明理由。46. （8分）某文件系统空间的最大容量为4TB（ITB=24）,以磁盘块为基本安排单位。磁盘块大小为1KB。文件控制块（FCB）包含一个512B的索引表区。请回答下列问题。（
21、1）假设索引表区仅采纳干脆索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？（2）假设索引表区采纳如下结构：第07字节采纳起始块号，块数格式表示文件创建时预安排的连续存储空间。其中起始块号占6B,块数占2B,剩余504字节采纳干脆索引结构，一个索引项占6B,则可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。47. （9分）主机H通过快速以太网连接Internet,IP地址为，服务器S的IP地址为。H与S运用TCP通信时，在H上捕获的其中5个IP分组如题47-a表所示
22、。题47-a表编号IP分组的前40字节内容（十六进制）145000030019b40008006Ide8ca80008d3444750Oblen2)longList=Ll-next;shortlist=L2-next;1.=Ienl-Ien2;表长之差elselongList=L2-next;shortlist=Ll-next;1.=Ien2-Ienl;表长之差)While(L)longList=longList-next;While(IongListS=NULL)if(IongList=ShortList)/同步找寻共同结点returnIongList;elselongList=longLi
23、st-next;Shortlist=ShortIist-next;/whilereturnNULL;(3)算法的时间困难度为O(Ienl+len2),空间困难度为0(1)。43 .【解析】(1)MIPS=CPU主频Xl(WCPl=80M4=20;平均每条指令访存1.5次,Cache的命中率为99%,故每秒Cache缺失的次数=20MXI.5xl%=3OOOOO(次)；(2)在不运用DMA传送的状况下，全部主存的存取操作都须要经过CPU,所以主存带宽至少应为20Ms1.54B=120MBso由于页式虚拟存储方式的页表始终位于内存，则产生缺页异样的只能是指令的访存。每秒产生缺页中断20Ms1.50
24、.0005%=150次。因此平均每秒发出的DMA恳求次数至少是1504KB4B=150K次。(3)优先响应DMA恳求。DMA通常连接高速I/O设备，若不刚好处理可能丢失数据。(4)当4体低位交叉存储器稳定运行时，能供应的最大带宽为44B50ns=320MBSo44 .【解析】(1) X的机器码为冈仆=miIlOlIlllB,即指令执行前(RI)=FDFFH,右移1位后位IlllIllOIlllIlllB,即指令执行后(Rl)=FEFFHo(2)至少须要4+(5-1)=8个时钟周期数。(3) h的ID段被堵塞的缘由：因为h与Ii和I2都存在数据相关，需等到Ii和I2将结果写回寄存器后，I3才能2
25、024年全国硕士探讨生入学统一考试一计算机专业掷出综合试题读寄存器内容，所以3的ID段被堵塞。U的IF段被堵塞的缘由：因为4的前条指令h在ID段被堵塞，所以U的IF段被堵塞。(4)因2*x操作有左移和加法两种实现方法，故x=x*2+a对应的指令序列为IlLOADRl,x12LOADR2,a13SHLRl或者ADDRl,Rl14ADDRl,R215STORER2,x时间单元指令1234567891011121314151617注5赤指令你就水维妒执他过用妫口冬所示。12IFIDEXMWB13IFIDEXMWB14IFIDEXMWB15IFIDEXMWB故执行x=x*2+a语句最少须要17个时钟周
26、期。45【解析】(1)页框号为21。因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页框(21),其对应的页框号为21。(2)页框号为32。理由：因111()故发生第三轮扫描，页号为1的页框在其次轮已处于空闲页框链表中，此刻该页又被重新访问，因此应被重新放回驻留集中，其页框号为32。(3)页框号为41。理由：因为第2页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41,页框号为41o(4)合适。理由：假如程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。46【解析】(1)文件系统中所能容纳的磁盘块总数为4TB1KB=232。要完全
27、表示全部磁盘块，索引项中的块号最少要占328=4B0而索引表区仅采纳干脆索引结构，故512B的索引表区能容纳512B4B=128个索引项。每个索引项对应一个磁盘块，所以该系统可支持的单个文件最大长度是128xlKB=128KB0(2)这里的考查的安排方式不同于我们所熟识的三种经典安排方式，但是题目中给出了具体的说明。所求的单个文件最大长度一共包含两部分：预安排的连续空间和干脆索引区。连续区块数占2B,共可以表示2m个磁盘块，即226Bo干脆索引区共504B6B=84个索引项。所以该系统可支持的单个文件最大长度是2%B+84KB.为了使单个文件的长度达到最大，应使连续区的块数字段表示的空间大小尽
28、可能接近系统最大容量4TBo分别设起始块号和块数分别占4B,这样起始块号可以寻址的范围是232个磁盘块，共4TB,即整个系统空间。同样的，块数字段可以表示最多232个磁盘块，共4TBo47.【解析】(1)由于题47-a表中1、3、4号分组的原IP地址均为(COa80008H),所以1,3,4号分组是由H发送的。题47-a表中1号分组封装的TCP段的FLAG为02H(即SYN=1,ACK=0),seq=846b41c5H,2号分组封装的TCP段的FLAG为12H(即SYN=LACK=D,seq=e0599fefH,ack=846b41c6H,3号分组封装的TCP段的FLAG为IOH(即ACK=D
29、,seq=846b41c6H,ack=e0599ffDH,所以1、2、3号分组完成了TCP连接建立过程。17由于快速以太网数据帧有效载荷的最小长度为46字节，表中3、5号分组的总长度为40（28H）字节，小于46字节，其余分组总长度均大于46字节。所以3、5号分组通过快速以太网传输时进行了短充。（2）由3号分组封装的TCP段可知，发送应用层数据初始序号为seq=846b41c6H,由5号分组封装的TCP段可知，ack为seq=846b41d6H,所以5号分组已经收到的应用层数据的字节数为846b41d6H-846b41c6H=10H=16o（3）由于S发出的IP分组的标识=6811H,所以该分组所对应的是题47-a表中的5号分组。S发出的IP分组的TTL=40H=64,5号分组的TTL=31H=49,64-49=15,所以，可以推断该IP分组到达H时经过了15个路由器。
