2021年计算机408统考真题.pdf

《2021年计算机408统考真题.pdf》由会员分享，可在线阅读，更多相关《2021年计算机408统考真题.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2021全国硕士研究生招生考试计算机学科专业基础试题一、单项选择题第 0140小题，每小题2 分，共 80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。0 1.已知头指针h 指向一个带头结点的非空单循环链表，结点结构为datanext其中next是指向直接后继结点的指针，P 是尾指针，q 是临时指针。现要删除该链表的第一个元素，正确的语句序列是()oA.h-next=h-next-next;q=h-next;free(q);B.q=h-next;h-next=h-next-next;free(q);C.q=h-next;h-next=q-next;if(p!=q)p=h;free(

2、q);D.q=h-next;h-next=q-next;if(p=q)p=h;free(q);0 2.已知初始为空的队列Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是1,2,3,4,5,则不能得到的出队序列是()0A.5,4,3,1,2 B.5,3,1,2,4 C.4,2,1,3,5 D.4,1,3,2,503.已知二维数组A 按行优先方式存储，每个元素占用1个存储单元。若元素A00的存储地址是100,A33的存储地址是2 2 0,则元素A55的存储地址是（）0A.295 B.300 C.301 D.30604.某森林厂对应的二叉树为T,若 T的先序

3、遍历序列是a,b,d,c,e,g,f,中序遍历序列是b,d,a,e,g,c,f,则尸中树的棵数是（）oA.1 B.2 C.3 D.405.若某二叉树有5 个叶结点，其权值分别为10,12,16,21,3 0,则其最小的带权路径长度（WPL）是（）。A.89 B.200 C.208 D.28906.给定平衡二叉树如下图所示，插入关键字23后，根中的关键字是（）。（20）163025402021年计算机408统考真题 第 1 页，共 9 页 A.16B.20C.23D.2507.给定如下有向图，该图的拓扑有序序列的个数是（）。A.1 B.2 C.3 D.408.使 用 Dijkstra算法求下图中

4、从顶点1 到其余各顶点的最短路径，将当前找到的从顶点1 到顶点2,3,4,5 的最短路径长度保存在数组dist中，求出第二条最短路径后，dist中的内容更新 为（）oA.26,3,14,6 B.25,3,14,6 C.21,3,14,6 D.15,3,14,609.在一棵高度为3 的3 阶B 树中，根为第1层，若第2 层中有4 个关键字，则该树的结点个数最多是（）。A.11 B.10 C.9 D.810.设数组 S=93,946,372,9,146,151,301,485,236,327,43,892）,采用最低位优先（LSD）基数排序将S 排列成升序序列。第 1趟分配、收集后，元素372之前

5、、之后紧邻的元素分别 是（）oA.43,892 B.236,301 C.301,892 D.485,30111.将关键字6,9,1,5,8,4,7 依次插入到初始为空的大根堆H 中，得到的H 是（）。A.9,8,7,6,5,4,1 B.9,8,7,5,6,1,4C.9,8,7,5,6,4,1 D.9,6,7,5,8,4,112.2017年公布的全球超级计算机TOP 500排名中，我国“神威太湖之光”超级计算机蝉联第一，其浮点运算速度为93.0146 PFLOPS,说明该计算机每秒钟内完成的浮点操作次数约为（）0A.9.3x1013 次 B.9.3X10”次 c.9.3 千万亿次 D.9.3 亿

6、亿次 002 2021年计算机408统考真题 第 2 页，共 9 页 13.已知带符号整数用补码表示，变量x,y,z的机器数分别为FFFDH,FFDFH,7FFCH,下列结论中，正确的是（）oA.若x j和z为无符号整数，贝IjzvxvyB.若x j和z为无符号整数，贝UxVyVzC.若x j和z为带符号整数，贝IjxvyvzD.若x j和z为带符号整数，贝仃v xz14.下列数值中，不能用IEEE 754浮点格式精确表示的是（）。A.1.2 B.1.25 C.2.0 D.2.515.某计算机的存储器总线中有2 4位地址线和3 2位数据线，按字编址，字长为3 2位。如果00 0000H3FFF

