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

声明：

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

一、单项选择：

第1～40小题，每小题2分，共80分。

DataStructure

🤓✍️「1」、下列程序段的时间复杂度是（）？

int sum = 0;
for (int i = 1; i < n; i *= 2;)
    for (int j = 0; j < i; j++;)
        sum++;
  • A、𝜪(log(n))
  • B、𝜪(n)
  • C、𝜪(nlog(n))
  • D、𝜪(n^2)
【B】易错题。外层循环i有m=⌊log(n-1)⌋次，内层循环j有1+2+4+8+...+m=exp(m)-1。

🤓✍️「2」、给定有限符号集S，in和out均为S中所有元素的任意排列。对于初始为空的栈K，下列叙述中正确的是（）？

  • A、若in是K的入栈序列，则不能判断out是否为其可能的出栈序列。
  • B、若out是K的出栈序列，则不能判断in是否为其可能的入栈序列。
  • C、若in是K的入栈序列，out是对应in的出栈序列，则in与out一定不同。
  • D、若in是K的入栈序列，out是对应in的出栈序列，则in与out可能互为倒序。
【D】都能模拟出来。

🤓✍️「3」、若结点p与q在二叉树T的中序遍历序列里相邻，且p在q之前，则下列p与q的关系中，不可能的是（）？

Ⅰ꙳q是p的父   Ⅱ꙳q是p的右孩子   Ⅲ꙳q是p的右兄弟   Ⅳ꙳q是p的父的父

  • A、Ⅰ,
  • B、Ⅲ,
  • C、Ⅱ,Ⅲ,
  • D、Ⅱ,Ⅳ,
【B】。

🤓✍️「4」、若三叉树T中有244个结点，叶结点的高度为1，则T的高度至少是（）？

  • A、8
  • B、7
  • C、6
  • D、5
【C】考虑满三叉树高度为𝒽，(exp3(𝒽)-1)÷2≥244，取6。

🤓✍️「5」、对任意给定的含n个字符的有限集S，用二叉树表示S的哈夫曼编码集和定长编码集，分别得到二叉树T1和T2。下列叙述中正确的是（）？

  • A、T1与T2的结点数一定相同。
  • B、T1的高度一定大于T2的高度。
  • C、出现频次不同的字符在T1中一定处于不同的层。
  • D、出现频次不同的字符在T2中一定处于相同的层。
【D】T1是二叉哈夫曼树，T2近似于完全二叉树。

🤓✍️「6」、对于无向图G=(V,E)，下列选项中正确的是（）？

  • A、当|V|>|E|时，G一定是连通的。
  • B、当|V|<|E|时，G一定是连通的。
  • C、当|V|=|E|-1时，G一定是不连通的。
  • D、当|V|>|E|+1时，G一定是不连通的。
【D】G是连通的，有|E|≥|V|-1，逆否就是选项D。

🤓✍️「7」、下图为有10个活动的AOE网，时间余量最大的活动是（）？

  • A、c
  • B、g
  • C、h
  • D、j
【B】按照关键路径的算法👇。

🤓✍️「8」、在下图所示的5阶B-树T中，删除关键字260之后需要进行必要的调整，得到新的B-树T1。下列选项中不可能是T1根结点中关键字序列的是（）？

  • A、60,90,280,
  • B、60,90,350,
  • C、60,85,110,350,
  • D、60,90,110,350,
【D】回顾B-树的删除👇。

🤓✍️「9」、下列因素中，影响哈希方法平均查找长度的是（）？

Ⅰ꙳装填因子     Ⅱ꙳哈希函数     Ⅲ꙳冲突解决策略

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

🤓✍️「10」、使用二路归并排序对含n个元素的数组M[]进行排序时，二路归并操作的功能是（）？

  • A、将两个有序表合并为一个新的有序表。
  • B、将M划分为两部分，两部分的元素个数大致相等。
  • C、将M划分为几个部分，每个部分中仅含有一个元素。
  • D、将M划分为两部分，一部分元素的值均小于另一部分元素的值。
【A】概念题。

🤓✍️「11」、对数据进行排序时，若采用直接插入排序而不采用快速排序，则可能的原因是（）？

Ⅰ꙳大部分元素已有序           Ⅱ꙳待排序元素数量很少
Ⅲ꙳要求空间复杂度为𝜪(1)     Ⅳ꙳要求排序算法是稳定的

  • A、Ⅰ,Ⅱ,
  • B、Ⅲ,Ⅳ,
  • C、Ⅰ,Ⅱ,Ⅳ,
  • D、Ⅰ,Ⅱ,Ⅲ,Ⅳ,
