2020全国硕士研究生招生考试计算机学科专业基础试题

一、单项选择题

第01~40小题,每小题2分,共80分。下列每题给出的四个选项中,只有一个选项最符合试题要求。

01.将一个10×10对称矩阵M的上三角部分的元素mi,j(1≤i≤j≤10)按列优先存入C语言的一维数组N中,元素m7,2在N中的下标是()。
C
02.对空栈S进行Push和Pop操作,入栈序列为a,b,c,d,e,经过Push,Push,Pop,Push,Pop,Push, Push,Pop操作后得到的出栈序列是()。
D
03.对于任意一棵高度为5且有10个结点的二叉树,若采用顺序存储结构保存,每个结点占1个存储单元(仅存放结点的数据信息),则存放该二叉树需要的存储单元数量至少是()。
A
二叉树采用顺序存储时,用数组下标来表示结点之间的父子关系。对于一棵高度为5的二叉树,为了满足任意性,其1~5层的所有结点都要被存储起来,即考虑为一棵高度为5的满二叉树,总共需要存储单元的数量为1+2+4+8+16=31。
04.己知森林F及与之对应的二叉树T,若F的先根遍历序列是a,b,c,d,e,,中根遍历序列是 b,a,d,fe,c,则T的后根遍历序列是()。
C
05.
B
06.修改递归方式实现的图的深度优先搜索(DFS)算法,将输出(访问)顶点信息的语句移到退出递归前(即执行输出语句后立刻退出递归)。采用修改后的算法遍历有向无环图G,若输出结果中包含G中的全部顶点,则输出的顶点序列是G的()。
B
07.已知无向图G如下所示,使用克鲁斯卡尔(Kruskal)算法求图G的最小生成树,加到最小生成树中的边依次是()。
A
Kruskal算法:按权值递增顺序依次选取n-1条边,并保证这n-1条边不构成回路。初始构造一个仅含n个顶点的森林;第一步,选取权值最小的边(b,f)加入最小生成树;第二步,剩余边中权值最小的边为(b,d),加入最小生成树,第二步操作后权值最小的边(d,f)不能选,因为会与之前已选取的边形成回路;接下来依次选取权值9,10,11对应的边加入最小生成树,此时6个顶点形成了一棵树,最小生成树构造完成。按照上述过程,加到最小生成树的边依次为(b,f),(b,d),(a,e),(c,e),(b,e)。其生成过程如下所示。
08.若使用AOE网估算工程进度,则下列叙述中正确的是()。
B
关键路径是指权值之和最大而非边数最多的路径,故选项A错误。选项B正确,是关键路径的概念。无论是存在一条还是存在多条关键路径,增加任一关键活动的时间都会延长工程的工期,因为关键路径始终是权值之和最大的那条路径,选项C错误。仅有一条关键路径时,减少关键活动的时间会缩短工程的工期;存在多条关键路径时,缩短一条关键活动的时间不一定会缩短工程的工期,缩短了路径长度的那条关键路径不一定还是关键路径,选项D错误。
09.下列关于大根堆(至少含2个元素)的叙述中,正确的是()。
Ⅰ.可以将堆视为一棵完全二叉树
Ⅱ.可以采用顺序存储方式保存堆
Ⅲ.可以将堆视为一棵二叉排序树
Ⅳ.堆中的次大值一定在根的下一层
C
这是一道简单的概念题。堆是一棵完全树,采用一维数组存储,故I正确,Ⅱ正确。大根堆只要求根结点值大于左右孩子值,并不要求左右孩子值有序,Ⅲ错误。堆的定义是递归的,所以其左右子树也是大根堆,所以堆的次大值一定是其左孩子或右孩子,Ⅳ正确。
10.依次将关键字5,6,9,13,8,2,12,15插入初始为空的4阶B树后,根结点中包含的关键字是()。
B
11.对大部分元素已有序的数组进行排序时,直接插入排序比简单选择排序效率更高,其原因是()。
I.直接插入排序过程中元素之间的比较次数更少
Ⅱ.直接插入排序过程中所需要的辅助空间更少
Ⅲ.直接插入排序过程中元素的移动次数更少
A
考虑较极端的情况,对于有序数组,直接插入排序的比较次数为n-1,简单选择排序的比较次数始终为1+2+…+n-1=n(n-1)/2,I正确。两种排序方法的辅助空间都是O(1),无差别,Ⅱ错误。初始有序时,移动次数均为0;对于通常情况,直接插入排序每趟插入都需要依次向后挪位,而简单选择排序只需与找到的最小元素交换位置,后者的移动次数少很多,Ⅲ错误。
12.下列给出的部件中,其位数(宽度)一定与机器字长相同的是()。
I.ALU
Ⅱ.指令寄存器
Ⅲ.通用寄存器
Ⅳ.浮点寄存器
B
机器字长是指CPU内部用于整数运算的数据通路的宽度。CPU内部数据通路是指CPU内部的数据流经的路径及路径上的部件,主要是CPU内部进行数据运算、存储和传送的部件,这些部件的宽度基本上要一致才能相互匹配。因此,机器字长等于CPU内部用于整数运算的运算器位数和通用寄存器宽度。
13.已知带符号整数用补码表示,float型数据用IEEE754标准表示,假定变量x的类型只可能是int或float,当x的机器数为C800 0000H时,x的值可能是()。
A
14.
D
15.下列关于TLB和Cache的叙述中,错误的是()。
D
Cache由SRAM组成;TLB通常由相联存储器组成,也可由SRAM组成。DRAM需要不断刷新,性能偏低,不适合组成TLB和Cache。选项A、B和C都是TLB和Cache的特点。
16.某计算机采用16位定长指令字格式,操作码位数和寻址方式位数固定,指令系统有48条指令,支持直接、间接、立即、相对4种寻址方式。单地址指令中,直接寻址方式的可寻址范围是()。
A
48条指令需要6位操作码字段(25 < 48 < 26),4种寻址方式需要2位寻址特征位(4=22),还剩16-6-2=8位作为地址码,故直接寻址范围为0~255。注意,主存地址不能为负。
17.下列给出的处理器类型中,理想情况下,CPI为1的是()。
I.单周期CPU
Ⅱ.多周期CPU
Ⅲ.基本流水线CPU
Ⅳ.超标量流水线CPU
B
CPI表示执行指令所需的时钟周期数。对于一个程序或一台机器来说,其CPI指执行该程序或机器指令集中的所有指令所需的平均时钟周期数。对于单周期CPU,令指令周期=时钟周期,CPI=1,I正确。对于多周期CPU,CPU的执行过程分成几个阶段,每个阶段用一个时钟去完成,每种指令所用的时钟数可以不同,CPI>1,Ⅱ错误。对于基本流水线CPU,让每个时钟周期流出一条指令,CPI=1,Ⅲ正确。超标量流水线CPU在每个时钟周期内并发执行多条独立的指令,每个时钟周期流出多条指令,CPI< 1,Ⅳ错误。
18.下列关于“自陷”(Trap,也称陷阱)的叙述中,错误的是()。
A
自陷是一种内部异常,A错误。在80x86中,用于程序调试的“断点设置”功能是通过“自陷”方式实现的,选项B正确。执行到自陷指令时,无条件或有条件地自动调出操作系统内核程序进行执行,选项C正确。CPU执行“陷阱指令”后,会自动地根据不同“陷阱”类型进行相应的处理,然后返回到“陷阱指令”的下一条指令执行,选项D正确。
19.QPI总线是一种点对点全工同步串行总线,总线上的设备可同时接收和发送信息,每个方向可同时传输20位信息(16位数据+4位校验位),每个QPI数据包有80位信息,分2个时钟周期传送,每个时钟周期传递2次。因此,QPI总线带宽为:每秒传送次数×2B×2。若QPI时钟频率为2.4GHz,则总线带宽为()。
C
每个时钟周期传送2次,故每秒传送的次数=时钟频率×2=2.4G×2/s。
总线带宽=每秒传送次数×2B×2=2.4G×2×2B×2/s=19.2GB/s。
题中已给出总线带宽公式,降低了难度。公式中的“×2B”是因为每次传输16位数据,“×2”
是因为采用点对点全双工总线,两个方向可同时传输信息。
20.下列事件中,属于外部中断事件的是()。
I.访存时缺页
Ⅱ.定时器到时
Ⅲ.网络数据包到达
C
访存时缺页属于内部异常,I错误;定时器到时描述的是时钟中断,属于外部中断,Ⅱ正确:网络数据包到达描述的是CPU执行指令以外的事件,属于外部中断,Ⅲ正确。
21.外部中断包括不可屏蔽中断(NMI)和可屏蔽中断,下列关于外部中断的叙述中,错误的是()。
B
由CPU内部产生的异常称为内中断,内中断都是不可屏蔽中断。通过中断请求线INTR和 NMI,从CPU外部发出的中断请求为外中断,通过INTR信号线发出的外中断是可屏蔽中断,而通过NMI信号线发出的是不可屏蔽中断。不可屏蔽中断不受中断标志位的影响,即使在关中断的情况下也会被响应,选项A正确。不可屏蔽中断的处理优先级最高,任何时候只要发生不可屏蔽中断,都要中止现行程序的执行,转到不可屏蔽中断处理程序执行,选项C正确。CPU响应中断需要满足3个条件:①中断源有中断请求;②CPU允许中断及开中断;③一条指令执行完毕,且没有更紧迫的任务。故选项B错误。
22.若设备采用周期挪用DMA方式进行输入和输出,每次DMA传送的数据块大小为512字节,相应的I/O接口中有一个32位数数据缓冲寄存器。对于数据输入过程,下列叙述中,错误的是()。
C
周期挪用法由DMA控制器挪用一个或几个主存周期来访问主存,传送完一个数据字后立即释放总线,是一种单字传送方式,每个字传送完后CPU可以访问主存,选项C错误。停止CPU访存法则是指在整个数据块的传送过程中,使CPU脱离总线,停止访问主存。
23.若多个进程共享同一个文件F,则下列叙述中,正确的是()。
B
多个进程可同时以“读”或“写”方式打开文件,操作系统并不保证写操作的互斥性,进程可通过系统调用对文件加锁,保证互斥写(读者-写者问题),选项A错误。整个系统只有一个系统打开文件表,同一个文件打开多次只需改变引用计数,选项B正确。用户进程的打开文件表关于同一个文件不一定相同,例如读写指针位置不一定相同,选项C错误。进程关闭文件时,文件的引用计数减1,引用计数变为0时才删除系统打开文件表中的表项,选项D错误。
24.下列选项中,支持文件长度可变、随机访问的磁盘存储空间分配方式是()。
A
索引分配支持变长的文件,同时可以随机访问文件的指定数据块,选项A正确。链接分配不支持随机访问,需要依靠指针依次访问,选项B错误。连续分配的文件长度固定,不支持可变文件长度(连续分配的文件长度虽然也可变,但是需大量移动数据,代价较大,相比之下不太合适),选项C错误。动态分区分配是内存管理方式,不是磁盘空间的管理方式,选项D错误。
25.下列与中断相关的操作中,由操作系统完成的是()。
I.保存被中断程序的中断点
Ⅱ.提供中断服务
Ⅲ.初始化中断向量表
Ⅳ.保存中断屏蔽字
D
当CPU检测到中断信号后,由硬件自动保存被中断程序的断点(即程序计数器PC),I错误。之后,硬件找到该中断信号对应的中断向量,中断向量指明中断服务程序入口地址(各中断向量统一存放在中断向量表中,该表由操作系统初始化,Ⅲ正确)。接下来开始执行中断服务程序,保存PSW、保存中断屏蔽字、保存各通用寄存器的值,并提供与中断信号对应的中断服务,中断服务程序属于操作系统内核,Ⅱ和Ⅳ正确。
26.下列与进程调度有关的因素中,在设计多级反馈队列调度算法时需要考虑的是()。
I.就绪队列的数量
Ⅱ.就绪队列的优先级
Ⅲ.各就绪队列的调度算法
Ⅳ.进程在就绪队列间的迁移条件
D
多级反馈队列调度算法需要综合考虑优先级数量、优先级之间的转换规则等,就绪队列的数量会影响长进程的最终完成时间,I正确;就绪队列的优先级会影响进程执行的顺序,Ⅱ正确;各就绪队列的调度算法会影响各队列中进程的调度顺序,Ⅲ正确;进程在就绪队列中的迁移条件会影响各进程在各队列中的执行时间,Ⅳ正确。
27.
B
28.下列因素中,影响请求分页系统有效(平均)访存时间的是()。
I.缺页率
Ⅱ.磁盘读写时间
Ⅲ.内存访问时间
Ⅳ.执行缺页处理程序的CPU时间
D
I影响缺页中断的频率,缺页率越高,平均访存时间越长;Ⅱ和Ⅳ影响缺页中断的处理时间,中断处理时间越长,平均访存时间越长;Ⅲ影响访问页表和访问目标物理地址的时间,故I、Ⅱ、Ⅲ和Ⅳ均正确。
29.下列关于父进程与子进程的叙述中,错误的是()。
B
父进程与子进程当然可以并发执行,选项A正确。父进程可与子进程共享一部分资源,但不能共享虚拟地址空间,在创建子进程时,会为子进程分配资源,如虚拟地址空间等,选项B错误。临界资源一次只能为一个进程所用,选项D正确。进程控制块PCB是进程存在的唯一标志,每个进程都有自己的PCB,选项C正确。
30.对于具备设备独立性的系统,下列叙述中,错误的是()。
D
设备可视为特殊文件,选项A正确。用户使用逻辑设备名来访问物理文件,有利于设备独立性,选项B正确。通过逻辑设备名访问物理设备时,需要建立逻辑设备和物理设备之间的映射关系,选项C正确。应用程序按逻辑设备名访问设备,再经驱动程序的处理来控制物理设备,若更换物理设备,则只需更换驱动程序,而无须修改应用程序,选项D错误。
31.某文件系统的目录项由文件名和索引结点号构成。若每个目录项长度为64字节,其中4字节存放索引结点号,60字节存放文件名。文件名由小写英文字母构成,则该文件系统能创建的文件数量的上限为()。
B
在总长为64字节的目录项中,索引结点占4字节,即32位。不同目录下的文件的文件名可以相同,所以在考虑系统创建最多文件数量时,只需考虑索引结点的个数,即创建文件数量上限=索引结点数量上限。整个系统中最多存储232个索引结点,因此整个系统最多可以表示232个文件,选项B正确。
32.下列准则中,实现临界区互斥机制必须遵循的是()。
I.两个进程不能同时进入临界区
Ⅱ.允许进程访问空闲的临界资源
Ⅲ.进程等待进入临界区的时间是有限的
Ⅳ.不能进入临界区的执行态进程立即放弃CPU
C
实现临界区互斥需满足多个准则。“忙则等待”准则,即两个进程不能同时访问临界区,I正确。“空闲让进”准则,若临界区空闲,则允许其他进程访问,Ⅱ正确。“有限等待”准则,即进程应该在有限时间内访问临界区,Ⅲ正确。I、Ⅱ和Ⅲ是互斥机制必须遵循的原则。Ⅳ是“让权等待”准则,不一定非得实现,如皮特森算法。
33.
C
协议由语法、语义和时序(又称同步)三部分组成。语法规定了通信双方彼此“如何讲”,即规定了传输数据的格式。语义规定了通信双方彼此“讲什么”,规定了所要完成的功能,如通信双方要发出什么控制信息、执行的动作和返回的应答。时序规定了信息交流的次序。由图可知发送方与接收方依次交换信息,体现了协议三要素中的时序要素。
34.下列关于虚电路网络的叙述中,错误的是()。
B
虚电路服务需要有建立连接过程,每个分组使用短的虚电路号,属于同一条虚电路的分组按照同一路由进行转发,分组到达终点的顺序与发送顺序相同,可以保证有序传输,不需要为每条虚电路预分配带宽。
35.在下图所示的网络中,冲突域和广播域的个数分别是()。
C
36.假设主机甲采用停-等协议向主机乙发送数据帧,数据帧长与确认帧长均为1000B,数据传输速率是10kbps,单项传播延时是200ms。则甲的最大信道利用率为()。
D
发送数据帧和确认帧的时间均为t=1000×8b/10kbps=800ms。
发送周期T=800ms+200ms+800ms+200ms=2000ms。
信道利用率=t/T×100%=800/2000×100%=40%。
37.
A
为了尽量避免碰撞,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、FS3、IFS4对应SIFS。
38.若主机甲与主机乙已建立一条TCP连接,最大段长(MSS)为1KB,往返时间(RTT)为 2s,则在不出现拥塞的前提下,拥塞窗口从8KB增长到32KB所需的最长时间是()。
D
由于慢开始门限ssthresh可以根据需求设置,为了求拥塞窗口从8KB增长到32KB所需的最长时间,可以假定慢开始门限小于等于8KB,只要不出现拥塞,拥塞窗口就都是加法增大,每经历一个传输轮次(RTT),拥塞窗口逐次加1,所需最长时间为(32-8)×2s=48ms。
39.若主机甲与主机乙建立TCP连接时,发送的SYN段中的序号为1000,在断开连接时,甲发送给乙的FN段中的序号为5001,则在无任何重传的情况下,甲向乙已经发送的应用层数据的字节数为()。
C
甲与乙建立TCP连接时发送的SYN段中的序号为1000,则在数据传输阶段所用的起始序号为1001;断开连接时,甲发送给乙的FN段中的序号为5001,在无任何重传的情况下,甲向乙已经发送的应用层数据的字节数为5001-1001=4000。
40.
D
题中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~47小题,共70分。

