2022年计算机408统考真题.docx

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

1、绝密启用前全国硕士研究生入学统一考试计算机科学与技术学科联考2022年全国硕士研究生招生考试计算机学科专业基础试题（科目代码：408)考生注意事项1. 答题前，考生在试题册指定位置上填写考生编号和考生姓名；在答题卡指定位置上填写报考单位、考生姓名和考生编号，并涂写考生编号信息点。2. 考生须把试题册上的“试卷条形码黏贴条取下，黏贴在答题卡的“试卷条形码黏贴位置”框中，不按规定黏贴条形码而影响评卷结果的，责任由考生自负。3. 选择题的答案必须涂写在答题卡和相应题号的选项上，非选择题的答案必须书写在答题卡指定位置的边框区城内，超出答题区域书写的答案无效；在草稿纸、试题册上答题无效。4. 填（书）写

2、部分必须使用黑色字迹签字笔书写，字迹工整、笔迹清楚；涂写部分必须使用2B铅笔涂写。5. 考试结束，将答题卡和试题册按规定交回。（以下信息考生必须认真填写）考生编号考生姓名Ol下列程序段的时间复杂度是(,，int sum=)。0;for(in七i = 1; ifor(int j = ;j2)个字符的有限集S,用二叉树表示S的哈夫曼编码集和定长编码集，分别得到二叉树Tl和T2。下列叙述中，正确的是()。A. Tl与T2的结点数相同B. Tl的高度大于T2的高度 C.出现频次不同的字符在Tl中处千不同的层D出现频次不同的字符在T2中处千相同的层06. 对千无向图G=(V,E),下列选项中，正确的是（

3、 ）。A. 当IV|国时，G一定是连通的B. 当VE+l时，G一定是不连通的07. 下图是一个有10个活动的AOE网，时间余量最大的活动是()。A. CC. hB. gD. j08. 在下图所示的5阶B树T中，删除关键字260之后需要进行必要的调整，得到新的B树Tl。下列选项中，不可能是Tl根结点中关键字序列的是（ ）。A. 60, 90,280B. 60,90,350C. 60, 85, 110, 350D. 60, 90, 110, 35009. 下列因素中，影响散列（哈希）方法平均查找长度的是（ ）。I.装填因子II.散列函数III.冲突解决策略A.仅I、IIB.仅I、IIIC.仅II、

4、IIID. I、II、III第2页（共8页）10. 使用二路归并排序对含n个元素的数组M进行排序时，二路归并操作的功能是（ ）。A. 将两个有序表合并为一个新的有序表B. 将M划分为两部分，两部分的元素个数大致相等C. 将M划分为n个部分，每个部分中仅含有一个元素D. 将M划分为两部分，一部分元素的值均小于另一部分元素的值11. 对数据进行排序时，若采用直接插入排序而不采用快速排序，则可能的原因是()。I.大部分元素已有序II.待排序元素数量很少III.要求空间复杂度为0(l)w要求排序算法是稳定的A.仅I、IIB.仅III、IVC.仅1、II、IV.D. I、II、III、IV12. 某计算

5、机主频为1 GHz,程序P运行过程中，共执行了10000条指令，其中，80的指令执行平均需1个时钟周期，20的指令执行平均需10个时钟周期。程序P的平均CPI和CPU执行时间分别是（ ）。第3页（共8页）A. 2.8, 28 sB. 28, 28 sC. 2.8, 28 ms13. 32位补码所能表示的整数范围是（ ）。A. -232231_1B. -2312311c. -232l32114. -0.4375的IEEE 754单精度浮点数表示为（ ）。D. 28, 28 msD.2312321A. BEEO OOOOHB. BF60 OOOOHC. BF70 OOOOHD. COEO OOOO

6、H15. 某计算机主存地址为24位，采用分页虚拟存储管理方式，虚拟地址空间大小为4GB,页大小为。4KB,按字节编址。某进程的页表部分内容如下表所示。虚页号82实页号（页框号）024H存在位129180H130018H当CPU访问虚拟地址0008 2840H时，虚实地址转换的结果是（ ）。A. 得到主存地址024840HB.得到主存地址18 0840HC.得到主存地址01 8840HD.检测到缺页异常16. 若计算机主存地址为32位，按字节编址，某Cache的数据区容量为32KB,主存块大小为64 B,采用8路组相联映射方式，该Cache中比较器的个数和位数分别为()。A. 8, 20B. 8

7、, 23C. 64, 20D. 64, 2317. 某内存条包含8个8192x8192x8位的DRAM芯片，按字节编址，支持突发(burst)传送方式，对应存储器总线宽度为64位，每个DRAM芯片内有一个行缓冲区(row buffer)。下列关千该内存条的叙述中，不正确的是（）。A. 内存条的容量为512MBB.采用多模块交叉编址方式C.芯片的地址引脚为26位D.芯片内行缓冲有8192x8位18. 下列选项中，属于指令集体系结构(ISA)规定的内容是()。I.指令字格式和指令类型II. CPU的时钟周期III.通用寄存器个数和位数IV.加法器的进位方式A.仅I、IIB.仅I、IIIC.仅II、

8、IVD.仅I、III、IV19. 设计某指令系统时，假设采用16位定长指令字格式，操作码使用扩展编码方式，地址码为6位，包含零地址、一地址和二地址3种格式的指令。若二地址指令有12条，一地址指令有 254条，则零地址指令的条数最多为( )。A. 0B. 2C. 64D. 12820. 将高级语言源程序转换为可执行目标文件的主要过程是（ ）。A. 预处理一编译一汇编-链接B.预处理-+汇编一编译-链接C.预处理-编译一链接一汇编D.预处理一汇编一链接一编译 21.下列关千中断I/0方式的叙述中，不正确的是()。A.适用千键盘、针式打印机等字符型设备 B.外设和主机之间的数据传送通过软件完成 C.

9、外设准备数据的时间应小千中断处理时间D.外设为某进程准备数据时CPU可运行其他进程22. 下列关千并行处理技术的叙述中，不正确的是（ ）。A. 多核处理器属千MIMD结构B向量处理器属千SIMD结构 C.硬件多线程技术只可用千多核处理器D. SMP中所有处理器共享单一物理地址空间23. 下列关千多道程序系统的叙述中，不正确的是()。A. 支持进程的并发执行B.不必支持虚拟存储管理C.需要实现对共享资源的管理D.进程数越多CPU利用率越高24. 下列选项中，需要在操作系统进行初始化过程中创建的是（ ）。A. 中断向量表B.文件系统的根目录C.硬盘分区表D.文件系统的索引结点表25. 进程PO、P

10、l、P2和P3进入就绪队列的时刻、优先级（值越小优先权越高）及CPU执行时间如下表所示。进程进入就绪队列的时刻优先级CPU执行时间POOms15lOOmsPl!Oms2060msP2lOms1020msP315ms6lOms若系统采用基千优先权的抢占式进程调度算法，则从Oms时刻开始调度，到4个进程都运行结束为止，发生进程调度的总次数为（）。A. 4B. 5C. 6D. 726. 系统中有三个进程PO、Pl、P2及三类资源A、B、C。若某时刻系统分配资源的情况如下表所示，则此时系统中存在的安全序列的个数为()。第4页（共8页）已分配资源数进程AIB尚需资源数可用资源数cA I B|c3 - 3

11、B - 2 - 2A - 0c0 - 2 - 0。三3I2A. 1B. 2C. 3D. 427. 下列关千CPU模式的叙述中，正确的是（ ）。A. CPU处于用户态时只能执行特权指令B. CPU处于内核态时只能执行特权指令C. CPU处于用户态时只能执行非特权指令D. CPU处于内核态时只能执行非特权指令28. 下列事件或操作中，可能导致进程P由执行态变为阻塞态的是()。I.进程P读文件II.进程P的时间片用完III.进程P申请外设IV.进程P执行信号晕的wait(）操作 A.仅1、IVB.仅II、III C.仅III、IVD.仅I、III、IV29. 某进程访问的页b不在内存中，导致产生缺页

12、异常，该缺页异常处理过程中不一定包含的操作是（）。第5页（共8页）A. 淘汰内存中的页C.将页b从外存读入内存30. 下列选项中，不会影响系统缺页率的是（B.建立页号与页框号的对应关系D. 修改页表中页b对应的存在位)。A. 页置换算法B.工作集的大小C.进程的数量D.页缓冲队列的长度31. 执行系统调用的过程涉及下列操作，其中由操作系统完成的是()。I.保存断点和程序状态字II.保存通用寄存器的内容III.执行系统调用服务例程IV.将CPU模式改为内核态A.仅I、IIIB.仅11、IIIC.仅II、IVD仅II、III、W32. 下列关于驱动程序的叙述中，不正确的是（ ）。A. 驱动程序与1

13、/0控制方式无关B. 初始化设备是由驱动程序控制完成的c.进程在执行驱动程序时可能进入阻塞态D.读写设备的操作是由驱动程序控制完成的33. 在ISO/OSI参考模型中，实现两个相邻结点间流量控制功能的是（ ）。A.物理层B.数据链路层C.网络层D.传输层34. 在一条带宽为200kHz的无噪声信道上，若采用4个幅值的ASK调制，则该信道的最大数据传输速率是（）。ft.200 kbps. B. 400 kbps. C. 800 kbpsD. 1600 kbps35. 若某主机的IP地址是183.80.72.48,子网掩码是255.255.192.0,则该主机所在网络的网络地址是（）。A. 183

14、.80.0.0B. 183.80.64.0C. 183.80.72.0D. 183.80.192.036. 下图所示网络中的主机H的子网掩码与默认网关分别是（ ）。HI92.168.1.60A. 255.255.255.192, 192.168.1.1B. 255.255.255.192, 192.168.1.62C. 255.255.255.224, 192.168.1.1D. 255.255.255.224, 192.168.1.6237. 在SDN网络体系结构中，SDN控制器向数据平面的SDN交换机下发流表时所使用的接口是A. 东向接口B.南向接口c.西向接口D.北向接口38. 假设主机

15、甲和主机乙已建立一个TCP连接，最大段长MSS= 1 KB,甲一直有数据向乙发送，当甲的拥塞窗口为16KB时，计时器发生了超时，则甲的拥塞窗口再次增长到16KB所需要的时间至少是()。A. 4 RTT B. 5 RTTC. 11 RTTD. 16 RTT39. 假设客户C和服务器S已建立一个TCP连接，通信往返时间RTT= 50ms,最长报文段寿命 MSL=800ms,数据传输结束后，C主动请求断开连接。若从C主动向S发出FIN段时刻算起，则C和S进入CLOSED状态所需的时间至少分别是( )。A. 850ms, 50msB. 1650 ms, 50 msC. 850 ms, 75 ms.D.

16、 1650 ms, 75 ms40. 假设主机H通过HTTP/1.l请求浏览某Web服务器S上的Web页news408.html, news408.html引用了同目录下的1幅图像，news408.html文件大小为1 MSS（最大段长），图像文件大小为 3 MSS, H访问S的往返时间RTT= lOms,忽略HTTP响应报文的首部开销和TCP段传输时延。若H已完成域名解析，则从H请求与S建立TCP连接时刻起，到接收到全部内容止，所需的时间至少是（ ）。A. 30msB. 40msC. 50msD. 60ms二、综合应用题：4147小题，共70分。41. (13分）已知非空二叉树T的结点值均为

17、正整数，采用顺序存储方式保存，数据结构定义如下：typedef s七ruct I,MAXSIZE为己定义常量-int SqBiTNodeMAX SIZE； II保存三叉树结点值的数组int.ElemNum;实际占用的数组元素个数” SqBi匹ee;，.，T中不存在的结点在数组SqBiTNode中用1表示。例如，对于下图所示的两棵非空二叉树 Tl和T2,35二叉树Tl二叉树T2Tl的存储结果如下Tl.SqBiTNode勹 I 25 I 60 I -I I 30 -I 80 I -1 I -1 I 27Tl.ElemNum = 10T2的存储结果如下：第6贝（共8贝）T2.SqBiTNode T2

18、.ElemNum = 11曰50 l 60-1 ! 30 丿 -1 ! -1 二35请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回true,否则，返回false。要求：1) 给出算法的基本设计思想。2) 根据设计思想，采用C或C+语言描述算法，关键之处给出注释。42. (10分）现有n (n 100000)个数保存在一维数组M中，需要查找M中最小的10个数。请回答下列问题。1) 设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简述其算法思想（不需要程序实现）。2) 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。43. (15

19、分）某CPU中部分数据通路如题43图所示，其中，GPRs为通用寄存器组；FR为标志寄存器，用千存放ALU产生的标志信息；带箭头虚线表示控制信号，如控制信号Read、Write分别表示主存读、主存写，MDRin表示内部总线上数据写入MDR, MDRout表示MDR的内容送内部总线。GPRin系统总线题43图请回答下列问题。l)设ALU的输入端A、B及输出端F的最高位分别为A15、B15及F15, FR中的符号标志和溢出标志分别为SF和OF,则SF的逻辑表达式是什么？A加B、A减B时OF的逻辑表达式分别是什么？要求逻辑表达式的输入变量为A15、B15及F1502) 为什么要设置暂存器Y和Z?3)