【D】Ⅰ꙳是书上给出的最适合用直接插入排序的情况。Ⅲ꙳快速排序需要递归栈𝜪(log(n))。Ⅳ꙳直接插入排序是稳定的，快速排序不稳定。Ⅱ꙳根据选项来确定。

ComputerOrganization

🤓✍️「12」、某机器主频为1GHz，程序P运行过程中，共执行了10000条指令，其中：80%的指令执行平均需1个时钟周期，20%的指令执行平均需10个时钟周期。程序P的平均CPI和CPU执行时间分别（）？

  • A、2.8,28us,
  • B、28,28us,
  • C、2.8,28ms,
  • D、28,28ms,
【A】程序P的平均CPI=80%×1+20%×10=2.8，CPU执行时间=10000×2.8÷1GHz=28us。

🤓✍️「13」、32位补码所能表示的整数范围（）？

  • A、-exp(32)～exp(31)-1
  • B、-exp(31)～exp(31)-1
  • C、-exp(32)～exp(32)-1
  • D、-exp(31)～exp(32)-1
【B】送分题。

🤓✍️「14」、-0.4375的IEEE754单精度浮点数表示（）？

  • A、0xBEE0 0000
  • B、0xBF60 0000
  • C、0xBF70 0000
  • D、0xC0E0 0000
【A】0.4375=0b0.0111=0b1.11×exp(-2)。

🤓✍️「15」、某机器主存地址为24位，采用分页虚拟存储管理方式，虚拟地址空间大小为4GB，页大小为4KB，按字节编址。某进程的页表部分内容如下表所示，当CPU访问虚拟地址0x0008 2840时，虚实地址转换结果为（）？

页面号页框号存在位
820x0240
.........
1290x1801
1300x0181
  • A、主存地址0x02 4840
  • B、主存地址0x18 0840
  • C、主存地址0x01 8840
  • D、检测到缺页异常
【C】页内偏移占低log(4K)=12位，虚拟地址共log(4G)=32位，高20位为页面号，实际地址24位，高12位为页框号。查页表，0x00082=130👉0x018，存在位为1，即得到实地址0x018 840。

🤓✍️「16」、某机器主存地址为32位，按字节编址，Cache的数据区容量为32KB，主存块大小为64B，采用8路组相联映射方式，该Cache中比较器的个数和位数分别为（）？

  • A、8,20,
  • B、8,23,
  • C、64,20,
  • D、64,23,
【A】比较器的个数就是8。块内偏移占log(64)=6位，Cache有32KB÷64B=512个块，64行8列，Cache行号占log(64)=6位，主存地址：［主存标记20位｜Cache行号6位｜块内偏移6位］，比较器的位数就是主存标记20位。

🤓✍️「17」、某内存条包含8个8192×8192×8b的DRAM芯片，按字节编址，支持突发传送方式，对应存储器总线宽度为64位，每个DRAM芯片内有一个行缓冲区。下列关于该内存条的叙述中不正确的是（）？

  • A、内存条的容量为512MB。
  • B、采用多模块交叉编址方式。
  • C、芯片的地址引脚为26位。
  • D、芯片内行缓冲区有8192×8b。
【C】选项A，内存条容量8×8192×8192×8b=512MB。选项B，存储器总线宽度64位，而单个DRAM芯片宽度是8位，需要8个芯片同时出力，即8体交叉编址。选项C，DRAM芯片采用行列式，地址线复用，log(8192)=13位就够了。选项D，芯片内行缓冲区就是一行的大小，8192×8b。

🤓✍️「18」、下列选项中，属于指令集体系结构"ISA"规定的内容是（）？

Ⅰ꙳指令字格式和指令类型           Ⅱ꙳CPU的时钟周期
Ⅲ꙳通用寄存器个数和位数         Ⅳ꙳加法器的进位方式

  • A、Ⅰ,Ⅱ,
  • B、Ⅰ,Ⅲ,
  • C、Ⅱ,Ⅳ,
  • D、Ⅰ,Ⅲ,Ⅳ,
【B】概念题。Ⅰ꙳Ⅲ꙳显然是的。Ⅳ꙳加法器的进位方式由电路实现决定。

🤓✍️「19」、设计某指令系统时，假设采用16位定长指令字格式，操作码使用扩展编码方式，地址码为6位，包含零地址·一地址·二地址3种格式的指令。若二地址指令有12条，一地址指令有254条，则零地址指令的条数最多（）？

  • A、0
  • B、2
  • C、64
  • D、128
【D】二地址指令操作码有4位，留了exp(4)-12=4条给一地址指令，一地址指令操作码多了6位，留了4×exp(6)-254=2条给零地址指令，零地址指令操作码多了6位，最多2×exp(6)=128条。

