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