7、FFH为RAM区，那么需要512Kx8位的RAM芯片数为（）。A.8 B.16 C.32 D.6416.若计算机主存地址为32位，按字节编址，Cache数据区大小为32K B,主存块大小为32B,采用直接映射方式和回写（Write Back）策略，则Cache行的位数至少是（）。A.275 B.274 C.258 D.25717.下列寄存器中，汇编语言程序员可见的是（）oI.指令寄存器 I I.微指令寄存器 I II.基址寄存器A.仅 I、II B.仅 I、IV C.仅 n、IV18.下列关于数据通路的叙述中，错误的是（）0A.数据通路包含ALU等组合逻辑（操作）元件B.数据通路包含寄存器等时

8、序逻辑（状态）元件C.数据通路不包含用于异常事件检测及响应的电路D.数据通路中的数据流动路径由控制信号进行控制19.下列关于总线的叙述中，错误的是（）oA.总线是在两个或多个部件之间进行数据交换的传输介质B.同步总线由时钟信号定时，时钟频率不一定等于工作频率C.异步总线由握手信号定时，一次握手过程完成一位数据交换D.突 发（Burst）传送总线事务可以在总线上连续传送多个数据20.下列选项中，不属于I/O接口的是（）oA.磁盘驱动器 B.打印机适配器 C.网络控制器I V.标志/状态寄存器D.仅 n i、ivD.可编程中断控制器21.异常事件在当前指令执行过程中进行检测，中断请求则在当前指令执

9、行后进行检测。下列事件中，相应处理程序执行后，必须回到当前指令重新执行的是（）oA.系统调用 B.页缺失 C.DMA传送结束 D.打印机缺纸 003 2021年计算机408统考真题 第 3 页，共 9 页 22.下列是关于多重中断系统中CPU响应中断的叙述，其中错误的是（）oA.仅在用户态（执行用户程序）下，CPU才能检测和响应中断B.CPU只有在检测到中断请求信号后，才会进入中断响应周期C.进入中断响应周期时，CPU一定处于中断允许（开中断）状态D.若 CPU检测到中断请求信号，则一定存在未被屏蔽的中断源请求信号23.下列指令中，只能在内核态执行的是（）oA.trap指令 B.I/O指令 C

10、.数据传送指令 D.设置断点指令24.下列操作中，操作系统在创建新进程时，必须完成的是（）0I.申请空白的进程控制块I I.初始化进程控制块 m.设置进程状态为执行态A.仅 I B.仅 I、II C.仅 I、III D.仅 n、III25.下列内核的数据结构或程序中，分时系统实现时间片轮转调度需要使用的是（）oI.进程控制块 I I.时钟中断处理程序III.进程就绪队列 I V.进程阻塞队列A.仅 II、III B.仅 I、IV C.仅 I、II、III D.仅 I、II、IV26.某系统中磁盘的磁道数为200（0-199）,磁头当前在184号磁道上。用户进程提出的磁盘访问请求对应的磁道号依次

11、为184,187,176,182,199。若采用最短寻道时间优先调度算法（SSTF）完成磁盘访问，则磁头移动的距离（磁道数）是（）oA.37 B.38 C.41 D.4227.下列事件中，可能引起进程调度程序执行的是（）oI.中断处理结束I I.进程阻塞 i n.进程执行结束 i v.进程的时间片用完A.仅 I、III B.仅 II、IV C.仅皿、IV D.I、n、in 和 IV28.某请求分页存储系统的页大小为4K B,按字节编址。系统给进程P 分配2 个固定的页框,并采用改进型Clock置换算法，进程P 页表的部分内容如下表所示。页框号存在位1：存在，0:不存在访问位1：访问，0:未访问

12、修改位1：修改，0:未修改20 H00060 H11080 H111若 P 访问虚拟地址为02A01H的存储单元，则经地址变换后得到的物理地址是（）0A.00A01H B.20A01H C.60A01H D.80A01H29.在采用二级页表的分页系统中，CPU页表基址寄存器中的内容是（）。A.当前进程的一级页表的起始虚拟地址 004 2021年计算机408统考真题 第 4 页，共 9 页 B.当前进程的一级页表的起始物理地址C.当前进程的二级页表的起始虚拟地址D.当前进程的二级页表的起始物理地址3 0.若目录dir下有文件file l,则为删除该文件内核不必完成的工作是（）oA.删除filel