🤓✍️「20」、将高级语言源程序转换为可执行目标文件的主要过程是（）？

  • A、预处理⮕编译⮕汇编⮕链接
  • B、预处理⮕汇编⮕编译⮕链接
  • C、预处理⮕编译⮕链接⮕汇编
  • D、预处理⮕汇编⮕链接⮕编译
【A】概念题。熟悉C语言和gcc容易知道。

🤓✍️「21」、下列关于中断I/O方式的叙述中，不正确的是（）？

  • A、适用于键盘，针式打印机等字符型设备。
  • B、外设和主机之间的数据传送通过软件完成。
  • C、外设准备数据的时间应小于中断处理时间。
  • D、外设为某进程准备数据时CPU可运行其他进程。
【C】应大于，否则I/O接口中的数据会被覆盖。

🤓✍️「21」、下列关于并行处理技术的叙述中，不正确的是（）？

  • A、多核处理器属于MIMD结构。
  • B、向量处理器属于SIMD结构。
  • C、硬件多线程技术只可用于多核处理器。
  • D、SMP中所有处理器共享单一物理地址空间。
【C】单核多线程也是能做到的。

OperatingSystem

🤓✍️「23」、下列关于多道程序系统的叙述中，不正确的是（）？

  • A、支持进程的并发执行。
  • B、不必支持虚拟存储管理。
  • C、需要实现对共享资源的管理。
  • D、进程数越多CPU利用率越高。
【D】进程数量越多，进程之间的资源竞争越激烈，甚至可能抢夺资源而死锁，导致CPU利用率低。

🤓✍️「24」、下列选项中，需要在操作系统进行初始化过程中创建的是（）？

  • A、中断向量表
  • B、文件系统的根目录
  • C、硬盘分区表
  • D、文件系统的索引结点表
【A】选项C，在硬盘逻辑格式化的过程中完成。选项BD，在文件系统初始化的过程中完成。

🤓✍️「25」、进程P0,P1,P2,P3进入就绪队列的时刻·优先级·CPU执行时间如下表所示，优先值越小优先权越高，若系统采用基于优先权的抢占式进程调度算法，则从0ms时刻开始调度，到4个进程都运行结束为止，发生进程调度的总次数为（）？

进程进入就绪队列的时刻优先级CPU执行时间
P00ms15100ms
P110ms2060ms
P210ms1020ms
P315ms610ms
  • A、4
  • B、5
  • C、6
  • D、7
【C】如下图。

🤓✍️「26」、系统中有三个进程P0,P1,P2及三类资源A,B,C。若某时刻系统分配资源的情况如下表所示，则此时系统中存在的安全序列的个数为（）？

进程已分配资源数尚需资源数可用资源数
ABCABCABC
P0201021132
P1020123
P2101013
  • A、1
  • B、2
  • C、3
  • D、4
【B】P0,P1,P2，P0,P2,P1两个。

🤓✍️「27」、下列关于CPU模式的叙述中，正确的是（）？

  • A、CPU处于用户态时只能执行特权指令。
  • B、CPU处于内核态时只能执行特权指令。
  • C、CPU处于用户态时只能执行非特权指令。
  • D、CPU处于内核态时只能执行非特权指令。
【C】用户态只能执行非特权指令，内核态能执行非特权指令和特权指令。

🤓✍️「28」、下列事件或操作中，可能导致进程P由运行态变为阻塞态的是（）？

Ⅰ꙳进程P读文件           Ⅱ꙳进程P的时间片用完
Ⅲ꙳进程P申请外设       Ⅳ꙳进程P执行信号量的wait操作

  • A、Ⅰ,Ⅳ,
  • B、Ⅱ,Ⅲ,
  • C、Ⅲ,Ⅳ,
  • D、Ⅰ,Ⅲ,Ⅳ,
【D】运行态变阻塞态是资源相关。

🤓✍️「29」、某进程访问的页b不在内存中，导致产生缺页异常，该缺页异常处理过程中不一定包含的操作是（）？

  • A、淘汰内存中的页
  • B、建立页面号与页框号的对应关系
  • C、将页b从外存读入内存
  • D、修改页表中页b对应的存在位
【A】如果分配给该进程的页框数还够用，就不必淘汰内存中的页。

🤓✍️「30」、下列选项中，不会影响系统缺页率的是（）？

  • A、页置换算法
  • B、工作集的大小
  • C、进程的数量
  • D、页缓冲队列的长度
【D】页缓冲队列是将被淘汰的页面缓存下来，暂时不写回外存，队列长度会影响页面置换的速度，但不会影响缺页率。

