2026年11408试卷真题及答案

2026年11408试卷真题及答案第一部分单项选择题（共40小题，每小题2分，共80分）已知某递归算法的时间复杂度递推式为T(n)=2T(n/4)+O(n)，且边界条件T(若栈的输入序列为1,2,3,4,5，下列选项中不可能得到的合法输出序列是A.2,1,3,5,4B.3,4,2,5,1C.1,5,2,3,4D.4,3,2,1,5已知非空双向循环链表中p指向某节点，其直接前驱节点存在，执行下列哪组操作可以删除p节点并释放对应空间A.p->prior->next=p->next;p->next->prior=p->prior;free(p);B.p->next->prior=p->prior;p->prior->next=p;free(p);C.p->prior->next=p;p->next->prior=p->prior;free(p);D.p->next->prior=p->next;p->prior->next=p->prior;free(p);一棵高度为4的3阶B树（根节点高度为1），其最多包含的关键字总数为A.26B.15C.8D.27已知二叉树的先序遍历序列为A,B,D,E,C,F,G，中序遍历序列为D,B,E,A,F,C,G，其后续遍历序列为A.D,E,B,F,G,C,AB.D,E,B,A,F,G,CC.A,B,C,D,E,F,GD.G,F,E,D,C,B,A下列排序算法中，最好时间复杂度为O(n)且稳定的是

A.快速排序B.直接插入排序C.已知无向图G包含6个顶点，其中边权值依次为1、2、3、4、5、6、7，该图的最小生成树的总权值不可能为A.10B.11C.12D.13已知哈希表的装填因子为0.7，采用线性探测法处理冲突，其平均查找长度约为A.2.5B.1.5C.3.2D.0.7若使用KMP算法对主串”ababcababac”和模式串”ababac”进行匹配，模式串的next数组元素值序列为A.0,1,1,2,3,4B.1,1,2,3,4,5C.0,1,2,1,2,3D.1,2,3,4,5,6下列关于红黑树的描述中，错误的是A.根节点一定是黑色的B.从任意节点到其所有叶节点的路径包含相同数量的黑色节点C.可以存在两个连续的红色节点D.所有叶节点（空指针节点）都是黑色的某32位RISC-V微处理器的指令字长固定为32位，其中I型立即数字段分配为：低7位为opcode，接下来3位为funct3，接下来5位为rs1编号，接下来5位为rd编号，剩余位存放带符号立即数，该I型指令可表示的立即数取值范围是A.-2048~2047B.-4096~4095C.-128~127D.-512~511某存储器按字节编址，地址总线位数为36位，数据总线位数为64位，该存储器的总容量为A.16GBB.64GBC.32GBD.4GB已知浮点数表示格式为1位符号位、5位阶码（移码表示，偏置值为16）、10位尾数（原码表示，隐藏最高位1），则十进制数-12.375的对应浮点数编码为A.1100111000111000B.1011011000111000C.0100111000111000D.1100110000111000下列关于RISC指令集特征的描述中，错误的是A.指令长度固定，译码复杂度低B.寻址方式数量远少于CISC指令集C.所有指令都支持访问任意内存单元D.通用寄存器数量远多于CISC指令集某指令流水线共包含5个流水段，每个流水段的延迟分别为2ns、1ns、3ns、2ns、2ns，忽略流水线寄存器延迟，该流水线的最大吞吐率为A.1/3(条/ns)B.1/2(条/ns)C.1/10(条/ns)D.1/5(条/ns)采用独立编址方式的I/O端口，其区分内存地址和I/O端口地址的依据是A.地址总线的最高位B.控制总线的专用读写信号C.不同的地址总线范围D.访问指令的操作码字段某系统总线的传输周期包含1个地址周期和3个数据周期，总线时钟频率为100MHz，总线位宽为32位，该总线的最大传输带宽为A.400MB/sB.300MB/sC.100MB/sD.800MB/s某8位二进制数的补码编码为11111001，其对应的十进制真值为A.-7B.7C.-121D.121下列关于虚拟存储器和Cache的描述中，正确的是A.二者均完全由硬件实现，对程序员完全透明B.二者均基于程序的局部性原理实现C.二者的替换算法完全由操作系统实现D.二者的块大小固定为4KB某DRAM芯片的存储容量为16M×32位，其行地址引脚数和列地址引脚数之和为A.24B.12C.13D.26向量中断方式下，中断向量地址存放的是A.中断服务程序的入口地址B.中断向量表对应的存储地址C.中断请求的优先级编号D.中断服务程序的返回地址某浮点数运算器对尾数做规格化处理，已知尾数采用补码表示，下列属于规格化正数的是A.0.01111B.0.10000C.1.01111D.1.10000某4核CPU系统采用抢占式短作业优先调度算法，忽略所有调度开销，4个作业的到达时间和要求运行时长分别为：A(0时刻,10ms)、B(1时刻,4ms)、C(2时刻,2ms)、D(3时刻,2ms)，所有作业全部完成后的平均周转时间为A.7.25msB.6.75msC.8msD.7.5ms下列关于多进程和多线程的描述中，错误的是A.同一进程内的多个线程可以共享进程的全局变量地址空间B.进程是资源分配的基本单位，线程是CPU调度的基本单位C.线程切换的开销远小于进程切换的开销D.多个独立线程执行时一定会触发进程间通信机制系统当前有3个并发进程，共同访问临界资源的互斥信号量初值为1，某时刻该信号量的当前值为-2，下列描述正确的是A.当前有2个进程在信号量的阻塞队列中等待B.当前有1个进程正在访问临界资源C.已经有2个进程执行了V操作D.当前所有进程都处于就绪状态某系统的内存物理地址空间总大小为8GB，采用分页存储管理方式，页面大小为4KB，某进程的页表总大小占用1MB存储空间，该进程的最大逻辑地址空间大小为A.2GBB.4GBC.1GBD.8GB下列磁盘调度算法中，平均寻道长度最短、且不会出现饥饿现象的是A.先来先服务算法B.最短寻道时间优先算法C.电梯调度算法D.循环扫描算法某文件系统采用索引节点管理磁盘块，每个索引节点包含10个直接地址项、1个一级索引项、1个二级索引项、1个三级索引项，磁盘块大小为4KB，每个地址项占4字节，该文件系统支持的单个最大文件大小约为A.4TBB.4GBC.4MBD.4KB下列关于死锁的四个必要条件中，可以通过破坏资源的独占访问特性来避免死锁的方法是A.银行家算法B.破坏环路等待条件C.SPooling技术D.资源一次性分配策略某系统采用静态优先级调度算法，下列进程中优先级最高的是A.运行时长1ms的终端交互进程B.运行时长1s的批处理大作业进程C.I/O频繁的视频解码进程D.操作系统内核的中断处理进程下列操作系统的存储管理方式中，会产生内部碎片的是A.分段存储管理B.分页存储管理C.可变分区分配D.段页式存储管理设备管理的缓冲池机制中，用于存放从设备输入的尚未被进程读取数据的缓冲队列是A.空缓冲队列B.输入缓冲队列C.输出缓冲队列D.工作缓冲队列QUIC协议作为HTTP/3的底层支撑协议，在TCP/IP参考模型中所处的层级是A.网络层B.传输层C.应用层（基于UDP实现传输层功能）D.数据链路层已知某主机的IP地址为32，子网掩码为24，该主机所处的子网的广播地址是A.59B.55C.27D.91下列关于CSMA/CD协议的描述中，正确的是A.该协议可以完全避免冲突的产生B.冲突检测的最长时间为信号在两个最远站点间传播时延的2倍C.该协议适用于所有无线局域网环境D.冲突发生后立刻重传当前帧即可保证传输成功TCP报文段的首部最小长度为A.20字节B.60字节C.10字节D.40字节某信道的信噪比为30dB，信道带宽为4kHz，依据香农定理，该信道的最大数据传输速率约为A.40kbpsB.12kbpsC.64kbpsD.56kbpsPPP协议在异步传输模式下采用的转义字符机制是A.比特填充B.字节填充C.字符计数D.标志位区分下列应用层协议中，默认使用UDP端口53的是A.FTPB.DNSC.SMTPD.HTTP路由协议RIP是基于距离矢量算法的内部网关协议，其最大跳数为A.15B.16C.31D.63单项选择题参考答案与解析选B，依据主定理，a=2、b=4，logba=0.5，f(n)与选C，若5先出栈，说明1、2、3、4已经全部入栈，后续出栈顺序必须满足4在3前、3在2前，不可能出现2在3、4之前的序列。选A，双向链表删除操作需要修改p的前驱节点的next指针指向p的后继，p的后继节点的prior指针指向p的前驱。选A，3阶B树每个节点最多容纳2个关键字，高度为4的树总关键字数为2*(2^3+2^2+2^1+2^0)=26。选A，通过先序和中序序列还原二叉树，后续遍历序列对应D,E,B,F,G,C,A。选B，直接插入排序在序列完全有序时时间复杂度为O(n)，且是稳定排序。选A，6个顶点的最小生成树包含5条边，从小到大选5条边1+2+3+4+5=15，最大最小生成树为13，不可能得到10。选A，线性探测法平均查找长度公式为(1+1/(1-ɑ))/2，代入ɑ=0.7计算得到约2.5。选A，KMP算法next数组计算规则得到序列为0,1,1,2,3,4。选C，红黑树明确规定不能存在两个连续的红色节点。选A，剩余立即数位数为12位，带符号数范围为−211到选B，按字节编址36位地址总线对应容量为236选A，转换为二进制规格化表示后对应编码为1100111000111000。选C，RISC架构的指令仅load/store指令可以访问内存，其余运算类指令仅操作寄存器。选A，流水线瓶颈段延迟为3ns，最大吞吐率为1/3条每ns。选B，独立编址依靠控制总线的专用I/O读写信号区分内存访问和I/O端口访问。选B，4个总线周期传输4字节3=12字节，总线时钟100MHz对应1s内25M个传输周期，总带宽为25M12B=300MB/s。选A，补码11111001转换为原码对应十进制-7。选B，虚拟存储器和Cache都基于局部性原理实现。选A，16M对应24位地址，DRAM行列地址分时传送，行列地址引脚总数为24。选A，向量中断的中断向量存储的是中断服务程序的入口地址。选B，规格化补码正数的符号位为0，最高数值位为1，对应0.10000。选B，四个作业周转时间分别为10ms、4ms、2ms、2ms，平均为(10+4+2+2)/4=6.75ms。选D，同一进程内的多个线程不需要触发进程间通信机制即可直接交换数据。选A，互斥信号量值为-2代表有2个进程在阻塞队列中等待临界资源。选A，每个页表项占4字节，1MB页表共262144个页表项，每个页面对应4KB，总大小为262144*4KB=2GB。选C，电梯调度算法兼顾寻道效率和不会出现饥饿现象。选B，计算总容量为104KB+10244KB+102410244KB+102410241024*4KB，受32位逻辑地址限制最大支持4GB文件。选C，SPooling技术将独占设备改造为共享设备，破坏了死锁的独占访问条件。选D，内核中断处理进程拥有系统最高优先级。选B，分页存储管理每个页面最后部分未占满的空间属于内部碎片。选B，输入缓冲队列用于存放设备输入的待处理数据。选C，QUIC基于UDP实现，属于应用层实现的类传输层协议。选A，子网地址为28，广播地址为59。选B，冲突检测的最大时长为端到端传播时延的2倍，即争用期。选A，TCP首部选项字段默认无附加信息，最小长度为20字节。选A，信噪比30dB对应功率比1000，香农公式计算得到速率约为40kbps。选B，PPP异步模式下采用字节填充机制转义特殊字符。选B，DNS查询默认使用UDP53端口。选A，RIP协议最大允许跳数为15，跳数16代表不可达。第二部分综合应用题（共7小题，共70分）（10分）已知带权无向图G的顶点集V={v1,v2,v3,v4,v5,v6}，边集E及权值为：(v1,v2,6)、(v1,v3,1)、(v1,v4,5)、(v2,v3,5)、(v2,v5,3)、(v3,v4,5)、(v3,v5,6)、(v3,v6,4)、(v4,v6,2)、(v5,v6,6)。请分别给出用Prim算法从v1顶点出发构造最小生成树的过程、最小生成树的总权值，以及图G从v1到所有其他顶点的Dijkstra最短路径长度。参考解答：Prim算法从v1开始依次加入的顶点顺序为v1→v3→v2→v6→v4→v5，每次选择当前连接已选集合和未选集合的最小权边，选中的边依次为(v1,v3,1)、(v2,v3,5)、(v3,v6,4)、(v4,v6,2)、(v2,v5,3)，最小生成树总权值为1+2+3+4+5=15。Dijkstra算法得到的各顶点最短路径长度为v1到v2为6，v1到v3为1，v1到v4为7，v1到v5为9，v1到v6为7。（15分）已知长度为n的整型数组arr，所有元素取值范围为1~n，数组中恰好有2个整数各自重复出现了1次，其余元素均仅出现1次。请设计时间复杂度为O(n)、空间复杂度为O(1)的算法，找到这两个重复的整数，要求写出算法思路、核心代码片段，并推导复杂度符合要求的依据。参考解答：算法思路：首先遍历数组所有元素，将下标为arr[i]的位置的元素取反，遍历完成后所有值为正的下标就是第一次遍历检测到的重复数之一，记录第一个重复数后，计算数组所有元素的总和减去1~n的总和得到两个重复数之和，用该和减去第一个重复数即可得到第二个重复数，全程不需要额外的标记数组，遍历次数仅为2次，时间复杂度为O(n)，仅使用若干临时变量，空间复杂度为O(1)。代码实现核心逻辑如下：

intfindTwoDup(intarr[],intn,int*res1,int*res2){

intsum1=0,sum2=0,s=n*(n+1)/2;

for(inti=0;i<n;i++)sum1+=arr[i];

*res1=0;

for(inti=0;i<n;i++){

intidx=abs(arr[i]);

if(arr[idx-1]<0){*res1=idx;break;}

arr[idx-1]=-arr[idx-1];

}

*res2=sum1-s-*res1;

return0;

}复杂度推导：两次线性遍历数组，总执行次数与n线性相关，无嵌套循环，时间复杂度为O(n)，额外开辟的空间不随n的增长而变化，空间复杂度为O(1)，符合题目要求。（12分）某32位CPU系统的主存总容量为16MB，采用4路组相联Cache，Cache总容量为64KB，每个Cache块大小为32B。请计算该Cache的总组数、主存地址的标记位位数、组索引位位数、块内偏移位位数，假设CPU连续访问主存地址序列从0开始，步长为32B，共访问200次，初始状态Cache全部为空，计算该访问序列的Cache命中率，以及对应的平均访存时间（已知主存访问延迟为100ns，Cache访问延迟为2ns）。参考解答：块内偏移位为log232=5位，Cache总块数为64KB/32B=2048块，4路组相联对应总组数为2048/4=512组，组索引位为log2参考解答：FIFO置换算法缺页次数为9，缺页率为9/12=75%；LRU最近最少使用置换算法缺页次数为8，缺页率为8/12≈66.7%，LRU算法缺页次数更低，符合局部性原理