文档内容
2020全国硕士研究生招生考试
计算机学科专业基础试题参考答案
一、单项选择题
01. C 02. D 03. A 04. C 05. B 06. B 07. A 08. B
09. C 10. B 11. A 12. B 13. A 14. D 15. D 16. A
17. B 18. A 19. C 20. C 21. B 22. C 23. B 24. A
25. D 26. D 27. B 28. D 29. B 30. D 31. B 32. C
33. C 34. B 35. C 36. D 37. A 38. D 39. C 40. D
01.【解析】
上三角矩阵按列优先存储，先存储仅1个元素的第一列，再存储有2个元素的第二列，以
此类推。加7,2位于左下角，对应右上角的元素为加2, 7 ,在加2,7之前存有
第 1列：1
第2列：2
第6列：6
第7列：1
前面共存有1+2 + 3 + 4 + 5 + 6+1=22个元素（数组下标范围为0〜21）, 注意数组下标
从0开始，故加工7在数组N 中的下标为2 2 ,即加7,2在数组N 中的下标为22。
02. 【解析】
按题意，出入栈操作的过程如下：
操作 栈内元素 出栈元素
Push a
Push a b
Pop a b
Push a c
Pop a c
Push a d
Push ade
Pop a d e
故出栈序列为“ c,e。
03• 【解析】
二叉树采用顺序存储时，用数组下标来表示结点之间的父子关系。对于一棵高度为5 的二叉树，为了满足任意性，其 1〜5 层的所有结点都要被存储起来，即考虑为一棵高度为5
的满二叉树，总共需要存储单元的数量为1 + 2 + 4 + 8 + 16 = 31。
04• 【解析】
森林厂的先根遍历序列对应其二叉树T的先序遍历序列，森林尸的中根遍历序列对应其二
叉树T的中序遍历序列。即T的 先 序 遍 历 序 列 为 中 序 遍 历 序 列 为 6,凡&工内
co根据二叉树T的先序序列和中序序列可以唯一确定它的结构，构造过程如下：
可以得到二叉树T的后序序列为瓦工e, d,c, a.
05. 【解析】
每个选项都逐一验证，选项B 生成二叉排序树的过程如下:
显然选项B错误。
06. 【解析】
DFS是一个递归算法，在遍历过程中，先访问的顶点被压入栈底。设在图中有顶点匕，它
有后继顶点蚱 即 存 在 边 根 据 DFS的规则，修入栈后，必先遍历完其后继顶点后
片才会出栈，也就是说“会在v/之后出栈，在如题所指的过程中，必在％后打印。由于修
和U具有任意性，从上面的规律可以看出，输出顶点的序列是逆拓扑有序序列。
07. 【解析】
Kruskal算法：按权值递增顺序依次选取勿-1条边，并保证这〃-1条边不构成回路。初始
构造一个仅含〃个顶点的森林；第一步，选取权值最小的边S J)加入最小生成树；第二步,
剩余边中权值最小的边为(瓦加入最小生成树，第二步操作后权值最小的边3 J )不能选,
因为会与之前已选取的边形成回路；接下来依次选取权值9, 10, 11对应的边加入最小生成
树，此时6 个顶点形成了一棵树，最小生成树构造完成。按照上述过程，加到最小生成树
的边依次为(6 J), 3 ,m,(a, e), (c, e), 3, e)。其生成过程如下所示。
• 031 •第一步 第二步 第三步
选 砂 他 /> 选取边 选取边
第四步 第五步
选取边 选 破 〈a e>
08. 【解析】
关键路径是指权值之和最大而非边数最多的路径，故选项A 错误。选项B 正确，是关键路
径的概念。无论是存在一条还是存在多条关键路径，增加任一关键活动的时间都会延长工
程的工期，因为关键路径始终是权值之和最大的那条路径，选项C 错误。仅有一条关键路
径时，减少关键活动的时间会缩短工程的工期；存在多条关键路径时，缩短一条关键活动
的时间不一定会缩短工程的工期，缩短了路径长度的那条关键路径不一定还是关键路径，
选项D 错误。
09• 【解析】
这是一道简单的概念题。堆是一棵完全树，采用一维数组存储，故 I正确，II正确。大根
堆只要求根结点值大于左右孩子值，并不要求左右孩子值有序，in错误。堆的定义是递归
的，所以其左右子树也是大根堆，所以堆的次大值一定是其左孩子或右孩子，IV正确。
10• 【解析】
一个4 阶B 树的任意非叶结点至多含有加-1 = 3个关键字，在关键字依次插入的过程中,
会导致结点的不断分裂，插入过程如下所示。
得到根结点包含的关键字为6, 9o
11.【解析】
考虑较极端的情况，对于有序数组，直接插入排序的比较次数为〃- 1 , 简单选择排序的比
较次数始终为1 + 2 +… 1 = 1)/2, I正确。两种排序方法的辅助空间都是0(1),无
差别，II错误。初始有序时，移动次数均为0；对于通常情况，直接插入排序每趟插入都
• 032 •需要依次向后挪位，而简单选择排序只需与找到的最小元素交换位置，后者的移动次数少
很多，in 错误。
12 . 【解析】
机器字长是指CPU内部用于整数运算的数据通路的宽度。CPU内部数据通路是指CPU内
部的数据流经的路径及路径上的部件，主要是CPU内部进行数据运算、存储和传送的部件,
这些部件的宽度基本上要一致才能相互匹配。因此，机器字长等于CPU内部用于整数运算
的运算器位数和通用寄存器宽度。
13• 【解析】
C800 0000H = 1100 1000 0000 0000 0000 0000 0000 0000 o
将其转换为对应的float型或int型：
1 )为float型时，尾数隐藏最高位1 ,数符为1表示负数，阶码1001 0000 = 27+24= 128 + 16,
再减去偏置值127得到1 7 ,算出x值为-2。
2 )为int型时，带符号补码，为负数，数值部分取反加1 ,得011 1000 0000 0000 0000 0000
0000 0000,算出 X 值为-7x227。
14 . 【解析】
在32位计算机中，按字节编址，根据小端方式和按边界对齐的定义，给出变量a的存放方
式如下：
地址 _ 2020 FE00H 2020 FE01H 2020 FE02H 2020 FE03H
1 11 1
未知 未知
说明 xl (LSB) xl (MSB)
地址 _ 2020 FE04H 2020 FE05H 2020 FE06H 2020 FE07H
1 11
00H OOH 34H 12H |
说明 x2 (LSB) x2 (MSB)
于是，34H所在存储单元的地址为2020 FE06Ho
15 . 【解析】
Cache由SRAM组成；TLB通常由相联存储器组成，也可由SRAM组成。DRAM需要不
断刷新，性能偏低，不适合组成TLB和Cacheo选项A、B 和C都是TLB和Cache的特点。
16• 【解析】
48条指令需要6位操作码字段(25 <48<26), 4 种寻址方式需要2位寻址特征位(4 = 22),
还剩16-6-2 = 8位作为地址码，故直接寻址范围为0~255。注意，主存地址不能为负。
17. 【解析】
CPI表示执行指令所需的时钟周期数。对于一个程序或一台机器来说，其 CPI指执行该程
序或机器指令集中的所有指令所需的平均时钟周期数。对于单周期CPU,令指令周期= 时
钟周期，CPI=1, I正确。对于多周期CPU, CPU的执行过程分成几个阶段，每个阶段用
一个时钟去完成，每种指令所用的时钟数可以不同，CPI>1,II错误。对于基本流水线CPU,
让每个时钟周期流出一条指令，CPI = 1, in 正确。超标量流水线CPU在每个时钟周期内
• 033 -并发执行多条独立的指令，每个时钟周期流出多条指令，CPivi, IV错误。
18 . 【解析】
自陷是一种内部异常，A错误。在80x86中，用于程序调试的“断点设置”功能是通过“自
陷”方式实现的，选项B 正确。执行到自陷指令时，无条件或有条件地自动调出操作系统
内核程序进行执行，选项C 正确。CPU执行“陷阱指令”后，会自动地根据不同“陷阱”
类型进行相应的处理，然后返回到“陷阱指令”的下一条指令执行，选项D 正确。
19 . 【解析】
每个时钟周期传送2 次，故每秒传送的次数= 时钟频率x2 = 2.4Gx2/s。
总线带宽=每秒传送次数x2Bx2 = 2.4Gx2x2Bx2/s=19.2GB/s。
题中已给出总线带宽公式，降低了难度。公式中的“x2B”是因为每次传输16位数据，“x2”
是因为采用点对点全双工总线，两个方向可同时传输信息。
20 . 【解析】
访存时缺页属于内部异常，I错误；定时器到时描述的是时钟中断，属于外部中断，II正确；
网络数据包到达描述的是CPU执行指令以外的事件，属于外部中断，III正确。
21 . 【解析】
由CPU内部产生的异常称为内中断，内中断都是不可屏蔽中断。通过中断请求线INTR和，
NML从CPU外部发出的中断请求为外中断，通过INTR信号线发出的外中断是可屏蔽中
断，而通过NMI信号线发出的是不可屏蔽中断。不可屏蔽中断不受中断标志位的影响，即
使在关中断的情况下也会被响应，选项A 正确。不可屏蔽中断的处理优先级最高，任何时
候只要发生不可屏蔽中断，都要中止现行程序的执行，转到不可屏蔽中断处理程序执行，
选项C正确。CPU响应中断需要满足3个条件：①中断源有中断请求；② CPU允许中断
及开中断；③一条指令执行完毕，且没有更紧迫的任务。故选项B错误。
22 . 【解析】
周期挪用法由DMA控制器挪用一个或几个主存周期来访问主存，传送完一个数据字后立
即释放总线，是一种单字传送方式，每个字传送完后CPU可以访问主存，选项C 错误。
停止CPU访存法则是指在整个数据块的传送过程中，使CPU脱离总线，停止访问主存。
23• 【解析】
多个进程可同时以“读”或 “写”方式打开文件，操作系统并不保证写操作的互斥性，进
程可通过系统调用对文件加锁，保证互斥写（读者-写者问题），选项A错误。整个系统只
有一个系统打开文件表，同一个文件打开多次只需改变引用计数，选项B 正确。用户进程
的打开文件表关于同一个文件不一定相同，例如读写指针位置不一定相同，选项C错误。
进程关闭文件时，文件的引用计数减1 ,引用计数变为0 时才删除系统打开文件表中的表
项，选项D错误。
24 • 【解析】
索引分配支持变长的文件，同时可以随机访问文件的指定数据块，选项A 正确。链接分配
不支持随机访问，需要依靠指针依次访问，选项B错误。连续分配的文件长度固定，不支持
• 034 •可变文件长度(连续分配的文件长度虽然也可变，但是需大量移动数据，代价较大，相比之
下不太合适)，选项C 错误。动态分区分配是内存管理方式，不是磁盘空间的管理方式，选
项D错误。
25 . 【解析】
当CPU检测到中断信号后，由硬件自动保存被中断程序的断点(即程序计数器PC), I错
误。之后，硬件找到该中断信号对应的中断向量，中断向量指明中断服务程序入口地址(各
中断向量统一存放在中断向量表中，该表由操作系统初始化，in 正确)。接下来开始执行
中断服务程序，保存PSW、保存中断屏蔽字、保存各通用寄存器的值，并提供与中断信号
对应的中断服务，中断服务程序属于操作系统内核，II和IV正确。
26• 【解析】
多级反馈队列调度算法需要综合考虑优先级数量、优先级之间的转换规则等，就绪队列的
数量会影响长进程的最终完成时间，I正确；就绪队列的优先级会影响进程执行的顺序，II
正确；各就绪队列的调度算法会影响各队列中进程的调度顺序，m 正确；进程在就绪队列
中的迁移条件会影响各进程在各队列中的执行时间，IV正确。
27 . 【解析】
首先求出需求矩阵：
A B A B A B
4 4 2 3 2 1
Need = Max - Allocation = — =
3 1 2 1 1 0
3 4 1 2 2 2
由Allocation得知当前Available为(1, 0)。由需求矩阵可知，初始只能满足P2的需求，选
项A错误。P2释放资源后Available变为(3, 1 ),此时仅能满足P1的需求，选项C错误。
P1释放资源后Available变为(5, 4 ),可以满足P3的需求，得到的安全序列为P2, Pl, P3,
选项B 正确，选项D错误。
28 . 【解析】
I 影响缺页中断的频率，缺页率越高，平均访存时间越长；II和IV影响缺页中断的处理时
间，中断处理时间越长，平均访存时间越长；皿影响访问页表和访问目标物理地址的时间，
故I、II、III和IV均正确。
29 . 【解析】
父进程与子进程当然可以并发执行，选项A 正确。父进程可与子进程共享一部分资源，但
不能共享虚拟地址空间，在创建子进程时，会为子进程分配资源，如虚拟地址空间等，选
项B 错误。临界资源一次只能为一个进程所用，选项D 正确。进程控制块PCB是进程存
在的唯一标志，每个进程都有自己的PCB,选项C 正确。
30• 【解析】
设备可视为特殊文件，选项A 正确。用户使用逻辑设备名来访问物理文件，有利于设备独
立性，选项B 正确。通过逻辑设备名访问物理设备时，需要建立逻辑设备和物理设备之间
的映射关系，选项C正确。应用程序按逻辑设备名访问设备，再经驱动程序的处理来控制
• 035 •物理设备，若更换物理设备，则只需更换驱动程序，而无须修改应用程序，选项D 错误。
31 . 【解析】
在总长为64字节的目录项中，索引结点占4 字节，即32位。不同目录下的文件的文件名
可以相同，所以在考虑系统创建最多文件数量时，只需考虑索引结点的个数，即创建文件
数量上限= 索引结点数量上限。整个系统中最多存储 个索引结点，因此整个系统最多
232
可以表示
232
个文件，选项B 正确。
32 . 【解析】
实现临界区互斥需满足多个准则。“忙则等待”准则，即两个进程不能同时访问临界区，I
正确。 “空闲让进”准则，若临界区空闲，则允许其他进程访问，II正确。 “有限等待”
准则，即进程应该在有限时间内访问临界区，III正确。I、II和m 是互斥机制必须遵循的
原则。IV是 “让权等待”准则，不一定非得实现，如皮特森算法。
33 • 【解析】
协议由语法、语义和时序（又称同步）三部分组成。语法规定了通信双方彼此“如何讲”，
即规定了传输数据的格式。语义规定了通信双方彼此“讲什么”，规定了所要完成的功能，
如通信双方要发出什么控制信息、执行的动作和返回的应答。时序规定了信息交流的次序。
由图可知发送方与接收方依次交换信息，体现了协议三要素中的时序要素。
34 . 【解析】
虚电路服务需要有建立连接过程，每个分组使用短的虚电路号，属于同一条虚电路的分组
按照同一路由进行转发，分组到达终点的顺序与发送顺序相同，可以保证有序传输，不需
要为每条虚电路预分配带宽。
35 . 【解析】
网络层设备路由器可以隔离广播域和冲突域；链路层设备普通交换机只能隔离冲突域；物
理层设备集线器、中继器既不能隔离冲突域又不能隔离广播域。因此，题中共有2 个广播
域、4 个冲突域。
36 . 【解析】
发送数据帧和确认帧的时间均为t= 1000x8b/10kbps = 800mso
• 036 -发送周期 T= 800ms + 200ms + 800ms + 200ms = 2000ms
o
信道利用率=//TxlOO% = 800/2000x100% = 40%。
37. 【解析】
为了尽量避免碰撞，802.11规定，所有站在完成发送后，必须等待一段很短的时间（继续
监听）才能发送下一帧。这段时间称为帧间间隔（InterFrame Space, IFS）。帧间间隔的长
短取决于该站要发送的帧的类型。IEEE 802.11使用3种帧间间隔：
DIFS （分布式协调IFS）：最长的IFS,优先级最低，用于异步帧竞争访问的时延。
PIFS （点协调IFS）：中等长度的IFS,优先级居中，在PCF操作中使用。
SIFS （短IFS）：最短的IFS,优先级最高，用于需要立即响应的操作。
网络中的控制帧及所接收数据的确认帧都采用SIFS作为发送之前的等待时延。当结点要发
送数据帧时，载波监听到信道空闲时，需等待DIFS后发送RTS预约信道，图中IFS1对应
的是帧间间隔DIFS,时间最长，图中IFS2、IFS3、IFS4对应SIFS。
38• 【解析】
由于慢开始门限ssthresh可以根据需求设置，为了求拥塞窗口从8KB增长到32KB所需的
最长时间，可以假定慢开始门限小于等于8KB,只要不出现拥塞，拥塞窗口就都是加法增
大，每经历一个传输轮次（RTT）,拥塞窗口逐次加1,所需最长时间为（32-8）x2ms = 48ms。
39. 【解析】
甲与乙建立TCP连接时发送的SYN段中的序号为1000,则在数据传输阶段所用的起始序
号为1001；断开连接时，甲发送给乙的FIN段中的序号为5001,在无任何重传的情况下，
甲向乙已经发送的应用层数据的字节数为5001- 1001 =4000o
40• 【解析】
题中RTT均为局域网内主机（主机H、本地域名服务器）访问Internet上各服务器的往返
时间，且忽略其他时延，因此主机H 向本地域名服务器的查询时延忽略不计。最短时间：
本地主机中有该域名到IP 地址对应的记录，因此不需要DNS查询时延，直接和
www.abc.com服务器建立TCP连接再进行资源访问，TCP连接建立需要1个RTT,接着发
送访问请求并收到服务器资源响应需要1个RTT,共计2个RTT,即20ms；最长时间：本
地主机递归查询本地域名服务器（延时忽略），本地服务器依次迭代查询根域名服务器、com
顶级域名服务器、abc.com域名服务器，共3个RTT,查询到IP地址后，将该映射返回给
主机H ,主机H 和www.abc.com服务器建立TCP连接再进行资源访问，共2个RTT,因
此最长时间需要3+2 = 5个RTT,即50ms。
二、综合应用题
41• 【解析】
分析。由0 =卜一回+ |6-°| + |。一4 2 0 得：
① 当 a = 6 = c 时，距离最小。
② 其余情况。不失一般性，假 设 观 察 下 面 的 数 轴 :
• 037 •L\ L?
a b L3 c
L = |df — Z)|, L = |Z? — c| , Z = |c — a| , Z) = |<7 — Z)| + — c| + |c — a| = Z + Z + £ = 2L
x 2 3 t 2 3 3
由。的表达式可知，事实上决定。大小的关键是々和。之间的距离，于是问题就可以简化
为每次固定c找一个a使得4 =卜-司最小。
1 )算法的基本设计思想
①使用。min记录所有已处理过的三元组的最小距离，初值为一个足够大的整数。
②集合Si、S?和区分别保存在数组A、B、C 中。数组的下标变量％ =/ = k=0,当》<|引、
/<圆|且左〈冈时(同表示集合S 中的元素个数)，循环执行a)〜c)。
a)计算(A[4,B[/],C因)的距离。； (计算Q)
b )若。VOmin，贝 ljQmin=。； (更新。)
c)将A[4,B[/],C因中的最小值的下标+1； (对照分析：最小值为4 ,最大值为C,
这里。不变而更新试图寻找更小距离。)
③输出。min，结束。
2 )算法实现：
#define INT_MAX 0x7fffffff
int abs_(int a) {〃计算绝对值
if(a<0) return -a;
else return a;
)
bool xls_min (int a, int b, int c) { 〃a是否是三个数中的最小值
if(a<-b&&a<=c) return true;
return false;
)
int findMinofTrip(int A[],int n,int B[],int m,int C[] int p){
z
//D_min用于记录三元组的最小距离，初值赋为工NT_MAX
int i-0 j=0,k=0,D_min=INT_MAX,D;
r
while(i0){
D-abs_(A[i]-B[j] )+abs_(B[j]-C[k] )+abs__(C[k]-A[i]); 〃计算 D
if (D=(x+1)*(x+1))
x=x+l;
A. O(log〃) B. O ( n )2/l C. O ( n ) D. O(«2)
02.若将一棵树T转化为对应的二叉树BT,则下列对B T 的遍历中，其遍历序列与T 的后根遍
历序列相同的是( )o
A . 先序遍历 B . 中序遍历 C . 后序遍历 D . 按层遍历
03.对〃个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则〃的值是
( )o
A. 56 B. 57 C. 58 D. 60
04.在任意一棵非空平衡二叉树(AVL树)方中，删除某结点y之后形成平衡二叉树八，再将
y插入72形成平衡二叉树73。下 列 关 于 与 A 的叙述中，正确的是( )o
L 若y是Ti的叶结点，则”与网可能不相同
II . 若y不是看的叶结点，则方与北一定不相同
III . 若y不是看的叶结点，则Ti与73一定相同
A . 仅 I B . 仅 n C . 仅 I、II D . 仅 I、III
05.下图所示的A O E 网表示一项包含8个活动的工程。活动 d 的最早开始时间和最迟开始时间
分别是( )0
A. 3 和 7 B. 12 和 12 C. 12 和 14 D. 15 和 15
06.用有向无环图描述表达式(x + y)((x+，)/%)，需要的顶点个数至少是( )。
