文档内容
2021全国硕士研究生招生考试计算机学科专业基础试题
一、单项选择题
第01〜40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。
01.已知头指针h 指向一个带头结点的非空单循环链表，结点结构为
data next
其中next是指向直接后继结点的指针，P 是尾指针，q 是临时指针。现要删除该链表的第
一个元素，正确的语句序列是( )o
A. 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(q);
D. q = h-> next; h -> next = q-> next; if(p == q)p = h; free(q);
02.已知初始为空的队列Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出
队操作。若Q 的入队序列是1,2, 3, 4, 5 ,则不能得到的出队序列是( )
0
A. 5,4,3, 1,2 B. 5,3, 1,2,4 C. 4, 2, 1,3,5 D. 4, 1,3, 2, 5
03.已知二维数组A 按行优先方式存储，每个元素占用1个存储单元。若元素A[0][0]的存储地
址是100, A[3][3]的存储地址是220,则元素A[5][5]的存储地址是（ ）
0
A. 295 B. 300 C. 301 D. 306
04.某森林厂对应的二叉树为T,若T的先序遍历序列是a, b, d, c, e, g, f , 中序遍历序列是b, d,
a, e, g, c, f , 则尸中树的棵数是（ ）
o
A. 1 B. 2 C. 3 D. 4
05.若某二叉树有5个叶结点，其权值分别为10, 12, 16, 21, 30,则其最小的带权路径长度（WPL）
是 （ ）。
A. 89 B. 200 C. 208 D. 289
06.给定平衡二叉树如下图所示，插入关键字23后，根中的关键字是（ ）。
（20）
16 30
25 40
2021年计算机408统考真题 第 1 页，共 9 页A. 16 B. 20 C. 23 D. 25
07.给定如下有向图，该图的拓扑有序序列的个数是（ ）。
A. 1 B. 2 C. 3 D. 4
08.使用Dijkstra算法求下图中从顶点1到其余各顶点的最短路径，将当前找到的从顶点1到
顶点2, 3, 4, 5 的最短路径长度保存在数组dist中，求出第二条最短路径后，dist中的内容更
新为（ ）o
A. 26,3,14,6 B. 25, 3, 14, 6 C. 21,3, 14,6 D. 15,3, 14,6
09.在一棵高度为3 的3阶B树中，根为第1层，若第2层中有4个关键字，则该树的结点个
数最多是（ ）。
A. 11 B. 10 C. 9 D. 8
10.设数组 S[] = {93, 946, 372, 9, 146,151, 301, 485, 236, 327, 43, 892）, 采用最低位优先（LSD）
基数排序将S排列成升序序列。第 1趟分配、收集后，元素372之前、之后紧邻的元素分
别是（ ）o
A. 43,892 B. 236,301 C. 301,892 D. 485,301
11.将关键字6, 9, 1,5, 8, 4, 7依次插入到初始为空的大根堆H 中，得到的H 是 （ ）。
A. 9, 8, 7, 6, 5, 4, 1 B. 9, 8, 7,5,6, 1,4
C. 9, 8, 7, 5, 6, 4, 1 D. 9, 6, 7, 5, 8, 4, 1
12. 2017年公布的全球超级计算机TOP 500排名中，我国“神威•太湖之光”超级计算机蝉联
第一，其浮点运算速度为93.0146 PFLOPS,说明该计算机每秒钟内完成的浮点操作次数约
为 （ ）
0
A. 9.3x1013 次 B. 9.3X10” 次 . 9.3 千万亿次 D. 9.3 亿亿次
c
・ 002 • 2021年计算机408统考真题 第 2 页，共 9 页13.已知带符号整数用补码表示，变量x,y,z的机器数分别为FFFDH,FFDFH,7FFCH,下列结
论中，正确的是（ ）o
A .若x j 和z 为无符号整数，贝Ijzvxvy
B .若x j 和z 为无符号整数，贝UxVyVz
C .若x j 和z 为带符号整数，贝Ijxvyvz
D .若x j 和z 为带符号整数，贝仃vx〈z
14 . 下列数值中，不能用IEEE 754浮点格式精确表示的是（ ）。
A. 1.2 B. 1.25 C. 2.0 D. 2.5
15 . 某计算机的存储器总线中有24位地址线和32位数据线，按字编址，字长为32位。如果
00 0000H〜3FFFFFH为RAM区，那么需要512Kx8位的RAM芯片数为（ ）。
A. 8 B. 16 C. 32 D. 64
16 . 若计算机主存地址为32位，按字节编址，Cache数据区大小为32KB,主存块大小为32B,
采用直接映射方式和回写（Write Back）策略，则Cache行的位数至少是（ ）。
A. 275 B. 274 C. 258 D. 257
17 . 下列寄存器中，汇编语言程序员可见的是（ ）
o
I.指令寄存器 II.微指令寄存器 III.基址寄存器 IV .标志/状态寄存器
A .仅 I、II B .仅 I、IV C .仅 n、IV D .仅 ni、iv
18 . 下列关于数据通路的叙述中，错误的是（ ）
0
A .数据通路包含ALU等组合逻辑（操作）元件
B .数据通路包含寄存器等时序逻辑（状态）元件
C .数据通路不包含用于异常事件检测及响应的电路
D .数据通路中的数据流动路径由控制信号进行控制
19 . 下列关于总线的叙述中，错误的是（ ）
o
A .总线是在两个或多个部件之间进行数据交换的传输介质
B .同步总线由时钟信号定时，时钟频率不一定等于工作频率
C .异步总线由握手信号定时，一次握手过程完成一位数据交换
D .突发（Burst）传送总线事务可以在总线上连续传送多个数据
20 . 下列选项中，不属于I/O接口的是（ ）
o
A .磁盘驱动器 B .打印机适配器 C .网络控制器 D .可编程中断控制器
21 . 异常事件在当前指令执行过程中进行检测，中断请求则在当前指令执行后进行检测。下列
事件中，相应处理程序执行后，必须回到当前指令重新执行的是（ ）o
A .系统调用 B .页缺失 C. DMA传送结束 D .打印机缺纸
2021年计算机408统考真题 第 3 页，共 9 页 • 003 •22.下列是关于多重中断系统中CPU响应中断的叙述，其中错误的是（ ）
o
A .仅在用户态（执行用户程序）下，CPU才能检测和响应中断
B. CPU只有在检测到中断请求信号后，才会进入中断响应周期
C .进入中断响应周期时，CPU一定处于中断允许（开中断）状态
D .若CPU检测到中断请求信号，则一定存在未被屏蔽的中断源请求信号
23 . 下列指令中，只能在内核态执行的是（ ）o
A. trap指令 B .I/O指令 C .数据传送指令 D .设置断点指令
24 . 下列操作中，操作系统在创建新进程时，必须完成的是（ ）
0
I . 申请空白的进程控制块II.初始化进程控制块 m .设置进程状态为执行态
A .仅 I B .仅 I、II C .仅 I、III D .仅 n、III
25 . 下列内核的数据结构或程序中，分时系统实现时间片轮转调度需要使用的是（ ）o
I .进程控制块 II.时钟中断处理程序III.进程就绪队列 IV .进程阻塞队列
A .仅 II、III B .仅 I、IV C .仅 I、II、III D .仅 I、II、IV
26 . 某系统中磁盘的磁道数为200 （0-199）, 磁头当前在184号磁道上。用户进程提出的磁盘
访问请求对应的磁道号依次为184, 187, 176, 182, 199。若采用最短寻道时间优先调度算法
（SSTF）完成磁盘访问，则磁头移动的距离（磁道数）是 （ ）
o
A. 37 B. 38 C. 41 D. 42
27 . 下列事件中，可能引起进程调度程序执行的是（ ）
o
I . 中断处理结束II.进程阻塞 in .进程执行结束 iv .进程的时间片用完
A .仅 I、III B .仅 II、IV C .仅皿、IV D. I、n、in 和 IV
28 . 某请求分页存储系统的页大小为4KB,按字节编址。系统给进程P分配2个固定的页框,
并采用改进型Clock置换算法，进程P页表的部分内容如下表所示。
存在位 访问位 修改位
页框号
1：存在，0 :不存在 1：访问，0 :未访问 1：修改，0 :未修改
20 H 0 0 0
60 H 1 1 0
80 H 1 1 1
若P访问虚拟地址为02A01H的存储单元，则经地址变换后得到的物理地址是（ ）
0
A. 00A01H B. 20A01H C. 60A01H D. 80A01H
29 . 在采用二级页表的分页系统中，CPU页表基址寄存器中的内容是（ ）。
A .当前进程的一级页表的起始虚拟地址
• 004 • 2021年计算机408统考真题 第 4 页，共 9 页B .当前进程的一级页表的起始物理地址
C .当前进程的二级页表的起始虚拟地址
D .当前进程的二级页表的起始物理地址
3 0 .若目录dir下有文件filel,则为删除该文件内核不必完成的工作是（ ）
o
A .删除filel的快捷方式 B .释放filel的文件控制块
C .释放filel占用的磁盘空间 D .删除目录dir中与filel对应的目录项
31.若系统中有〃（〃2 2 ）个进程，每个进程均需要使用某类临界资源2个，则系统不会发生
死锁所需的该类资源总数至少是（ )o
A. 2 B. n C. 〃 + 1 D. 2n
3 2 .下列选项中，通过系统调用完成的操作是（ ）o
A .页置换 B .进程调度 C .创建新进程 D .生成随机整数
3 3 .在TCP/IP参考模型中，由传输层相邻的下一层实现的主要功能是（ ）。
A .对话管理 B .路由选择
C .端到端报文段传输 D .结点到结点流量控制
若下图为一段差分曼彻斯特编码信号波形，则其编码的二进制位串是（ ）
A. 1011 1001 B. 1101 0001 C. 0010 1110 D. 1011 0110
3 5 .现将一个IP网络划分为3 个子网, 若其中一个子网是192.168.9.128/26,则下列网络中,
不可能是另外两个子网之一的是（ ) O
A. 192.168.9.0/25 B. 192.168.9.0/26
C. 192.168.9.192/26 D. 192.168.9.192/27
36 . 若路由器向MTU = 800B的链路转发一个总长度为1580B的IP数据报（首部长度为20B）
时，进行了分片，且每个分片尽可能大，则第2 个分片的总长度字段和MF标志位的值分
别是（ ）o
A. 796,0 B. 796, 1 C. 800,0 D. 800, 1
37 . 某网络中的所有路由器均采用距离向量路由算法计算路由。若路由器E与邻居路由器A,B,
C和D之间的直接链路距离分别是8, 10, 12和6 ,且E收到邻居路由器的距离向量如下表
所示，则路由器E更新后的到达目的网络Netl〜Net4的距离分别是（ ）。
2021年计算机408统考真题 第 5 页，共 9 页 ・ 005 •目的网络 A的距离向量 B的距离向量 C的距离向量 D的距离向量
1 23 20 22
12 35 30 28
24 18 16 36
36 30 8 24
A. 9, 10, 12, 6 B. 9, 10, 28, 20 C. 9, 20, 12, 20 D. 9,20,28,20
38 . 若客户首先向服务器发送FIN段请求断开TCP连接，则当客户收到服务器发送的FIN段并
向服务器发送了 ACK段后，客户的TCP状态转换为（ ）。
A. CLOSE_WAIT B. TIME_WAIT C. FIN_WAIT_1 D. FIN_WAIT_2
39 . 若大小为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 时刻收到乙发送的序号seq = 601、确认序号ack_seq = 501、
接收窗口 rcvwnd = 500B的段，则甲在未收到新的确认段之前，可以继续向乙发送的数据序号
范围是（ ）。
二、综合应用题
第41〜47小题，共70分。
41 . （15分）已知无向连通图G 由顶点集P和边集E 组成，|^| > 0 ,当G 中度为奇数的顶点个
数为不大于2 的偶数时，G 存在包含所有边且长度为区|的路径（称为EL路径）。设图G
采用邻接矩阵存储，类型定义如下：
typedef struct{ //图的定义
int numVertices,numEdges;
//图中实际的顶点数和边数
char VerticesList[MAXV];
//顶点表。MAXV为已定义常量
int Edge[MAXV][MAXV]；
・ 006 ・ 2021年计算机408统考真题 第 6 页，共 9 页//邻接矩阵
}MGraph;
请设计算法int 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(int)*n);
//C++语言：count=new int [n];
for(i=0;i to) s ffi-, Jl!lj t1 �tiJ S 3t�*ITTr;J�¾{ti-?
3) M t 0 fiJ t 1 WHsJ, H2 �y��4:'x:fiJJL1-1=j.tl:t1J-'. Web i,JjfoJ;j<§�B"J$!J!? �4:'x:f1JITT¾fti-$9!?
$!J!ITT § ITT MAC ±-&±Jl::¾{ti-?
2021年计算机408统考真题 第 9 页，共 9 页 • 009 •
