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

声明：

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

§一 单项选择：

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

DataStructure

№1✍️ 下列对顺序存储的有序表｛长度为正整数n｝实现给定操作的算法中，平均时间复杂度为𝜪(1)是（🔠）？

  • 🄰查找包含指定值元素的算法
  • 🄱插入指定下标元素的算法
  • 🄲删除第idx个元素的算法
  • 🄳获取第idx个元素的算法
【D】简单题。我们知道array[idx+1]就可以直接完成该“算法”。

№2✍️ 现有非空双向链表DL，其结点结构为[prev|data|next]，prev是前驱指针，next是后继指针。若要在DL中指针p所指向的结点｛非尾结点｝之后插入指针s指向的新结点，则在执行了语句序列s->next = p->next; p->next = s后，还要执行的是（🔠）？

  • 🄰s->next->prev = p; s->prev = p;
  • 🄱p->next->prev = s; s->prev = p;
  • 🄲s->prev = s->next->prev; s->next->prev = s;
  • 🄳p->next->prev = s->prev; s->next->prev = p;
【C】简单题。。

№3✍️ 若采用三元组表存储稀疏矩阵SM，要求能从三元组表还原矩阵，则除三元组表外，还需要保存的是（🔠）？

Ⅰ꙳SM的行数   Ⅱ꙳SM中包含非零元素的行数   Ⅲ꙳SM的列数   Ⅳ꙳SM中包含非零元素的列数

  • 🄰Ⅰ,Ⅲ,
  • 🄱Ⅰ,Ⅳ,
  • 🄲Ⅱ,Ⅳ,
  • 🄳Ⅰ,Ⅱ,Ⅲ,Ⅳ,
【A】简单题。注意矩阵的行数跟列数不一定相等，都要存。

№4✍️ 在由6个字符组成字符集CS中，各字符出现的频次分别为3,4,5,6,8,10，为CS构造的哈夫曼编码的加权平均长度为（🔠）？

  • 🄰2.4
  • 🄱2.5
  • 🄲2.67
  • 🄳2.75
【B】所构造哈夫曼树如解图，加权平均长度等于分支结点之和除以叶结点之和，(36+15+21+7+11)÷(2+4+5+6+8+10)=2.5。

№5✍️ 已知一棵二叉树的树形如右图所示，若其后序遍历序列为f,d,b,e,c,a，则其先序遍历序列是（🔠）？

  • 🄰a,e,d,f,b,c,
  • 🄱a,c,e,b,d,f,
  • 🄲c,a,b,e,f,d,
  • 🄳d,f,e,b,a,c,
【A】后序序列中只能确定最后一个是根，再结合树形，还原二叉树如解图。

№6✍️ 已知无向连通图UCG中各边的权值均为1。下列算法中，一定能求出UCG中从某顶点到其余各顶点最短路径的是（🔠）？

Ⅰ꙳Prim算法   Ⅱ꙳Kruskal算法   Ⅲ꙳BFS算法

  • 🄰Ⅰ,
  • 🄱Ⅲ,
  • 🄲Ⅰ,Ⅱ,
  • 🄳Ⅰ,Ⅱ,Ⅲ,
【B】各边权值相等可以用BFS算法，各边权值不相等的图只能用Dijkstra算法和Floyd算法。

№7✍️ 下列非空B-树的叙述中，正确的是（🔠）？

Ⅰ꙳插入操作可能增加树的高度           Ⅱ꙳删除操作一定会导致叶结点的变化
Ⅲ꙳查找某关键字总是要追寻到根结点     Ⅳ꙳插入的新关键字最终位于叶结点中

  • 🄰Ⅰ,
  • 🄱Ⅰ,Ⅱ,
  • 🄲Ⅲ,Ⅳ,
  • 🄳Ⅰ,Ⅱ,Ⅳ,
【B】回忆B-树的插入删除操作。

№8✍️ 对含有600个元素的有序顺序表进行折半查找，关键字间的比较次数最多是（🔠）？

  • 🄰9
  • 🄱10
  • 🄲30
  • 🄳300
【B】⌊log(600)⌋+1=10。

№9✍️ 现有长度为5，初始为空的散列表HT，散列函数𝑯𝒂𝒔𝒉(𝑘)=(𝑘+4)%5，用线性探查再散列法解决冲突。若关键字序列2022,12,25依次插入HT中，然后删除25，则HT中查找失败的平均查找长度是（🔠）？

  • 🄰1
  • 🄱1.6
  • 🄲1.8
  • 🄳2.2
