2026年408考研测试题及答案

2026年408考研测试题及答案

一、单项选择题（10题，每题2分）1.数据结构中，某算法对n个元素进行排序，平均比较次数为n(n-1)/2，其时间复杂度为（）。A.O(1)B.O(n)C.O(n²)D.O(2ⁿ)2.栈的基本操作中，不可能在O(1)时间完成的是（）。A.入栈B.出栈C.取栈顶元素D.求栈的大小3.已知二叉树前序遍历序列为A,B,D,C,E，中序遍历序列为B,D,A,E,C，则后序遍历序列为（）。A.D,B,E,C,AB.D,B,E,A,CC.D,E,B,C,AD.D,B,A,E,C4.图的邻接表存储中，每个顶点的邻接表存储的是（）。A.该顶点的入边B.该顶点的出边C.与该顶点相关的所有边D.该顶点的度5.CPU执行指令过程中，可能插入等待周期的阶段是（）。A.取指B.译码C.执行D.间址6.Cache的命中率H定义为（）。A.命中次数/总访问次数B.总访问次数/命中次数C.总时间/命中时间D.命中时间/总时间7.指令流水线的基本级别不包括（）。A.取指B.译码C.执行D.编译8.可能导致进程饥饿的调度算法是（）。A.先来先服务B.时间片轮转C.最高优先级D.多级反馈队列9.分页存储管理中页表的核心作用是（）。A.将逻辑地址转换为物理地址B.记录进程的页号C.管理内存空闲块D.实现页面置换10.IP地址/24的网络地址是（）。A.B.C.D.5511.TCP三次握手的主要作用是（）。A.建立可靠的端到端连接B.同步序列号C.确认数据传输顺序D.协商窗口大小12.下列属于数据链路层的协议是（）。A.IPB.TCPC.ARPD.DNS13.操作系统中，进程状态转换时，不可能发生的是（）。A.运行态→就绪态B.阻塞态→运行态C.就绪态→运行态D.运行态→阻塞态14.死锁预防的核心策略是破坏死锁的（）。A.互斥条件B.请求与保持条件C.不剥夺条件D.循环等待条件15.虚拟内存技术中，页面置换算法LRU的含义是（）。A.最近最少使用B.最佳置换C.先进先出D.时钟置换16.计算机组成原理中，总线按传输信息类型分为（）。A.地址总线、数据总线、控制总线B.内部总线、系统总线、外部总线C.并行总线、串行总线、双向总线D.片内总线、局部总线、系统总线17.中断处理过程中，系统自动保存的是（）。A.程序计数器和状态寄存器B.通用寄存器和程序计数器C.数据寄存器和状态寄存器D.指令寄存器和地址寄存器18.下列不属于文件管理功能的是（）。A.文件存储空间分配B.文件目录管理C.进程调度D.文件安全性控制19.UDP协议的端口号范围是（）。A.0-1023B.1024-65535C.1-65535D.0-6553520.树的高度为h（根为1层），其最少节点数为（）。A.hB.2^(h-1)C.h(h+1)/2D.h(h-1)/2+1二、填空题（10题，每题2分）1.栈的操作原则是______，常见存储结构为顺序存储和______。2.二叉树按层序遍历顺序为A,B,C,D,E,F，其前序遍历可能为______。3.图的邻接矩阵存储中，邻接矩阵的第i行非零元素个数等于顶点i的______。4.Cache与主存的映射方式有全相联、直接相联和______，其中______命中率最高。5.指令寻址方式决定了______的来源，常见方式有立即寻址、直接寻址和______。6.进程调度的三个基本状态是运行态、就绪态和______；死锁的四个必要条件包括互斥、请求与保持、______和循环等待。7.虚拟内存技术中，页面置换算法除LRU外，还包括FIFO（先进先出）和______（写出一种即可），其中______实现开销最大。8.TCP/IP模型应用层的常见协议有HTTP、FTP和______，IP地址/16的广播地址是______。9.数据链路层的主要功能是将IP数据报封装成______，并通过______协议检测传输错误。10.运输层的UDP使用______复用分用，TCP使用______机制实现可靠传输。三、判断题（10题，每题2分）1.算法的时间复杂度与空间复杂度一定正相关。（）2.栈可通过队列实现，队列可通过栈实现。（）3.完全二叉树的第i层节点数一定为2^(i-1)。（）4.中断处理过程中系统会自动屏蔽所有中断请求。（）5.虚拟存储器容量取决于内存和外存总容量。（）6.时间片轮转调度一定能保证每个进程获得公平CPU时间。（）7.文件目录项包含文件名和物理地址等信息。（）8.TCP三次握手可防止重复连接请求。（）9.物理层定义了电气特性和机械特性。（）10.进程调度算法均可抢占CPU。（）四、简答题（4题，每题5分）1.简述快速排序的基本思想及优化方法。2.说明Cache的工作原理及主要性能指标。3.比较进程调度与作业调度的区别。4.解释TCP三次握手的过程及作用。五、讨论题（4题，每题5分）1.分析死锁产生原因及银行家算法的核心思路。2.比较页式与段式存储管理的优缺点及地址映射方式。3.为什么说TCP比UDP更可靠？结合机制说明。4.设计简单文件系统需考虑哪些关键问题？答案和解析一、单项选择题答案1.C解析：平均比较次数n(n-1)/2对应冒泡排序/插入排序的平均时间复杂度O(n²)。2.D解析：求栈大小需遍历或维护计数器，时间O(n)，其他操作均为O(1)。3.A解析：前序A为根，中序左子树B,D，右子树E,C，左子树前序B,D，右子树前序E,C，后序遍历左→右→根，得D,B,E,C,A。4.B解析：邻接表存储顶点的出边，入边用逆邻接表。5.A解析：取指阶段需从内存读指令，若内存速度慢，CPU需等待，插入等待周期。6.A解析：Cache命中率=命中次数/总访问次数。7.D解析：编译为前端，非流水线基本阶段。8.C解析：最高优先级调度若优先级不变，低优先级进程可能长期等待。9.A解析：页表将逻辑页号映射到物理块号，实现地址转换。10.A解析：IP地址/24的网络地址为（/24表示前24位为网络位）。11.A解析：三次握手建立可靠连接，同步序列号为辅助功能。12.C解析：ARP为数据链路层协议，IP为网络层，TCP/UDP为运输层。13.B解析：进程只能从阻塞态→就绪态，无法直接→运行态（需调度）。14.B解析：死锁预防破坏“请求与保持”条件（需一次性申请资源）。15.A解析：LRU即最近最少使用页面置换算法。16.A解析：总线按信息类型分为地址、数据、控制总线。17.A解析：中断处理需保存程序计数器（PC）和状态寄存器（PSW）。18.C解析：进程调度属于CPU管理，非文件管理。19.D解析：UDP端口号范围为0-65535（动态端口范围1024-65535）。20.A解析：树的最少节点数为高度h（线性链），最多为2^(h-1)。二、填空题答案1.后进先出（LIFO）链式存储2.A,B,D,C,E,F（或其他合理前序序列）3.出度4.组相联全相联5.操作数间接寻址6.阻塞态不可剥夺7.OPT（或NRU）LRU8.SMTP（或Telnet）559.帧（或数据帧）CRC10.端口号确认重传三、判断题答案1.×解析：时间复杂度与空间复杂度无必然联系（如快速排序空间O(logn)vs冒泡排序O(1)）。2.×解析：队列可实现栈（先进先出→后进先出），但栈无法实现队列（O(1)出队需双栈）。3.×解析：完全二叉树第i层最少节点数为1（仅根节点时），最多为2^(i-1)。4.×解析：仅屏蔽当前中断，允许优先级更高的中断。5.×解析：虚拟内存容量受限于地址总线宽度（如4GB），而非内存+外存总和。6.×解析：短进程可能因长进程抢占导致饥饿。7.√解析：目录项包含文件名、物理地址（如inode）或索引指针。8.√解析：三次握手通过初始序列号防止重复连接请求。9.√解析：物理层定义机械特性（接口形状）、电气特性（电压范围）。10.×解析：非抢占式调度（如FCFS）不可抢占。四、简答题答案1.快速排序：基本思想是分治，选基准划分左右子数组，递归排序。优化：基准选三数中值（首中尾）、小规模数组改用插入排序、尾递归优化栈空间。2.Cache：原理是基于局部性原理，将频繁访问数据暂存于高速Cache，访问时先查Cache。指标：命中率、平均访问时间、失效率、带宽。3.区别：进程调度（短期）：CPU分配；作业调度（长期）：作业装入内存。调度对象：进程vs作业；频率：进程秒级vs作业分钟级。4.TCP三次握手：SYN（客户端→服务端）、SYN+ACK（服务端→客户端）、ACK（客户端→服务端）。作用：同步初始序列号，确认双方收发能力，建立可靠连接。五、讨论题答案1.死锁原因：资源不足、进程推进顺序不当。银行家算法：通过检查资源分配安全性，模拟分配后系统是否仍安全，避免死锁。核心：需求-分配-释放模拟，拒绝不安全请求。2.页式：优点：离散分配、无碎片；缺点：地址空间连续。段式：优点：逻辑独立、共享方便；缺点：内存碎片大。地址映射：页式通过页表（页号→块号），段式通过段表（段号→基址