2026年考研计算机学科专业基础综合题库及答案

2026年考研计算机学科专业基础综合题库及答案一、单项选择题（每题2分，共40题，共80分）（一）数据结构（第1~11题）1.下列函数中，当n充分大时渐近时间复杂度最小的是：A.TB.TC.TD.T2.在长度为n的顺序表中删除第i个元素（1≤A.nB.nC.nD.i3.元素a,A.eB.dC.cD.b4.循环队列存储在一维数组A[A.(B.(C.rD.(5.一棵完全二叉树共有1001个结点，则该二叉树中叶子结点的个数为：A.500B.501C.250D.10006.在含有n个结点的二叉排序树中进行查找，最坏情况下的时间复杂度为：A.OB.OC.OD.O7.一个有n个顶点、e条边的有向图采用邻接表存储，求图中某一指定顶点的入度时，最坏情况下的时间复杂度为：A.OB.OC.OD.O8.用Kruskal算法求含n个顶点、e条边的带权连通图的最小生成树时，算法的时间复杂度为：A.OB.OC.OD.O9.在AOE网中，下列关于关键路径的说法中，错误的是：A.关键路径是从源点到汇点路径长度最长的路径，其长度表示完成工程的最短时间B.关键路径上的活动称为关键活动，其时间余量为零C.一个AOE网中只存在一条关键路径D.当存在多条关键路径时，缩短其中一条路径上的关键活动的时间，整个工程的工期可能不变10.设散列表长度为11，散列函数为H(A.4B.5C.6D.711.下列排序算法中，元素之间的比较次数与待排序序列的初始排列无关的是：A.直接插入排序B.快速排序C.简单选择排序D.冒泡排序（二）计算机组成原理（第12~23题）12.某计算机主存容量为1MB，按字节编址，则访问主存所需的地址线根数为：A.16B.20C.24D.3213.8位补码10000000对应的十进制真值为：A.−B.−C.−D.−14.在IEEE754单精度浮点数格式中，阶码采用的编码方式是：A.补码B.原码C.移码（偏置值为127）D.反码15.某Cache采用直接映射方式，主存块大小为32B，Cache共有64行，主存地址为32位，则主存地址中标记字段占：A.5位B.6位C.21位D.26位16.下列关于RISC的叙述中，错误的是：A.指令条数少，指令格式规整B.绝大多数指令在一个机器周期内完成C.以微程序控制方式为主D.只有加载（Load）和存储（Store）指令才能访问存储器17.操作数的地址存放在某个寄存器中，根据该寄存器中的地址访问主存以取得操作数，这种寻址方式称为：A.直接寻址B.寄存器寻址C.寄存器间接寻址D.立即寻址18.微程序控制器中，一条微指令的控制字段用来表示：A.一组微操作控制信号B.主存单元的地址C.指令的操作码D.通用寄存器的编号19.在CPU中，指令周期、机器周期和时钟周期三者的关系是：A.指令周期>机器周期>时钟周期B.机器周期>指令周期>时钟周期C.时钟周期>机器周期>指令周期D.指令周期>时钟周期>机器周期20.某指令流水线有5段，各段耗时分别为2ns、2ns、3ns、2ns、2ns，不考虑锁存器延迟，该流水线的最大吞吐率为：A.13B.12C.15D.11121.某同步总线的工作频率为100MHz，每个总线周期可传输8B数据，则该总线的数据传输率为：A.100MB/sB.200MB/sC.400MB/sD.800MB/s22.DMA方式与程序中断方式相比，其主要优点是：A.由CPU完成数据的传送B.传输速度快，由DMA控制器直接控制主存与I/O设备之间的数据交换C.能处理随机事件D.不需要额外地硬件支持23.某磁盘转速为7200转/分，平均寻道时间为5ms，则磁盘的平均存取时间约为（忽略数据传输时间）：A.5.0msB.9.2msC.4.2msD.12.5ms（三）操作系统（第24~33题）24.在进程的三态模型中，下列状态转换中不可能发生的是：A.运行态→就绪态B.就绪态→运行态C.运行态→阻塞态D.阻塞态→运行态25.下列关于线程的叙述中，正确的是：A.线程是资源分配的基本单位B.同一进程中的多个线程共享该进程的地址空间，可以并发执行C.每个线程具有完全独立的地址空间D.线程间的切换开销大于进程间的切换开销26.设有4个作业，到达时间均为0，服务时间分别为6、4、3、5，采用非抢占式短作业优先调度算法，则它们的平均周转时间为：A.9.0B.10.0C.11.5D.6.527.有m个生产者进程和n个消费者进程共享一个容量为k的有界缓冲区，用PV操作实现同步与互斥。为保证各生产者进程互斥地使用缓冲区，应设置：A.一个互斥信号量mutex，初值为1B.一个资源信号量empty，初值为kC.一个资源信号量full，初值为0D.不需要设置信号量28.系统中有3个并发进程，它们共享同一类资源4台，每个进程最多申请该类资源2台，则该系统：A.可能发生死锁B.一定发生死锁C.不会发生死锁D.无法判断是否会发生死锁29.某请求分页系统页面大小为4KB，逻辑地址8196对应的页号和页内偏移为：A.页号2，偏移量4B.页号2，偏移量8C.页号1，偏移量4100D.页号3，偏移量030.在请求分页系统中，LRU置换算法选择被淘汰的页面是：A.最近最久未使用的页面B.最先进入内存的页面C.访问次数最少的页面D.将来最长时间不被访问的页面31.下列文件的物理分配方式中，既便于文件动态增长，又能较好支持随机访问的是：A.连续分配B.隐式链接分配C.索引分配D.位示图32.在文件系统中设置当前目录（工作目录）的主要目的是：A.加快文件的读写速度B.减少访问磁盘的次数，加快文件的检索速度C.节省磁盘存储空间D.便于多个用户共享文件33.下列磁盘调度算法中，可能导致磁头臂长期停留在某一区域、使其远端进程长时间得不到服务（饥饿）的是：A.先来先服务（FCFS）B.最短寻道时间优先（SSTF）C.扫描算法（SCAN）D.循环扫描算法（C-SCAN）（四）计算机网络（第34~40题）34.在TCP/IP体系结构中，负责相邻结点之间的数据成帧、差错检测等功能的层次是：A.应用层B.传输层C.网际层D.网络接口层35.标准以太网MAC帧中，用于差错检测的字段是：A.前导码B.帧检验序列（FCS）C.源MAC地址D.类型字段36.以太网采用CSMA/CD协议，当检测到冲突后，站点进行重传所采用的退避算法是：A.固定退避算法B.二进制指数退避算法C.线性退避算法D.立即重发37.下列IP地址中，属于私网地址的是：A.172.32.1.1B.192.168.1.1C.219.224.1.1D.8.8.8.838.某主机的IP地址为192.168.10.100，子网掩码为255.255.255.240，则该主机所在子网的网络地址为：A.192.168.10.96B.192.168.10.100C.192.168.10.0D.192.168.10.11239.在TCP连接建立的三次握手中，服务器发送的第二个报文段的控制位为：A.SYN=1，ACK=1B.SYN=1，ACK=0C.ACK=1，FIN=1D.SYN=1，FIN=140.DNS协议在默认情况下使用的传输层协议及端口号为：A.UDP，端口53B.TCP，端口53C.UDP，端口67D.TCP，端口80二、综合应用题（共7题，共70分）41.（15分）设带头结点的单链表L，结点的数据域为data（整数），指针域为next。设计一个算法判断该链表是否为中心对称（如21→32→47→(1)$。请写出算法的基本思想与实现代码（或伪代码）。intisSymmetric(LinkListL){//L为带头结点的单链表

if(L->next==NULL)return1;//空表视为对称

LNode*slow=L->next,*fast=L->next;

//1.快慢指针寻找中间结点

while(fast->next!=NULL&&fast->next->next!=NULL){

slow=slow->next;

fast=fast->next->next;

}

//2.将链表从中间断开为前后两半

LNode*head=slow->next;//后半段第一个结点

slow->next=NULL;

//3.就地逆置后半段

LNode*pre=NULL,*p=head;

while(p!=NULL){

LNode*r=p->next;

p->next=pre;

pre=p;

p=r;

}

head=pre;//逆置后后半段的新表头

//4.依次比较两半对应结点的值

LNode*p1=L->next,*p2=head;

intflag=1;

while(p2!=NULL){

if(p1->data!=p2->data){

flag=0;

break;

}

p1=p1->next;

p2=p2->next;

}

//5.（可选）再次逆置后半段并接回，恢复链表原状

returnflag;

}解析：-当链表有奇数个结点时，slow指向正中间结点，后半段比前半段少一个结点，此时无需将正中间结点与自身比较；当链表有偶数个结点时，两半长度相等。-逆置后半段仅使用常数个辅助指针，空间复杂度为O(-整个算法对链表只进行有限次顺序遍历，时间复杂度为O(42.（10分）一棵二叉树的先序遍历序列为A,B,(1)画出该二叉树；(2)写出该二叉树的后序遍历序列。A

/\

BC

/\/

DEF(2)后序遍历序列为：D解析：后序遍历按"左子树、右子树、根结点"的顺序递归进行。A的左子树后序为D,E,B，右子树后序为43.（10分）设某计算机的主存容量为64KB，按字节编址；Cache容量为4KB，采用直接映射方式，主存与Cache之间按16B的块进行数据交换。要求：(1)主存地址中各字段（块内地址、Cache行号、标记）分别占多少位？画出主存地址格式；(2)若CPU访问的主存地址为0x1234，则该地址所在的主存块映射到Cache的哪一行？对应的标记值是多少？(3)当访问0x1234时Cache未命中，说明将主存块调入Cache的过程。|标记（4位）|Cache行号（8位）|块内地址（4位）|(2)0x1234=0001001000110100B，按上述字段划分：-块内地址=0100B=4；-Cache行号=00100011B=35；-标记=0001B=1。故该地址所在主存块映射到Cache的第35行，对应标记值为1。(3)未命中时，由硬件将主存地址所在的主存块（地址范围0x1230—0x123F，共16B）调入Cache的第35行，将该行的标记置为1，并将有效位置1。若第35行原来的有效位为1（已被其他主存块占用），则在写回法下需先将原主存块写回主存，再装入新块；在写直达法下可直接覆盖。44.（10分）某计算机采用5段指令流水线，各段所需时间分别为3ns、2ns、4ns、2ns、3ns，每两级之间锁存器的延迟为1ns。要求：(1)该流水线的时钟周期应取多少？(2)连续执行100条指令（不考虑分支转移和流水线冲突），共需多少时间？(3)该流水线的实际吞吐率是多少（单位：条/秒）？T(3)实际吞吐率为：TP解析：流水线建立时间后，进入稳态，每个时钟周期执行完一条指令；时钟周期由最慢段和锁存器延迟共同决定。45.（10分）某车站售票厅内设一个售票窗口，售票厅最多可容纳10人（含正在买票者）。顾客进入售票厅后在窗口前排队买票，售票员空闲时为队首顾客售票。请用P、V操作写出顾客进程与售票员进程的同步算法，并说明所用信号量的含义及初值。P(empty);//申请进入售票厅

V(haveCustomer);//告知售票员有顾客排队

P(service);//等待被服务

买票;

V(empty);//买完离开，释放容量售票员进程：while(TRUE){

P(haveCustomer);//无顾客排队则等待

V(service);//为一名顾客服务

售票;

}解析：-empty保证售票厅内人数不超过10，当厅内满员时，顾客在入口处等待，实现容量限制。-haveCustomer与service成对出现，实现售票员与顾客之间的同步：先有顾客排队，售票员才能售票；先被售票员唤醒，顾客才能买到票。-若需严格按到达先后次序（FIFO）服务，可增设互斥信号量保护排队队列；在本题同步要求下，上述信号量已能保证互斥与同步的正确性。46.（10分）某请求分页系统采用固定分配局部置换策略，分配给某进程的物理块数为4，进程的页面访问序列为：1假设初始时内存为空，凡第一次访问到的页面都产生缺页。要求：(1)分别采用FIFO置换算法和LRU置换算法，给出各自的页面置换过程；(2)分别计算两种算法的缺页次数和缺页率。答案：(1)FIFO置换算法的置换过程：访问页面123412512345内存块状态11,21,2,31,2,3,41,2,3,41,2,3,42,3,4,51,3,4,51,2,4,51,2,3,51,2,3,42,3,4,5是否缺页缺缺缺缺命中命中缺缺缺缺缺缺LRU置换算法的置换过程：访问页面123412512345内存块状态11,21,2,31,2,3,41,2,3,41,2,3,41,2,4,51,2,4,51,2,4,51,2,3,51,2,3,41,2,4,5是否缺页缺缺缺缺命中命中缺命中命中缺缺缺(2)FIFO算法缺页10次，缺页率=1012≈解析：LRU是栈式算法，不会出现Belady异常；而FIFO算法可能出现分配的物理块数增多而缺页率反而上升的Belady异常。47.（5分）某单位申请到一个B类地址块172.22.0.0/16，现要求划分成若干个子网，使每个子网最多能容纳1000台主机。要求：(1)至少需要借用多少位主机号作为子网号？(2)写出划分后的子网掩码；(3)写出第1个子网的网络地址及其可分配的IP地址范围。参考答案与解析一、单项选择题1.答案：B解析：由limn→∞2.答案：A解析：删除第i个元素后，其后的n−3.答案：D解析：D中e先出栈时，栈内自底向上为c,d,e，故e出栈后d必然先于c出栈，4.答案：A5.答案：B解析：由n0=n2+1及n=n0+n6.答案：A解析：当二叉排序树退化为单支树时，查找长度与顺序查找相同，为O(7.答案：C解析：邻接表只表示出边，求入度需扫描所有顶点的边表，统计指向该顶点的边的条数，时间复杂度为O(8.答案：B解析：Kruskal算法的开销主要在按权值对e条边进行排序，故为O(9.答案：C解析：AOE网中可能存在多条关键路径，C错误。缩短关键活动并不必然缩短工期，前提是该活动位于所有关键路径上。10.答案：B解析：$H(22)=0$，$H(44)=0$冲突后存入1，$H(15)=4$，$H(26)=4$冲突后探测5为空，故26存入地址5。11.答案：C解析：简单选择排序的移动次数与初始排列有关，但比较次数始终为n(12.答案：B解析：1MB=213.答案：A14.答案：C15.答案：C解析：块内地址=log232=516.答案：C解析：RISC以硬布线控制为主，CISC以微程序控制为主，C错误。17.答案：C18.答案：A19.答案：A20.答案：A解析：流水线的吞吐率受最慢段的延迟限制，最大吞吐率=121.答案：D解析：数据传输率=100×1022.答案：B23.答案：B解析：平均旋转等待时间=607200×24.答案：D解析：阻塞态只能先转换为就绪态，再由调度程序调度进入运行态，不能直接转换为运行态。25.答案：B解析：进程是资源分配的基本单位，线程是调度的基本单位；同一进程的线程共享进程的地址空间，线程切换开销小于进程切换。26.答案：B解析：调度顺序为服务时间3、4、5、6的作业，完成时间分别为3、7、12、18，平均周转时间=327.答案：A28.答案：C解析：系统资源数4满足4≥29.答案：A解析：8196=2×4096+4，故页号为2，偏移量为4。30.答案：A解析：D是OPT置换算法的特征，该算法在实际中无法实现。31.答案：C32.答案：B33.答案：B34.答案：D35.