【C】再散列法解决冲突用和都是懒删除，即只作个删除标记。为什么呢？因为真删除会导致后面添加进来的关键字无法通过线性探测找到正确的位置。(1+3+2+1+2)÷5=1.8。

№10✍️ 下列排序算法中，不稳定的有（🔠）？

Ⅰ꙳希尔排序     Ⅱ꙳归并排序     Ⅲ꙳查快速排序     Ⅳ꙳堆排序     Ⅴ꙳基数排序

  • 🄰Ⅰ,Ⅱ,
  • 🄱Ⅱ,Ⅴ,
  • 🄲Ⅰ,Ⅲ,Ⅳ,
  • 🄳Ⅲ,Ⅳ,Ⅴ,
【C】稳定的有“插冒归基”。

№11✍️ 使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是68,11,70,23,80,77,48,81,93,88，则该次划分的枢轴是（🔠）？

  • 🄰11
  • 🄱70
  • 🄲80
  • 🄳81
【D】只有81满足〔左边全比它小右边全比它大〕。

ComputerOrganization

№12✍️ 若机器M的主频为1.5GHz，在M上执行程序P指令数为5×exp10(5)，P的平均CPI为1.2，则P在M上的指令执行速度和用户CPU时间分别为（🔠）？

  • 🄰0.8GIPS,0.4ms,
  • 🄱0.8GIPS,0.4us,
  • 🄲1.25GIPS,0.4ms,
  • 🄳1.25GIPS,0.4us,
【C】P在M上的指令执行速度=1.5G÷1.2=1.25GIPS，用户CPU时间=5×exp10(5)÷1.25G=0.4ms。

№13✍️ 若short型变量x=-8190，则x的机器数是（🔠）？

  • 🄰0xE002
  • 🄱0xE001
  • 🄲0x9FFF
  • 🄳0x9FFE
【A】short型为16位补码，8190=0c0:001,1111,1111,1110，-8190=0b1:110,0000,0000,0010。

№14✍️ 已知float型变量用IEEE754单精度浮点数格式表示。若float型变量x的机器数为0x8020,0000，则x的真值是（🔠）？

  • 🄰-1.0×exp(-128)
  • 🄱-1.25×exp(-127)
  • 🄲-1.25×exp(-126)
  • 🄳NaN
【A】阶数全0为非规格化数，-0b0.01×exp(-126)=-1.0×exp(-128)。

№15✍️ 某计算机的CPU有30根地址线，按字节编址，CPU和主存连接时，要求主存芯片占满所有可能的存储地址空间，并且RAM区和ROM区所分配的空间大小为3:1。若RAM在连续低地址区，ROM在连续高地址区，则ROM的地址范围（🔠）？

  • 🄰0x0000,0000～0x0FFF,FFFF
  • 🄱0x1000,0000～0x2FFF,FFFF
  • 🄲0x3000,0000～0x3FFF,FFFF
  • 🄳0x4000,0000～0x4FFF,FFFF
【C】RAM占0x0000,0000～0x0FFF,FFFF、0x1000,0000～0x1FFF,FFFF、0x2000,0000～0x2FFF,FFFF，ROM占0x3000,0000～0x3FFF,FFFF。

№16✍️ 已知x,y为int型，当x=100,y=200时，执行“x-y”得到的溢出标志OF、借位标志CF分别为0、1，那么当x=10,y=-20时，执行得到的OF、CF分别是（🔠）？

  • 🄰OF=0,CF=0,
  • 🄱OF=0,CF=1,
  • 🄲OF=1,CF=0,
  • 🄳OF=1,CF=1,
【B】易错题。x-y=10+20=30，不大于INT_MAX，OF=0。计算CF时要把操作数当作无符号数，-20将转变为exp(32)-20，很明显10不够减要借位，CF=1。

№17✍️ 某运算类型指令中有一个地址码为通用寄存器编号，对应通用寄存器存放的是操作数或操作数的主存地址，CPU区分两者的依据是（🔠）？

  • 🄰操作数的寻址方式
  • 🄱操作数的编码方式
  • 🄲通用寄存器的编号
  • 🄳通用寄存器的编号
【A】寄存器直接寻址，存放的是操作数；寄存器间接寻址，存放的是操作数的主存地址。

