2019年12月考研的408试题,本篇为小题部分,大题见下一篇。

声明:

  • 0x和0b分别表示十六进制数和二进制数,其余为十进制数。
  • 0y和0c分别表示十六进制形式补码和二进制形式补码。
  • exp()和log()分别是以2为底的指数和对数,exp10()以10为底。
  • 乘除号用最朴素的×÷,分数用/,⌊⌋⌈⌉分别是向上向下取整。
  • 参与计算的英文字母变量用的是手写体。
  • 对原题一些容易误会的文字做了修改。
  • 图片使用亿图图示等绘制。

一、单项选择:

第1~40小题,每小题2分,共80分。

DataStructure

🤓✍️「1」、将一个10×10对称矩阵𝑴的上三角部分的元素M[i][j](1≤i≤j≤10)按列优先存入C语言的一维数组N[]中,元素M[7][2]在N中的下标是()?

  • A、15
  • B、16
  • C、22
  • D、23
【A】也即对称矩阵𝑴的下三角部分按行优先,M[7][2]是第23个元素,在N中下标是22。

🤓✍️「2」、对空栈S进行Push与Pop操作,入栈序列a,b,c,d,e经过Push,Push,Pop,Push,Pop,Push,Push,Pop操作后得到的出栈序列是()?

  • A、b,a,c,
  • B、b,a,e,
  • C、b,c,a,
  • D、b,c,e,
【D】模拟题。

🤓✍️「3」、对于任意一棵高度为5且有10个结点的二叉树,若采用顺序存储结构保存,每个结点占1个存储单元,仅存放结点的数据信息,则存放该二叉树需要的存储单元数量至少是()?

  • A、31
  • B、16
  • C、15
  • D、10
【A】为了满足这棵二叉树的任意性,把所有空结点也保存,成一棵5层满二叉树。

🤓✍️「4」、已知一棵二叉树,先序遍历序列是a,b,c,d,e,f,中序遍历序列是b,a,d,f,e,c,其后序遍历序列是()?

  • A、b,a,d,f,e,c,
  • B、b,d,f,e,c,a,
  • C、b,f,e,d,c,a,
  • D、f,e,d,c,b,a,
【C】根据二叉树的先序遍历和中序遍历可唯一确定此树,如下图👇。

🤓✍️「5」、下列给定的关键字输入序列中,不能生成如下二叉排序树的是()?

  • A、4,5,2,1,3,
  • B、4,5,1,2,3,
  • C、4,2,5,3,1,
  • D、4,2,1,3,5,
【B】选项B生成的是如下二叉排序树,非AVL树不能旋转。

🤓✍️「6」、修改递归方式实现的图的深度优先搜索算法,将访问顶点信息的语句移到退出递归前,即执行输出语句后立刻退出递归。采用修改后的算法遍历有向无环图G,若输出结果中包含G中的全部顶点,则输出的顶点序列是G的()?

  • A、拓扑有序序列
  • B、逆拓扑有序序列
  • C、广度优先搜索序列
  • D、深度优先搜索序列
【B】举个例子👇。

🤓✍️「7」、已知无向图G如下所示,使用克鲁斯卡尔算法求图G的最小生成树,加入到最小生成树中的边依次是()?

  • A、(b,f),(b,d),(a,e),(c,e),(b,e),
  • B、(b,f),(b,d),(b,e),(a,e),(c,e),
  • C、(a,e),(b,e),(c,e),(b,d),(b,f),
  • D、(a,e),(c,e),(b,e),(b,f),(b,d),
【A】按照克鲁斯卡尔算法的规则👇。

🤓✍️「8」、若使用AOE网估算工程进度,则下列叙述中正确的是()?

  • A、关键路径是从原点到汇点边数最多的一条路径。
  • B、关键路径是从原点到汇点路径长度最长的路径。
  • C、增加任一关键活动的时间不会延长工程的工期。
  • D、缩短任一关键活动的时间将会缩短工程的工期。
【B】关键路径的定义:权值总和最大。

🤓✍️「9」、下列关于大根堆的叙述中,正确的是()?

Ⅰ꙳可以将堆视为一棵完全二叉树。       Ⅱ꙳可以采用顺序存储方式保存堆。
Ⅲ꙳可以将堆视为一棵二叉排序树。     Ⅳ꙳堆中的次大值一定在根的下一层。

  • A、Ⅰ,Ⅱ,
  • B、Ⅱ,Ⅲ,
  • C、Ⅰ,Ⅱ,Ⅳ,
  • D、Ⅰ,Ⅲ,Ⅳ,