🤓✍️「31」、执行系统调用的过程涉及下列操作，其中由操作系统完成的（）？

Ⅰ꙳保存断点和程序状态字           Ⅱ꙳保存通用寄存器的内容
Ⅲ꙳执行系统调用服务例程         Ⅳ꙳将CPU模式改为内核态

  • A、Ⅰ,Ⅲ,
  • B、Ⅱ,Ⅲ,
  • C、Ⅱ,Ⅳ,
  • D、Ⅱ,Ⅲ,Ⅳ,
【D】Ⅰ꙳Ⅳ꙳都由硬件完成。

🤓✍️「32」、下列关于驱动程序的叙述中，不正确的是（）？

  • A、驱动程序与I/O控制方式无关。
  • B、初始化设备是由驱动程序控制完成的。
  • C、进程在执行驱动程序时可能进入阻塞态。
  • D、读／写设备的操作是由驱动程序控制完成的。
【A】驱动程序跟设备有关，厂家会根据设备特性，在驱动程序中实现一种合适的I/O控制方式。

ComputerNetWork

🤓✍️「33」、在OSI七层参考模型中，实现两个相邻节点间流量控制功能的是（）？

  • A、物理层
  • B、链路层
  • C、网络层
  • D、传输层
【B】链路层针对相邻节点间流量控制，网络层针对整个网络流量控制，传输层针对端到端流量控制。

🤓✍️「34」、在一条带宽为200KHz的无噪声信道上，若采用4个幅值的ASK调制技术，“幅移键控”"AmplitudeShiftKeying"，则该信道的最大数据传输速率是（）？

  • A、200Kbps
  • B、400Kbps
  • C、800Kbps
  • D、1600Kbps
【C】不需要知道ASK调制技术的原理，由奈氏准则，理论最大数据传输速率=2×200KHz×log(4)b=800Kbps。

🤓✍️「35」、若某主机的IP地址是183.80.72.48，子网掩码是255.255.192.0，则该主机所在网络的网络地址是（）？

  • A、183.80.0.0
  • B、183.80.64.0
  • C、183.80.72.0
  • D、183.80.192.0
【B】主机的IP地址和其子网掩码按位与一下即可。

🤓✍️「36」、下图所示网络中的主机H的子网掩码与默认网关分别（）？

  • A、255.255.255.192, 192.168.1.1,
  • B、255.255.255.192, 192.168.1.62,
  • C、255.255.255.224, 192.168.1.1,
  • D、255.255.255.224, 192.168.1.62,
【D】主机H与其直连路由器R在同一网络，子网掩码应与直连路由器有等长的前缀，默认网关也就是直连路由器。

🤓✍️「37」、在SDN的网络体系结构中，“软件定义网络”"SoftwareDefinedNetworking"，SDN控制器向数据平面的SDN交换机下发流表时所使用的接口是（）？

  • A、东向接口
  • B、南向接口
  • C、西向接口
  • D、北向接口
【B】概念题。

🤓✍️「38」、假设主机甲和主机乙已建立一个TCP连接，最大段长MSS=1KB，甲一直有数据向乙发送，当甲的拥塞窗口为16KB时，计时器发生了超时，则甲的拥塞窗口再次增长到16KB所需要的时间至少是（）？

  • A、4RTT
  • B、5RTT
  • C、11RTT
  • D、16RTT
【C】计时器发生了超时时，慢开始门限降到8KB，拥塞窗口降为1，如下。

🤓✍️「39」、假设客户端C和服务器S已建立一个TCP连接，通信往返时间RTT=50ms，最长报文段寿命MSL=800ms，数据传输结束后，C主动请求断开连接。若从C主动向S发出FIN段时刻算起，则C和S进入CLOSED状态所的时间至少分别是（）？

  • A、850ms,50ms,
  • B、1650ms,50ms,
  • C、850ms,75ms,
  • D、1650ms,75ms,
【D】考TCP四次挥手。

🤓✍️「40」、假设主机H通过HTTP/1.1请求浏览某Web服务器S上的new408.html，new408.html引用了同目录下的1个pic.jpg图像，new408.html的大小为1MSS，pic.html的大小为3MSS，H访问S的往返时间RTT=10ms，忽略HTTP响应报文的首部开销和TCP段的传输时延。若H已完成域名解析，则从H请求与S建立TCP连接时刻起，到接收全部内容为止，所需的时间至少是（）？

  • A、30ms
  • B、40ms
  • C、50ms
  • D、60ms
【B】如下。
最后修改于：2024年10月12日
© 允许规范转载
如果觉得我的文章对你有用请狠狠地打赏我