文档内容
全国硕士研究生入学统一考试
计算机科学与技术学科联考
2022全国硕士研究生招生考试计算机学科专业基础试题参考答案
一、单项选择题
01. B 02. D 03. B 04. C 05. D 06. D 07. B 08. D
09. D 10. A 11. D 12. A 13. B 14. A 15. C 16. A
17. C 18. B 19. D 20. A 21. C 22. C 23. D 24. A
25. C 26. B 27. C 28. D 29. A 30. D 31. B 32. A
33. B 34. C 35. B 36. D 37. B 38. C 39. D 40. B
01. B。【解析】当外层循环的变量z■取不同值时，内层循环就执行多少次，因此总循环次数为力
的所有取值之和。假设外层循环共执行后次，当2 =1,2,4,8,…,21(2"]<)«2左)时，内层循
环执行i次，因此总循环次数7 = 1 + 2 + 4 + 8 +…+ 21 = 2左-1 ,即 " T<2〃，时间复杂度为
O(n) o
02. D。【解析】通过模拟出入栈操作，可以判断入栈序列in和出栈序列。ut是否合法。因此，已
知in序列可以判断out序列是否为可能的出栈序列;已知out序列也可以判断in序列是否为
可能的入栈序列，A 和B错误。如果每个元素入栈后立即出栈，则in序列和。ut序列相同，
C错误。如果所有元素都入栈后才依次出栈，则in序列和out序列互为倒序，D正确。
03. B。【解析】对于此类题，每种情况只需举出一个反例即可。如图1所示，q 是p 的双亲，中
序遍历序列为｛p,qb，I可能。如图2所示，q是p 的右孩子，中序遍历序列为｛p,q｝, II可能。
如图4所示，q是p 的双亲的双亲，中序遍历序列为｛x,p,q｝, IV可能。如图3所示，q是p
的右兄弟，F 是 q 和p 的父结点，中序遍历要求先遍历左子树,再访问根结点,最后遍历右
子树，因此一定先访问p ,再访问F ,最后访问q, p和q不可能相邻出现，皿不可能。
04. Co【解析】高度一定的三叉树中结点数最多的情况是满三叉树。高度为5 的满三叉树的结点
数 =30+3J 32+ 33 + 34=121,高度为 6 的满三叉树的结点数=3°+ 31 + 32+33 + 34+35=364
0
由于三叉树T 的结点数为244, 121v 244 V 364,因此T 的高度至少为6。
05. D。【解析】可以画一个简单的特例来证明。图1是满足条件的二叉树T L 图2是满足条件的
二叉树T 2,结点中有值表示这个结点是编码字符。T1和T2的结点数不同，A错误。T1的高
度等于T2的高度，B 错误。出现频次不同的字符在T1中也可能处于相同的层，C错误。对
于定长编码集，所有字符一定都在T2中处于相同的层,而且都是叶子结点。
106. D。【解析】注意，V是图的边数，E是图的顶点数。A和B 明显错误，如图1所示，|V|＜|E|,
但图G不连通;如图2所示，|V| ＞ |E|,但图G不连通。如图3所示,在无向图中至少要有|V| - 1
个顶点才可能连通，顶点数小于IM -1一定不可能连通，C错误，D正确。
c 的时间余量=vl(3)_ve(2)-l = 5_2_l=2,g 的时间余量==vl(6)- ve(3)-1 = 12-5-1=6,
h的时间余量=vl(5)-ve(4)-l = 11-8-1 =2,j 的时间余量=vl(6)-ve(5)-1 = 12-9-1 = 2,
时间余量最大的活动是g。
08. D 【解析】在 5阶B树中，除根结点外的非叶结点的关键字数左需要满足24后4 4 。当被删
o
关键字x 不在终端结点(最低层非叶结点)时，可以用x 的前驱(或后继)关键字y来替代x,
然后在相应结点中删除y。情况①：删除260,将其前驱H0放入260处，删除110后的结点
＜100＞不满足5阶B树定义，从左兄弟中借85,将85放入根中，将根中的90移入结点＜100＞
变为＜90，100＞。情况②：删除260,将其后继280放入260处，结点＜300不满足5阶B树定
义且左右兄弟都不够借，结点＜300＞可以和左兄弟＜100, 110＞以及关键字280合并成一个新的
结点＜100, 110, 280, 300＞。情况③：在情况②中，结点＜300＞也可以和右兄弟＜400, 500＞以及
关键字350合并成一个新的结点＜300, 350, 400, 500＞。综上，T1根结点中的关键字序列可能
是＜60, 85, 110, 350＞或＜60, 90, 350或＜60, 90, 2 8 0 ,仅 D 不可能。
09. Do【解析】填装因子越大，说明哈希表中存储的元素越满，发生冲突的可能性就越高，导致
平均查找长度越大。散列函数、冲突解决策略也会影响发生冲突的可能性。I、IL in都正确。
10. Ao【解析】送分概念题。王道书对归并的定义原话是“归并的含义是将两个或两个以上的有
序表合并成一个新的有序表”，而二路归并是将两个有序表合并为一个新的有序表。
11. D。【解析】直接插入排序和快速排序的特点如下表所示。
适合初始序列情况 适合元素数量 空间复杂度 稳定性
直接插入排序 大部分元素有序 较少 0(1) 稳定
快速排序 基本无序 较多 O(log2 九) 不稳定
2可见，I、n、in、iv 都是采用直接插入排序而不采用快速排序的可能原因。
12. A。【解析】CPI指平均每条指令的执行需要多少个时钟周期。由于80%的指令执行平均需要
1个时钟周期，20%的指令执行平均需要10个时钟周期，因此CPI = 80%xl + 20%xl0 = 2.8。
计算机主频为1GHz,程序P共执行10000条指令，平均每条指令需要2.8个时钟周期，因此,
CPU 执行时间= （10000x2.8）/109= 2.8x10—5$ = 28即。
13. B o【解析】〃位补码整数的最小值是1,00... 0 （即-2〃T ）；最大值是0,11…1 （即2〃T -1）。 n
位补码整数所能表示的范围是-2%T 〜 2 ^ 一1 , 32位补码整数所能表示的范围是-231〜
231-1 O
14. A。【解析】IEEE 754单精度浮点数格式中依次为数符1位、阶码8 位 （偏置值127）、尾数
23位 （隐藏1位）。-0.4375 =-1.75x2一2 ,保证小数点前是1。根据单精度浮点数格式，数符
为 1 ;阶码为移码表示，-2 + 127 = 125,写成8位二进制数为01111101；尾数隐藏小数点前
的 1 ,剩下的0.75写成二进制数为0.11,所以尾数部分是1100…0。该浮点数的二进制格式为
1011 1110 1110 0000 0000 0000 000 0000,对应的十六进制格式为 BEEO 0000H
o
15. Co【解析】页大小为4KB = 212B, 按字节编址，故页内地址为12位。虚拟地址空间大小为
4GB = 232B ,故虚拟地址共32位，其中低12位为页内地址，高 20位为虚页号。题中给出的
虚拟地址为0008 2840H,虚页号为高20位即00082H （页内地址为低12位即840H）, 82H对
应的十进制数为130（注意题中页表的虚页号部分末尾未写H ,所以是十进制数，故查找时要
先将虚页号转换为十进制数），查页表命中，且存在位为L 对应页框号为018H。将查找到的
页框号018H和页内地址840H拼接J 得到主存地址为01 8840H。
16. A。【解析】Cache采用组相联映射，主存地址结构应分为Tag标记、组号、块内地址三部分。
主存块大小=Cache块大小= 64B = 26B ,因此块内地址占6位。Cache数据区容量为32KB,
每个Cache块大小为64B,则Cache总块数=32KB/64B = 29,由于采用8路组相联映射，即
每 8个Cache块为一个分组，因此总共被分为2〃8 = 2$组，因此，组号占6位。除了块内地
址和组号，剩余的位为Tag标记，占32- 6 -6 = 20位。地址结构如下所示。
Tag标记 组号 块内地址
20位 6位 6位
Cache采用8路组相联映射，因此在访问一个物理地址时，要先根据组号定位到某一分组，然
后用物理地址的高20位 （Tag标记）与分组中8个Cache行的Tag标记做并行比较（用8个
20位 “比较器”实现），若某个Cache行的Tag标记与物理地址的高20位完全一致，则选
中该Cache行。综上所述，在组相联映射的Cache中 , “比较器”用于并行地比较分组中所
有 Cache行的Tag标记位与欲访问物理地址的Tag标记位，因此比较器的个数就是分组中的
Cache行数8 ,比较器的位数就是Tag标记位数20。
17. C。【解析】8x 8192x8192x8bit = 512MB,内存条的容量为512MB, A 正确。存储器总线宽
度 64 = 8x8bit,而每个芯片一次只能传输8bit,需要8体多模块交叉编址才能实现，B 正确。
512MB = 229B ,按字节编址，因此芯片的地址引脚为29位 ,C错误。芯片内行数是8192, 一
行的大小是8192x8bit,行缓冲长度就是一行的大小,D 正确。
18. B。【解析】指令集处于软硬件的交界面上。指令字和指令格式、通用寄存器个数和位数都与
机器指令有关，由ISA规定。两个CPU可以有不同的时钟周期，但指令集可以相同，CPU的
时钟周期不由ISA规定。加法器的进位方式涉及电路设计，也不由指令集规定。
19. Do【解析】地址码为6位,一条二地址指令会占用26条一地址指令的空间，一条一地址指令
3会占用26条零地址指令的空间。如果全都是零地址指令，则最多有216条，减去一地址指令
和二地址指令所占用的零地址指令空间，即216 — 254x26- 12x26x26= (210- 254- 12x 26)x
26=(4X26-254)X26=2X26= 128。
20. A。【解析】将源程序转换为可执行目标文件的过程分为预处理、编译、汇编、链接四个阶段。
21. C。【解析】中断I/O方式适用于字符型设备，此类设备的特点是数据传输速率慢，以字符或
字为单位进行传输，A 正确。若采用中断I/O方式，当外设准备好数据后，向CPU发出中断
请求，CPU暂时中止现行程序，转去运行中断服务程序，由中断服务程序完成数据传送，B
正确。若外设准备数据的时间小于中断处理时间，则可能导致数据丢失，以输入设备为例，
设备为进程准备的数据会先写入设备控制器的缓冲区(缓冲区大小有限，通常只能暂存几个
字节)，缓冲区每写满一次，就会向CPU发出一次中断请求，CPU响应并处理中断的过程，
就是将缓冲区中的数据“取走”的过程，因此若外设准备数据的时间小于中断处理时间，则
可能导致外设往缓冲区写入数据的速度快于CPU从缓冲区取走数据的速度，从而导致缓冲区
的数据被覆盖，进而导致数据丢失。C错误。若采用中断I/O方式，则外设为某进程准备数据
时，可令该进程阻塞，CPU运行其他进程，D 正确。
22. C。【解析】MIMD结构分为多计算机系统和多处理器系统，A 正确。向量处理器是SIMD的
变体，属于SIMD结构，B 正确。硬件多线程技术是在一个核中处理多个线程，可用于单核
处理器，C 错误。共享内存多处理器(SM P)具有共享的单一物理地址空间，所有核都可通
过存取指令来访问同一片主存地址空间，D 正确。
23. D。【解析】操作系统的基本特点：股 、共塞、虚拟、异步，其中最基本、一定要实现的是
并发和共享，A、C 正确。早期的多道批处理操作系统会将所有进程的数据全部调入主存，再
让多道程序并发执行，即使不支持虚拟存储管理，也能实现“多道程序并发”，B 正确。进
程多并不意味着CPU利用率高，进程数量越多，进程之间的资源竞争越激烈，甚至可能因为
资源竞争而出现死锁现象，导致CPU利用率低，D错误。
24. A。【解析】在操作系统初始化的过程中需要创建中断向量表，用于实现“中断处理”，CPU
检测到中断信号后，根据中断号查询中断向量表，跳转到对应的中断处理程序，A 正确。当
硬盘被逻辑格式化时，需要对硬盘进行分区，即创建硬盘分区表。分区完成后，需要在每个
分区初始化一个特定的文件系统，并创建文件系统的根目录。如果某个分区采用Unix文件系
统 (U FS),则还要在该分区中建立文件系统的索引结点表。综上，C 是在硬盘逻辑格式化的
过程中完成的，B、D 是在初始化文件系统的过程中完成的。
25. C。【解析】0 时刻调度进程P0获得CPU； 10ms时P2进入就绪队列，调度P2抢占获得CPU；
15ms时P3进入就绪队列，调度P3抢占获得CPU； 25ms时P3执行完毕，调度P2获得CPU；
40ms时P2执行完毕，调度P0获得CPU； 130ms时P2执行完毕，调度P1获得CPU； 190ms
时P2执行完毕，结束；总共调度6 次。
26. B。【解析】初始时系统中的可用资源数为<1,3, 2 > ,只能满足P0的需求<0,2, 1>,所以安全
序列第一个只能是P 0,将资源分配给P0后，P0执行完释放所占资源，可用资源数变为VI, 3,
2> + <2,0,1> = <3,3,3>,此时可用资源数既能满足P L 也能满足P 2,可以先分配给PL P1
执行完释放资源再分配给P2；也可以先分配给P2, P2执行完释放资源再分配给P1。所以安
全序列可以是①P0、Pl、P2或②P0、P2、Pio
27. Co【解析】CPU在用户态时只能执行非特权指令，在内核态时可以执行特权指令和非特权
指令。
28. D。【解析】进程P读文件时，进程从执行态进入阻塞态，等待磁盘I/O完成，I 正确。进程P
4的时间片用完，导致进程从执行态进入就绪态，转入就绪队列等待下次被调度，n 错误。进
程 P 申请外设，若外设是独占设备且正在被其他进程使用，则进程P从执行态进入阻塞态，
等待系统分配外设，皿正确。进程P 执行信号量的w aito操作，如果信号量的值小于等于
0 ,则进程进入阻塞态，等待其他进程用signal。操作唤醒，IV正确。
29. A。【解析】缺页异常需要从磁盘调页到内存中，将新调入的页与页框建立对应关系，并修改
该页的存在位，B、C、D正确；如果内存中有空闲页框，就不需要淘汰其他页,A错误。
30. D。【解析】页置换算法会影响缺页率，例如，LRU算法的缺页率通常要比FIFO算法的缺页
率低，排除A。工作集的大小决定了分配给进程的物理块数，分配给进程的物理块数越多，
缺页率就越低，排除Bo进程的数量越多，对内存资源的竞争越激烈，每个进程被分配的物
理块数越少，缺页率也就越高，排除Co页缓冲队列是将被淘汰的页面缓存下来，暂时不写
回磁盘，队列长度会影响页面置换的速度，但不会影响缺页率，答案选D。
31. B。【解析】发生系统调用时，CPU执行陷入（Trap）指令,检测到“内中断”后，由CPU负
责保存断点（PC）和程序状态字，并将CPU模式改为内核态，然后执行操作系统内核的系统
调用入口程序，该内核程序负责保存通用寄存器的内容，再调用某个特定的系统调用服务例
程。综上，I、IV是由硬件完成的，n、III是由操作系统完成的。
32. A。【解析】厂家在设计一个设备时，通常会为该设备编写驱动程序，主机需要先安装驱动程
序，才能使用设备。当一个设备被连接到主机时，驱动程序负责初始化设备（如将设备控制
器中的寄存器初始化），B正确。当进程在执行驱动程序时，可能会因为设备忙碌而进入阻塞
态，C 正确。设备的读/写操作本质就是在设备控制器和主机之间传送数据，而只有厂家知道
设备控制器的内部实现，因此也只有厂家提供的驱动程序能控制设备的读/写操作，D 正确。
厂家会根据设备特性，在驱动程序中实现一种合适的I/O控制方式,A错误。
33. B。【解析】在 OSI参考模型中，数据链路层、网络层、传输层都具有流量控制功能,数据链
路层是根邻结点之间的流量控制，网络层是整个网络中的流量控制，传输层是端到端的流量
控制O
34.C 。【遍析】根据奈奎斯特定理，最大数据传输速率= 2%log2y, 4个幅值的ASK调制说明
有4个相位，将 P= 4代入，得 800kbps。
35. B。【解析】主机所在网络的网络地址可以通过主机的IP地址和子网掩码逐位相与得到。子网
掩码255.255.192.0的二进制前18位为1、后 14位为0 ,把主机IP地址的后14位变为0 ,得
到的结果为183.80.64.0,即为主机所在网络的网络地址。
36. Do【解析】默认网关可以理解为离当前主机最近的路由器的端口地址，所以是192.168.L62,
而该主机的子网掩码和网关的子网掩码也相同，/27即为255.255.255,224。
37. Bo【解析】SDN对上层开发者提供的编程接口称为北向接口，而南向接口则负责控制平面和
数据平面间的通信，所以SDN控制器向数据平面的SDN交换机下发流表时使用南向接口。
38. C。【解析】时刻0 发生了超时，门限值ssthresh变为拥塞窗口 cwnd的一半即8 ,同时cwnd
置为L 执行慢开始算法,cwnd指数增长，经过3个 RTT,增长到ssthresh值;之后执行拥
塞避免算法，cwnd线性增长，再经过8个RTT,增长到16,共花费11个RTT,如下表所示。
时刻 0 1 2 .；3 4 5 6 7 8 9 10 11
拥塞窗口 1 2 4 8 9 10 11 12 13 14 15 16
39. D。【解析】TCP连接的释放过程如下图所示。题目问的是最少时间，所以当服务器S收到客
户C发送的FIN请求后不再发送数据，而是立马发送FIN请求（即第②步和第③步同时发生,
5忽略FIN-WAIT-2和 CLOSE-WAIT状态)。C收到S发来的FIN报文段后，进入CLOSED状
态还需等到TIME-WAIT结束，总用时至少为1RTT + 2MSL = 50 + 800x2 = 1650ms S进入
o
CLOSED状态需要经过3次报文段的传输时间，即1.5RTT = 75ms。
40. B。【解析】HTTP/1.1默认使用流水线的持久连接，所有请求都是连续发送的。题目要求最少
时间，最理想的流程是TCP在第三次握手的报文段中捎带HTTP请求，以及TCP连接后慢开
始阶段不考虑拥塞情况。假设接收方有足够大的缓存空间，即发送窗口等同于拥塞窗口，总
共需要经过：第 1个RTT,进行TCP连接，此时服务器S 的发送窗口 = 1MSS,并在第三次
握手时捎带HTTP请求；第2个RTT,服务器S发送大小为1MSS的html文件，主机C确认
后服务器S 的发送窗口变为2MSS；第 3个RTT,服务器S发送大小为2Mss的图像文件，
主机C确认后服务器S 的发送窗口变为4MSS；第4个RTT,服务器S发送剩下的1MSS图
像文件，完成传输，总共需要4个RTT,即40ms。
二、综合应用题
4 L 【解析】
[答案1]
1 )算法的基本设计思想
对于采用顺序存储方式保存的二叉树，根结点保存在SqBiTN°de[0]中；当某结点保存在
SqBiTNode [i]中时，若有左孩子，则其值保存在SqBiTNode [2i+l]中；若有右孩子，则
其值保存在SqBiTNod㊀[2i+2]中；若有双亲结点，则其值保存在SqBiTNode [ (i-1)/2 ]
中。
二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子树
中的全部结点值。中序遍历二叉搜索树得到一个升序序列。
使用整型变量va1 记录中序遍历过程中已遍历结点的最大值，初值为一个负整数。若当
前遍历的结点值小于等于v a l,则算法返回fa ls e ,否则，将v a l的值更新为当前结点
的值。
62 )算法实现
【答案2】
1)算法的基本设计思想
对于采用顺序存储方式保存的二叉树，根结点保存在SqBiTNode [0] 当某结点保存在
SqBiTNod㊀[i]中时,若有左孩子，贝！|其值保存在SqBiTNode [2i+1]中；若有右孩子，则
其值保存在SqBiTNode [2i+2]中；若有双亲结点，则其值保存在SqBiTNode [ (” 1)/2]
中。
二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子树
中的全部结点值。设置两个数组pmax和pmin。根据二叉搜索树的定义，SqBiTNode [i]
中的值应该大于以SqBiTNod㊀[2i+l]为根的子树中的最大值(保存在pmax[2i+l]
中)，小于以SqBiTNod㊀[2i+2]为根的子树中的最小值(保存在pmin[2i+1]中)。初
始时，用数组SqBiTNode中前ElemNum个元素的值对数组pmax和pmin初始化。
在数组SqBiTNode中从后向前扫描，扫描过程中逐一验证结点与子树之间是否满足上述
的大小关系。
2 )算法实现
bool judgeBST(SqBiTree bt){
int k m *pmin,*pmax;
z z
pmin=(int *)malloc(sizeof(int)*(bt.ElemNum));
pmax=(int *)malloc(sizeof(int)*(bt.ElemNum));
for (k-0; k0; k--) { //从最后一个叶结点向根遍历
if(bt.SqBiTNode[k]!=-l){
if (k%2==1&&bt. SqBiTNode [m] >pmax [k]) 〃其为左孩子
else if (k%2==0&&bt. SqBiTNode [m]
