2026年计算机考研专业课真题及答案

2026年计算机考研专业课真题及答案一、单项选择题（每题2分，共30分）1.在具有n个结点的二叉排序树中，查找一个关键字的最坏时间复杂度是（）。A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)答案：A解析：在二叉排序树中，当树退化成单支树（即每个结点只有左孩子或只有右孩子）时，查找一个关键字需要遍历所有结点，因此最坏时间复杂度为O(n)。2.下列排序算法中，平均时间复杂度为O(nlogn)且是稳定的排序算法是（）。A.堆排序B.快速排序C.归并排序D.希尔排序答案：C解析：归并排序的平均时间复杂度为O(nlogn)，并且在合并过程中，当两个元素相等时，可以保证先复制前一个子序列中的元素，从而保持稳定性。堆排序和快速排序不稳定，希尔排序的时间复杂度通常优于O(n^2)，但不稳定且平均时间复杂度分析复杂，通常不认为是O(nlogn)的稳定算法。3.一个进程从运行状态进入就绪状态，可能的原因是（）。A.等待I/O操作完成B.时间片用完C.等待某资源被释放D.被更高优先级的进程抢占答案：B解析：时间片用完是分时系统中，正在运行的进程被迫让出CPU，从运行态转为就绪态的典型原因。A和C选项会导致进程从运行态进入阻塞（等待）状态。D选项“被更高优先级的进程抢占”也可能导致从运行态转为就绪态，但题目为单选题，且B选项是最直接、最典型的原因，在大多数教材中，时间片用完是进程从运行到就绪的标准转换条件之一。4.在TCP协议中，采用（）来保证可靠传输。A.校验和B.确认与超时重传机制C.流量控制D.拥塞控制答案：B解析：TCP的可靠传输主要依赖于确认与超时重传机制。校验和用于检测数据在传输过程中是否出错，是可靠性的基础但非核心机制。流量控制解决的是发送方与接收方速率匹配问题，拥塞控制解决的是网络整体负荷问题，它们都服务于可靠性，但核心的可靠交付保证是确认与重传。5.某计算机采用虚拟页式存储管理，其页面大小为4KB，虚拟地址为32位。若页表项大小为4字节，则采用单级页表时，页表最大占用（）。A.1MBB.4MBC.1KBD.4KB答案：B解析：页面大小为4KB=2^12B，故页内偏移占12位。虚拟地址32位，则虚页号占32-12=20位，故最多有2^20个页面。每个页表项4字节，因此页表最大大小为2^204B=42^20B=4MB。解析：页面大小为4KB=2^12B，故页内偏移占12位。虚拟地址32位，则虚页号占32-12=20位，故最多有2^20个页面。每个页表项4字节，因此页表最大大小为2^204B=42^20B=4MB。6.下列有关数据库事务隔离级别的描述中，错误的是（）。A.读未提交（ReadUncommitted）级别可能发生脏读B.可重复读（RepeatableRead）可以避免幻读C.串行化（Serializable）级别性能最高D.读已提交（ReadCommitted）可以避免脏读答案：C解析：串行化（Serializable）级别通过强制事务串行执行来保证最高的隔离性，避免了脏读、不可重复读和幻读，但其并发性能最低，而不是最高。7.在C语言中，若有定义`inta[3][4];`，则表达式`(a[1]+2)`等价于（）。7.在C语言中，若有定义`inta[3][4];`，则表达式`(a[1]+2)`等价于（）。A.`a[1][2]`B.`(&a[0][0]+6)`B.`(&a[0][0]+6)`C.`((int)a+14+2)`C.`((int)a+14+2)`D.以上都正确答案：D解析：`a[1]`是第二行首元素的地址，`a[1]+2`是第二行第三个元素的地址，`(a[1]+2)`即`a[1][2]`。对于二维数组`a[3][4]`，在内存中按行优先连续存放，`a[1][2]`是第`14+2=6`个元素（从0开始计），所以`(&a[0][0]+6)`也正确。`(int)a`将a转换为指向整型的指针，`((int)a+14+2)`同样访问的是第6个整型元素，即`a[1][2]`。因此A、B、C均正确。解析：`a[1]`是第二行首元素的地址，`a[1]+2`是第二行第三个元素的地址，`(a[1]+2)`即`a[1][2]`。对于二维数组`a[3][4]`，在内存中按行优先连续存放，`a[1][2]`是第`14+2=6`个元素（从0开始计），所以`(&a[0][0]+6)`也正确。`(int)a`将a转换为指向整型的指针，`((int)a+14+2)`同样访问的是第6个整型元素，即`a[1][2]`。因此A、B、C均正确。8.对于一棵高度为h的平衡二叉树（AVL树），其最少结点数N(h)满足递推关系（）。A.N(h)=N(h-1)+N(h-2)+1B.N(h)=2N(h-1)+1C.N(h)=N(h-1)+1D.N(h)=2N(h-2)+1答案：A解析：要使高度为h的AVL树结点数最少，则左右子树的高度应相差1，且它们也应是结点数最少的平衡二叉树。因此，左子树高度为h-1，右子树高度为h-2（或反之），加上根结点，得到递推式：N(h)=N(h-1)+N(h-2)+1。其中N(0)=0（空树），N(1)=1。9.下列IPv4地址中，属于私有地址（PrivateAddress）的是（）。A.10.1.2.3B.172.15.1.1C.192.169.1.1D.224.0.0.1答案：A解析：私有地址范围包括：10.0.0.0~10.255.255.255(10.0.0.0/8)，172.16.0.0~172.31.255.255(172.16.0.0/12)，192.168.0.0~192.168.255.255(192.168.0.0/16)。172.15.1.1不在172.16.0.0/12范围内。192.169.1.1不在192.168.0.0/16范围内。224.0.0.1是D类组播地址。10.在操作系统中，银行家算法用于（）。A.死锁预防B.死锁避免C.死锁检测D.死锁解除答案：B解析：银行家算法是一种著名的死锁避免算法。它通过动态检查资源分配状态，判断此次分配是否会导致系统进入不安全状态，从而决定是否允许此次分配，避免系统进入死锁状态。11.一个具有n个顶点和e条边的无向图，采用邻接表存储，则空间复杂度为（）。A.O(n)B.O(e)C.O(n+e)D.O(ne)D.O(ne)答案：C解析：邻接表存储无向图时，顶点表占用O(n)空间，边表（或邻接链表）总共存储2e个边结点（因为每条边在两个顶点的链表中各出现一次），占用O(e)空间。因此总空间复杂度为O(n+e)。12.在关系数据库设计中，若关系模式R的规范化程度达到了3NF，则（）。A.一定消除了插入和删除异常B.仍可能存在一定的数据冗余C.所有非主属性都完全函数依赖于候选码D.所有非主属性都不传递依赖于候选码答案：D解析：第三范式（3NF）要求每个非主属性既不部分依赖于候选码，也不传递依赖于候选码。达到3NF并不一定完全消除插入和删除异常（BCNF可以进一步消除），仍可能存在一定的数据冗余（如主属性间的部分或传递依赖可能导致冗余）。C选项是2NF的要求。因此D选项是3NF的准确定义之一。13.下列指令中，通常属于特权指令的是（）。A.加法指令ADDB.访管指令SVCC.修改程序状态字指令D.数据传送指令MOV答案：C解析：特权指令是指只能在操作系统内核态下执行的指令，如修改程序状态字（PSW）、开关中断、进行I/O操作等。ADD、MOV是普通算术逻辑指令，SVC（访管指令/陷入指令）是在用户态下主动引发陷入，进入内核态的手段，其本身不是特权指令。14.假设某分页存储系统中，内存访问时间为100ns，快表（TLB）访问时间为10ns，命中率为90%。则有效访问时间（EAT）约为（）。A.110nsB.120nsC.130nsD.200ns答案：B解析：有效访问时间EAT=TLB命中时间+TLB缺失开销。TLB命中时，只需一次TLB访问和一次内存访问：10+100=110ns。TLB缺失时，需要先访问TLB（未命中），再访问内存中的页表（一次内存访问），最后根据物理地址访问内存数据（又一次内存访问），共需10+100+100=210ns。因此，EAT=0.9110+0.1210=99+21=120ns。解析：有效访问时间EAT=TLB命中时间+TLB缺失开销。TLB命中时，只需一次TLB访问和一次内存访问：10+100=110ns。TLB缺失时，需要先访问TLB（未命中），再访问内存中的页表（一次内存访问），最后根据物理地址访问内存数据（又一次内存访问），共需10+100+100=210ns。因此，EAT=0.9110+0.1210=99+21=120ns。15.对长度为n的线性表进行顺序查找，在等概率查找且查找成功的情况下，平均查找长度为（）。A.nB.n/2C.(n+1)/2D.log2(n)答案：C解析：顺序查找成功时，查找第i个元素需要比较i次。在等概率（每个元素被查找概率为1/n）条件下，平均查找长度ASL=(1+2+3+...+n)/n=n(n+1)/2/n=(n+1)/2。二、多项选择题（每题3分，共15分。每题至少有两个正确选项，多选、少选、错选均不得分）1.下列哪些数据结构可以有效地支持“查找第k小（或第k大）元素”操作？（）A.二叉搜索树（BST）B.大顶堆（Max-Heap）C.红黑树（Red-BlackTree）D.未排序的数组答案：A、C解析：二叉搜索树（BST）和红黑树（一种平衡二叉搜索树）的中序遍历是有序的，可以通过修改树结构（增加子树结点数信息）或遍历来找到第k小的元素，效率较高（O(logn)或O(n)）。大顶堆只能快速找到最大元素，要找到第k大元素并不直接高效。未排序数组需要部分排序或选择算法，虽然平均O(n)但题目问“可以有效支持”，通常指有内在顺序特性或高效算法，未排序数组不具备此特性。2.关于TCP和UDP协议，下列说法正确的有（）。A.TCP提供面向连接的可靠字节流服务，UDP提供无连接的不可靠数据报服务B.TCP首部开销（20字节）通常比UDP首部开销（8字节）大C.TCP具有流量控制和拥塞控制机制，而UDP没有D.DNS查询只使用UDP协议答案：A、B、C解析：A、B、C均为TCP和UDP的基本特性描述，正确。DNS查询主要使用UDP协议（端口53），但当响应报文过大（超过512字节）或进行区域传输时，会使用TCP协议。因此D选项“只使用”过于绝对，错误。3.在操作系统的进程调度中，可能导致“饥饿（Starvation）”现象的调度算法有（）。A.先来先服务（FCFS）B.短作业优先（SJF）C.高响应比优先（HRRN）D.基于静态优先级的抢占式调度答案：B、D解析：短作业优先（SJF）可能使长作业长期得不到服务，导致饥饿。基于静态优先级的抢占式调度中，低优先级进程可能永远无法获得CPU，导致饥饿。先来先服务（FCFS）对所有作业公平，不会导致饥饿。高响应比优先（HRRN）的响应比公式（R=(等待时间+要求服务时间)/要求服务时间）保证了长作业随着等待时间增长，响应比会增大，从而获得服务，避免了饥饿。4.下列属于数据库系统特点的有（）。A.数据结构化B.数据冗余度低，共享性高C.数据独立性高D.数据由DBMS统一管理和控制答案：A、B、C、D解析：数据库系统的特点主要包括：数据结构化（与文件系统的根本区别）；数据的共享性高、冗余度低且易扩充；数据独立性高（包括物理独立性和逻辑独立性）；数据由数据库管理系统（DBMS）统一管理和控制（提供数据安全性、完整性、并发控制和故障恢复等）。因此四个选项均正确。5.下列算法中，利用了“分治（DivideandConquer）”策略的有（）。A.归并排序B.快速排序C.堆排序D.二分查找答案：A、B、D解析：分治法的三个步骤：分解、解决、合并。归并排序和快速排序是典型的分治算法。二分查找每次将问题规模减半，也属于分治策略。堆排序主要利用堆这种数据结构的性质，其核心是调整堆的过程，不属于典型的分治算法。三、填空题（每空2分，共20分）1.在一个用数组实现的循环队列中，队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素。若队列的最大容量为MaxSize，则判断队列为满的条件是______。答案：(rear+1)%MaxSize==front解析：这是循环队列判满的一种常用方法，通过牺牲一个存储单元来区分队空和队满。2.在图的深度优先搜索（DFS）遍历中，通常需要借助______数据结构来辅助实现。答案：栈（或递归调用栈）解析：深度优先搜索通常使用栈来保存当前路径上的顶点，以便回溯。递归实现则利用系统调用栈。3.在虚拟内存管理中，当访问的页面不在内存中时，会触发一次______中断。答案：缺页（或PageFault）解析：当CPU要访问的页面不在物理内存（页表项中有效位为0）时，由硬件产生缺页中断，由操作系统进行页面调入等处理。4.在关系代数中，从两个关系的笛卡尔积中选取满足连接条件的元组，该操作称为______连接。答案：θ（或条件）解析：这是最广义的连接操作定义，即θ连接。等值连接和自然连接是其特例。5.假设某计算机的指令系统采用定长操作码，若指令总共有60种不同的操作，则操作码至少需要______位。答案：6解析：2^5=32<60，2^6=64>=60。因此至少需要6位才能编码60种不同的操作。6.在TCP连接建立过程中，客户端发送的SYN报文段中，其序列号seq的值为x；服务器端回复的SYN+ACK报文段中，确认号ack的值为______。答案：x+1解析：在TCP三次握手中，服务器对客户端SYN的确认，其确认号ack等于客户端序列号seq（即x）加1。7.在二叉树中，度为0的结点数（叶子结点数）为n0，度为2的结点数为n2，则n0与n2的关系是______。答案：n0=n2+1解析：二叉树的性质：对于任何一棵二叉树，叶子结点数（n0）等于度为2的结点数（n2）加1。8.死锁产生的四个必要条件是：互斥条件、请求和保持条件、不剥夺条件和______。答案：循环等待条件解析：死锁产生的四个必要条件缺一不可。9.在SQL语言中，用于撤销数据库对象权限的命令是______。答案：REVOKE解析：GRANT授予权限，REVOKE撤销权限。10.假设有函数`F(n)=F(n-1)+F(n-2)`（n>=2），且`F(0)=0,F(1)=1`。该函数的时间复杂度若用递归实现且无优化，是______。答案：O(2^n)或指数阶解析：斐波那契数列的递归实现会形成一棵递归树，其时间复杂度约为O(2^n)。四、简答题（每题10分，共40分）1.简述什么是“抖动”（Thrashing）现象，并说明操作系统通常采用什么策略来减少或避免抖动。答案：“抖动”现象是指在虚拟存储系统中，由于分配给进程的物理页面（帧）数不足，导致进程在运行过程中频繁发生缺页中断，大部分时间都用于页面的换入换出（即I/O操作），而实际执行计算的时间很少，系统吞吐量急剧下降，CPU利用率显著降低的一种状态。操作系统通常采用以下策略来减少或避免抖动：（1）采用局部置换策略：当某个进程发生缺页时，只从该进程自身分配的物理帧中选取页面进行置换，防止一个进程的缺页行为影响到其他进程的帧分配。（2）利用工作集模型：工作集是进程在某段时间间隔内实际访问的页面集合。操作系统可以跟踪每个进程的工作集，并确保分配给进程的物理帧数不小于其工作集大小。这样，进程在运行过程中所需的页面大部分都在内存中，从而减少缺页率。（3）采用缺页率算法（PFF）：动态调整分配给进程的物理帧数。当进程的缺页率过高时，增加其分配的帧数；当缺页率过低时，适当减少其分配的帧数，以平衡内存利用和系统性能。（4）挂起部分进程：当系统检测到抖动发生时，可以选择挂起一个或几个进程，将它们占用的所有帧释放并分配给其他活跃进程，从而迅速减轻内存压力，使剩余进程能够顺利运行。2.比较说明静态链接和动态链接的区别与优缺点。答案：静态链接和动态链接是程序链接的两种主要方式。区别：（1）链接时机：静态链接发生在程序编译链接成可执行文件时；动态链接发生在程序加载运行时（加载时动态链接）或程序运行过程中需要时（运行时动态链接）。（2）库的包含方式：静态链接将库函数的代码和数据直接复制到最终的可执行文件中；动态链接仅在可执行文件中记录共享库（如.dll，.so文件）的名称和少量重定位信息，库代码和数据在程序运行时才被加载到内存。（3）生成文件：静态链接生成的可执行文件独立、完整；动态链接生成的可执行文件较小，但运行时依赖相应的共享库文件。优缺点：静态链接优点：生成的可执行文件独立，发布时无需携带额外的库文件，移植性较好；运行速度快，因为函数调用在链接时已解析为直接地址。缺点：可执行文件体积较大，浪费磁盘和内存空间（如果多个程序使用相同库，每个程序都包含一份副本）；库更新困难，必须重新编译链接所有使用该库的程序。动态链接优点：显著减少可执行文件体积；多个进程可以共享内存中的同一份库代码，节省内存；库升级方便，只需替换共享库文件，只要接口不变，程序无需重新编译链接。缺点：程序运行时依赖共享库的存在和版本兼容性，移植性稍差；第一次调用共享库函数或程序加载时有一定链接开销；可能存在“DLLHell”问题（在Windows上指版本冲突）。3.什么是数据库的“丢失修改”、“不可重复读”和“幻读”现象？请分别举例说明。答案：丢失修改、不可重复读和幻读是数据库并发操作可能引发的三类数据不一致性问题。（1）丢失修改：指两个或多个事务同时修改同一数据，后提交的事务覆盖了先提交事务的修改结果，导致先提交事务的修改丢失。举例：事务T1和T2同时读取账户A的余额为100元。T1将A余额增加50元，写回150。随后T2将A余额减少30元，基于它读到的100元计算，写回70。最终A余额为70元，T1的增加操作效果丢失。（2）不可重复读：指在一个事务内，多次读取同一数据，由于其他事务的修改和提交，导致该事务前后读取的结果不一致。举例：事务T1第一次读取账户A的余额为100元。此时事务T2修改A余额为150元并提交。接着T1再次读取A余额，得到150元。T1在同一个事务内两次读取同一数据A，结果却不一致。（3）幻读：指在一个事务内，多次按相同条件查询，由于其他事务的插入或删除操作，导致该事务前后查询到的记录集合（行数）发生了变化。举例：事务T1查询年龄大于20岁的员工人数，得到10人。此时事务T2插入了一名年龄21岁的新员工记录并提交。接着T1再次以相同条件查询，得到11人。T1在同一个事务内两次相同的查询，结果集的行数增加了，如同产生了“幻觉”。4.简述Dijkstra算法的主要思想、步骤及其适用范围。该算法能否处理带有负权边的图？为什么？答案：Dijkstra算法是解决单源最短路径问题的经典贪心算法，用于计算从图中一个特定源点到其他所有顶点的最短路径。主要思想：设置一个顶点集合S，存放已求得最短路径的顶点。初始时，S只包含源点。每次从尚未加入S的顶点集合V-S中，选取一个当前距离源点最短的顶点u加入S，然后对u的所有出边进行松弛操作，更新源点到V-S中其他顶点的距离估计。重复此过程，直到S包含所有顶点（或仅包含目标顶点）。基本步骤：（1）初始化：将源点s的距离dist[s]设为0，其他顶点v的距离dist[v]设为无穷大。将所有顶点标记为未访问（或未加入S）。（2）循环执行：从未访问顶点中，选取dist值最小的顶点u，将其标记为已访问（加入S）。（3）松弛操作：对于顶点u的每一个邻接点v，如果dist[u]+w(u,v)<dist[v]，则更新dist[v]=dist[u]+w(u,v)。（w(u,v)是边(u,v)的权值）（4）重复步骤（2）和（3），直到所有顶点都被访问（或目标顶点被访问）。适用范围：适用于带非负权重的有向图或无向图。Dijkstra算法不能正确处理带有负权边的图。原因在于其贪心选择策略基于一个假设：当前从S集合中选出的、具有最小dist值的顶点u，其dist值就是从源点到u的最短路径长度，并且这个值在后续不会再被减小。如果存在负权边，这个假设就不成立。因为后续通过其他顶点和负权边，有可能找到一条更短的路径到达u，从而需要更新dist[u]。但此时u已被标记为“已访问”（或已加入S），算法将不再对其dist值进行更新，从而导致错误的结果。五、应用题（共45分）1.（15分）给定一个关键字序列为：{45,24,53,12,37,93,30}。（1）请画出以此序列构建一棵二叉排序树（BST）的过程。（5分）（2）请画出删除关键字45后的二叉排序树。（5分）（3）基于初始的BST，请给出其先序遍历、中序遍历和后序遍历的结果。（5分）答案：（1）构建二叉排序树的过程（最终树形结构描述）：初始树为空。插入45：成为根结点。插入24：24<45，作为45的左孩子。插入53：53>45，作为45的右孩子。插入12：12<45，12<24，作为24的左孩子。插入37：37<45，37>24，作为24的右孩子。插入93：93>45，93>53，作为53的右孩子。插入30：30<45，30>24，30<37，作为37的左孩子。最终BST结构（文字描述）：根结点45。45的左子树：根24。24的左孩子12；24的右孩子37，37的左孩子30。45的右子树：根53。53的右孩子93。（2）删除关键字45后的二叉排序树：删除结点45（有两个孩子），需要找到其前驱或后继替代。这里选择用其前驱（即左子树中最大的结点）37替代。查找前驱：在45的左子树（根24）中，沿右分支查找，最大结点是37。用37替换45的位置。原来37的位置由它的左子树（根30）替代。30成为24的右孩子。因此，删除后的BST新根为37。37的左子树：原45的左子树（但根24的右孩子现在变为30）。即：37的左孩子是24。24的左孩子12；24的右孩子30。37的右子树：原45的右子树（根53，右孩子93）。（3）遍历结果（基于初始BST）：先序遍历（根左右）：45,24,12,37,30,53,93。中序遍历（左根右）：12,24,30,37,45,53,93。（二叉排序树的中序遍历是有序序列）后序遍历（左右根）：12,30,37,24,93,53,45。2.（15分）假设系统中有三类资源：A（10个）、B（5个）、C（7个）。在时刻T0，系统状态如下：进程最大需求Max已分配Allocation可用AvailableP0(7,5,3)(0,1,0)(3,3,2)P1(3,2,2)(2,0,0)P2(9,0,2)(3,0,2)P3(2,2,2)(2,1,1)P4(4,3,3)(0,0,2)（注：表格中Available为T0时刻的可用资源向量）（1）计算每个进程的仍需资源量（Need）矩阵。（3分）（2）判断当前系统状态是否安全？请给出安全序列或说明原因。（使用银行家算法）（12分）答案：（1）计算Need矩阵。Need=MaxAllocation。P0:(7-0,5-1,3-0)=(7,4,3)P1:(3-2,2-0,2-0)=(1,2,2)P2:(9-3,0-0,2-2)=(6,0,0)P3:(2-2,2-1,2-1)=(0,1,1)P4:(4-0,3-0,3-2)=(4,3,1)（2）判断系统安全性。已知Available(T0)=(3,3,2)。比较Need[i]与Work（初始Work=Available）。第一步：寻找Need[i]<=Work的进程。P1Need(1,2,2)>Work(3,3,2)?1<=3,2<=3,2<=2，成立。P1满足条件。假设P1执行完毕，释放其Allocation(2,0,0)。则Work=Work+Allocation(P1)=(3,3,2)+(2,0,0)=(5,3,2)。将P1加入安全序列。第二步：Work(5,3,2)。P3Need(0,1,1)<=(5,3,2)，成立。P3执行，释放(2,1,1)。Work=(5,3,2)+(2,1,1)=(7,4,3)。安全序列：P1,P3。第三步：Work(7,4,3)。P0Need(7,4,3)<=(7,4,3)，成立。P0执行，释放(0,1,0)。Work=(7,4,3)+(0,1