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

2021年全国硕士研究生招生考试 55计算帕学科专业基础试题 皂一、单项选择题：1-40小题，每小题2分，共80分。下列每题给 fb的四个选项中｀只有一个选项是最符合题目要求的。_l.已知头指针h指向一个带头结点的非空单循环链表，结点结构为_二，其中nefit是指向直桵后继结点的指针，p是尾指针，q是临时指针。现要删除该链表的第一个元素，正确的语句序列是h->nefil=h->next->nexl; q=h->next; free(q);q=h->next; h->next=h->next->next; fiee(q);q=t; t=->nex; i(p!=qp=h; fe);q)p=h;q=h->next; q)p=h;Q‘'u2?lSgsÐ'slSgQ‘'u2?lSgsÐ'slSgsl',2s4.AC．．D已知二维数组A按行优先方式存储，每个元素占川l个存储单．．D若元素[OJO]10,A[3][3]的存储地址是220.则元素A[5][5]的存储地川奾IL300A.IL300.301 ，某森林F对应的二义树为'/''若Ï的先忭迪历序列是a.h.d、c.e,，f,中序地历序列是I,,d,IIA.1,t!,g,C:,f,中序地历序列是I,,d,IIA.1B.一·.3 D.4二叉树有个叶，其权（八分别为1,162,30,则其最第1／18页小的带权路径长度(�'PL)小的带权路径长度(�'PL)C.208T入关键字2C.208T入关键字23后，根中的关键字是给定平衡二叉树如下图所示，抇16C.23

B.20-}一56-}一562全生考和专础ACB.2AC第2／18页A.26,3,14,6 n.25,3,I4,6 57C.21,3,14,6 D.15,3,14,69.在一棵高度为3的3阶B树中，根为第1层，若笫2层中有4个关键字，则该树的结点个数最多是A.11C.A.11C.9D.810.设数组S[]=j93,946,3729,J46,151301,485,236327,43,892!,采用最低位优先(LSD)基数排序将S排列成升序序列。第l趟分配、收集后，元素372之前、之后紧邻的元素分别是A.43,892 B.236,301C.301,892 D.485301将关键字6,9,1,5,8,4,7依次插入到初始为空的大根堆H中，得到的H是A.9,8,7,6,5,4,19,8,7,5,6,4,1

B.9,8,7,5,6,1,4D.9,6,7,5,8,4,1B.9.3xJ0B.9.3xJ015次A9.3x1013次I3.已知带符号整数川补码表示，变队．｀、y、z的机器数分别为FFFDFFFDfl、FFDFH、7FFCH,下列结论中，正确的是若x、y和z为无符号整数，则z<x<y若x、y和z<'}孕z若x、y和z为带符号整数，则x<y<z若x、y和z为带符号整数，则y<x<z14下列数伯中，不能川IEEE754浮点格式粘确表示的是0.1.25第3／18页15.某计算机的存储器总线中有24位地址15.某计算机的存储器总线中有24位地址线和32位数据线，按字编若000000HFFFFH为RAM区，则需要址，字长为32位。512fix8位的RAM芯片数为A.8È.32若计货机主存地址为32位，按字节编址，Cache数据区大小为32KB.32B,采川直桵映射方式和回写(W百teBack)策略，则Cache行的位数至少是A.275