【C】根据大根堆的定义很容易排除Ⅲ꙳。

🤓✍️「10」、依次将关键字5,6,9,13,8,2,12,15插入初始为空的4阶B-树后,根结点中包含的关键字是()?

  • A、8,
  • B、6,9,
  • C、8,13,
  • D、9,12,
【B】考B-树的插入👇。

🤓✍️「11」、对大部分元素已有序的数组进行排序时,直接插入排序比简单选择排序效率更高,其原因是()?

Ⅰ꙳直接插入排序过程中元素之间的比较次数更少。
Ⅱ꙳直接插入排序过程中所需要的辅助空间更少。
Ⅲ꙳直接插入排序过程中元素的移动次数更少。

  • A、Ⅰ,
  • B、Ⅲ,
  • C、Ⅰ,Ⅱ,
  • D、Ⅰ,Ⅱ,Ⅲ,
【A】Ⅰ꙳简单选择排序的比较次数始终为(n-1)+(n-2)+...+1,基本有序的情况下,直接插入排序的比较次数约为(n-1)。Ⅱ꙳两种排序方法所需要的辅助空间都仅仅是几个变量。Ⅲ꙳简单选择排序靠的是交换元素,直接插入排序每趟都要后移一些元素。

ComputerOrganization

🤓✍️「12」、下列给出的部件中,其位数一定与机器字长相同的()?

Ⅰ꙳ALU     Ⅱ꙳指令寄存器     Ⅲ꙳通用寄存器     Ⅳ꙳浮点寄存器

  • A、Ⅰ,Ⅱ,
  • B、Ⅰ,Ⅲ,
  • C、Ⅱ,Ⅲ,
  • D、Ⅱ,Ⅲ,Ⅳ,
【B】位于数据通路上的部件的位数一定与机器字长相同。

🤓✍️「13」、已知int型变量用补码表示,float型变量用IEEE754标准表示,假定变量x的类型只可能是int或float,当x的机器数为C8000000时,x的值可能是()?

  • A、-7×exp(27)
  • B、-1×exp(16)
  • C、1×exp(17)
  • D、25×exp(27)
【A】为int型是-7×exp(27),为float型是-1×exp(17)。

🤓✍️「14」、在按字节编址,采用小端方式的32位计算机中,按边界对齐方式为以下C语言结构型变量a分配存储空间,若a的首地址为0x2020FE00,a.x2的机器数为0y12340000,则字节{34}所在存储单元的地址是()?

struct record {
short x1;
int x2;
} a;
  • A、0x2020 FE03
  • B、0x2020 FE04
  • C、0x2020 FE05
  • D、0x2020 FE06
【D】为int型是-7×exp(27),为float型是-1×exp(17)。

🤓✍️「15」、下列关于TLB和Cache的叙述中,错误的()?

  • A、命中率都与程序局部性有关。
  • B、缺失后都需要去访问主存。
  • C、缺失处理都可以由硬件实现。
  • D、都由DRAM存储器组成。
【D】DRAM要不断刷新,读写速度慢一些,一般做主存。Cache一般由SRAM存储器组成,TLB一般由相联存储器组成。

🤓✍️「16」、某机器采用16位定长指令字格式,操作码位数和寻址方式位数固定,指令系统有48条指令,支持直接·间接·立即·相对4种寻址方式。单地址指令中,直接寻址方式的可寻址范围是()?

  • A、0~255
  • B、0~1023
  • C、-128~127
  • D、-512~511
【A】操作码⌈log(48)⌉=6位,寻址方式⌈log(4)⌉=2位,8位地址码,在直接寻址方式下表示范围为0~255。

🤓✍️「17」、下列给出的处理器类型中,理想情况下,CPI为1的是()?

Ⅰ꙳单周期CPU     Ⅱ꙳多周期CPU     Ⅲ꙳基本流水线CPU     Ⅳ꙳超标量流水线CPU

  • A、Ⅰ,Ⅱ,
  • B、Ⅰ,Ⅲ,
  • C、Ⅱ,Ⅳ,
  • D、Ⅲ,Ⅳ,