41.
分析。由D=|a-b|+|b-c|+|c-a|≥0得:
①当a=b=c时,距离最小。
②其余情况。不失一般性,假设α≤b≤c,观察下面的数轴:
42.
1)使用一棵二叉树保存字符集中各字符的编码,每个编码对应于从根开始到达某叶结点的一条路径,路径长度等于编码位数,路径到达的叶结点中保存该编码对应的字符。
2)从左至右依次扫描0/1串中的各位。从根开始,根据串中当前位沿当前结点的左子指针或右子指针下移,直到移动到叶结点时为止。输出叶结点中保存的字符。然后从根开始重复这个过程,直到扫描到0/1串结束,译码完成。
3)二叉树既可用于保存各字符的编码,又可用于检测编码是否具有前缀特性。判定编码是否具有前缀特性的过程,也是构建二叉树的过程。初始时,二叉树中仅含有根结点,其左子指针和右子指针均为空。
依次读入每个编码C,建立/寻找从根开始对应于该编码的一条路径,过程如下:
对每个编码,从左至右扫描C的各位,根据C的当前位(0或1)沿结点的指针(左子指针或右子指针)向下移动。当遇到空指针时,创建新结点,让空指针指向该新结点并继续移动。沿指针移动的过程中,可能遇到三种情况:
①若遇到了叶结点(非根),则表明不具有前缀特性,返回。
②若在处理C的所有位的过程中,均没有创建新结点,则表明不具有前缀特性,返回。
③若在处理C的最后一个编码位时创建了新结点,则继续验证下一个编码。若所有编码均通过验证,则编码具有前缀特性。
43.
44.
45.
46.3)已知数组a按行优先方式存放,若对数组a分别按行遍历和按列遍历,则哪种遍历方式的局部性更好?
2)根据数组的随机存取特点,数组a在虚拟地址空间中所占的区域必须连续,由于数组a不止占用一页,相邻逻辑页在物理上不一定相邻,因此数组a在物理地址空间中所占的区域可以不连续。
3)由1)可知每个页面正好可以存放一整行的数组元素,“按行优先方式存放”意味着数组的同一行的所有元素都存放在同一个页面中,同一列的各个元素都存放在不同的页面中,因此数组a按行遍历的局部性较好。
47.

错题本

Copyright © 阿鑫 2022 all right reserved,powered by Gitbook最初发布时间: 2024-04-28

results matching ""

    No results matching ""