274D.25758-58-02》士生考试计科算专业大纲I.指令寄存器 II.微指令寄存器m.基址寄存器 N.标志／状态寄存器下列关于数据通路的叙述中，错误的是数据通路包含ALU等组合逻辑（操作）元件数据通路包含寄存器等时序逻辑（状态）元件数据通路不包含用于异楷串件检测及响应的电路数机通路中的数据流动路径山，控制伈号进行控制下列关于总线的叙述中，估误的是总线是在两个或多个部件之间进行数趴交换的传愉介质同步总线山时钟估勺定时，时钟肋冲不一定等于工作频率异步总线由腥手伈号定时，一次lht手过和完成一位数据交换突发(Burst)传送总线串务可以在总线上迕纹传送多个数剿下列选项中，不屈于1/0拔口的是0.打印机适配器第4／18页D.可编程中断控制器一c.D.可编程中断控制器一异常事件在当前指令执行过程中进行检测，中断诮求则在当前指入执行后进行检测。下列事件中，相应处理程序执行后，必须匝到当前指令重新执行的是D.打印机缺纸下列是关于多重中断系统中CPU响应中断的叙述，其中错误D.打印机缺纸的是的是仅在用户态（执行用户程序）下，CPU才能检测和响应中断CP只有在检测到中断请求信号后，才会进入中断响应周期c.进入中断响应周期时，CPU定处于中断允许（开中断）状态D.若P测到中断请求信号，则一定存在未被屏蔽的中断源请求信号请求信号下列指令中，只能在内核态执行的是C.数据传送指令 D.设置断点指令下列操作中，操作系统在创建新进程时，必须完成的是I.II.皿设置进程状态为执行态{又I.皿 D.、mIV.进程阻塞队列下列内核的数据结构或程序中，分时系统实现时间片轮转调度需要使用的是IV.进程阻塞队列II.进程控制块m.进程就绪队列进程控制块C.仅I、Il、m

n.时钟中断处理程序..仅I、Il、W某系统中磁盘的磁道数为2000199)磁头当前在184号磁道第5／18页上。上。川户进程捉出的磁盘访问诮求对应的磁迫号依次为184、187、17Ľ、182、1FF。若采川服短寻迫时间优先册度符法(SfiTF)宅成磁盘访问，则磁头移动的卧商（磁迫数）是ì.41A.37 B.ì.41D.D.42下列咑件中，可能引起进程调度和序执行的是I.中断处理结束m进程执行结束I.中断处理结束

N.进程的时间片用兀II.进程阳塞D. I、IIm和WII.进程阳塞某诘求分页存储系统的页大小为4KB,按字节编址。系统给进程P分配2个固定的页框，并采用改进型Clock置换算法，进程P页表的部分内容如下表所示。页号 页框号