№18✍️ 数据通路由组合逻辑元件｛操作元件｝、时序逻辑元件｛状态元件｝组成，以下给出的元件中，属于组合逻辑元件的是（🔠）？

Ⅰ꙳算术逻辑单元"ALU"     Ⅱ꙳程序计数器"PC"     Ⅲ꙳通用寄存器组"GPRs"     Ⅳ꙳多路选择器"MUX"

  • 🄰Ⅰ,Ⅱ,
  • 🄱Ⅰ,Ⅳ,
  • 🄲Ⅱ,Ⅲ,
  • 🄳Ⅰ,Ⅱ,Ⅳ,
【B】书上没有。两者的区别是：操作元件，输出仅取决于输入，如与门或门、多路选择器、比较器、加减法器。状态元件，输出不只取决于输入，还受存储器或时钟信号的影响，具有记忆功能，如触发器、计数器、寄存器。

№19✍️ 某计算机采用〈取指，译码／取数，执行，访存，写回〉的5段流水线，RISC处理器中执行如下指令序列，其中第1列是指令序号，s0,s1,s2,s3,t2是寄存器编号。若采用旁路技术处理数据冒险，采用硬件阻塞方式处理控制冒险，则在I1～I4执行过程中，发生流水线阻塞的是（🔠）？

I1    add s2, s1, s0    ; R[s2]←R[s1]+R[s0]
I2    load s3, 0(s2)    ; R[s3]←Mem[R[s2]+0]
I3    beq t2, s3, L1    ; if R[t2]=R[s3] jump L1
I4    addi t2, t2, 20   ; R[t2]←R[t2]+20
I5    L1:...
  • 🄰I3,
  • 🄱I2,I4,
  • 🄲I3,I4,
  • 🄳I2,I3,I4,
【C】如解图。

№20✍️ 某存储总线宽度为64b，总线时钟频率为1GHz，在总线上传输一个数据或地址需要一个时钟周期，不支持突发传送方式。若通过该总线连接CPU和主存，主存每次准备一个64b数据需要6ns，主存块大小为32B，则读取一个主存块需要的时间是（🔠）？

  • 🄰8ns
  • 🄱11ns
  • 🄲26ns
  • 🄳32ns
【D】1个时钟周期是1÷1GHz=1ns，CPU传地址1ns、主存准备数据6ns、主存传数据1ns，需要32B÷64b=4次，共4×8ns=32ns。

№21✍️ 下列关于硬件和异常／中断关系的叙述中，错误的是（🔠）？

  • 🄰CPU在执行一条指令的过程中检测异常事件。
  • 🄱CPU在执行完一条指令时检测中断请求信号。
  • 🄲开中断时CPU检测到中断请求后就进行中断响应。
  • 🄳外部设备通过中断控制器向CPU发中断结束信号。
【D】中断服务程序执行完成后会直接返回，不需要外设发中断结束信号。

№22✍️ 下列关于I/O控制方式的叙述中，错误的是（🔠）？

  • 🄰查询方式下，通过CPU执行查询程序进行I/O操作。
  • 🄱中断方式下，通过CPU执行中断服务程序进行I/O操作。
  • 🄲DMA方式下，通过CPU执行DMA传送程序进行I/O操作。
  • 🄳对于SSD、网络适配器等高速设备，采用DMA方式输入输出。
【C】DMA传送程序不需要CPU来执行。

OperatingSystem

№23✍️ 与宏内核相比，微内核具有的特征是（🔠）？

Ⅰ꙳较好的性能     Ⅱ꙳较高的可靠性     Ⅲ꙳较高的安全性     Ⅳ꙳较强的可扩展性

  • 🄰Ⅱ,Ⅳ,
  • 🄱Ⅰ,Ⅱ,Ⅲ,
  • 🄲Ⅰ,Ⅲ,Ⅳ,
  • 🄳Ⅱ,Ⅲ,Ⅳ,
【D】概念题。微内核操作系统采用模块化设计，将一部分功能移至用户空间，这就需要通过进程间通信机制来实现系统内核与用户空间的交互。这种通信会引入额外的开销，包括上下文切换、数据拷贝等。

№24✍️ 在操作系统内核中，中断向量表适合采用的数据结构是（🔠）？

  • 🄰数组
  • 🄱队列
  • 🄲单向链表
  • 🄳双向链表
【A】通过中断号寻找中断处理程序入口地址的过程正好像通过下标访问数组元素。

