2026年考研复试题库及答案解析

2026年考研复试题库及答案解析一、单项选择题（每题3分，共30分）1.在一个具有5个结点的二叉排序树中，查找一个不存在的关键字，所需的最大比较次数是（）。A.3B.4C.5D.62.下列关于虚拟内存的叙述中，错误的是（）。A.虚拟内存的引入是为了扩充物理内存B.虚拟内存的实现基于局部性原理C.虚拟内存的大小受限于物理内存的大小D.虚拟内存允许程序在部分装入内存时即可运行3.TCP协议在建立连接时，采用三次握手。假设主机A向主机B发起连接，A发送的SYN报文段中序号字段为seq=x，则B返回的SYN+ACK报文段中，确认号字段A.aB.aC.aD.a4.一个浮点数采用IEEE754单精度格式表示，其机器数为010000011A.12.0B.24.0C.48.0D.96.05.在关系数据库中，若关系模式R∈A.R必定属于BCNFB.R中不存在传递依赖C.R中每个非主属性既不部分依赖于候选键，也不传递依赖于候选键D.R中不存在主属性对候选键的部分依赖和传递依赖6.某分页存储管理系统中，页面大小为4KB。若进程A的逻辑地址为0xA.0B.0C.0D.07.在CSMA/CD协议中，假设网络中的单程端到端传播时延为τ，数据帧的发送时延为T，为了确保能够检测到冲突，必须满足（）。A.TB.TC.TD.T8.对于给定的关键字序列12,A.12B.23C.34D.679.在计算机体系结构中，指令流水线中出现“数据冒险”是指（）。A.后续指令需要的操作数尚未由前一条指令计算完成B.指令在执行过程中遇到了转移指令C.多条指令在同一时刻争用同一个硬件功能部件D.取指令时发生了缺页中断10.若一组记录的初始关键字序列为49,A.27B.13C.27D.27二、多项选择题（每题4分，共20分，漏选得2分，错选不得分）1.下列排序算法中，时间复杂度在最坏情况下为O(A.快速排序B.归并排序C.堆排序D.冒泡排序2.进程的三种基本状态是就绪、运行和阻塞。下列状态转换中，可能发生的有（）。A.就绪→运行B.运行→就绪C.运行→阻塞D.阻塞→运行3.TCP/IP参考模型中，属于应用层的协议有（）。A.HTTPB.FTPC.ARPD.DNS4.在数据库并发控制中，封锁协议能够保证的一致性特征包括（）。A.无丢失修改B.不可重复读C.不读“脏”数据D.死锁避免5.引入高速缓存是为了解决CPU与主存之间速度不匹配的问题。下列关于Cache的描述，正确的有（）。A.Cache的存取速度比主存快，但比CPU寄存器慢B.Cache与主存之间的映射完全由硬件实现C.程序的局部性原理是Cache工作的基础D.命中率是衡量Cache性能的重要指标，命中率越高，等效存取速度越接近主存三、填空题（每空2分，共20分）1.已知一棵完全二叉树有n个结点，若n为偶数，则该树中度为1的结点个数为__________；若n为奇数，则度为1的结点个数为__________。2.在操作系统的I/O控制方式中，__________方式主要用于高速外设与主存之间的数据传输，在此过程中CPU不需要干预数据传输的细节。3.在IPv4中，地址``属于__________类地址，其默认的子网掩码是__________。4.浮点数加减法运算的对阶原则是__________，以防止尾数溢出导致数据丢失。5.设关系模式R(A,B,6.在指令流水线中，解决控制冒险的常用技术包括__________和__________。7.在一棵高度为h的m阶B树中，根结点至少有__________个关键字（假设根结点不是终端结点）。四、简答题（每题10分，共40分）1.简述虚拟内存的基本概念、实现机制及其引入的核心目的。2.简述TCP拥塞控制中慢开始和拥塞避免算法的工作原理，并说明它们是如何相互转换的。3.简述数据库中“死锁”的概念，并列举至少两种预防死锁的方法。4.简述RISC（精简指令集计算机）和CISC（复杂指令集计算机）的主要区别。五、综合应用题（每题15分，共60分，需写出详细计算或推导过程）1.【操作系统与数据结构综合计算题】某系统采用请求分页存储管理，页面大小为4KB，分配给某进程的物理块数为3。该进程按顺序访问的页面序列为：1,2,3,4,1,2,5,1,2,3,4,5。若系统分别采用FIFO（先进先出）和LRU（最近最久未使用）页面置换算法，请计算这两种算法下的缺页次数和缺页率，并给出详细的过程分析。2.【计算机网络综合计算题】某单位分配到一个网络前缀为`/24`的IP地址块。该单位包含4个部门，A部门有50台主机，B部门有30台主机，C部门有20台主机，D部门有10台主机。现要求通过可变长子网划分（VLSM）为这4个部门分配子网，且不使用全0和全1的子网号。（1）请给出A、B、C、D四个部门的子网网络地址及子网掩码。（2）若从D部门划分后剩余的未分配IP空间中，给部门内部的三台服务器分配固定IP，请写出这三台服务器可使用的IP地址范围。3.【计算机组成原理综合计算题】假设某计算机主存容量为256MB，按字节编址。Cache采用直接映射方式，Cache数据区容量为64K（1）主存地址应划分为哪几个字段？各字段的位数为多少位？（2）若CPU依次访问的十六进制主存地址序列为：`0x1A2B3C`，`0x1A2B40`，`0x1A2C00`，`0x1A2B3D`，请计算上述每个主存地址对应的Cache字块标记、Cache块号和块内地址。（3）分析上述访问序列的Cache命中情况。4.【数据库系统综合分析题】设有一个教务管理数据库，包含以下三个关系模式：学生表：Student(Sno,Sname,Sdept,Sage)课程表：Course(Cno,Cname,Cpno,Credit)选课表：SC(Sno,Cno,Grade)其中，Sno为学号，Sname为姓名，Sdept为所在系，Sage为年龄；Cno为课程号，Cname为课程名，Cpno为先修课程号，Credit为学分；Grade为成绩。要求写出实现以下功能的SQL语句，并给出对应的关系代数表达式：（1）查询选修了课程号为"C01"且成绩大于80分的学生的学号和姓名。（2）查询没有选修任何课程的学生的学号和姓名。（3）查询选修了全部课程的学生学号和姓名。（使用双重否定或除法运算的逻辑）六、算法设计题（共20分）给定一个无序的整数数组`nums`和一个整数目标值`target`。请设计一个时间复杂度为O(N)要求：1.写出算法的设计思路。2.使用C或C++或Java语言写出完整的算法实现。3.分析算法的时间复杂度和空间复杂度。===答案与解析===一、单项选择题1.【答案】C【解析】二叉排序树的形态取决于关键字的插入顺序。在最坏情况下，二叉排序树会退化成一条单链表（即每个结点只有右孩子或只有左孩子）。对于具有5个结点的单链表，查找一个不存在的关键字需要比较5次（遍历到最后一个结点仍未找到返回空）。2.【答案】C【解析】虚拟内存的引入是为了让程序员可以使用比实际物理内存大得多的地址空间。因此，虚拟内存的大小受限于计算机的地址位数（如32位系统中虚存最大为4GB）以及磁盘交换区的大小，而不仅仅是物理内存的大小。3.【答案】A【解析】在TCP三次握手中，A发送SYN报文，序号seq=x。B收到后，需要确认A的SYN，因此确认号ac4.【答案】B【解析】IEEE754单精度浮点数由1位符号位、8位指数位、23位尾数位组成。给定机器数010000011符号位S=指数位E=10000011，其十进制值为128+尾数位M=100.真值=(5.【答案】C【解析】根据第三范式（3NF）的定义：关系模式R∈3N6.【答案】A【解析】页面大小为4KB，说明页内偏移地址长度为12位（=4096=4KB）。逻辑地址0x1A2B的二进制低12位为7.【答案】B【解析】CSMA/CD协议要求在发送数据帧的同时能够检测到可能发生的冲突。最极端的情况是，发送方在发送数据后经过最大往返时延2τ才能检测到冲突信号。因此，为了确保发送端能够检测到冲突，数据帧的发送时延T必须大于或等于两倍的单程传播时延τ，即T8.【答案】B【解析】依次插入关键字建立AVL树的过程如下：插入12,34,5后，根为12；插入23，发生LL型旋转，根变为23（左12，右34）；插入67，不触发失衡；插入89，在34的右子树触发RR型旋转，根仍为23；插入45，在34的左子树触发RL型旋转，34的左子树重平衡，整体仍平衡，根为23。最终根结点为23。故选B。9.【答案】A【解析】指令流水线中的数据冒险是指后续指令的执行需要依赖前面指令的执行结果，而前面的指令尚未写入寄存器或存储器，导致后续指令无法继续执行。B是控制冒险，C是结构冒险，D是异常中断。10.【答案】D【解析】快速排序以49为基准。初始：4938659776132749从后往前找小于49的：27。交换得：2738659776134949从前往后找大于49的：65。交换得：2738499776136549从后往前找小于49的：13。交换得：2738139776496549从前往后找大于49的：97。交换得：2738134976976549一趟排序结束，49到达最终位置。结果为27,二、多项选择题1.【答案】BC【解析】快速排序最坏时间复杂度为O()；归并排序在最坏、最好和平均情况下时间复杂度均为O(Nl2.【答案】ABC【解析】进程状态转换中，就绪态被调度后转为运行态（A）；运行态时间片用完转为就绪态（B）；运行态因等待I/O等资源转为阻塞态（C）。阻塞态不能直接转为运行态，必须先转为就绪态等待调度（D错误）。3.【答案】ABD【解析】HTTP（超文本传输协议）、FTP（文件传输协议）、DNS（域名系统协议）均为应用层协议。ARP（地址解析协议）属于网络层和数据链路层的过渡层，通常归为网络层。4.【答案】AC【解析】一级封锁协议可防止丢失修改；二级封锁协议防止丢失修改和读“脏”数据；三级封锁协议防止丢失修改、读“脏”数据和不可重复读。但封锁协议本身不能避免死锁，死锁需要通过预防或检测机制解决。故选AC。5.【答案】ABC【解析】Cache存取速度介于CPU寄存器和主存之间（A正确）；Cache映射由硬件完成（B正确）；局部性原理是基础（C正确）；D错误，命中率越高，等效存取速度越接近Cache的存取速度，而非主存。三、填空题1.【答案】1；0【解析】完全二叉树度为1的结点最多只有一个。当n为偶数时，最后一个结点是其父结点的左孩子，其父结点度为1，故有1个度为1的结点。当n为奇数时，所有分支结点都有左右孩子，度为1的结点数为0。2.【答案】DMA（直接存储器存取）【解析】DMA方式用于高速外设与主存间的大批量数据传输，CPU只在数据传输开始和结束时介入。3.【答案】C；【解析】IPv4地址分为A、B、C、D、E五类。192.x.x.x的首字节介于192~223之间，属于C类地址，默认子网掩码为。4.【答案】小阶向大阶看齐【解析】浮点数加减法中，对阶原则是使两个数的阶码相同。由于小阶向大阶看齐时，小阶的尾数需要右移，丢失的是低位部分，误差较小；若大阶向小阶看齐，大阶尾数左移会导致高位丢失，产生严重错误。5.【答案】A；2NF（第二范式）【解析】根据函数依赖集，A能唯一决定B、C、D，故A为候选键。由于存在A→6.【答案】分支预测；流水线停顿（或延迟转移）【解析】控制冒险主要是由于转移指令引起的。解决方法包括尽早判断转移是否成功、分支预测技术、延迟转移技术等。7.【答案】1【解析】在m阶B树中，根结点如果不是终端结点，则至少有2个分支，即至少包含1个关键字。四、简答题1.【答案与解析】虚拟内存是一种通过操作系统将内存和外存结合使用的存储管理技术。它允许程序在逻辑上使用比物理内存大得多的地址空间。实现机制：主要基于局部性原理，通过请求分页或请求分段实现。系统将程序划分为多个页面（或段段），只将当前需要的部分调入物理内存，其他部分留在外存（如磁盘交换区）。当程序访问到不在内存的数据时，产生缺页（或缺段）中断，由操作系统将所需数据从外存调入内存；若内存已满，则按照置换算法（如LRU、FIFO等）将暂时不用的页面换出外存。引入目的：核心目的是为了扩充内存容量，使得大型程序能够在小内存环境中运行；同时提高了内存利用率，实现了多道程序并发执行时的内存隔离与保护，方便了程序的编译链接和加载。2.【答案与解析】慢开始算法：在TCP连接建立初期或拥塞消除后，拥塞窗口（cwnd）设为1。每收到一个确认报文段，c拥塞避免算法：当cwnd达到慢开始门限（s相互转换：当网络发生超时拥塞时，认为网络已经拥塞。此时将ssthresh更新为当前cwnd的一半，并将3.【答案与解析】死锁概念：在数据库系统中，如果两个或多个事务相互持有对方所需的资源，且都在等待对方释放资源，导致这些事务永远无法继续执行的状态称为死锁。预防死锁的方法：（1）一次封锁法：要求每个事务在开始执行前，一次性地申请并封锁它所需要的所有数据资源。如果有一个资源不可用，则事务不申请任何资源并等待。（2）顺序封锁法：预先对所有的数据对象规定一个封锁顺序，每个事务都必须按照这个顺序对数据进行封锁，从而防止循环等待的发生。（3）破坏不可剥夺条件：规定当事务申请资源未果时，必须释放已占有的所有资源，以防互相阻塞。4.【答案与解析】RISC（精简指令集计算机）与CISC（复杂指令集计算机）的主要区别如下：（1）指令系统：RISC指令数量少、种类少、格式简单、长度固定；CISC指令数量多、格式多样、长度可变。（2）寻址方式：RISC寻址方式种类少，通常只有_load/store_指令访问内存；CISC寻址方式丰富，大量指令都可以访问内存。（3）执行时间：RISC指令较简单，大多数指令在一个时钟周期内完成；CISC指令复杂，执行时间往往需要多个时钟周期。（4）寄存器与流水线：RISC拥有较多的通用寄存器，且高度依赖流水线技术来提升性能；CISC寄存器较少，对流水线的支持较弱。（5）控制器实现：RISC多采用硬布线控制器，逻辑速度快；CISC多采用微程序控制器，便于实现复杂指令。五、综合应用题1.【答案与解析】已知：页面大小4KB（不影响缺页分析，仅针对页号处理），物理块数m=采用FIFO算法：访问次序分析（队列结构，先进先出）：1：缺页。内存：[1]。2：缺页。内存：[1,2]。3：缺页。内存：[1,2,3]。4：缺页。淘汰1，调入4。内存：[2,3,4]。1：缺页。淘汰2，调入1。内存：[3,4,1]。2：缺页。淘汰3，调入2。内存：[4,1,2]。5：缺页。淘汰4，调入5。内存：[1,2,5]。1：命中。内存：[1,2,5]。2：命中。内存：[1,2,5]。3：缺页。淘汰1，调入3。内存：[2,5,3]。4：缺页。淘汰2，调入4。内存：[5,3,4]。5：缺页。淘汰5（注意此处5是最早进入的），调入5。内存：[3,4,5]。由于发生Belady异常，最终缺页次数竟然达到11次。让我们重新核对FIFO的进入次序：1入->2入->3入->4入(淘汰1)->1入(淘汰2)->2入(淘汰3)->5入(淘汰4)->1(命中)->2(命中)->3入(淘汰1)->4入(淘汰2)->5入(淘汰5)。内存序列详细演进：[1],[1,2],[1,2,3],[4,2,3],[4,1,3],[4,1,2],[5,1,2],[5,1,2](1命中),[5,1,2](2命中),[5,3,2],[5,3,4],[5,3,4]（此时5是最早的，淘汰5，调入5，缺页9次。等下，淘汰最早进入的。当前队列[5,1,2]，最早的是5？不是，5是刚进来的，但1和2是更早的。让我们正确列出FIFO队列先后：初始：空队列访问1：缺页。队列：[1]访问2：缺页。队列：[1,2]访问3：缺页。队列：[1,2,3]访问4：缺页，淘汰1。队列：[2,3,4]访问1：缺页，淘汰2。队列：[3,4,1]访问2：缺页，淘汰3。队列：[4,1,2]访问5：缺页，淘汰4。队列：[1,2,5]访问1：命中。队列：[1,2,5](1仍在内存)访问2：命中。队列：[1,2,5](2仍在内存)访问3：缺页，淘汰1。队列：[2,5,3]访问4：缺页，淘汰2。队列：[5,3,4]访问5：命中。队列：[5,3,4](5仍在内存)缺页次数：9次。缺页率：9/12=75%。采用LRU算法：访问次序分析（栈结构，使用最近被访问的置顶）：1：缺页。栈：[1]。2：缺页。栈：[2,1]。3：缺页。栈：[3,2,1]。4：缺页。淘汰1。栈：[4,3,2]。1：缺页。淘汰2。栈：[1,4,3]。2：缺页。淘汰3。栈：[2,1,4]。5：缺页。淘汰4。栈：[5,2,1]。1：命中。栈：[1,5,2]。2：命中。栈：[2,1,5]。3：缺页。淘汰5。栈：[3,2,1]。4：缺页。淘汰1。栈：[4,3,2]。5：缺页。淘汰2。栈：[5,4,3]。缺页次数：10次。缺页率：10/12=83.3%。（由于FIFO可能比LRU缺页少，这属于特定序列下的现象，但实际中LRU通常优于FIFO。上述推演无误）。2.【答案与解析】为了不使用全0和全1子网，并尽量减少IP地址浪费，按照主机需求由大到小的顺序进行VLSM子网划分。需求依次为：A(50台),B(30台),C(20台),D(10台)。网络前缀原为`/24`，掩码``。主机数满足公式−2A部门需50台主机，−2=62第一个可用子网号（由于不用全0全1子网，我们采用从第一个实际可用子网开始分配，题目说不使用全0和全1子网，意味着子网号不能为全0和全1）：对于`/24`，划分`/26`后的子网块大小为64。全0子网为`0`，则第一个可用子网为`4/26`。故A部门分配：网络地址：`4/26`（即`4`），子网掩码：`92`。可用IP：`5`~`26`，广播地址`27`。B部门需30台主机，−2从`28/25`继续划分（前一块`64-127`已分给A）。划分`/27`后子网块大小为32。第一个可用子网为`28/27`（子网号128不全0）。故B部门分配：网络地址：`28/27`（即`28`），子网掩码：`24`。可用IP：`29`~`58`，广播地址`59`。C部门需20台主机，−2紧接B部门，下一个可用子网为`60/27`（子网号160不全0）。故C部门分配：网络地址：`60/27`，子网掩码：`24`。可用IP：`61`~`90`，广播地址`91`。D部门需10台主机，−2紧接C部门，下一个可用子网为`92/28`（子网号192不全0）。故D部门分配：网络地址：`92/28`，子网掩码：`40`。可用IP：`93`~`06`，广播地址`07`。（2）D部门剩余未分配的IP空间：整个D部门所在的`/28`块为`92`~`07`。已经将子网块分配给D，如果要找未分配的IP，D部门使用了14个主机IP。若此时只给三台服务器分配固定IP，则这三台服务器可以使用D部门内的任意三个IP，例如：可用IP范围1：`93`可用IP范围2：`94`可用IP范围3：`95`（注：如果是指除了D部门之外剩余的网络空间，在`92/28`之后还剩余`08/28`这个子网未分配，该子网的可用IP范围是`09`~`22`。根据题意，通常指该部门内分配给服务器，也可指整体网络剩余空间。以上两种范围均可合理说明，这里给出D部门内部的IP范围即可：`93`~`06`中任意三个IP）。3.【答案与解析】（1）主存容量为256MCache数据区容量为64KB=Cache块数=64采用直接映射方式，主存地址划分为：Tag（主存字块标记）、Line（Cache块号）、Offset（块内地址）。Offset位数=lLine位数=lTag位数=28各字段位数：Tag12位，Cache块号10位，块内地址6位。（2）分析给定地址，将它们转为二进制并提取字段：地址`0x1A2B3C`的二进制：`000110100010101100111100`Tag(前12位)=`000110100010`=十六进制`0x1A2`(即十进制418)Line(中间10位)=`1011001111`=十六进制`0x2CF`(即十进制719)Offset(末6位)=`111100`=十六进制`0x3C`(即十进制60)地址`0x1A2B40`的二进制：`000110100010101101000000`Tag=`000110100010`=`0x1A2`Line=`1011010000`=`0x2D0`(即十进制720)Offset=`000000`=`0x00`地址`0x1A2C00`的二进制：`000110100010110000000000`Tag=`000110100010`=`0x1A2`Line=`1100000000`=`0x300`(即十进制768)Offset=`000000`=`0x00`地址`0x1A2B3D`的二进制：`000110100010101100111101`Tag=`000110100010`=`0x1A2`Line=`1011001111`=`0x2CF`Offset=`111101`=`0x3D`（3）Cache命中情况分析：访问`0x1A2B3C`：映射到第719行。当前Cache空，未命中。将该块载入第719行，有效位置1，Tag更新为`0x1A2`。访问`0x1A2B40`：映射到第720行。与上一个地址不在同一块（719vs720），未命中。将该块载入第720行，Tag更新为`0x1A2`。访问`0x1A2C00`：映射到第768行。与前面访问均不同，未命中。将该块载入第768行，Tag更新为`0x1A2`。访问`0x1A2B3D`：映射到第719行。检查第719行的Tag，其Tag为`0x1A2`，与当前请求地址Tag`0x1A2`相同，且有效位为1，命中。总命中次数为1次。4.【答案与解析】（1）查询选修了课程号为"C01"且成绩大于80分的学生的学号和姓名。SQL语句：```sqlSELECTStudent.Sno,Student.SnameFROMStudentJOINSCONStudent.Sno=SC.SnoWHERESC.Cno='C01'ANDSC.Grade>80;```关系代数表达式：(（2）查询没有选修任何课程的学生的学号和姓名。SQL语句：```sqlSELECTSno,SnameFROMStudentWHERESnoNOTIN(SELECTSnoFROMSC);```关系代数表达式：(或者使用差集操作：Stud（3）查询选修了全部课程的学生学号和姓名。SQL语句：```sqlSELECTSno,SnameFROMStudentWHERENOTEXISTS(SELECT*FROMCourseWHERENOTEXISTS(SELECT*FROMSCWHERESC.Sno=Student.SnoANDSC.Cno=Course.Cno));```关系代数表达式：利用除法运算：首先在SC中找出Sno和Cno的投影，然后除以Course中Cno的投影，得到选了所有课的Sno，再与Student自然连接取投影。(六、算法设计题【答案与解析】1.设计思路：本题是经典的“最大子数组和”问题的扩展（Kadane算法的变种）。我们维护以下几个变量：`currentSum`：表示以当前元素为结尾的连续子数组的最大和。`maxSum`：表示全局最大连续子数组和。`currentLength`：表示以当前元素为结尾且产生最大和的子数组长度。`minLength`：表示全局产生最大和的子数组的最短长度。在遍历数组时，对于第`i`个元素`nums[i]`：如果`currentSum>0`，说明前一段子数组对当前和有正向贡献，我们将`nums[i]`加入当前子数组：`currentSum+=nums[i]`，并且`currentLength++`。如果`currentSum<=0`，说明前一段子数组对当前和没有正向贡献甚至有负向贡献。此时应该抛弃前面的子数组，以`nums[i]`为起点重新开始。此时`currentSum=nums[i]`，`currentLength=1`。更新全局最大和：如果`currentSum>maxSum`，说明找到了更大的子数组和。此时更新`maxSum=currentSum`，并将`minLength`重置为`currentLength`。如果`currentSum==maxSum`，说明出现了和相同的子数组。此时需要比较长度：如果`currentLength<minLength`，则更新`minLength=currentLength`。如果`currentSum<maxSum`，不做更新。遍历完数组后，`maxSum`即为连续子数组的最大和，`minLength`即为和最大且长度最短的子数组长度。该算法只需一次遍历，满足O(N)2.算法实现（以C++为例）：```cpp#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;pair<int,int>findMaxSubarraySumAndMinLength(constvector<