存在位 访问位 修改位60志202全国生专基I:存在，0:60志202全国生专基o 。 ... ．．．o 。 。20H。234 l80fl I I L．．． ... ...若P访问虚拟地址为02AOIH的存储t)t元，则经地址变换后得到的物理地址见B.B.IIC.J0AOIH D.80AO111在采川二级页表的分页系统中，CPU页表拈址寄存监中的内容是当前进程的一级页表的起始f.l�拟地址第6／18页c.当前进程的c.当前进程的二级页表的起始虚拟地址D.当前进程的二级页表的起始物理地址录dir下有文件file录dir下有文件file1,则为删除该文件内核不必完成的工作是删除file1的快捷方寸释放file1的文件控制块释放file1占用的磁盘空间删除目录dir中与fi1e1对应的目录项A.2若系统中有11(11�2个进程，每个进程均需要使用某类临界资源2个，则系统不会发生死锁所需的该类资源总数至少是A.2nn+I

2n下列选项中，通过系统调用完成的操作是页置换D.生成随机整数在TCP/IP参考模型中，由传输层相邻的下一层实现的主要功能是能是C.端到端报文段传输 D.结点到结点流狱控制若下图为一段差分曼彻斯特编码估号波形，则其编码的二进制位串是B.110I000l第7／18页C.00IO11I0 D.10110110现将个JP网络划分为3个子网，若其中个子网是28/26,则下列网络中，不可能是另外两个子网之的是A./25

B./2662＿试业基究生计算士研若路由器向MTU=800B的链路转发一个总长度为162＿试业基究生计算士研A.796,0 B.796,I.8000 D.800,1某网络中的所有路由器均采用距离向批路由算法计算路由。若路由器E与邻居路由器A、B、C和D之间的直接链路距离分别是8、IO、12和6,且E收到邻居路由器的距离向量如下表所示，则路由器E更新后的到达目的网络NellNet4的距离分别是目的网络A的距离向盘B的距离向耳C的距离向扯D的距离向扭NetLl22Net212353028Net3241630824A.9,IO,12,6B.9,IO,28,20C.9,20,12,20D.9,20,28,20Net4若客户首先向服务器发送NTP迕接，则当客户收到服务器发送的FIN段并向服务器发送了ACK段后，客户的Net4CLOSE_WAIT J.TME_/AlTD.FIN_WAIT_2若大小为12B的应用层数据分别通过1个UDP数据报和1个第8／18页TCP段传输，则该UDP数据报和TCP段实现的有效载荷（应用 63B.B.37.5%,37.5%D.P0.0%37.5%云数据）最大传输效率分别是A.37.5%1Ľ.7%C.Ľ0.,17%假设主机甲通过TCP向主机乙发送数据，部分过和如下图所7八o甲在I。时刻发送了一个序号se云数据）最大传输效率分别是A.37.5%1Ľ.7%C.Ľ0.,17%≲carcvwnd500≲caI。三B数据seq6ake=50rvw今B11A.501-1000C.701-1000

B.601-1100D.801-1100�二、综合应用题：�(15分）已知无向迕汕I冬IC山顶从u \I和边从E组成、1£1>0、兰G中度为奇数的顶点个数为不大于2的aij数时、C存在包含所H边且长度为I1·径称为:悄径）（、设图（，、采川仙，类朋定义从III、:typfidefstiufiInumŽtc尤s,111111I·s;／／图中实际的顶点数和边娄rVeitict!sifit[V];／／顶点表。 MAXV为已定义常正第9／18页intEdge[MAXY][MAXY];IMGraIMGraph;计法：ntLrh),判断G是否存在EL路径，若存在，则返回I0。要求：(I)给出算法的基本设计思想。根据设计思想，采用C或C++语言描述符法，关键之处给出注释。说明你所设计算法的时间复杂度和空间复杂度。(8分）已知某排序算法如下：*count;íoidcmpCountSort(inta[],intb[],intn)int1*count;count=(int*)allocszeo(in)*n;newint[n];for(i=O;i<n;i++)for(i=i<nl;i+)frj=i+l;j<n+)elseb[coun=a[;[elseb[coun=a[;count;for(i=O;i<n;i++count;｝请回答下列问题。(I)若有inta[]I25IO,25IO,cmpCountfiort(ab,P)后数组h中的内容是什么？

则调用6464202该算法是稳定的吗？若是，则阐述理山；否则，修改为稳定排第10／18页(15分）假定计算机M16位，按字节编址，连接CPU和主存的系统总线中地址线为20位、数据线为8位，采用16位定长指令字，指令格式及其说明如下：格式 6位 2位2位2位 4位 指令功能或指令类型说明R刑I1JIJ

000000 rs rt rdoplop2 rs rt 1mmopltfirget

[]冬-[]opI[t]含ALU运算、条件转移和访存操作3类指令PC的低10target其中，oplop3为操作码，rs、rt和rd为通用寄存器编号，Rr]表示寄存器r的内容，imm为立即数，target为转移目标的形式地址。请回答下列问题。(I)ALU的宽度是多少位？可寻址主存空间大小为多少字节？(MAR)和主存数据寄存器(MDR分别应有多少位？R型格式最多可定义多少种操作?I型和J型格式总共最多可定义多少种操作？通用寄存器最多有多少个？假op]00100011时，分别表示带符号整数减法和带符号整数乘法指令，则指令0182H的功能是什么（参考上述指令功能说明的格式进行描述）？若1、2、3中前内容分为130521-1、1、0020H.则分别执行指令0182H和0183H后，3号通川寄存器内容各是什么？各自结果是否溢出？(4)若采用1型格式的访存指令中imm(偏移员）为带符号整数，则地址计算时应对imm进行零扩展还是符号扩展？(5)无条件转移指令可以采用上述哪种指令格式？(8分）假设计算机M24位，按字节编址；采用分页第11／18页304KB;Tfiil2路组相联方式和LRU替换策略，共8组。祔回答下列问题。(1)徘拟地址中哪几位表示虚页号？哪几位表示页内地址？已知访问TLB时加页号高位部分用作TLil标记，低位部分用作TLB组号，M的虚拟地址中哪几位是TLB标记？哪几组号？TLB初始时为空，访问的虚页号依次为IO、12、167、26、4、1220,在此过程中，哪一个虚页号对应的TLB表项被替换？说明理由。M32TLB表项的位数增加几位？增加几位？(7分）下表给出了整型信号量S的wait()和signal()操作的功能描述，以及采用开／关中断指令实现信号扭操作互斥的两种方法。功能描述方法l方法23emapkore3;3emapkore3;3emapkore3;(Ifiait(3lI3c=l;关中断；关中断；，｝fikile(3c=0l;开中断；关中断；II开中断；开中断；开中断；I6666202究大纲3=33=3+$·I S=3+I，开中断；开中断；I 第12／18页

I=3cI;=3cI;fi讷回答下列问题。 67皂一(I)为什么在wait()和signal()操作中对信号批S的访问必须互皂一(2)分别说明方法l和方法2是否正确。 若不正确，诮说明理山。(3)用户程序能否使用开／关中断指令实现临界区互斥？为 (8分）某计货机用硬盘作为启动盘，硬盘第一个扇区存放主引导记录，其中包含磁盘引导程序和分区表。磁盘引导程序用于选择要引导哪个分区的操作系统，分区表记录硬盘上各分区的位置等描述信息。硬盘被划分成若干个分区，每个分区的第一个扇区存放分区引导程序，用于引导该分区中的操作系统。系统采用多阶段引导方式，除了执行磁盘引导程序和分区引导程序外，还需要执行ROM中的引导程序。请回答下列问题。 系统启动过程中操作系统的初始化程序、分区引导程序、ROM中的引导程序、磁盘引导程序的执行顺序是什么？把硬盘制作为启动盘时，需要完成操作系统的安装、磁盘的物理格式化、逻辑格式化、对磁盘进行分区，执行这4个操作的正确顺序是什么？磁盘扇区的划分和文件系统根目录的建立分别是在第(2)问的哪个操作中完成的？ (9分）某网络拓扑如题47图所示，以太网交换机S通过路由器R与Internet互联。路山湍部分倓口、本地域名服务器、Hl、H2的IP地址和MAC地址如图中所示。在I。时刻HI的ARť表和SH1在此刻利川浏览器通过域名请求访问fieb服务器，在lI时刻(tI>t。)S第一次收到了封装HITP诮求报文的以太网帧，假设从t。到tI期间网络未发生任何与此次Web访问无关的网络通信。第13／18页R子InternetR子m器ole5•5192.168.1.l/25m器ole5•5本地域名服务器26/2500-11-22-33-44-bb.

192.168.I.3/2500-11-22-33-44-dd/2500-11-22-33-44-cc题47图请回答下列问题。ttI期间，Hl除了HTTP之外还运行了哪个应用层协议？从应用层到数据链路层，该应用层协议报文是通过哪些协议进行逐层封装的？换若S<MAC，则II时刻表的内容是什么？换丿火t。到tI期间，H2

·少会仪收到儿个与此次\Vfib访问相关68＿68＿纲的帧？桵收到的见什么帧？帧的目的MAC地址是什么？的帧？桵收到的见什么帧？帧的目的MAC地址是什么？第14／18页2021年全国硕士研究生招生考试S92021年全国硕士研究生招生考试5.B计算机学科专业基础试题参考答案 皂5.B1.1.D6.D2.2.D7.A

8.9.A19.C3.B8.9.A19.CCC11.B12.D13.D14.A15.C16.A17.D18.C2fl.A21.B22.A23.B24.B25.C26.C27.D28.C29.B30.A1.C32.C33.B34.A36.B37.D38.B39.D40.C二、综合应用题二、综合应用题35.B算法的基本设计思想35.B对于采用邻接矩阵存储的无向图，邻接矩阵每一行（列）中非零元素的个数为本行（列）可以依次计算连通图G中各顶点的度，并记录度为奇数的顶点个数，若个1'否则返回0。(2)算法实现r"tlsEzrTtEL(MCrn;flC)／／采用邻拔矩I作存储，判断图是否存在WL路径r"tn׿r××,r,j,c+""t=D;hur(r=0;rc”."»mvưilrהưư;r++)hûsj=;jc."»mi;j+.II依次计货各个顶点的度.II依次计货各个顶点的度第15／18页j];j];ff!=0)／／对度为奇数的顶点计数count++;count++;if(count==0II count==2)／／不存在EL路／／不存在EL路径，返回O

return1;returnO;

／／存在EL路径，返回l(3)算法的时间复杂度和空间复杂度本参考答案给出的算法的时间复杂度是O(n2),空间复杂度C1)b[J=l-1o,1o,11,19,25,25I元素之间的比较次数是n(n-l)/2。不是。需要将程序中的if语句修改如下：[)cunt[j]+;elseou[(I)ALU的宽度为16位。可寻址主存空间大小为2:,0字节（或1Mil。存拙、M16位、2位和8位。IOIJ1型和JIOIJ0IB1=0000000IR[R[l]-H[2]。002[=B052l1-0008H=B04AH结果不溢出；执行指令0113311后，R[3]=R[I]x第16／18页R[2]=R[2]=B052H结果溢出。x应对imm进行符号扩展。(5)无条件转移指令可以采用J30-12=18位表示虚页号。12位表示页内4KB=30-12=18位表示虚页号。12位表示页内地址。TLB28=23组，所以虚拟地址（或虚页号）18-3=15TLB