13、的快捷方式 B.释放filel的文件控制块C.释放filel占用的磁盘空间 D.删除目录dir中与filel对应的目录项3 1.若系统中有（2 2）个进程，每个进程均需要使用某类临界资源2 个，则系统不会发生死锁所需的该类资源总数至少是（)oA.2B.nC.+1D.2n3 2.下列选项中，通过系统调用完成的操作是（）oA.页置换B.进程调度C.创建新进程D.生成随机整数3 3.在 TCP/IP参考模型中，由传输层相邻的下一层实现的主要功能是（）。A.对话管理 B.路由选择C.端到端报文段传输 D.结点到结点流量控制若下图为一段差分曼彻斯特编码信号波形，则其编码的二进制位串是（）A.1011 1

14、001 B.1101 00013 5.现将一个IP 网络划分为3 个子网,不可能是另外两个子网之一的是（A.192.168.9.0/25C.192.168.9.192/26C.0010 1110 D.1011 0110若其中一个子网是192.168.9.128/26,则下列网络中,)OB.192.168.9.0/26D.192.168.9.192/2736.若路由器向MTU=800B的链路转发一个总长度为1580B的IP数据报（首部长度为20B）时，进行了分片，且每个分片尽可能大，则第2 个分片的总长度字段和MF标志位的值分别 是（）oA.796,0 B.796,1 C.800,0 D.800

15、,137.某网络中的所有路由器均采用距离向量路由算法计算路由。若路由器E 与邻居路由器A,B,C 和 D 之间的直接链路距离分别是8,10,12和 6,且 E 收到邻居路由器的距离向量如下表所示，则路由器E 更新后的到达目的网络NetlNet4的距离分别是（）。005 2021年计算机408统考真题 第 5 页，共 9 页 目的网络 A 的距离向量 B 的距离向量 C 的距离向量 D 的距离向量123202212353028241816363630824A.9,10,12,6 B.9,10,28,20 C.9,20,12,20 D.9,20,28,2038.若客户首先向服务器发送FIN段请求断

16、开TCP连接，则当客户收到服务器发送的FIN段并向服务器发送了 ACK段后，客户的TCP状态转换为（）。A.CLOSE_WAIT B.TIME_WAIT C.FIN_WAIT_1 D.FIN_WAIT_239.若大小为12B的应用层数据分别通过1 个 UDP数据报和1 个 TCP段传输，则该UDP数据报和TCP段实现的有效载荷（应用层数据）最大传输效率分别是（）。A.37.5%,16.7%B.37.5%,37.5%C.60.0%,16.7%D.60.0%,37.5%40.设主机甲通过TCP向主机乙发送数据，部分过程如下图所示。甲在而时刻发送一个序号seq=501、封装200B数据的段，在 4

17、时刻收到乙发送的序号seq=601、确认序号ack_seq=501、接收窗口 rcvwnd=500B的段，则甲在未收到新的确认段之前，可以继续向乙发送的数据序号范围是（）。二、综合应用题第 4147小题，共 70分。41.（15分）已知无向连通图G 由顶点集P 和边集E 组成，|0,当 G 中度为奇数的顶点个数为不大于2 的偶数时，G 存在包含所有边且长度为区|的路径（称 为 E L 路径）。设 图G采用邻接矩阵存储，类型定义如下：typedef struct /图的定义int numVertices,numEdges;/图中实际的顶点数和边数char VerticesListMAXV;/顶点

18、表。MAXV为已定义常量int EdgeMAXVMAXV；006 2021年计算机408统考真题 第 6 页，共 9 页/邻接矩阵MGraph;请设计算法in t IsExistEL(MGraph G),判断G 是否存在EL路径，若存在，则返回1,否则返回0。要求：1)给出算法的基本设计思想。2)根据设计思想，采用C 或 C+语言描述算法，关键之处给出注释。3)说明你所设计算法的时间复杂度和空间复杂度。42.(8 分)已知某排序算法如下：void cmpCountSort(int a,int b,int n)int i,j,*count;count=(int*)malloc(sizeof(in

19、t)*n);/C+语言：count=new int n;for(i=0;in;i+)counti=0;for(i=0;in-l;i+)for(j=i+l;j n;j+)if(aiaj)countj+;else counti+;for(i=0;in;i+)bcounti=a i;free(count);/C+语言：delete count;)请回答下列问题。1)若有 in t a =25,-10z25,10zl lz1 9 ,b 6 则调用 cmpCountSort(a,b,6)后数组b 中的内容是什么？2)若 a 中含有个元素，则算法执行过程中，元素之间的比较次数是多少？3)该算法是稳定的吗？

