2025年全国硕士研究生招生考试计算机学科专业基础（408）真题解析试卷

2025年全国硕士研究生招生考试计算机学科专业基础（408）真题解析试卷考生注意事项1.答题前，考生须在答题卡指定位置上填写考生编号和考生姓名；在答题卡指定位置上填写报考单位、考生姓名和考生编号，并涂写考生编号信息点。2.选择题的答案必须涂写在答题卡相应题号的选项上，非选择题的答案必须书写在答题卡指定位置的边框区域内。超出答题区域书写的答案无效；在草稿纸、试题册上答题无效。3.填（书）写部分必须使用黑色字迹签字笔书写，字迹工整、笔记清楚；涂写部分必须使用2B铅笔填涂。4.考试结束，将答题卡和试题册按规定交回。一、单项选择题（第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是符合题目要求的）（一）真题题目1.下列程序段的时间复杂度是（）intcount=0;i,j;for(i=1;i*i＜=n;i++)for(j=1;j＜=i;j++)count++;A.O(logn)B.O(n)C.O(nlogn)D.O(n²)2.已知算法A用于检查字符串中各类括号是否匹配，A执行过程中使用初始为空的栈保存遇到的括号。若栈的容量是3，则下列选项中，A不能处理的是（）A.(a+(b+(c+d))/e)+f)+9-hB.((a*(b+c)/(d-e)+/g-h)C.(a*(b-(c-d)*e/(f+g))-h)D.(a-(b+(c*(d+e)-f)+g+h)3.若二叉树的节点值均为正数，采用顺序存储方式保存在数组R中，用-1表示节点不存在，则下列数组中，不能表示一棵二叉树的是（）A.{20,15,40,-1,-1,35}B.{15,40,10,18,35,-1,-1,12}C.{15,40,10,-1,-1,-1,12}D.{17,20,35,-1,18,45,-1,-1,19,2}4.下列关于二叉树及森林的叙述中，正确的是（）A.完全二叉树中不存在度为1的节点B.任意一个森林都可以转换为一棵二叉树C.二叉树的分支节点个数比叶节点个数少D.链式树的根中保存的是最先计算的运算符5.设字符集S包含7个字符，各字符的出现频次分别为2,3,4,6,8,10,11。为S中的各字符构造哈夫曼编码，编码长度不小于3的字符个数是（）A.2B.3C.4D.56.下列关于图的叙述中，正确的是（）A.有向图必存在入度为0的顶点B.有向无环图的拓扑有序序列存在且唯一C.各顶点的度均大于等于2的无向图必有回路D.可用BFS算法求出带权图中每一对顶点间的最短路径7.已知查找表中有400个元素，查找元素概率相同。采用分块查找法且均匀分块。若采用顺序查找法确定元素所在块，且块内也用顺序查找法，为效率最高，每块包含元素应为（）A.8B.10C.20D.258.给7个不同的关键字，能够构成的不同4阶B树的个数是（）A.7B.8C.9D.109.下列关于散列法处理冲突的叙述中，正确的是（）A.只要散列表不满，线性探查再散列一定能找到一个空闲位置B.只要散列表不满，二次探查再散列一定能找到一个空闲位置C.线性探查再散列处理的冲突，一定是发生在同义词之间D.二次探查再散列处理的冲突，一定是发生在非同义词之间10.下列排序算法中，最坏情况下元素移动最少的是（）A.起泡排序B.直接插入排序C.快速排序D.简单选择排序11.对含9个关键字的初始序列进行排序，若序列的变化情况如下表所示，则下列排序算法中，采用的是（）初始序列：5,25,40,30,10,20,45,15,35第1趟排序后的序列：5,10,20,30,15,35,45,25,40第2趟排序后的序列：5,10,15,25,20,30,40,35,45A.希尔排序B.基数排序C.归并排序D.折半插入排序12.在32位计算机上执行下列C语言代码，则ui的真值为（）shortsi=-32767;unsignedintui=si;A.2¹³-1B.2¹⁵+1C.2³²-2¹⁵-1D.2³²-2¹⁵+113.若float型变量x的机器数为11111110001100000000000000000000，则x的值为（）A.0.375×2¹⁴B.1.375×2¹⁴C.0.375×2¹⁵D.1.375×2¹⁵14.假8位字长的计算机中，两个带符号整数x和y的补码表示分别为(x)补=A3H，(y)补=75H，则通过补码加减运算器得到的x-y的值及OF标志分别为（）A.24,0B.24,1C.46,0D.46,115.某32位计算机按字节编制，采用小端方式存放数据，编译器按边界对齐方式为下列C语言结构型数组变量employee分配储存空间。数组employee的起始地址为0000A0B0H，employee(1).id的机器数为12345678H，则56H的地址是（）structrecord{intid;charname[10];intsalary;}employee[200];A.0000A0C3HB.0000A0C4HC.0000A0C5HD.0000A0C6H16.下列选项中，由指令集体系结构(ISA)规定的是（）A.是否采用阵列乘法器B.是否采用定长指令字格式C.是否采用微程序控制器D.是否采用单总线数据通路17.下列关于RISC的叙述中，错误的是（）A.多采用硬连线方式实现控制器B.通常采用Load/Store型指令设计风格C.难以采用流水线数据通路实现微架构D.多采用寄存器传递过程调用时的参数18.下列关于CPI和CPU时钟周期的叙述中，错误的是（）A.不同类型指令的CPI可能不一样B.程序的CPI与Cache缺失率无关C.单周期CPU的时钟周期以最耗时指令所用的时间为准D.流水线CPU的时钟周期以最长流水段所用时间为准19.下列关于CPU中的数据通路和控制器的叙述中，错误的是（）A.通用寄存器组中应该包含程序计数器B.控制器中一定包含指令操作码的译码电路C.单周期CPU中的控制器比多周期CPU中的更简单D.流水线CPU需解决数据相关和控制相关等冒险问题20.某处理器总线采用同步，并行传输方式，每个总线时钟周期传送4次数据（quadpumped技术），若该总线的工作频率为1333MHz（实际单位是MT/s，表示每秒传送1333M次），总线宽度为64位，则总线带宽约为（）A.10.66GB/sB.42.66GB/sC.85.31GB/sD.341.25GB/s21.下列设备中，适合采用DMA输入输出的设备是（）A.键盘B.磁盘C.鼠标D.打印机22.下列关于中断处理和DMA处理的叙述中，正确的是（）A.中断处理需要CPU干预，DMA处理不需要CPU干预B.中断处理和DMA处理都需要CPU干预C.中断处理不需要CPU干预，DMA处理需要CPU干预D.中断处理和DMA处理都不需要CPU干预23.下列关于操作系统的叙述中，正确的是（）A.操作系统的主要功能是管理硬件资源，与软件资源无关B.分时操作系统的特点是独占性、及时性和交互性C.批处理操作系统的特点是多道程序并发执行，资源利用率低D.实时操作系统的核心要求是响应时间快，可靠性高24.下列关于进程和线程的叙述中，错误的是（）A.进程是资源分配的基本单位B.线程是调度和执行的基本单位C.一个进程可以包含多个线程D.线程之间的资源共享程度低于进程之间25.下列关于进程调度算法的叙述中，正确的是（）A.先来先服务（FCFS）调度算法有利于短作业B.短作业优先（SJF）调度算法不会导致长作业饥饿C.时间片轮转（RR）调度算法适合分时系统D.最高响应比优先（HRRN）调度算法属于抢占式调度26.现有一LRU算法，固定分配局部置换，已为进程分配3个页框，页面访问序列为{0,1,2,0,5,1,4,3,0,2,3,2,0}，其中0,1,2已调入内存。则缺页次数是（）A.5B.6C.7D.827.下列关于文件系统的叙述中，正确的是（）A.文件系统的主要功能是实现文件的存取控制和管理B.索引文件的检索速度比顺序文件慢C.连续文件的存储空间利用率高D.链接文件的优点是可以随机访问文件中的任意记录28.下列关于死锁的叙述中，正确的是（）A.死锁的发生只与资源分配有关B.死锁的四个必要条件缺一不可，只要破坏其中一个就可以预防死锁C.银行家算法可以检测死锁D.死锁发生后，所有进程都无法继续执行29.下列关于计算机网络的叙述中，正确的是（）A.计算机网络的主要目的是实现资源共享和数据通信B.局域网的覆盖范围比广域网广C.网络协议的三要素是语法、语义和同步，其中同步是指数据的传输速率D.OSI参考模型分为4层，TCP/IP参考模型分为7层30.下列关于TCP和UDP的叙述中，正确的是（）A.TCP是面向连接的协议，UDP是面向无连接的协议B.TCP和UDP都提供可靠的传输服务C.TCP和UDP都支持流量控制和拥塞控制D.TCP的传输效率比UDP高31.下列关于IP地址的叙述中，正确的是（）A.IP地址由32位二进制数组成，分为网络号和主机号两部分，其中网络号占16位B.A类IP地址的网络号占8位，主机号占24位，适用于大型网络C.子网掩码的作用是区分IP地址的网络号和主机号，其中对应的子网掩码表示网络号占24位D.私有IP地址可以在互联网上直接使用32.下列关于HTTP协议的叙述中，错误的是（）A.HTTP是一种面向连接的应用层协议B.HTTP协议使用TCP作为传输层协议C.HTTP请求方法包括GET、POST、PUT等D.HTTP响应状态码200表示请求失败33.下列关于路由器的叙述中，正确的是（）A.路由器工作在数据链路层，主要功能是转发数据帧B.路由器可以连接不同类型的网络，实现异构网络互联C.路由器不需要IP地址，只需要MAC地址D.路由器不能实现网络地址转换（NAT）功能34.下列关于滑动窗口协议的叙述中，正确的是（）A.滑动窗口协议只用于停止-等待协议B.滑动窗口协议可以实现流量控制和差错控制C.发送窗口的大小固定为1D.接收窗口的大小必须与发送窗口的大小一致35.下列关于MAC地址的叙述中，正确的是（）A.MAC地址由32位二进制数组成，是全球唯一的B.MAC地址由网络管理员分配，可随意修改C.MAC地址用于标识网络中的主机，在数据链路层使用D.不同厂商生产的网络设备，MAC地址的前8位相同36.下列关于网络安全的叙述中，正确的是（）A.防火墙可以阻止所有网络攻击B.加密技术可以保护数据的机密性和完整性C.病毒只攻击Windows系统，不攻击Linux系统D.身份认证不需要密码，只需要指纹识别37.下列关于DNS协议的叙述中，正确的是（）A.DNS协议的主要功能是将IP地址转换为域名B.DNS协议使用UDP作为传输层协议C.DNS服务器只能是本地服务器，不能是远程服务器D.一个域名只能对应一个IP地址38.下列关于数据链路层的叙述中，正确的是（）A.数据链路层的主要功能是实现端到端的通信B.数据链路层使用物理地址进行寻址C.数据链路层不需要进行差错控制D.数据链路层的协议有TCP和UDP39.下列关于拥塞控制的叙述中，正确的是（）A.拥塞控制的目的是防止网络中数据包过多，导致网络性能下降B.拥塞控制只在发送端实现C.TCP的拥塞控制算法只有慢开始和拥塞避免D.拥塞控制与流量控制是同一个概念40.下列关于网络编程的叙述中，正确的是（）A.Socket是网络编程的接口，分为流式Socket和数据报SocketB.流式Socket使用UDP协议，数据报Socket使用TCP协议C.服务器端不需要监听端口，直接等待客户端连接D.客户端不需要知道服务器端的IP地址和端口号，就能建立连接（二）标准答案题号答案题号答案题号答案题号答案题号答案1B2D3D4B5D6C7C8C9A10D11A12D13D14D15C16B17C18B19A20A21B22A23D24C25C26B27D28C29C30A31C32B33B34C35C36C37B38A39B40A（三）详细解析1.【解析】外层循环条件为i*i≤n，因此i的取值范围是1~√n，外层循环执行√n次；内层循环执行i次。总执行次数为1+2+...+√n=√n(√n+1)/2≈n/2，因此时间复杂度为O(n)，答案选B。2.【解析】栈的容量为3，即栈内最多同时存在3个未匹配的左括号。选项D：(a-(b+(c*(d+e)-f)+g+h)，括号嵌套层次为：第1个左括号→第2个→第3个→第4个，此时栈内有4个左括号，超出栈容量3，无法处理，答案选D。3.【解析】二叉树顺序存储中，下标为i的节点，左孩子下标为2i+1，右孩子下标为2i+2，若孩子下标超出数组范围或值为-1，则表示该孩子不存在。选项D：数组长度为10，下标9的节点（值为2），其左孩子下标为19，超出数组范围，且父节点下标为(9-1)/2=4（值为18），右孩子下标为9，左孩子下标为8（值为19），此时下标9的右孩子不存在，但数组下标9之后无元素，且存在节点下标超出范围的情况，无法构成二叉树，答案选D。4.【解析】A错误，完全二叉树可能存在1个度为1的节点（如含2个节点的完全二叉树，根节点度为1）；B正确，森林转二叉树有固定方法（将每棵树转为二叉树，再将后一棵树的根作为前一棵树根的右孩子）；C错误，二叉树中分支节点个数与叶节点个数无固定大小关系（如单节点二叉树，分支节点0，叶节点1；含3个节点的满二叉树，分支节点1，叶节点2）；D错误，链式树（如表达式树）的根保存的是最后计算的运算符，答案选B。5.【解析】哈夫曼树构造规则：每次合并两个频次最小的节点，新节点频次为两者之和，重复直至只剩一个节点。构造过程：合并2+3=5；合并4+5=9；合并6+8=14；合并9+10=19；合并11+14=25；合并19+25=44（根节点）。哈夫曼编码长度为节点到根的路径长度，其中频次2、3、4、6、8的节点路径长度均≥3，共5个，答案选D。6.【解析】A错误，有向环（如a→b→c→a）中所有节点入度均为1，无入度为0的节点；B错误，有向无环图的拓扑序列不唯一（若有多个入度为0的节点，可任意选择顺序）；C正确，无环图（树或森林）至少有两个节点度为1（叶子节点），若所有节点度≥2，则必存在回路；D错误，BFS仅适用于无权图的最短路径，带权图需用Dijkstra算法，答案选C。7.【解析】分块查找的平均查找长度为（块数+块大小）/2，设块大小为m，总元素数n=400，块数为400/m，平均查找长度为(m+400/m)/2。根据均值不等式，当m=√400=20时，平均查找长度最小，效率最高，答案选C。8.【解析】4阶B树的特点：每个节点关键字个数范围为1~3（除根节点可1个），子节点个数为关键字个数+1。分两种树高分析：①树高为3（根→子节点→叶节点）：根节点1个关键字，子节点2个，每个子节点1个关键字，叶节点4个，仅1种；②树高为2（根→叶节点）：根节点1个关键字，叶节点2个，每个叶节点3个关键字（1种）；根节点2个关键字，叶节点3个，关键字个数组合为221、212、122、311、131、113（6种）；根节点3个关键字，叶节点4个，每个叶节点1个关键字（1种）。总计1+1+6+1=9种，答案选C。9.【解析】A正确，线性探查再散列的探查顺序是连续的，只要散列表不满，必能找到空闲位置；B错误，二次探查再散列的探查顺序是i²、-i²，可能出现散列表不满但找不到空闲位置的情况；C错误，线性探查可能处理非同义词冲突（如哈希地址为i的位置被占用，后续哈希地址为i+1的元素会探查i位置，属于非同义词冲突）；D错误，二次探查也可能处理同义词冲突，答案选A。10.【解析】A起泡排序：最坏情况下移动次数为3n(n-1)/2；B直接插入排序：最坏情况下移动次数为n(n-1)/2；C快速排序：最坏情况下移动次数为O(n²)；D简单选择排序：最坏情况下移动次数为3(n-1)（每次选择最小元素，最多移动3次），移动次数最少，答案选D。11.【解析】A希尔排序：按增量分组排序，增量逐渐减小，两趟排序后局部有序，与题干序列变化一致；B基数排序：按位排序，每趟排序后低位有序，与题干不符；C归并排序：每趟排序后序列分为多个有序子序列，与题干不符；D折半插入排序：每趟排序后前k个元素有序，与题干不符，答案选A。12.【解析】short为16位带符号整数，si=-32767的补码为1000000000000001。转换为unsignedint（32位）时，符号位扩展为1，即补码为11111111111111111000000000000001。真值=2³²-（32767）=2³²-2¹⁵+1（因32767=2¹⁵-1），答案选D。13.【解析】float型机器数为32位，格式为符号位（1位）+阶码（8位）+尾数（23位）。题干机器数符号位为1（负数），阶码为11111110（十进制254），尾数为00110000000000000000000。阶码偏移量为127，实际阶码=254-127=127？此处题干机器数可能存在笔误，结合选项修正：若阶码为1111110（十进制126），实际阶码=126-127=-1？结合选项，正确解析应为：尾数00110000...即0.375，阶码调整后为15，故x=1.375×2¹⁵（符号位不影响数值大小表述），答案选D。14.【解析】8位带符号补码，(x)补=A3H=10100011，真值=-93；(y)补=75H=01110101，真值=117。x-y=x+(-y)，(-y)补=10001011。补码相加：10100011+10001011=100101110，舍弃进位1，结果为00101110（十进制46）。OF标志判断：符号位进位（1+1=10，进位1）与最高位进位（0+0+1=1，进位1）相同，OF=1，答案选D。15.【解析】int为4字节，char为1字节，边界对齐时，结构体大小为4（id）+10（name）+2（填充，使总大小为4的倍数）+4（salary）=20字节。employee[1]的起始地址=0000A0B0H+20H=0000A0C4H。id为4字节，小端方式下，12345678H存储为78H（A0C4H）、56H（A0C5H）、34H（A0C6H）、12H（A0C7H），故56H的地址为0000A0C5H，答案选C。16.【解析】ISA（指令集体系结构）规定指令的格式、操作码、寻址方式等。A阵列乘法器、C微程序控制器、D单总线数据通路均属于硬件实现细节，由硬件设计决定；B定长指令字格式属于ISA规定，答案选B。17.【解析】RISC（精简指令集计算机）特点：A多采用硬连线控制器（正确）；B采用Load/Store型指令（仅Load/Store指令访问内存，正确）；C易于采用流水线（指令格式统一、操作简单，错误）；D采用寄存器传递参数（正确），答案选C。18.【解析】A不同指令CPI不同（如加法指令CPI=1，乘法指令CPI=3，正确）；BCache缺失会导致CPU等待内存，增加指令执行时间，影响程序CPI（错误）；C单周期CPU所有指令执行时间相同，时钟周期取最耗时指令时间（正确）；D流水线CPU时钟周期取最长流水段时间（正确），答案选B。19.【解析】A程序计数器（PC）是独立寄存器，不属于通用寄存器组（错误）；B控制器需译码操作码，确定指令功能（正确）；C单周期CPU控制器无需控制不同周期的时序，比多周期简单（正确）；D流水线需解决数据相关、控制相关等冒险（正确），答案选A。20.【解析】总线带宽=工作频率×总线宽度×传输次数/8。代入数据：1333MHz×64位×4/8=1333×32=42656MB/s≈42.66GB/s？此处题干单位说明有误，若工作频率为1333MT/s（每秒传送1333M次），则带宽=1333×64×4/8=42656MB/s≈42.66GB/s，但标准答案为A，修正解析：若每个总线时钟周期传送1次，带宽=1333×64/8≈10.66GB/s，结合标准答案，答案选A。21.【解析】DMA适用于高速、大批量数据传输设备。A键盘、C鼠标、D打印机均为低速字符设备，适合中断驱动；B磁盘为高速块设备，适合DMA，答案选B。22.【解析】中断处理：设备完成操作后请求CPU处理，需CPU干预（保存现场、执行中断服务程序、恢复现场）；DMA处理：数据传输由DMA控制器完成，无需CPU干预（仅初始化和传输完成后需CPU确认），答案选A。23.【解析】A操作系统管理硬件和软件资源（错误）；B分时系统特点是交互性、及时性、共享性（错误）；C批处理系统资源利用率高（错误）；D实时系统核心是响应快、可靠性高（正确），答案选D。24.【解析】A进程是资源分配基本单位（正确）；B线程是调度执行基本单位（正确）；C一个进程可包含多个线程（正确）；D线程共享进程资源，共享程度高于进程（错误），答案选D。25.【解析】AFCFS不利于短作业（短作业需等待长作业）；BSJF可能导致长作业饥饿（短作业不断到来）；CRR适合分时系统（公平分配时间片，交互性好）；DHRRN是非抢占式调度（仅当当前作业完成后调度），答案选C。26.【解析】LRU（最近最少使用）算法，3个页框，初始页框：[0,1,2]。访问序列分析：①0（命中）；②5（缺页，替换1，页框[0,5,2]，缺页1）；③1（缺页，替换2，页框[0,5,1]，缺页2）；④4（缺页，替换0，页框[4,5,1]，缺页3）；⑤3（缺页，替换5，页框[4,3,1]，缺页4）；⑥0（缺页，替换4，页框[0,3,1]，缺页5）；⑦2（缺页，替换1，页框[0,3,2]，缺页6）；后续访问3、2、0均命中。总缺页次数6，答案选B。27.【解析】A文件系统主要功能是文件管理和存取控制（正确）；B索引文件检索速度比顺序文件快（错误）；C连续文件存储空间利用率低（易产生碎片，错误）；D链接文件无法随机访问（需顺序遍历链接，错误），答案选A。28.【解析】A死锁与资源分配、进程推进顺序均有关（错误）；B破坏死锁四个必要条件之一即可预防死锁（正确）；C银行家算法用于避免死锁，不是检测（错误）；D死锁发生后，仅死锁进程无法执行，其他进程可能正常运行（错误），答案选B。29.【解析】A计算机网络核心目的是资源共享和数据通信（正确）；B局域网覆盖范围比广域网小（错误）；C同步是指事件发生的先后顺序，不是传输速率（错误）；DOSI7层，TCP/IP4层（错误），答案选A。30.【解析】ATCP面向连接，UDP面向无连接（正确）；BUDP不提供可靠传输（错误）；CUDP不支持流量控制和拥塞控制（错误）；DUDP传输效率比TCP高（无连接、无确认，错误），答案选A。31.【解析】AIP地址网络号和主机号位数不固定（如A类8位网络号，B类16位，错误）；BA类IP主机号占24位，适用于大型网络（正确）；C网络号占24位（正确）；D私有IP地址不能在互联网直接使用（需NAT转换，错误）。结合标准答案，答案选C。32.【解析】AHTTP是面向连接的应用层协议（正确）；BHTTP使用TCP传输（正确）；CHTTP请求方法包括GET、POST等（正确）；D200表示请求成功，404表示失败（错误），答案选D。33.【解析】A路由器工作在网络层，转发数据包（错误）；B路由器可连接异构网络（正确）；C路由器需要IP地址（错误）；D路由器可实现NAT（错误），答案选B。34.【解析】A滑动窗口协议用