【B】单周期CPU中,指令周期=时钟周期,CPI=1;多周期CPU中,CPI>1。基本流水线CPU,每个时钟周期发射一条流水线,CPI=1;超标量流水线CPU,每个时钟周期并发多条流水线,CPI<1。

🤓✍️「18」、下列关于“自陷”"trap"的叙述中,错误的()?

  • A、自陷是通过陷阱指令预先设定的一类外部中断事件。
  • B、自陷可用于实现程序调试时的断点设置和单步跟踪。
  • C、自陷发生后CPU将转去执行操作系统内核相应程序。
  • D、自陷处理完成后返回到陷阱指令的下一条指令执行。
【A】自陷跟指令执行有关,属于内部异常。

🤓✍️「19」、QPI总线是一种点对点全工同步串行总线,总线上的设备可同时接收和发送信息,每个方向可同时传输16位数据+4位校验位,共20位信息,每个QPI数据包有80位信息,分2个时钟周期传送,每个时钟周期传递2次。因此,QPI总线带宽为:每秒传送次数×2B×2。若QPI时钟频率为2.4GHz,则总线带宽为()?

  • A、4.8GBps
  • B、9.6GBps
  • C、19.2GBps
  • D、38.4GBps
【C】按照题给的公式,2.4GHz×2×2B×2=19.2GBps。这里的×2B代表传输16位数据,×2代表全工两个方向。

🤓✍️「20」、下列事件中,属于外部中断事件是()?

Ⅰ꙳访存时缺页     Ⅱ꙳定时器到时     Ⅲ꙳网络数据包到达

  • A、Ⅰ,Ⅱ,
  • B、Ⅰ,Ⅲ,
  • C、Ⅱ,Ⅲ,
  • D、Ⅰ,Ⅱ,Ⅲ,
【C】Ⅰ꙳访存时缺页属于内部异常。

🤓✍️「21」、外部中断包括不可屏蔽中断"NonMaskableInterrupt"和可屏蔽中断"INTR",下列关于外部中断的叙述中,错误的是()?

  • A、CPU处于关中断状态时,也能响应NMI请求。
  • B、一旦INTR请求信号有效,CPU将立即响应。
  • C、NMI的优先级比INTR的优先级高。
  • D、可通过中断屏蔽字改变INTR的处理优先级。
【B】响应INTR请求需要2个条件:❶CPU处于开中断状态;❷处于指令周期的中断周期,且没有更紧迫的任务。

🤓✍️「22」、若设备采用周期挪用DMA方式进行输入和输出,每次DMA传送的数据块大小为512B,相应的I/O接口中有一个32位数据缓冲寄存器。对于数据输入过程,下列叙述中,错误的是()?

  • A、每准备好32位数据,DMA控制器就发出一次总线请求。
  • B、相对于CPU,DMA控制器的总线使用权的优先级更高。
  • C、在整个数据块的传送过程中,CPU不可以访问主存储器。
  • D、数据块传送结束时,会产生“DMA传送结束”中断请求。
【C】周期挪用,CPU和DMA可以同时访存,若有冲突则DMA优先。

OperatingSystem

🤓✍️「23」、若多个进程共享同一个文件F,则下列叙述中,正确的()?

  • A、各进程只能用“读”方式打开文件F。
  • B、在系统打开文件表中仅有一个表项包含F的属性。
  • C、各进程的用户打开文件表中关于F的表项内容相同。
  • D、进程关闭F时,系统删除F在系统打开文件表中的表项。
【B】选项A,多进程可以同时以“读”或“写”方式打开文件,但互斥写不归操作系统管,交由各进程来实现。选项B,整个系统只有一张系统打开文件表,同一个文件打开多次只需改变引用计数。选项C,进程的用户打开文件表关于同一个文件的读写指针位置不一定相同。选项D,进程关闭文件时,文件的引用计数减1,引用计数变为0时,删除系统打开文件表中的表项。

🤓✍️「24」、下列选项中,支持文件长度可变·随机访问的磁盘存储空间分配方式()?

  • A、索引分配
  • B、链接分配
  • C、连续分配
  • D、动态分区分配
【A】选项B,链接分配不支持随机访问。选项C,连续分配不支持长度可变。选项D,动态分区分配是内存管理方式,不是磁盘的管理方式。

🤓✍️「25」、下列与中断相关的操作中,由操作系统完成的是()?