20、若是，则阐述理由；否则，修改为稳定排序算法。43.(15分)假定计算机M 字长为16位，按字节编址，连接CPU和主存的系统总线中地址线为 20位、数据线为8 位，采用16位定长指令字，指令格式及其说明如下：格式6位2位2位2位4位指令功能或指令类型说明R型000000rsFtrdoplRrd-Rrs opl RrtI型op2rsrtimm含ALU运算、条件转移和访存操作3类指令J型op3targetPC 的低 10 位 target其中，oplop3为操作码，rs,rt和rd为通用寄存器编号，Rr表示寄存器i的内容，imm为立即数，target为转移目标的形式地址。请回答下列问题。1)A LU

21、 的宽度是多少位？可寻址主存空间大小为多少字节？指令寄存器、主存地址寄存器(M AR)和主存数据寄存器(M DR)分别应有多少位？2)R 型格式最多可定义多少种操作？I 型和J 型格式总共最多可定义多少种操作？通用寄 007 2021年计算机408统考真题 第 7 页，共 9 页 存器最多有多少个？3）假定o p l为 0010和 0011时，分别表示带符号整数减法和带符号整数乘法指令，则指令01B2H的功能是什么（参考上述指令功能说明的格式进行描述）？若 1,2,3 号通用寄存器当前内容分别为B052H,0008H,0020H,则分别执行指令01B2H和 01B3H后，3号通用寄存器内容各是

22、什么？各自结果是否溢出？4）若采用I 型格式的访存指令中imm（偏移量）为带符号整数，则地址计算时应对imm进行零扩展还是符号扩展？5）无条件转移指令可以采用上述哪种指令格式？44.（8 分）假设计算机M 的主存地址为24位，按字节编址；采用分页存储管理方式，虚拟地址为30位，页大小为4 KB；TLB采用2 路组相联方式和LRU替换策略，共 8 组。请回答下列问题。1）虚拟地址中哪几位表示虚页号？哪几位表示页内地址？2）已知访问TLB时虚页号高位部分用作TLB标记，低位部分用作TLB组号，M 的虚拟地址中哪几位是TLB标记？哪几位是TLB组号？3）假设TLB初始时为空，访问的虚页号依次为10,

23、12,16,7,26,4,12和 2 0,在此过程中，哪一个虚页号对应的TLB表项被替换？说明理由。4）若将M 中的虚拟地址位数增加到32位，则 TLB表项的位数增加几位？45.（7 分）下表给出了整型信号量S 的w ait（）和 s ig n a l。操作的功能描述，以及采用开/关中断指令实现信号量操作互斥的两种方法。功能描述方法1方法2Semaphore S;Semaphore S;Semaphore S;wait(S)wait(S)wait(S)while(S=0);关中断；关中断；S=S-1;while(S=0);while(S to)s ffi-J-.451:fiJ T tt HTT

24、P iw:JHXITT Ll:t:$9!,-WlfiU-,/to flj t1 1A lsJ *it:i ffiiJ 1=j.11:UJ-.Web ijj loJ xITT iffi ft oiwJrJLlioJo:El InternetR Web!lll4*-www.abc,com 192.168.1.1/25 192.168.1 126/25 00-11-22-33-44-bb 192.168.1.2/25 00-11-22-33-44-cc 192.168.1.3/25 00-11-22-33-44-dd 1)M t0 flj t1 WHsJ,H1 T HTTP z.jiiE1TTriJJ1-mfflrzfiYJ,i5l?Mmffl!zffiJ:tli!fiiHifzf,mfflmfflxmMU*ffmttITT?2):B S ITT3t*:rg7J,Jl!lj t1 tiJ S 3t*ITTr;Jti-?3)M t0fiJ t1 WHsJ,H2 y4:x:fiJJL1-1=j.tl:t1J-.Web i,JjfoJ;jBJ$!J!?4:x:f1JITTfti-$9!?$!J!ITT ITT MAC-&Jl:ti-?009 2021年计算机408统考真题 第 9 页，共 9 页