20、若GPRs的输入端rs、rd分别为所读、写的通用寄存器的编号，则GPRs中最多有多少个通用寄存器？rs和rd来自图中的哪个寄存器？已知GPRs内部有一个地址译码器和一个多路选择器，rd应连接地址译码器还是多路选择器？4) 取指令阶段（不考虑PC增量操作）的控制信号序列是什么？若从发出主存读命令到主存读出数据并传送到MDR共需5个时钟周期，则取指令阶段至少需要几个时钟周期？5) 图中控制信号由什么部件产生？图中哪些寄存器的输出信号会连到该部件的输入端？44. (8分）假设某磁盘驱动器中有4个双面盘片，每个盘面有20000个磁道，每个磁道有500个扇区，每个扇区可记录512字节的数据，盘片转速为7

21、200RPM（转分），平均寻道时间为5ms。请回答下列问题。l)每个扇区包含数据及其地址信息，地址信息分为3个字段。这3个字段的名称各是什么？对千该磁盘，各字段至少占多少位？2) 一个扇区的平均访问时间约为多少？3) 若采用周期挪用DMA方式进行磁盘与主机之间的数据传送，磁盘控制器中的数据缓冲区大小为64位，则在一个扇区读写过程中，DMA控制器向CPU发送了多少次总线请求？若CPU检测到DMA控制器的总线请求信号时也需要访问主存，则DMA控制器是否可以获得总线使用权？为什么？第7页（共8页）45. (7分）某文件系统的磁盘块大小为4KB,目录项由文件名和索引结点号构成，每个索引结点占256字节

22、，其中包含直接地址项10个，一级、二级和三级间接地址项各1个，每个地址项占4字节。该文件系统中子目录stu的结构如题45(a)图所示，stu包含子目录course和文件doc, course子目录包含文件course!和course2。各文件的文件名、索引结点号、占用磁盘块的块号如题45(b)图所示。请回答下列问题。studoc题45(a)图l)目录文件stu中每个目录项的内容是什么？2) 文件doc占用的磁盘块的块号x的值是多少？3) 若目录文件course的内容已在内存，则打开文件coursel并将其读入内存，需要读几个磁盘块？说明理由。4) 若文件course2的大小增长到6MB,则为了