Ⅰ꙳保存被中断程序的断点     Ⅱ꙳提供中断服务     Ⅲ꙳初始化中断向量表     Ⅳ꙳保存中断屏蔽字

  • A、Ⅰ,Ⅱ,
  • B、Ⅰ,Ⅱ,Ⅳ,
  • C、Ⅲ,Ⅳ,
  • D、Ⅱ,Ⅲ,Ⅳ,
【D】Ⅰ꙳由中断隐指令完成。

🤓✍️「26」、下列与进程调度有关的因素中,在设计多级反馈队列调度算法时需要考虑的是()?

Ⅰ꙳就绪队列的数量             Ⅱ꙳就绪队列的优先级
Ⅲ꙳各就绪队列的调度算法       Ⅳ꙳进程在就绪队列间的迁移条件

  • A、Ⅰ,Ⅱ,
  • B、Ⅲ,Ⅳ,
  • C、Ⅱ,Ⅲ,Ⅳ,
  • D、Ⅰ,Ⅱ,Ⅲ,Ⅳ,
【D】概念题。都是的。

🤓✍️「27」、某系统中有A,B两类资源各6个,𝓽时刻资源分配及需求情况如下表所示👇,𝓽时刻安全性检测结果()?

进程A已分配数量B已分配数量A需求总量B需求总量
P12344
P22131
P31234
  • A、存在安全序列P1,P2,P3
  • B、存在安全序列P2,P1,P3
  • C、存在安全序列P2,P3,P1
  • D、不存在安全序列
【B】根据银行家算法,资源供给向量={A:1,B:0},进程需求矩阵=[P1:{A:2,B:1},P2:{A:1,B:0},P3:{A:2,B:2}],可以得到安全序列P2,P1,P3。

🤓✍️「28」、下列因素中,影响请求分页系统平均访存时间的是()?

Ⅰ꙳缺页率     Ⅱ꙳磁盘读写时间     Ⅲ꙳内存访问时间     Ⅳ꙳执行缺页异常处理程序的CPU时间

  • A、Ⅱ,Ⅲ,
  • B、Ⅰ,Ⅳ,
  • C、Ⅰ,Ⅲ,Ⅳ,
  • D、Ⅰ,Ⅱ,Ⅲ,Ⅳ,
【D】Ⅰ꙳缺页率越高,磁盘读写时间越长,执行缺页异常处理程序的CPU时间越长,内存访问时间越长,平均访存时间都会越长。

🤓✍️「29」、下列关于父进程与子进程的叙述中,错误的是()?

  • A、父进程与子进程可以并发执行。
  • B、父进程与子进程共享虚拟地址空间。
  • C、父进程与子进程有不同的进程控制块。
  • D、父进程与子进程不能同时使用同一临界资源。
【B】父进程可与子进程共享一部分资源,但不能共享虚拟地址空间。

🤓✍️「30」、对于具备设备独立性的系统,下列叙述中,错误的()?

  • A、可以使用文件名访问物理设备。
  • B、用户程序使用逻辑设备名访问物理设备。
  • C、需要建立逻辑设备与物理设备之间的映射关系。
  • D、更换物理设备后必须修改访问该设备的应用程序。
【D】应用程序按逻辑设备名访问设备,再经驱动程序的处理来控制物理设备,若更换物理设备,则只需更换驱动程序,而无须修改应用程序。

🤓✍️「31」、某文件系统的目录项由文件名和索引结点号构成。若每个目录项长度为64字节,其中4字节存放索引结点号,60字节存放文件名,文件名由小写英文字母构成,则该文件系统能创建的文件数量的上限为()?

  • A、exp(26)
  • B、exp(32)
  • C、exp(60)
  • D、exp(64)
【B】1个索引结点对应1个文件,4字节=32位上限就是exp(32)个,跟文件名没关系。

🤓✍️「32」、下列准则中,实现临界区互斥机制必须遵循的是()?

Ⅰ꙳两个进程不能同时进入临界区         Ⅱ꙳允许进程访问空闲的临界资源
Ⅲ꙳进程等待进入临界区的时间是有限     Ⅳ꙳不能进入临界区的执行态进程立即放弃CPU

  • A、Ⅰ,Ⅳ,
  • B、Ⅱ,Ⅲ,
  • C、Ⅰ,Ⅱ,Ⅲ,
  • D、Ⅰ,Ⅲ,Ⅳ,
