文档内容
绝密★启用前
全国硕士研究生入学统一考试
计算机科学与技术学科联考
2022年全国硕士研究生招生考试
计算机学科专业基础试题
（科 目 代 码 ：408）
考生注意事项
1 .答题前，考生在试题册指定位置上填写考生编号和考生姓名；在答题卡指定位置上填写报
考单位、考生姓名和考生编号，并涂写考生编号信息点。
2 . 考生须把试题册上的“试卷条形码”黏贴条取下，黏贴在答题卡的“试卷条形码黏贴位置”
框中，不按规定黏贴条形码而影响评卷结果的，责任由考生自负。
3 . 选择题的答案必须涂写在答题卡和相应题号的选项上,非选择题的答案必须书写在答题卡
指定位置的边框区城内，超出答题区域书写的答案无效；在草稿纸、试题册上答题无效。
4 . 填 （书）写部分必须使用黑色字迹签字笔书写，字迹工整、笔迹清楚;涂写部分必须使用
2B铅笔涂写。
5 . 考试结束，将答题卡和试题册按规定交回。
（以下信息考生必须认真填写）
考生编号
考生姓名一、单项选择题：01〜40小题，每小题2 分，共 80分。下列每题给出的四个选项中，只有一个
选项是最符合题目要求的。
01.下列程序段的时间复杂度是（ ）。 …
int sum = 0;
for （int i = 1; i < n; i *= 2）
for （int j = 0; j < i; j++）
sum++；
A. O（log n ） B. O （ n ） C. O（?? log n ） D.
02.给定有限符号集S, in和 。ut均为S 中所有元素的任意排列。对于初始为空的栈S T ,下列
叙述中，正确的是（ ）0
A .若in是ST的入栈序列，则不能判断。ut是否为其可能的出栈序列
B .若out是ST的出栈序列，则不能判断in是否为其可能的入栈序列
C .若in是ST的入栈序列，out是对应in的出栈序列，则in与out 一定不同
D .若in是ST的入栈序列，out是对应in的出栈序列，则in与out可能互为倒序
03.若结点p 与q在二叉树T 的中序遍历序列中相邻，且p在q之前，则下列p 与q 的关系中，
不可能的是（ ）o
I. q是P 的双亲 II. q是p 的右孩子
III. q是p 的右兄弟 IV. q是p 的双亲的双亲
A .仅 I B .仅 ni c . 仅 II、in D .仅 n、IV
04.若三叉树T 中有244个结点（叶结点的高度为1）, 则T 的高度至少是（ ）
0
A. 8 B. 7 C. 6 D. 5
05.对任意给定的含〃（">2）个字符的有限集S ,用二叉树表示S 的哈夫曼编码集和定长编码
集，分别得到二叉树T1和T2。下列叙述中，正确的是（ ）
0
A. T1与T2的结点数相同 B. T1的高度大于T2的高度
C .出现频次不同的字符在T1中处于不同的层
D .出现频次不同的字符在T2中处于相同的层
06.对于无向图G = （YE）, 下列选项中，正确的是（ ）。
A .当|V|>|E|时，G一定是连通的
B .当|V|〈|E|时，G一定是连通的
C .当|V| = |E |T 时，G 一定是不连通的
D .当|V|>|E|+1时，G 一定是不连通的
07.下图是一个有10个活动的AOE网，时间余量最大的
，活动是（ ）。
A. c B. g
C. h D .j
08. 在下图所示的5阶B树T 中，删除关键字260之后需要进行必要的调整，得到新的B树T1。
下列选项中，不可能是T1根结点中关键字序列的是（ ）。
。 々 」
L 6 90 260 0
〕 [
30 50 ] 170 80 85 100 110 ] [ 280 300 ] [ 400 500
A. 60,90,280 B. 60, 90, 350
C. 60, 85,110, 350 D. 60,90, 110,350
09.下列因素中，影响散列（哈希）方法平均查找长度的是（ ）
0
I . 装填因子 II.散列函数 in .冲突解决策略
A .仅 I、II B .仅 I、III C .仅 n、III D. I、IL III
第2页 （共8页）10.使用二路归并排序对含九个元素的数组M 进行排序时，二路归并操作的功能是《 ）0
A . 将两个有序表合并为一个新的有序表
B . 将M 划分为两部分，两部分的元素个数大致相等
C 将M 划分为几个部分,每个部分中仅含有一个元素
D . 将乂划分为两部分，一部分元素的值均小于另一部分元素的值
对数据进行排序时，若采用直接插入排序而不采用快速排序,则可能的原因是（ ）。
L 大部分元素已有序 I L 待排序元素数量很少
in.要求空间复杂度为o （D IV.要求排序算法是稳定的
A , 仅 I、II B , 仅 HI、IV C . 仅 I、n、IV D. I、II、in、IV
12 . 某计算机主频为1 GHz,程序P 运行过程中，共执行了 10000条指令，其中，80%的指令执
行平均需1个时钟周期，20%的指令执行平均需10个时钟周期。程序P 的平均CPI和 CPU
执行时间分别是（ ）o
A. 2.8,2811s B. 28,28 pis C. 2.8, 28 ms D. 28, 28 ms
13 . 32位补码所能表示的整数范围是（ ）
o
A. -232- 231-1 B. -231-231-1 C. -232-232-l D. -231-232-l
14 . -04375的IEEE 754单精度浮点数表示为（ ）。
A. BEEO 0000H B. BF60 0000H C. BF70 0000H D. COEO 0000H
15 . 某计算机主存地址为24位，采用分页虚拟存储管理方式，虚拟地址空间大小为4 GB,页大小为
4KB,按字节编址。某进程的页表部分内容如下表所示。
C . 得到主存地址01 8840H D . 检测到缺页异常
16 .若计算机主存地址为32位，按字节编址，某Cache的数据区容量为32 KB,主存块大小为64
B , 采用8路组相联映射方式？该Cache中比较器的个数和位数分别为（ ）。
A. 8, 20 B. 8, 23 C. 64,20 D. 64, 23
17 . 某内存条包含8个 8192x8192x8位的D R A M芯片，按字节编址，支持突发（burst）传送方式,
对应存储器总线宽度为64位，每个D R A M 芯片内有一个行缓冲区（row buffer）。下列关于
该内存条的叙述中，不正确的是（ ）。
A . 内存条的容量为512 MB B . 采用多模块交叉编址方式
C . 芯片的地址引脚为26位 D . 芯片内行缓冲有8192x8位
18 . 下列选项中，属于指令集体系结构（ISA）规定的内容是（ ）。
L 指令字格式和指令类型 IL CPU的时钟周期
III.通用寄存器个数和位数 IV.加法器的进位方式
A . 仅 I、II B . 仅 I、in c . 仅 n、iv D. 仅 I、in、IV
/ 19.设计某指令系统时，假设采用16位定长指令字格式，操作码使用扩展编码方式，地址码为6
位，包含零地址、一地址和二地址3 种格式的指令。若二地址指令有12条，一地址指令有
254条，则零地址指令的条数最多为（ ）。
A. 0 B. 2 C. 64 D. 128
20.将高级语言源程序转换为可执行目标文件的主要过程是（
A . 预处理- 编译一汇编一链接 B . 预处理f 汇编一编译一链接
第3页 （共8页）C .预处理f 编译f 链接f 汇编 D .预处理f 汇编f 链接f 编译
21 . 下列关于中断I/O方式的叙述中，不正确的是（ ）。
A .适用于键盘、针式打印机等字符型设备
B .外设和主机之间的数据传送通过软件完成
C .外设准备数据的时间应小于中断处理时间
D .外设为某进程准备数据时CPU可运行其他进程
22 . 下列关于并行处理技术的叙述中，不正确的是（ ）。
A .多核处理器属于MIMD结构 B .向量处理器属于SIMD结构
C .硬件多线程技术只可用于多核处理器
D. SMP中所有处理器共享单一物理地址空间
23 . 下列关于多道程序系统的叙述中，不正确的是（ ）。
A .支持进程的并发执行 B .不必支持虚拟存储管理
C .需要实现对共享资源的管理 D .进程数越多CPU利用率越高
24 . 下列选项中，需要在操作系统进行初始化过程中创建的是（ ）。
A .中断向量表 B .文件系统的根目录
C ,硬盘分区表 D .文件系统的索引结点表
25 . 进程PO、Pl、P2和P3进入就绪队列的时亥IJ、优先级（值越小优先权越高）及CPU执行时间
如下表所示。
进程 进入就绪队列的时刻 优先级 CPU执行时间
P0 0 ms 15 100 ms
P1 10 ms 20 60 ms
P2 10 ms 10 20 ms
P3 15 ms 6 10 ms
若系统采用基于优先权的抢占式进程调度算法，则从0 ms时刻开始调度，到4个进程都
运行结束为止，发生进程调度的总次数为（
A. 4 B. 5 C. 6 D. 7
26 . 系统中有三个进程P0、Pl、P2及三类资源A、B、Co若某时刻系统分配资源的情况如下表
所示，则此时系统中存在的安全序列的个数为（ ）0
已分配资源数 尚需资源数 可用资源数
进程
A B C A B C A B C
P0 2 0 1 0 2 1
Pl 0 2 0 1 2 3 1 3 2
P2 1 0 1 0 1 3
A. 1 B. 2 C. 3 D. 4
27 . 下列关于CPU模式的叙述中，正确的是（ ）o
A. CPU处于用户态时只能执行特权指令 ,
B. CPU处于内核态时只能执行特权指令
C. CPU处于用户态时只能执行非特权指令
D. CPU处于内核态时只能执行非特权指令
28 . 下列事件或操作中，可能导致进程P 由执行态变为阻塞态的是（ ）。
I . 进程P读文件 II.进程P 的时间片用完
IIL 进程P 申请外设 IV .进程P执行信号量的wait（）操作
A .仅 I、IV B .仅 n、III C .仅皿、IV D ,仅 I、IIL IV
第4页 （共8页）29 .某进程访问的页b 不在内存中,导致产生缺页异常，该缺页异常处理过程中不一定包含的操
作 是 （ ）。 •
A .淘汰内存中的页 B .建立页号与页框号的对应关系
C .将页b 从外存读入内存 D .修改页表中页b 对应的存在位
30 . 下列选项中，不会影响系统缺页率的是（ ）。
A ,页置换算法 B .工作集的大小
C .进程的数量 D .页缓冲队列的长度
31 . 执行系统调用的过程涉及下列操作,其中由操作系统完成的是（
I . 保存断点和程序状态字 II.保存通用寄存器的内容
III.执行系统调用服务例程 IV .将CPU模式改为内核态
A .仅 I、III B .仅 II、III C .仅 II、IV D .仅 II、IIL IV
32 . 下列关于驱动程序的叙述中,不正确的是（ ）。
A .驱动程序与I/O控制方式无关
B .初始化设备是由驱动程序控制完成的
C .进程在执行驱动程序时可能进入阻塞态
D .读/写设备的操作是由驱动程序控制完成的
33 . 在ISO/OSI参考模型中，实现两个相邻结点间流量控制功能的是（ ）
o
A .物理层 B .数据链路层 C .网络层 D .传输层
34 . 在一条带宽为200 kHz的无噪声信道上，若采用4个幅值的ASK调制，则该信道的最大数据
传输速率是（ ）。
A. 200 kbps B. 400 kbps C. 800 kbps D. 1600 kbps
35 . 若某主机的IP地址是183.80.72.48,子网掩码是255.255.192.0,则该主机所在网络的网络地
址 是 （ ）
0
A. 183.80.0.0 B. 183.80.64.0 C. 183.80.72.0 D. 183.80.192.0
36 . 下图所示网络中的主机H 的子网掩码与默认网关分别是（ ）。
_ 喀 理 幽 信
Internet r 1"2_
[192.168.1.62/27
路由器
交换机 H
192.168.1.60
A. 255.255.255.192, 192.168.1.1 B. 255.255.255,192, 192.168.1.62
C. 255.255.255.224,192.168.1.1 D. 255.255.255.224,192.168.1.62
37 . 在 SDN网络体系结构中，SDN控制器向数据平面的SDN交换机下发流表时所使用的接口是
A ,东向接口 B .南向接口 C .西向接口 D .北向接口
38 . 假设主机甲和主机乙已建立一个TCP连接，最大段长MSS = 1K B ,甲一直有数据向乙发送,
当甲的拥塞窗口为16KB时，计时器发生了超时，则甲的拥塞窗口再次增长到16KB所需要
的时间至少是（ ）o
A. 4RTT B. 5RTT C. 11 RTT D. 16RTT
39 .假设客户C和服务器S 已建立一个TCP连接，通信往返时间RTT = 50 m s,最长报文段寿命
MSL = 800ms,数据传输结束后，C主动请求断开连接。若从C主动向S发出FIN段时刻算
起，则。和 S进入CLOSED状态所需的时间至少分别是（ 工
A. 850 ms, 50 ms B. 1650 ms, 50 ms
C. 850 ms, 75 ms D. 1650 ms, 75 ms
40.假设主机H 通过HTTP/1.1请求浏览某Web服务器S 上的Web页news408.htal, news408.html
第5页 （共8页）引用了同目录下的1幅图像，news408.html文件大小为1 MSS （最大段长），图像文件大小为
3 MSS, H 访问S 的往返时间RTT = 10 m s,忽略HTTP响应报文的首部开销和TCP段传输时
延。若 H 已完成域名解析，则从H 请求与S 建立TCP连接时刻起，到接收到全部内容止，
所需的时间至少是（ ）o
A. 30 ms B. 40 ms C. 50 ms D. 60 ms
二、综合应用题：41〜47小题，共70分。
4L （13分）已知非空二叉树T 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下:
type def struct { // MAX_S 工 ZE 为已定义常量
int SqBiTNode[MAX_SIZE]; 〃保存二叉树结点值的数组
int ElemNum; . 一 //实际占用的数组元素个数
} SqBiTree;
' T 市示后茬的结舌茬薪组SqBiTNode.申角二T袤奈。祠如…对于下函所示的的裸菲生二攵留
T1 和 T2,
请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若
是，则返回true,否则，返回false。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。
42. （10分）现有〃（«> 100000）个数保存在一维数组M 中，需要查找M 中最小的10个数。请
回答下列问题。
1）设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简述其算法思
想 （不需要程序实现）。
2）说明你所设计的算法平均情况下的时间复杂度和空间复杂度。
43. （15分）某 CPU中部分数据通路如题43图所示，其中，GPRs为通用寄存器组；FR为标志
寄存器，用于存放ALU产生的标志信息；带箭头虚线表示控制信号，如控制信号Read、Write
分别表示主存读、主存写，MDRin表示内部总线上数据写入MDR, MDRout表示MDR的内
容送内部总线。
第 6贝 （共 8贝）题43图
请回答下列问题。
1＞设ALU的输入端A、B及输出端F 的最高位分别为A . Bn及及5, FR中的符号标志和
溢出标志分别为SF和O F,则 SF的逻辑表达式是什么？ A加B、A减B 时OF的逻辑表
达式分别是什么？要求逻辑表达式的输入变量为A s B15及F15。
2）为什么要设置暂存器丫和Z?
3）若GPRs的输入端rs、rd分别为所读、写的通用寄存器的编号，则GPRs中最多有多少个
通用寄存器？ rs和：rd来自图中的哪个寄存器？已知GPRs内部有一个地址译码器和一个多
路选择器，rd应连接地址译码器还是多路选择器？
4）取指令阶段（不考虑PC增量操作）的控制信号序列是什么？若从发出主存读命令到主存
读出数据并传送到MDR共需5个时钟周期，则取指令阶段至少需要几个时钟周期？
5）图中控制信号由什么部件产生？图中哪些寄存器的输出信号会连到该部件的输入端？
44. （8分）假设某磁盘驱动器中有4个双面盘片,每个盘面有20000个磁道，每个磁道有500个
扇区，每个扇区可记录512字节的数据,盘片转速为7200 RPM（转/分）,平均寻道时间为5 ms。
请回答下列问题°
1）每个扇区包含数据及其地址信息，地址信息分为3个字段。这3个字段的名称各是什么？
对于该磁盘，各字段至少占多少位？
2） 一个扇区的平均访问时间约为多少？
3）若采用周期挪用DMA方式进行磁盘与主机之间的数据传送，磁盘控制器中的数据缓冲区
大小为64位，则在一个扇区读写过程中，DMA控制器向CPU发送了多少次总线请求？
若CPU检测到DMA控制器的总线请求信号时也需要访问主存,则DMA控制器是否可以
获得总线使用权?为什么？
45. （7分）某文件系统的磁盘块大小为4 K B ,目录项由文件名和
索引结点号构成，每个索引结点占256字节，其中包含直接
地址项10个，一级、二级和三级间接地址项各1个，每个地
址项占4 字节。该文件系统中子目录stu的结构如题45（a）图
所示，stu包含子目录course和文件doc, course子目录包含
文件course 1 和 course2。各文件的文件名、索引结点号、占
用磁盘块的块号如题45（b）图所示。
请回答下列问题。
第7页 （共8页）1）目录文件Stu中每个目录项的内容是什么？ 文件名 索引结点号 磁盘块号
2）文件doc占用的磁盘块的块号x 的值是多少？ stu 1 10
3）若目录文件course的内容已在内存，则打开文 course 2 20
件 coursel并将其读入内存，需要读几个磁盘 coursel 10 30
块？说明理由。 course2 100 40
4）若文件course!的大小增长到6 M B ,则为了存 doc 10 X
取 course2需要使用该文件索引结点的哪几级 题45(b)图
间接地址项？说明理由。
46 . （8 分）某进程的两个线程T1和T2并发执行A、B、C、D、E
和F共6个操作，其中T1执行A、E和F, T2执行B、C和D。
题46图表示上述6个操作的执行顺序所必须满足的约束：C在
A 和B 完成后执行，D 和E 在C 完成后执行，F 在E 完成后执
行。请使用信号量的wait。、signal。操作描述T1和T2之间的同
题46图
步关系，并说明所用信号量的作用及其初值。
47 . （9 分）某网络拓扑如题47图所示，R 为路由器，S为以太网交换机，AP是802.11接入点，
路由器的E0接口和DHCP服务器的IP地址配置如图中所示；H1与H2属于同一个广播域，
但不属于同一个冲突域；H2和H3属于同一个冲突域；H4和H5已经接入网络，并通过DHCP
动态获取了 IP地址。现有路由器、lOOBaseT以太网交换机和lOOBaseT集线器（Hub）三类
设备各若干台。
DHCP服务器
192.168.0.2/25
00-11-11-11-11-B1
192.168.0.4/25
00-11-11-11-11-E1
H2 H3 00-1M1-11-11-D1
题47图
请回答下列问题。
1）设备1和设备2 应该分别选择哪类设备？
2）若信号传播速度为2义1。8向5 ,以太网最小帧长为64 B ,信号通过设备2 时会产生额外的
L51尔的时间延迟，则H2与H3之间可以相距的最远距离是多少？
3）在 H4通过DHCP动态获取IP地址过程中，H4首先发送了 DHCP报文M, M 是哪种
DHCP报文？路由器E0接口能否收到封装M 的以太网帧？ S 向DHCP服务器转发的封装
M 的以太网帧的目的MAC地址是什么？
4）若H4向H5发送一个IP分组P ,则H5收到的封装P 的802.11帧的地址1、地址2 和地
址3分别是什么？
第8页 （共8页）
