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<n;i++) count[i]=0;
for(i=0;i<n-l;i++)
for(j=i + l;j <n;j ++)
if(a[i]<a[j]) count[j]++;
else count[i]++;
for(i=0;i<n;i++) b[count[i]]= a [i];
free (count) ; //C++语言：delete count;
)
请回答下列问题。
1 )若有 int a [ ] = {25,-10 25,10 l l 1 9 } ,b [6 ]则调用 cmpCountSort (a, b, 6)
z z z
后数组b 中的内容是什么？
2 )若a 中含有〃个元素，则算法执行过程中，元素之间的比较次数是多少？
3 )该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。
43. (15分)假定计算机M字长为16位，按字节编址，连接CPU和主存的系统总线中地址线
为20位、数据线为8位，采用16位定长指令字，指令格式及其说明如下：
格式 6位 2位 2位 2位 4位 指令功能或指令类型说明
R型 000000 rs Ft rd opl R[rd] - R[rs] opl R[rt]
含ALU运算、条件转移和访存
I型 op2 rs rt imm
操作3类指令
J型 op3 target PC 的低 10 位—target
其中，opl〜op3为操作码，rs, rt和rd为通用寄存器编号，R[r]表示寄存器i•的内容，imm
为立即数，target为转移目标的形式地址。请回答下列问题。
1) ALU的宽度是多少位？可寻址主存空间大小为多少字节？指令寄存器、主存地址寄存
器 (MAR)和主存数据寄存器(MDR)分别应有多少位？
2) R 型格式最多可定义多少种操作？ I 型和J 型格式总共最多可定义多少种操作？通用寄
• 007 •
2021年计算机408统考真题 第 7 页，共 9 页存器最多有多少个？
3）假定opl为0010和0011时，分别表示带符号整数减法和带符号整数乘法指令，则指令
01B2H的功能是什么（参考上述指令功能说明的格式进行描述）？若 1, 2, 3号通用寄
存器当前内容分别为B052H, 0008H, 0020H,则分别执行指令01B2H和01B3H后，3
号通用寄存器内容各是什么？各自结果是否溢出？
4）若采用I 型格式的访存指令中imm （偏移量）为带符号整数，则地址计算时应对imm
进行零扩展还是符号扩展？
5）无条件转移指令可以采用上述哪种指令格式？
44. （8 分）假设计算机M 的主存地址为24位，按字节编址；采用分页存储管理方式，虚拟
地址为30位，页大小为4 KB； TLB采用2路组相联方式和LRU替换策略，共8组。请回
答下列问题。
1）虚拟地址中哪几位表示虚页号？哪几位表示页内地址？
2）已知访问TLB时虚页号高位部分用作TLB标记，低位部分用作TLB组号，M 的虚拟
地址中哪几位是TLB标记？哪几位是TLB组号？
3）假设TLB初始时为空，访问的虚页号依次为10, 12, 16,7,26,4, 12和2 0 ,在此过程中，
哪一个虚页号对应的TLB表项被替换？说明理由。
4）若将M 中的虚拟地址位数增加到32位，则TLB表项的位数增加几位？
45. （7分）下表给出了整型信号量S 的wait （）和 signal。操作的功能描述，以及采用开/
关中断指令实现信号量操作互斥的两种方法。
功能描述 方法1 方法2
Semaphore S; Semaphore S; Semaphore S;
wait(S){ wait (S){ wait (S){
while(S<=0); 关中断； 关中断；
S=S-1; while(S<=0); while(S<=0);
) S=S-1; 开中断；
开中断； 关中断；
I
i J
S=S-1;
开中断；
J
signal(S){ signal (S){ signal(S){
S=S+1; 关中断； 关中断；
) S=S+1; S=S+1;
开中断； 开中断；
） ）
请回答下列问题。
1）为什么在wait （）和 signal。操作中对信号量S 的访问必须互斥执行？
2）分别说明方法1和方法2是否正确。若不正确，请说明理由。
3）用户程序能否使用开/关中断指令实现临界区互斥？为什么？
• 008 - 2021年计算机408统考真题 第 8 页，共 9 页46. C 8 7t) �itjHJLJ=IHJ!!ffi:ft7':1 Ja $Jffi:, �iffi:ffi-1-wi IR#�± 131 �-i23R, � i:r 'El. f{fittffi:13 1
� fjff ;Jc□ 7t IR lL fittffi:5 I � fjffJ =llf-� �Jg I� �JJ�1-?t IR ,r-rt�ft * #E, 7t IR *-i23R �iffl:J:
� ?t IR ITT ffr � � ta1i �ft-�, o �JI! ffi: ilii: :it!J 7t IVG tFf 1-?t 1R , 4:lt1-?t IR ITT ffi -1-wi IR ft nJi: 7t IR 131
�fiff, ffl r5 I ��?t!R i:p ITTt1�dt*#Eo *#E*ffl $�fr �51 �:Ji:it, � TtAfffitt ffi:131 �fi
fffD?tlR5l�f¥ff5'�. i£1m�tAff ROM "PITT5l�f¥ffo iw@J�rJUfoJ�o
1) *#E Ja $J Mfi i:p 1tf t* tJUr-J tJJ:tzi:lf-Uiff , 7t IR 5 I �f iff, ROM i:p ITT 5 I �fi ff, 1itt ffi:5 I
�fiff ITTtJiAT Jil_OOff¾fti-?
2)re�ffi:�ft7':1Ja$Jffl:�. 1m��JVG1tft*#EITT�-, fittffi:ITT���;rt�, �-�;rt�,
�•:m:*ff?t!R, tAff�41-ttftITT�m�ff¾tti-?
3)1ittffi:wilRITT�?tffiX#*#Effl§3RITTR�?t�¾ftffi2)�ITTU1-ttfti:r�JVGITT?
47. C9 7t) ���1,E1+:t,io� 47 OOJ=ifr�, Ll::t:�3'.t:�:rJL s iffiM�4Hl3ff R 1=j Internet 1Df:L �iEl3
ff iff�7tt:1HJ , :$:i-&�45 n� *ff, H L H2 ITT IP ±-&±JI::;¥□ MAC ±-&±Jl:::f,io 00 i:p J=ifr�o ft to �tLl H 1
ITT ARP *-t□ S ITT3t�*½J7'J�, Hl ft.tl:tt1J,tljffljxlj1ti:ffiffiM±!i11s www.abc.com i,w;Jhjj!oJ
Web n�*ff, ft t �tLl Ct1 > to) s ffi-<J-'.451:fiJ T tt• HTTP iw:JH�XITT Ll::t:�$9!, -WlfiU-,/\
1
to flj t 1A l'sJ � �*it:i {ffiiJ 1=j .11:UJ-'. Web ijj loJ x�ITT ��iffi ft o
1
{::El
Internet
R
Web!lll4}* -·"·•�-�
www.abc,com 192.1 68.1.1/25
192.168.1 126/25 192.168.1.3/25
00-11-22-33-44-bb 00-11-22-33-44-dd
192.168.1 .2/25
00-11-22-33-44-cc
iw@J�rJLli'oJ�o
1) M t flj t WHsJ, H1 �T HTTP z.j�i£iE1TTriJJ�1-mfflrzfiYJ,i5l? Mmffl!zffiJ�:tli!fiiHifzf,
0 1
�mfflm��fflx¾mMU®��*ff�mtt•ITT?
2):B' S ITT3t�*�:rg7'J<MAC ±-&±JI::, i4Tu □>, 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 •