【C】Ⅰ꙳忙则等待;Ⅱ꙳空闲让进;Ⅲ꙳有限等待;Ⅳ꙳让权等待,不一定非得遵循,如Peterson方法就没遵循,书上的方法就Semaphore方法能遵循。

ComputerNetWork

🤓✍️「33」、下图👇描述的协议要素是()?

Ⅰ꙳语法         Ⅱ꙳语义         Ⅲ꙳时序

  • A、Ⅰ,
  • B、Ⅱ,
  • C、Ⅲ,
  • D、Ⅰ,Ⅱ,Ⅲ,
【C】语法规定了通信双方彼此“如何讲”,语义规定了通信双方彼此“讲什么,时序规定了信息交流的次序。

🤓✍️「34」、下列关于虚电路网络的叙述中,错误的()?

  • A、可以确保数据分组传输顺序。
  • B、需要为每条虚电路预分配带宽。
  • C、建立虚电路时需要进行路由选择。
  • D、依据虚电路号VCID进行数据分组转发。
【B】易错题。注意采用电路交换的电话通信才是工作在物理层的真实电路,虚电路网络概念如下👇。

🤓✍️「35」、在下图所示的网络中,冲突域和广播域的个数分别是()?

  • A、2,2,
  • B、2,4,
  • C、4,2,
  • D、4,4,
【C】交换机隔离冲突域,路由器隔离广播域。

🤓✍️「36」、假设主机甲采用停等协议向主机乙发送数据帧,数据帧长与确认帧长均为1000B,数据传输速率是10Kbps,单向传播时延是200ms。甲的最大信道利用率为()?

  • A、80%
  • B、66.7%
  • C、44.4%
  • D、40%
【D】停等协议中发送窗口大小为1,数据帧与确认帧发送时延均为1000B÷10Kbps=800ms,发送周期=2×(800+200)ms=2000ms,800/2000=40%。

🤓✍️「37」、某IEEE802.11无线局域网中,主机H与AP之间发送或接收CSMA/CA帧的过程如下图👇。在H或AP发送帧前所等待的帧间间隔时间"IFS"中,最长的是()?

  • A、IFS1
  • B、IFS2
  • C、IFS3
  • D、IFS4
【A】IFS1用于预约信道的DIFS,规定为128us,IFS234均为SIFS,规定为28us。

🤓✍️「38」、若主机甲与主机乙已建立一条TCP连接,最大段长"MSS"为1KB,往返时间"RTT"为2ms,则在不出现拥塞的前提下,拥塞窗口从8KB增长到32KB所需的最长时间()?

  • A、4ms
  • B、8ms
  • C、24ms
  • D、48ms
【D】最长时间,拥塞窗口线性+1MSS,需24个RTT,48ms。

🤓✍️「39」、若主机甲与主机乙建立TCP连接时,发送的SYN段中的序号为1000,在断开连接时,甲发送给乙的FIN段中的序号为5001,则在无任何重传的情况下,甲向乙已经发送的应用层数据的字节数()?

  • A、4002
  • B、4001
  • C、4000
  • D、3999
【C】数据传输阶段甲给乙发送的第一个序号为1001,断开连接前甲给乙发送的最后一个序号为5000,共4000。

🤓✍️「40」、假设下图所示网络中的本地域名服务器只提供递归查询服务,其他域名服务器均只提供迭代查询服务。局域网内主机访问Internet上各服务器的往返时间"RTT"均为10ms,忽略其他各种时延。若主机H通过超链接http://www.abc.com/index.html请求浏览纯文本Web页index.html,则从点击超链接开始到浏览器接收到index.html页面为止,所需的最短时间与最长时间分别()?

  • A、10ms,40ms,
  • B、10ms,50ms,
  • C、20ms,40ms,
  • D、20ms,50ms,
【C】主机H向本地域名服务器的查询时延忽略不计。最短时间:本地主机中有该域名到IP地址对应的记录,不需要DNS查询,直接与www.abc.com服务器建立TCP连接,收到index.html,共2个RTT;最长时间:本地服务器依次迭代查询根域名服务器·com顶级域名服务器·abc.com域名服务器,再加上这3个RTT。
最后修改于:2024年09月29日
如果觉得我的文章对你有用请狠狠地打赏我