2026年考研计算机408专业基础综合真题回忆版

2026年考研计算机408专业基础综合真题回忆版一、单项选择题（每题2分，共80分）1.已知某程序段的执行时间可表示为T(A.OB.OC.OD.O2.设循环队列存储在数组A[A.(B.(C.(D.(3.具有1025个结点的完全二叉树中，叶子结点的个数为（）。A.512B.513C.1024D.10254.已知某二叉树的后序遍历序列为DEBFCA，中序遍历序列为DBEAFC，则其先序遍历序列为（）。A.ABDECFB.ABDFECC.ABDEFCD.ADBECF5.已知某二叉树的先序序列和后序序列，不能唯一确定该二叉树；若要利用这两个序列唯一确定该二叉树，则该二叉树必须满足（）。A.每个非叶结点都有左右孩子B.所有叶结点的层次相同C.每个结点的度为1D.所有结点都只有右孩子6.设图G的邻接表为：顶点1的邻接点依次为2、3；顶点2的邻接点为4；顶点3的邻接点为2、4；顶点4的邻接点为空。若从顶点1出发，按邻接点编号升序进行深度优先遍历，则遍历序列为（）。A.1,2,3,4B.1,2,4,3C.1,3,2,4D.1,3,4,27.下列关于Dijkstra算法的叙述中，错误的是（）。A.适用于所有边权非负的带权图B.可以用于求解单源最短路径问题C.使用优先队列优化后时间复杂度可以降低D.图中存在负权边时也一定能够正确求出最短路径8.依次将关键字5、3、7、2、4、6、8插入一棵初始为空的二叉排序树，则中序遍历该二叉树得到的关键字序列为（）。A.2,3,4,5,6,7,8B.5,3,7,2,4,6,8C.5,3,2,4,7,6,8D.2,4,3,6,8,7,59.下列排序算法中，平均时间复杂度为O(nlogA.堆排序B.快速排序C.归并排序D.直接插入排序10.对关键字序列{12,8,17,5,9,20}进行一趟快速排序（以第一个元素为基准）后的序列为（）。A.9,8,5,12,17,20B.5,8,9,12,17,20C.8,5,9,12,17,20D.9,8,12,5,17,2011.将关键字序列{9,17,5,20,12,8}建成大根堆，则根结点的值为（）。A.17B.20C.12D.912.下列排序算法中，不稳定的是（）。A.直接插入排序B.冒泡排序C.简单选择排序D.归并排序13.若一个8位二进制整数采用补码表示，且由3个1和5个0组成，则其最小值为（）。A.−B.−C.−D.−14.若浮点数采用IEEE754单精度格式，则−1.5A.0xBFC00000B.0xBFC00001C.0xBFF00000D.0xBFE0000015.用8K×4位的SRAM芯片构成32K×16位的存储器，需要芯片数为（）。A.4B.8C.16D.3216.某计算机Cache容量为16KB，主存与Cache之间按块传送，块大小为32B，按字节编址，采用直接映射方式。若主存地址为32位，则Cache标记字段的位数为（）。A.16B.18C.20D.2317.下列关于虚拟存储器的叙述中，错误的是（）。A.虚拟存储器的最大容量仅由主存容量决定B.页式虚拟存储器以页为单位进行分派和交换C.快表（TLB）用于加速逻辑地址到物理地址的转换D.页面换入换出由操作系统负责完成18.采用变址寻址方式时，操作数的有效地址是（）。A.指令中形式地址与变址寄存器内容之和B.程序计数器内容与指令中形式地址之和C.变址寄存器内容本身D.指令中形式地址本身19.在单周期处理器中，执行一条指令所需的时间（）。A.等于所有指令中最长的执行时间B.等于每条指令实际执行时间C.与时钟周期无关D.等于流水段个数乘以时钟周期20.某指令流水线有4段，各段耗时分别为2ns、2ns、2ns、3ns，每段之间的流水线寄存器延时为1ns，则该流水线的时钟周期至少为（）。A.2nsB.3nsC.4nsD.5ns21.CPU通常在下列哪一时刻采样中断请求信号？（）A.一条指令执行开始时B.一条指令执行结束时C.仅取指阶段D.每个时钟周期结束时刻22.下列总线标准中，属于串行总线的是（）。A.PCIB.USBC.ISAD.AHB23.在DMA方式中，数据传送过程中由（）控制总线完成数据交换。A.CPUB.DMA控制器C.中断控制器D.通道控制器24.在微程序控制器中，一条机器指令的功能通常由一组（）实现。A.微命令B.微程序C.微操作D.微指令25.在进程三态模型中，进程由阻塞态转换为就绪态的原因是（）。A.时间片用完B.被高优先级进程抢占C.等待的事件已经发生D.进程请求I/O26.下列进程调度算法中，可能使长进程长时间得不到运行而产生饥饿的是（）。A.先来先服务B.短进程优先C.时间片轮转D.多级反馈队列（所有就绪队列均采用时间片轮转）27.系统中有3个进程，每个进程最多需要4台打印机，为使系统不会发生死锁，至少需要安装（）台打印机。A.9B.10C.11D.1228.用P、V操作管理临界区时，正确的做法是（）。A.进入临界区前执行V操作，退出临界区后执行P操作B.进入临界区前执行P操作，退出临界区后执行V操作C.P、V操作均在进入临界区之前执行D.P、V操作均在退出临界区之后执行29.在可变分区存储管理中，采用最佳适应算法时，空闲分区通常按（）排列。A.地址递增B.地址递减C.容量递增D.容量递减30.某分页存储管理系统，页面大小为4KB，逻辑地址长度为32位，页号占20位，则页内偏移量占（）位。A.10B.11C.12D.2031.某进程的页面访问序列为1,2,3,4,1,2,5,1,2,3,4,5，分配给该进程3个物理块（初始为空），采用LRU置换算法时，缺页次数为（）。A.8B.9C.10D.1132.某文件系统采用混合索引分配方式，每个索引块最多存放256个盘块号，文件控制块中有13个地址项，其中10个直接地址项、1个一次间接地址项、1个二次间接地址项、1个三次间接地址项。则该文件最大可占用的盘块数为（）。A.256B.10C.13D.1033.使用绝对路径名访问文件时，从（）目录开始查找。A.当前目录B.根目录C.用户主目录D.上一级目录34.下列关于SPOOLing技术的叙述中，正确的是（）。A.只能在单道批处理系统中使用B.SPOOLing仍要求设备为独占设备C.SPOOLing直接完成每次设备与内存之间的数据交换D.可将一台物理打印机模拟为多台逻辑打印机35.采用曼彻斯特编码传输数据的10Mbps以太网，其波特率为（）。A.5MBaudB.10MBaudC.20MBaudD.40MBaud36.在10Mbps以太网中，某站点检测到冲突并按截断二进制指数退避算法重传。若该帧是第3次重传，则其等待的随机时隙数r的取值范围为（）。A.0B.0C.0D.137.某网络地址为/24，需要划分为4个等长的子网，则划分后的子网掩码为（）。A.28B.92C.24D.4038.在互联网中，实现不同自治系统之间路由选择的协议是（）。A.RIPB.OSPFC.BGPD.ARP39.在TCP拥塞控制中，当发生超时重传时，慢开始门限（ssthresh）通常被设置为当前拥塞窗口cwnd的（）。A.1/2B.1/4C.1/8D.不变40.下列应用层协议中，既支持UDP又支持TCP传输的是（）。A.DNSB.HTTPC.SMTPD.FTP二、综合应用题（共70分）41.（10分）设计一个算法，判断一个带头结点的单链表L中的结点值序列是否为回文序列。例如，结点值序列1→2→3→2→1是回文序列。要求：时间复杂度为O((1)$额外空间，允许改变链表结构。typedefstructLNode{

intdata;

structLNode*next;

}LNode;

intisPalindrome(LNode*L){

if(L->next==NULL)//空表视为回文

return1;

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

//快慢指针找中间结点

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

slow=slow->next;

fast=fast->next->next;

}

//逆置后半段链表

LNode*cur=slow->next;

slow->next=NULL;

LNode*pre=NULL;

while(cur!=NULL){

LNode*next=cur->next;

cur->next=pre;

pre=cur;

cur=next;

}

//比较前半段与逆置后的后半段

LNode*p=L->next,*q=pre;

while(q!=NULL){

if(p->data!=q->data)

return0;

p=p->next;

q=q->next;

}

return1;

}时间复杂度为O(n)42.（10分）已知关键字序列为{19,14,23,1,68,20,84,27,55,11,10,79}，散列函数为H(（1）画出散列表的结构。（2）计算等概率查找成功时的平均查找长度（ASL）。ASL43.（10分）某计算机按字节编址，主存地址长度为20位，Cache容量为8KB，主存与Cache之间交换的块大小为64B，Cache采用2路组相联映射方式。（1）计算该Cache的组数、块内地址位数、组索引位数和标记位数。（2）若某主存地址为0x2B3C6，求其对应的Cache组号。0010按“标记8位+组索引6位+块内地址6位”划分：00101011组索引为001111，即十进制15。因此该地址对应的Cache组号为15。44.（10分）某计算机采用5段流水线，各段执行时间均为1个时钟周期。规定：若一条load指令与下一条指令存在数据相关，则需要在两条指令之间插入3个停顿周期。现有指令序列：I1:lw$t1,0($s0)

I2:add$t2,$t1,$t3

I3:sw$t2,4($s0)假设其他数据相关均可通过转发解决，求该指令序列执行完所需的时钟周期数，并说明停顿插入的位置。答案：3条指令在5段流水线中无停顿时的完成周期数为：5I1（lw）的目标寄存器是t1，I2（add）的源操作数之一也是t1，因此I1与I2之间存在load-use数据相关，需要在I1与I2之间插入3个停顿周期。I3读I2的运算结果，可通过转发解决，不需要额外停顿。执行完成所需时钟周期数：7因此共需10个时钟周期，停顿插入在I1和I2之间。解析：I1的lw指令要到访存阶段结束才能得到主存数据，而I2在译码阶段就要读取寄存器t1，因此必须暂停I2及其后续指令3个时钟周期。45.（10分）公共汽车上，司机与售票员的工作流程如下：司机：启动车辆、正常行驶、到站停车；售票员：售票、开车门、关车门。要求：车辆到站停稳后售票员才能开车门；售票员关好车门后司机才能启动车辆。请用P、V操作描述司机与售票员的同步算法，并说明所用信号量的含义及初值。semaphores1=0;

semaphores2=0;

driver(){

while(1){

P(s1);

启动车辆;

正常行驶;

到站停车;

V(s2);

}

}

conductor(){

while(1){

关车门;

V(s1);

售票;

P(s2);

开车门;

}

}解析：初始状态车门未关，司机执行P(s1)阻塞，直到售票员关好车门并执行V(s1)后才启动；司机到站停车后执行V(s2)，售票员执行P(s2)后才能开车门，满足同步关系。46.（10分）某虚拟页式存储管理系统采用固定分配局部置换，进程运行时依次访问的页号为：1,2,3,4,1,2,5,1,2,3,4,5（1）若分配给该进程3个页框，采用FIFO置换算法，计算缺页次数并写出每次缺页时的页面换入换出过程。（2）若分配给该进程4个页框，仍采用FIFO置换算法，计算缺页次数。（3）结合上述结果说明Belady现象。47.（10分）某单位申请到CIDR地址块/20，需将其划分为3个子网，每个子网分别至少容纳500、250、120台主机。（1）给出最节省地址空间的子网划分方案，包括每个子网的网络地址、子网掩码、可用IP地址范围。（2）路由器采用最长前缀匹配转发分组，若收到目的IP地址为30的分组，该分组应匹配哪个子网？如果单位内没有配置默认路由，对该分组应如何处理？（3）该单位向外发布路由时，可以采用怎样的路由聚合？参考答案与解析一、单项选择题1.答案：A解析：当n充分大时，增长最快的高阶项决定渐近时间复杂度。2.答案：A3.答案：B解析：完全二叉树中度为1的结点数至多为1，且结点总数1025为奇数，因此n1=0。由n0=4.答案：A解析：后序最后一个A为根，结合中序可将左右子树逐层切分，先序为ABDECF。5.答案：A解析：先序与后序结合时，若一个结点只有一个孩子，则无法确定该孩子是左孩子还是右孩子；只有每个非叶结点都有左右孩子时才可唯一确定。6.答案：B解析：从1访问2，再深入访问4，4无邻接点后回溯到1，再访问3。7.答案：D解析：Dijkstra算法基于贪心策略，负权边可能破坏其正确性。8.答案：A解析：二叉排序树的中序遍历序列一定是有序递增序列。9.答案：B10.答案：A解析：基准12最终落在第4个位置，左边均小于12，右边均大于12。11.答案：B解析：从最后一个非叶结点开始向下调整，20会上升到根结点。12.答案：C解析：简单选择排序可能把关键字相同的元素相对顺序改变。13.答案：A解析：补码为10000011时数值最小，其真值为−27+14.答案：A解析：−1.515.答案：C16.答案：B解析：Cache块数=16KB/17.答案：A解析：虚拟存储器的容量由CPU地址位数和辅存容量共同决定，不受主存容量的限制。18.答案：A19.答案：A20.答案：C解析：时钟周期至少为最长段耗时加上流水线寄存器延时，即3+21.答案：B22.答案：B23.答案：B24.答案：B25.答案：C26.答案：B解析：非抢占式短进程优先会使长进程等待时间过长。27.答案：B解析：最坏情况是每个进程都占有3台，再增加1台即可保证至少有一个进程能执行完毕，即3×28.答案：B29.答案：C解析：最佳适应算法优先分配最小的满足要求的空闲分区，因此空闲分区表按容量递增组织效率较高。30.答案：C31.答案：B32.答案：B33.答案：B34.答案：D35.答案：C36.答案：B37.答案：B38.答案：C39.答案：A40.答案：A二、综合应用题41.答案：算法思想：先用快慢指针找到链表的中间结点，将中间结点之后的后半段链表原地逆置，然后从表头和逆置后的后半段头同步向后比较。若所有对应结点值均相等，则是回文序列。C语言描述如下：42.答案：（1）各关键字对应的散列地址为：关键字19142316820842755111079散列地址611013761311101因此散列地址0～12的链表依次为：0：NULL1：14→1→27→792：NULL3：68→554：NULL5：NULL6：19→847：208：NULL9：NULL10：23→1011：1112：NULL（2）各关键字的查找成功比较次数依次为：14比较1次，1比较2次，27比较3次，79比较4次，68比较1次，55比较2次，19比较1次，84比较2次，20比较1次，23比较1次，10比较2次，11比较1次。43.