№25✍️ 某系统采用分页式存储管理，用位图管理空闲页框。若页大小为4KB，物理内存大小为16GB，则位图所占空间大小是（🔠）？

  • 🄰128B
  • 🄱128KB
  • 🄲512KB
  • 🄳4MB
【C】16GB÷4KB×1b=512KB。

№26✍️ 下列操作完成时，导致CPU从内核态转为用户态的是（🔠）？

  • 🄰阻塞进程
  • 🄱执行CPU调度
  • 🄲唤醒进程
  • 🄳执行系统调用
【D】当用户程序需要访问特权指令或需要操作系统提供的服务时，它会通过系统调用请求进入内核态。在系统调用期间，CPU会切换到内核态执行相应的内核代码来满足用户程序的需求。一旦系统调用执行完毕，CPU会从内核态返回到用户态继续执行用户程序。

№27✍️ 下列由当前线程引起的事件或执行的操作中，可能导致该线程由运行态变为就绪态的是（🔠）？

  • 🄰键盘输入
  • 🄱缺页异常
  • 🄲主动让出CPU
  • 🄳信号量的wait()操作
【C】就绪态的条件是只缺CPU，不缺资源。

№28✍️ 对于采用虚拟内存管理方式的系统，下列关于进程虚拟地址空间的叙述中，错误的是（🔠）？

  • 🄰每个进程都有自己独立的虚拟地址空间。
  • 🄱C语言中的malloc()函数返回的是虚拟地址。
  • 🄲进程对数据段和代码段可以有不同的访问权限。
  • 🄳虚拟地址空间的大小由内存和外存决定。
【D】虚拟地址空间的大小受内存外存容量之和，还受系统地址位数的限制。

№29✍️ 进程P1、P2、P3进入就绪队列的时刻、优先级｛值越大越优先｝、CPU的执行时间如下表所示。若系统采用基于优先权的抢占式CPU调度算法，从0ms时刻开始进行调度，则P1、P2、P3的平均周转时间是（🔠）？

进程名进入就绪队列时刻优先级CPU执行时间
P10ms160ms
P220ms1042ms
P330ms10013ms
  • 🄰60ms
  • 🄱61ms
  • 🄲70ms
  • 🄳71ms
【B】如解图，(115+55+13)ms÷3=61ms。

№30✍️ 进程R、S共享数据data，若data在R、S中所在页的页面号分别为p1、p2，两个页所对应的页框号分别为f1、f2，则下列叙述中正确的是（🔠）？

  • 🄰p1和p2一定相等，f1和f2一定相等。
  • 🄱p1和p2一定相等，f1和f2不一定相等。
  • 🄲p1和p2不一定相等，f1和f2一定相等。
  • 🄳p1和p2不一定相等，f1和f2不一定相等。
【C】data在物理内存只有一份，因此f1和f2一定相等，但R和S有各自的页表，p1和p2可以不相等。

№31✍️ 若文件F仅被进程P打开并访问，则当进程P关闭F时，下列操作中文件系统需要完成的是（🔠）？

  • 🄰删除目录文件中F的目录项
  • 🄱释放F的索引节点所占的内存空间
  • 🄲释放F的索引节点所占的外存空间
  • 🄳将F在外存索引结点中的链接计数减1
【B】当进程关闭文件时，相关的文件描述符被释放，文件系统回收与之关联的内存。选项D是迷惑项，文件被关闭后，内存索引结点的访问计数减1，并非外存。

№32✍️ 下列因素中，设备分配需要考虑的是（🔠）？

Ⅰ꙳设备的类型     Ⅱ꙳设备的访问权限     Ⅲ꙳设备和占用状态     Ⅳ꙳逻辑设备与实体设备的映射关系

  • 🄰Ⅰ,Ⅱ,
  • 🄱Ⅱ,Ⅲ,
  • 🄲Ⅲ,Ⅳ,
  • 🄳Ⅰ,Ⅱ,Ⅲ,Ⅳ,
【D】简单题。

ComputerNetWork

№33✍️ 在下图所示的分组交换网络中，主机H1和H2通过路由器互连，2段链路的带宽均为100Mbps，时延带宽积｛即单向传播时延×宽带｝均为1000b。若H1向H2发送1个大小为1MB｛M视作exp10(6)｝的文件，分组长度1000B，则从H1开始发送时刻起到H2收到文件全部数据时刻止，所需的时间至少是（🔠）？

  • 🄰80.02ms
  • 🄱80.08ms
  • 🄲80.09ms
  • 🄳80.10ms
