绝密★启用前
全国硕士研究生入学统一考试
计算机科学与技术学科联考
2022年全国硕士研究生招生考试
计算机学科专业基础试题
(科目代码:408)
考生注意事项
1 .答题前,考生在试题册指定位置上填写考生编号和考生姓名;在答题卡指定位置上填写报
考单位、考生姓名和考生编号,并涂写考生编号信息点。
2 . 考生须把试题册上的“试卷条形码”黏贴条取下,黏贴在答题卡的“试卷条形码黏贴位置”
框中,不按规定黏贴条形码而影响评卷结果的,责任由考生自负。
3 . 选择题的答案必须涂写在答题卡和相应题号的选项上,非选择题的答案必须书写在答题卡
指定位置的边框区城内,超出答题区域书写的答案无效;在草稿纸、试题册上答题无效。
4 . 填(书)写部分必须使用黑色字迹签字笔书写,字迹工整、笔迹清楚;涂写部分必须使用
2B铅笔涂写。
5 . 考试结束,将答题卡和试题册按规定交回。
(以下信息考生必须认真填写)
考生编号
考生姓名
一、单项选择题:01〜4 0 小题,每小题2 分,共8 0 分。下列每题给出的四个选项中,只有一个
选项是最符合题目要求的。
0 1 . 下列程序段的时间复杂度是(
)。
…
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.
0 2 . 给定有限符号集S, in 和。u t均为S 中所有元素的任意排列。对于初始为空的栈S T ,下列
叙述中,正确的是(
)0
A . 若in 是ST 的入栈序列,则不能判断。u t是否为其可能的出栈序列
B . 若out是ST 的出栈序列,则不能判断in 是否为其可能的入栈序列
C . 若in 是ST 的入栈序列,out是对应in 的出栈序列,则in 与out 一定不同
D . 若in 是ST 的入栈序列,out是对应in 的出栈序列,则in 与out可能互为倒序
0 3 . 若结点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
0 4 . 若三叉树T 中有244个结点(叶结点的高度为1), 则T 的高度至少是(
)0
A. 8
B. 7
C. 6
D. 5
0 5 . 对任意给定的含〃(" > 2 )个字符的有限集S , 用二叉树表示S 的哈夫曼编码集和定长编码
集,分别得到二叉树T 1和T2。下列叙述中,正确的是(
)0
A. T 1与T 2 的结点数相同
B. T 1的高度大于T 2的高度
C . 出现频次不同的字符在T 1 中处于不同的层
D . 出现频次不同的字符在T 2 中处于相同的层
0 6 . 对于无向图G = (Y E ), 下列选项中,正确的是(
)。
A . 当|V |> |E |时,G 一定是连通的
B . 当|V |〈|E |时,G 一定是连通的
C . 当|V| = |E |T 时,G 一定是不连通的
D . 当|V |> |E |+ 1 时,G 一定是不连通的
0 7 . 下图是一个有10个活动的A O E 网,时间余量最大的
,活动是(
)。
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
0 9 . 下列因素中,影响散列(哈希)方法平均查找长度的是(
)0
I . 装填因子
I I . 散列函数
i n . 冲突解决策略
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 待排序元素数量很少
i n . 要求空间复杂度为o (D
I V . 要求排序算法是稳定的
A , 仅 I、II
B , 仅 HI、IV
C . 仅 I、n 、IV
D. I、II、in、IV
12 . 某计算机主频为1 G H z , 程序P 运行过程中,共执行了 10000条指令,其中,80%的指令执
行平均需1 个时钟周期,20% 的指令执行平均需10个时钟周期。程序P 的平均CPI和CPU
执行时间分别是(
)o
A. 2.8,2811s
B. 28,28 pis
C. 2.8, 28 ms
13 . 32位补码所能表示的整数范围是(
)o
A. -232- 231-1
B. -231- 2 31-1
C. -232- 2 32-l
14 . -04375的IEEE 754单精度浮点数表示为(
)。
A. BEEO 0000H
B. BF60 0000H
C. BF70 0000H
D. 28, 28 ms
D. -231- 2 32-l
D. COEO 0000H
15 . 某计算机主存地址为24位,采用分页虚拟存储管理方式,虚拟地址空间大小为4 G B , 页大小为
4 K B , 按字节编址。某进程的页表部分内容如下表所示。
C . 得到主存地址01 8840H
D . 检测到缺页异常
16 .若计算机主存地址为32位,按字节编址,某Cache的数据区容量为32 K B , 主存块大小为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 M B
B . 采用多模块交叉编址方式
C . 芯片的地址引脚为26位
D . 芯片内行缓冲有8192x8位
18 . 下列选项中,属于指令集体系结构(ISA)规定的内容是(
)。
L
指令字格式和指令类型
IL C P U 的时钟周期
III.通用寄存器个数和位数
I V . 加法器的进位方式
A . 仅 I、II
B . 仅 I、in
c . 仅 n 、iv
D. 仅 I、in、IV
/ 1 9 . 设计某指令系统时,假设采用16位定长指令字格式,操作码使用扩展编码方式,地址码为6
位,包含零地址、一地址和二地址3 种格式的指令。若二地址指令有1 2 条,一地址指令有
254条,则零地址指令的条数最多为(
)。
A. 0
B. 2
C. 64
D. 128
2 0 . 将高级语言源程序转换为可执行目标文件的主要过程是(
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、P l、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 m s时刻开始调度,到4 个进程都
运行结束为止,发生进程调度的总次数为(
A. 4
B. 5
C. 6
D. 7
26 . 系统中有三个进程P0、P l、P 2 及三类资源A、B、C o 若某时刻系统分配资源的情况如下表
所示,则此时系统中存在的安全序列的个数为(
)0
进程
已分配资源数
尚需资源数
可用资源数
A
B
C
A
B
C
A
B
C
P0
2
0
1
0
2
1
1
3
2
Pl
0
2
0
1
2
3
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 读文件
I I . 进程P 的时间片用完
I I L 进程P 申请外设
I V .进程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 . 进程的数量
31 . 执行系统调用的过程涉及下列操作,
D . 页缓冲队列的长度
其中由操作系统完成的是(
I . 保存断点和程序状态字
I I I . 执行系统调用服务例程
A . 仅 I、III
B . 仅 II、III
I I . 保存通用寄存器的内容
I V . 将CPU模式改为内核态
C . 仅 II、IV
D . 仅 II、IIL IV
32 . 下列关于驱动程序的叙述中,不正确的是(
)。
A . 驱动程序与I/O 控制方式无关
B . 初始化设备是由驱动程序控制完成的
C . 进程在执行驱动程序时可能进入阻塞态
D . 读/写设备的操作是由驱动程序控制完成的
33 . 在ISO/OSI参考模型中,实现两个相邻结点间流量控制功能的是(
)o
A . 物理层
B . 数据链路层
C . 网络层
D . 传输层
34 . 在一条带宽为200 kH z的无噪声信道上,若采用4 个幅值的A SK 调制,则该信道的最大数据
传输速率是(
)。
A. 200 kbps
B. 400 kbps
C. 800 kbps
D. 1600 kbps
35 . 若某主机的I P 地址是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
B. 255.255.255,192, 192.168.1.62
D. 255.255.255.224,192.168.1.62
A. 255.255.255.192, 192.168.1.1
C. 255.255.255.224,192.168.1.1
37 . 在SD N 网络体系结构中,SD N 控制器向数据平面的SD N 交换机下发流表时所使用的接口是
A , 东向接口
B . 南向接口
C . 西向接口
D . 北向接口
38 . 假设主机甲和主机乙已建立一个TCP连接,最大段长MSS = 1 K B ,甲一直有数据向乙发送,
当甲的拥塞窗口为16K B 时,计时器发生了超时,则甲的拥塞窗口再次增长到16K B所需要
的时间至少是(
)o
A. 4RTT
B. 5RTT
C. 11 RTT
D. 16RTT
39 .假设客户C 和服务器S 已建立一个TCP连接,通信往返时间RTT = 50 m s , 最长报文段寿命
MSL = 8 0 0 m s ,数据传输结束后,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
4 0 . 假设主机H 通过HTTP/1.1请求浏览某W eb服务器S 上的W eb页news408.htal, news408.html
第5 页(共8 页)
引用了同目录下的1 幅图像,news408.html文件大小为1 MSS (最大段长),图像文件大小为
3 MSS, H 访问S 的往返时间RTT = 10 m s ,忽略HTTP响应报文的首部开销和TCP段传输时
延。若H 已完成域名解析,则从H 请求与S 建立TC P连接时刻起,到接收到全部内容止,
所需的时间至少是(
)o
A. 30 ms
B. 40 ms
C. 50 ms
D. 60 ms
二、综合应用题:41〜4 7 小题,共7 0 分。
4L (13分)已知非空二叉树T 的结点值均为正整数,采用顺序存储方式保存,数据结构定义如下:
type def struct {
// MAX_S 工 ZE 为已定义常量
int SqBiTNode[MAX_SIZE];
〃保存二叉树结点值的数组
int ElemNum; .
一
/ / 实际占用的数组元素个数
} SqBiTree;
'
T 市示后茬的结舌茬薪组SqBiTNode.申角二T袤奈。祠如…对于下函所示的的裸菲生二攵留
T1 和 T2,
请设计一个尽可能高效的算法,判定一棵采用这种方式存储的二叉树是否为二叉搜索树,若
是,则返回tr u e ,否则,返回false。要求:
1)给出算法的基本设计思想。
2 )根据设计思想,采用C 或C++语言描述算法,关键之处给出注释。
42. (10分)现有〃(« > 100000)个数保存在一维数组M 中,需要查找M 中最小的10个数。请
回答下列问题。
1)设计一个完成上述查找任务的算法,要求平均情况下的比较次数尽可能少,简述其算法思
想(不需要程序实现)。
2)说明你所设计的算法平均情况下的时间复杂度和空间复杂度。
43. (1 5 分)某C P U 中部分数据通路如题4 3 图所示,其中,GPRs为通用寄存器组;F R 为标志
寄存器,用于存放ALU产生的标志信息;带箭头虚线表示控制信号,如控制信号Read、Write
分别表示主存读、主存写,MDRin表示内部总线上数据写入MDR, MDRout表示M DR的内
容送内部总线。
第6 贝(共8 贝)
题4 3 图
请回答下列问题。
1>设ALU的输入端A、B 及输出端F 的最高位分别为A . B n及及5, F R 中的符号标志和
溢出标志分别为SF和O F ,则S F 的逻辑表达式是什么? A 加B、A 减B 时O F 的逻辑表
达式分别是什么?要求逻辑表达式的输入变量为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 ,目录项由文件名和
索引结点号构成,每个索引结点占2 5 6 字节,其中包含直接
地址项10个,一级、二级和三级间接地址项各1 个,每个地
址项占4 字节。该文件系统中子目录stu 的结构如题45(a)图
所示,stu包含子目录course和文件doc, course子目录包含
文件course 1 和course2。各文件的文件名、索引结点号、占
用磁盘块的块号如题45(b)图所示。
请回答下列问题。
第7 页(共8 页)
间接地址项?说明理由。
1)目录文件Stu中每个目录项的内容是什么?
文件名
索引结点号
磁盘块号
2 )文件d o c占用的磁盘块的块号x 的值是多少?
stu
1
10
3)若目录文件course的内容已在内存,则打开文
course
2
20
件c o u rsel并将其读入内存,需要读几个磁盘
coursel
10
30
块?说明理由。
course2
100
40
4 )若文件course!的大小增长到6 M B ,则为了存
doc
10
X
取course2需要使用该文件索引结点的哪几级
题45(b)图
46 . (8 分)某进程的两个线程T 1 和T 2 并发执行A、B、C、D、E
和F 共6 个操作,其中T 1执行A、E 和F, T 2执行B、C 和D 。
题4 6 图表示上述6 个操作的执行顺序所必须满足的约束:C 在
A 和B 完成后执行,D 和E 在C 完成后执行,F 在E 完成后执
行。请使用信号量的wait。、signal。操作描述T 1和T 2之间的同
步关系,并说明所用信号量的作用及其初值。
题4 6 图
47 . (9 分)某网络拓扑如题4 7 图所示,R 为路由器,S 为以太网交换机,A P 是802.11接入点,
路由器的E 0接口和DHCP服务器的IP 地址配置如图中所示;H 1与H 2属于同一个广播域,
但不属于同一个冲突域;H 2和H 3属于同一个冲突域;H 4和H 5 已经接入网络,并通过DHCP
动态获取了 I P 地址。现有路由器、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
题4 7 图
请回答下列问题。
1)设备1 和设备2 应该分别选择哪类设备?
2 )若信号传播速度为2义1。8向5 , 以太网最小帧长为64 B , 信号通过设备2 时会产生额外的
L 51尔的时间延迟,则H 2与H 3之间可以相距的最远距离是多少?
3)在H 4 通过DHCP动态获取I P 地址过程中,H 4 首先发送了 DHCP报文M, M 是哪种
DHCP报文?路由器E 0接口能否收到封装M 的以太网帧? S 向DHCP服务器转发的封装
M 的以太网帧的目的M AC地址是什么?
4 )若H 4 向H 5 发送一个IP 分组P , 则H 5 收到的封装P 的802.11帧的地址1、地址2 和地
址3 分别是什么?
第8 页(共8 页)