23、存取course2需要使用该文件索引结点的哪几级间接地址项？说明理由。文件名索引结点号磁盘块号stu110course220course!1030course210040doc10X题45(b)图第8页（共8页）(A(B46. (8分）某进程的两个线程Tl和T2并发执行A、B、C、D、E和F共6个操作，其中Tl执行A、E和F, T2执行B、C和D。题46图表示上述6个操作的执行顺序所必须满足的约束：C在 A和B完成后执行，D和E在C完成后执行，F在E完成后执行。请使用信号量的wait(）、signal(）操作描述Tl和T2之间的同步关系，并说明所用信号量的作用及其初值。题46图47. (9分）

24、某网络拓扑如题47图所示，R为路由器，S为以太网交换机，AP是802.11接入点，路由器的EO接口和DHCP服务器的IP地址配置如图中所示；H1与H2属千同一个广播域，但不属于同一个冲突域；H2和H3属千同一个冲突域；H4和H5已经接入网络，并通过DHCP动态获取了IP地址。现有路由器、lOOBaseT以太网交换机和lOOBaseT集线器(Hub)三类设备各若干台。H5忑芍192.168.0.4/2500-11-11-11-11-ElH2请回答下列问题。192.168.0.3/25H3OO-l l-11-11-1 I-DI题47图l)设备l和设备2应该分别选择哪类设备？2) 若信号传播速度为2x108 mis,以太网最小帧长为64 B,信号通过设备2时会产生额外的1.51 s的时间延迟，则H2与H3之间可以相距的最远距离是多少？3) 在H4通过DHCP动态获取IP地址过程中，H4首先发送了DHCP报文M, M是哪种 DHCP报文？路由器EO接口能否收到封装M的以太网帧？S向DHCP服务器转发的封装 M的以太网帧的目的MAC地址是什么？4) 若H4向H5发送一个IP分组P,则H5收到的封装P的802.11帧的地址1、地址2和地址3分别是什么？