【B】单向传播时延=1000b÷100Mbps=0.01ms，分组发送时延=1000B÷100Mbps=0.08ms，有1MB÷1000B=1000个分组，2条链路，由公式得所需时间=(1000+2-1)×0.08ms+2×0.01ms=80.10ms。

№34✍️ 某无噪声理想信道带宽为4MHz，采用QAM“正交幅度调制”"QuadratureAmplitudeModulation"，若该信道的最大数据传输速率是48Mbps，则该信道采用的QAM方案是（🔠）？

  • 🄰QAM-16
  • 🄱QAM-32
  • 🄲QAM-64
  • 🄳QAM-128
【C】由奈氏准则，最高码元传输速率=2×4MHz，每码元可携带比特数=最大数据传输速率÷最高码元传输速率=48Mbps÷8MHz=6，那么可以调制出exp(6)=64种基本波形。

№35✍️ 假设通过同一信道，数据链路层分别采用的协议是SW、GBN、SR｛发送窗口和接收窗口相等｝传输数据，三个协议的数据帧长相同，忽略确认帧长度，帧序号占3比特。若对应三个协议的发送方最大信道利用率分别是U1、U2、U3，则U1、U2、U3满足的关系是（🔠）？

  • 🄰U1≤U2≤U3
  • 🄱U1≤U3≤U2
  • 🄲U2≤U3≤U1
  • 🄳U3≤U2≤U1
【B】发送方最大信道利用率随发送窗口的增大而增大，GBN的发送窗口最大为exp(3)-1=7，SR的发送窗口最大为exp(3)÷2=4，而SW的发送窗口固定为1。

№36✍️ 已知10BaseT以太网的争用时间片为51.2us。若网卡在发送某帧时发生了连续4次冲突，则基
于二进制指数退避算法确定的再次尝试重发该帧前等待的最长时间是（🔠）？

  • 🄰51.2us
  • 🄱204.8us
  • 🄲768us
  • 🄳819.2us
【B】。

№37✍️ 若甲向乙发送数据时采用循环冗余校验CRC，生成多项式为𝑮(𝑥)=𝑥^𝟒+𝑥+𝟏，则乙接收到下列比特串时，可以断定其在传输过程中未发生错误的是（🔠）？

  • 🄰1,0111,0000
  • 🄱1,0111,0100
  • 🄲1,0111,1000
  • 🄳1,0111,1100
【D】按照CRC的校验方式，以选项D为例，1,0111,1100,0000对10011做异或除法，余数为0。

№38✍️ 某网络拓扑如下图所示，其中路由器R2实现NAT功能。若主机E向Internet发送一个IP分组，则经过R2转发后，该IP分组的源IP地址是（🔠）？

  • 🄰195.123.0.33
  • 🄱195.123.0.35
  • 🄲192.168.0.1
  • 192.168.0.3
【A】经过R2的NAT转发后，IP分组的源IP地址将变为R2的NAT口IP地址，子网段192.123.0.34/30只剩1个IP地址可用，就是195.123.0.33。

№39✍️ 主机168.16.84.24/20所在子网的最小可分配IP地址和最大可分配IP地址分别是（🔠）？

  • 🄰168.16.80.1,168.16.84.254,
  • 🄱168.16.80.1,168.16.95.254,
  • 🄲168.16.84.1,168.16.84.254,
  • 168.16.84.1,168.16.95.254,
【B】考CIDR地址划分。

№40✍️ 下列关于IPv4和IPv6的叙述中，正确的是（🔠）？

Ⅰ꙳IPv6地址空间是IPv4地址空间的96倍。
Ⅱ꙳IPv4首部和IPv6基本首部的长度均可变。
Ⅲ꙳IPv4向IPv6过渡可以采用双协议栈和隧道技术。
Ⅳ꙳IPv6首部的Hop-Limit字段等价于IPv4首部的TTL字段。

  • 🄰Ⅰ,Ⅱ,
  • 🄱Ⅰ,Ⅳ,
  • 🄲Ⅱ,Ⅲ,
  • 🄳Ⅲ,Ⅳ,
【D】概念题。
最后修改于：2025年08月08日
© 允许规范转载
如果觉得我的文章对你有用请狠狠地打赏我