2025年计算机考研统考(408)真题与参考答案(清晰扫描版)

2025年计算机考研统考(408)真题与参考答案(清晰扫描版)一、单项选择题（第1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合试题要求）1.给定递归函数`intfun(intn){if(n<=1)return1;returnfun(n/2)+fun(n/2)+n;}`，其时间复杂度为：A.O(n)B.O(nlogn)C.O(n²)D.O(logn)参考答案：B解析：递推式为T(n)=2T(n/2)+n，根据主定理Case2，时间复杂度为O(nlogn)。2.初始为空的栈，入栈序列为a、b、c、d、e，不可能的出栈序列是：A.edcbaB.decbaC.dceabD.abcde参考答案：C解析：d先出栈时，a、b、c均已入栈且栈内顺序为c（栈顶）、b、a，a不可能先于b出栈。3.高度为5的完全二叉树（根节点位于第1层）的节点数不可能是：A.15B.16C.31D.30参考答案：A解析：高度为h的完全二叉树最少节点数为2^(h-1)，高度为5时最少为16，15是高度为4的完全二叉树的最大节点数。4.有向图G的邻接矩阵为`[[0,1,0,0],[0,0,1,1],[0,0,0,1],[1,0,0,0]]`，其强连通分量个数为：A.1B.2C.3D.4参考答案：A解析：4个节点构成一个闭合环，所有节点互相可达，整体为1个强连通分量。5.对序列{45,23,67,12,89,34,56,78}进行二路归并排序，第二趟归并结束后的序列是：A.{23,45,12,67,34,89,56,78}B.{23,45,12,67,34,56,78,89}C.{12,23,45,67,34,56,78,89}D.{12,23,34,45,56,67,78,89}参考答案：C解析：第一趟归并得到{23,45,12,67,34,89,56,78}，第二趟将前两个长度为2的子段、后两个长度为2的子段分别归并，得到{12,23,45,67,34,56,78,89}。6.下列关于散列表的说法正确的是：A.散列函数越复杂越好，冲突概率越低B.采用开放定址法处理冲突时，负载因子可以大于1C.采用链地址法处理冲突时，查找不需要比较关键字D.散列表的平均查找长度与表长无关，与负载因子和散列函数有关参考答案：D解析：散列函数过复杂会增加计算开销；开放定址法负载因子必须小于1；链地址法查找冲突元素仍需比较关键字。7.下列排序算法中，不稳定的是：A.插入排序B.冒泡排序C.希尔排序D.归并排序参考答案：C解析：希尔排序分组插入时可能改变相等元素的相对顺序，属于不稳定排序。8.一棵哈夫曼树有15个叶子节点，则非叶子节点的总数是：A.14B.15C.16D.17参考答案：A解析：哈夫曼树只有度为0和度为2的节点，满足n0=n2+1，因此n2=15-1=14。9.无向连通图有12个顶点、17条边，其最小生成树总权值为28。若删除一条权值为5的非树边，再加入一条权值为3的边且保持图连通，新的最小生成树总权值不可能是：A.26B.27C.28D.29参考答案：D解析：删除非树边不影响原有生成树，新增权值3的边最多替换生成树中一条权值≥3的边，总权值最大为28，不可能高于28。10.对n个元素进行快速排序，最坏情况下的空间复杂度是：A.O(1)B.O(logn)C.O(n)D.O(n²)参考答案：C解析：最坏情况下快速排序递归深度为n，栈空间开销为O(n)。11.某计算机采用补码定点整数，字长32位，其中1位符号位，能表示的最小负数是：A.-2^31B.-2^31+1C.-2^32D.-2^32+1参考答案：A解析：32位补码定点整数的表示范围为[-2^31,2^31-1]。12.某Cache容量为32KB，块大小为64B，采用直接映射方式，主存地址为32位按字节编址，主存地址中标记（Tag）的位数是：A.15B.17C.19D.21参考答案：B解析：块内地址占6位（2^6=64），Cache块数为32KB/64B=512，索引位占9位（2^9=512），Tag位为32-6-9=17位。13.某指令流水线由4个功能段组成，各段延迟分别为100ns、80ns、90ns、90ns，流水线满负荷工作时连续执行100条指令的吞吐率约为：A.8.77×10^6条/秒B.9.7×10^6条/秒C.1×10^7条/秒D.1.25×10^7条/秒参考答案：B解析：流水线周期为最大段延迟100ns，总执行时间为(4+100-1)×100ns=10300ns，吞吐率为100/(10300×10^-9)≈9.7×10^6条/秒。14.下列关于存储器层次结构的说法错误的是：A.Cache-主存层次主要解决CPU和主存的速度匹配问题B.主存-辅存层次主要解决存储器的容量扩展问题C.引入Cache后，程序员不需要考虑数据在Cache和主存之间的调度D.虚拟地址到物理地址的转换由操作系统完成，无需硬件支持参考答案：D解析：虚拟地址转换需要内存管理单元（MMU）硬件支持。15.某计算机主存地址空间为256MB按字节编址，指令Cache和数据Cache分离，均为4路组相联映射，块大小为64B。若指令Cache数据部分总容量为256KB，则指令Cache的组数是：A.256B.512C.1024D.2048参考答案：C解析：指令Cache总块数为256KB/64B=4096块，4路组相联下组数为4096/4=1024。16.某总线时钟频率为100MHz，总线宽度为32位，采用猝发传输方式，一次传输需要1个时钟周期发地址，4个时钟周期传4个32位数据，总线带宽为：A.100MB/sB.160MB/sC.320MB/sD.400MB/s参考答案：C解析：一次传输共5个时钟周期，传输数据量为4×4B=16B，每秒可传输100×10^6/5=20×10^6次，带宽为20×10^6×16B=320MB/s。17.下列关于RISC和CISC的说法正确的是：A.RISC的指令种类更多，功能更复杂B.RISC采用硬布线控制，CISC多采用微程序控制C.RISC的寄存器数量更少，寻址方式更丰富D.RISC的指令字长不固定，CISC的指令字长固定参考答案：B解析：RISC指令种类少、寻址方式简单、指令字长固定，通用寄存器数量多，采用硬布线控制提升执行效率。18.某磁盘转速为7200RPM，平均寻道时间为8ms，每个磁道有1000个扇区，每个扇区大小为512B，读取一个随机扇区的平均时间约为：A.8msB.12.17msC.16.33msD.20.5ms参考答案：B解析：平均旋转延迟为0.5/(7200/60)≈4.17ms，传输时间约为0.01ms，总平均时间≈8+4.17+0.01≈12.18ms。19.某浮点数阶码采用8位移码（含1位阶符），尾数采用24位补码（含1位数符），下列说法错误的是：A.阶码的表示范围是-128~+127B.规格化正尾数的范围是0.5≤M<1C.能表示的最大正数是(1-2^-23)×2^127D.能表示的最小正数是2^-151参考答案：D解析：最小规格化正尾数为2^-1，最小阶码为-128，因此最小正数为2^-1×2^-128=2^-129。20.下列操作中，不会引发中断的是：A.除数为0B.Cache缺失C.键盘输入字符D.缺页参考答案：B解析：Cache缺失由硬件直接处理，不需要触发中断。21.某计算机采用二级页表的分页存储管理，页大小为4KB，页表项大小为4B，逻辑地址空间为32位，则逻辑地址中一级页号、二级页号、页内偏移的位数分别是：A.10、10、12B.12、10、10C.8、12、12D.9、11、12参考答案：A解析：页内偏移占12位（2^12=4KB），单个页可存放4KB/4B=1024个页表项，二级页号占10位，一级页号占32-10-12=10位。22.下列关于I/O控制方式的说法正确的是：A.程序查询方式的CPU利用率最高B.中断方式不需要CPU干预数据传输C.DMA方式不需要CPU干预数据传输过程，只在传输开始和结束时需要CPU干预D.通道方式的CPU干预次数比DMA方式多参考答案：C解析：程序查询方式CPU利用率最低；中断方式需要CPU参与数据传输；通道方式CPU干预次数少于DMA。23.下列关于进程和线程的说法错误的是：A.线程是调度的基本单位，进程是资源分配的基本单位B.同一进程内的多个线程共享进程的地址空间C.不同进程的线程不能共享资源D.线程切换的开销比进程切换小参考答案：C解析：不同进程的线程可通过共享内存、管道等方式共享资源。24.某系统有5个进程，都需要同类资源4个，为保证系统不发生死锁，最少需要的资源数是：A.15B.16C.17D.20参考答案：B解析：死锁临界点为每个进程获得3个资源，共5×3=15个，额外增加1个资源即可打破死锁，总资源数为16。25.某分页存储管理系统页大小为4KB，进程页表为：页号0对应块号3，页号1对应块号7，页号2对应块号9，页号3对应块号2。逻辑地址0x1234对应的物理地址是：A.0x7234B.0x9234C.0x3234D.0x2234参考答案：AA.FCFSB.SSTFC.SCAND.CSCAN参考答案：B解析：最短寻道时间优先（SSTF）每次选择距离当前磁道最近的请求，平均寻道时间最短，但存在饥饿问题。27.某文件系统采用混合索引分配，i结点有10个直接地址项、1个一级间接地址项、1个二级间接地址项，每个地址项大小为4B，磁盘块大小为4KB，则单个文件的最大长度约为：A.4GBB.16GBC.32GBD.64GB参考答案：A解析：直接块可存储10×4KB=40KB，一级间接块可存储1024×4KB=4MB，二级间接块可存储1024×1024×4KB=4GB，总最大长度约为4GB。28.下列关于进程调度的说法正确的是：A.时间片轮转调度算法适用于批处理系统B.高响应比优先调度算法不利于短作业C.多级反馈队列调度算法能兼顾不同类型的作业D.先来先服务调度算法对短作业有利参考答案：C解析：时间片轮转适用于分时系统；高响应比优先兼顾长短作业；先来先服务对长作业有利。29.某系统有3个进程P1、P2、P3，资源类型为(A,B,C)，最大需求分别为P1(8,3,2)、P2(6,2,3)、P3(5,4,1)，已分配资源分别为P1(3,1,0)、P2(2,1,1)、P3(1,2,1)，剩余可用资源为(1,0,1)，则系统的安全序列是：A.P2→P1→P3B.P3→P2→P1C.P2→P3→P1D.不存在安全序列参考答案：D解析：剩余资源需求为P1(5,2,2)、P2(4,1,2)、P3(4,2,0)，可用资源(1,0,1)无法满足任何进程的需求，不存在安全序列。30.下列关于虚拟存储器的说法错误的是：A.虚拟存储器的容量由地址空间大小和辅存容量决定B.虚拟存储器利用了程序的局部性原理C.引入虚拟存储器后，程序员编程时需要考虑内存的容量限制D.缺页中断属于内部中断参考答案：C解析：虚拟存储器对程序员透明，编程时无需考虑内存容量限制。31.某文件系统采用连续分配方式，文件起始块号为100，块大小为4KB，访问文件偏移量26000字节处的数据，对应的磁盘块号是：A.104B.105C.106D.107参考答案：C解析：26000/4096≈6.35，对应逻辑块号为6，物理块号为100+6=106。32.下列设备中，属于独占设备的是：A.磁盘B.打印机C.键盘D.显示器参考答案：B解析：打印机同一时间只能被一个进程占用，属于独占设备。33.OSI参考模型中，负责端到端流量控制的层次是：A.网络层B.传输层C.数据链路层D.应用层参考答案：B解析：传输层负责端到端的流量控制、差错控制，数据链路层负责相邻节点间的流量控制。34.若某信道带宽为4kHz，信噪比为30dB，则该信道的最大数据传输率约为：A.4kbpsB.12kbpsC.40kbpsD.120kbps参考答案：C解析：30dB对应S/N=10^3=1000，根据香农公式C=4k×log2(1+1000)≈4k×10=40kbps。35.以太网的MAC地址长度是：A.32位B.48位C.64位D.128位参考答案：B36.下列IP地址中，属于私有地址的是：A.B.C.D.参考答案：C解析：私有地址范围为/8、/12、/16。37.TCP采用慢启动算法，初始拥塞窗口为1MSS，拥塞窗口阈值为16MSS，传输过程中无超时和3次重复确认，拥塞窗口达到10MSS时经过的RTT个数是：A.4B.5C.9D.10参考答案：A解析：慢启动阶段每个RTT拥塞窗口翻倍，1→2（1RTT）→4（2RTT）→8（3RTT）→16（4RTT），10MSS出现在第4个RTT内。38.下列路由协议中，属于链路状态路由协议的是：A.RIPB.OSPFC.BGPD.IGRP参考答案：B39.某HTTP请求报文的请求行是“GET/index.htmlHTTP/1.1”，下列说法错误的是：A.请求方法是GETB.请求的资源是/index.htmlC.使用的HTTP版本是1.1D.该请求建立TCP连接后，服务器返回响应立即释放连接参考答案：D解析：HTTP/1.1默认使用持久连接，不会立即释放TCP连接。40.下列关于DNS的说法正确的是：A.DNS使用TCP协议传输，端口号53B.DNS的作用是将IP地址转换为域名C.递归查询过程中，域名服务器需要代替客户端进行查询D.根域名服务器保存了所有二级域名服务器的IP地址参考答案：C解析：DNS默认使用UDP协议端口53，大报文时使用TCP；DNS主要作用是域名转IP；根域名服务器保存顶级域名服务器的IP地址。二、综合应用题（第41~47小题，共70分）41.（数据结构，10分）给定二叉树的先序遍历序列为{1,2,4,7,3,5,6,8}，中序遍历序列为{4,7,2,1,5,3,8,6}，要求：（1）画出该二叉树的结构（3分）（2）写出该二叉树的后序遍历序列（3分）（3）将该二叉树转换为对应的森林，画出森林结构（4分）参考答案：（1）二叉树结构：根节点为1，左孩子为2、右孩子为3；2的左孩子为4，4的右孩子为7；3的左孩子为5、右孩子为6；6的左孩子为8。（2）后序遍历序列：7、4、2、5、8、6、3、1（3）森林共2棵树：第一棵树根为1，子节点为2；2的子节点为4，4的子节点为7；第二棵树根为3，子节点为5、6；6的子节点为8。42.（数据结构，13分）给定长度为n的整数数组，元素可正、可负、可为0，要求找出数组中连续子数组的最大和，时间复杂度不高于O(n)。（1）描述算法核心思想（4分）（2）写出C语言实现代码（6分）（3）分析算法的时间复杂度和空间复杂度（3分）参考答案：（1）采用Kadane动态规划算法：定义变量`cur_max`表示以当前元素结尾的连续子数组的最大和，递推关系为`cur_max=max(当前元素,cur_max+当前元素)`，遍历过程中维护全局最大和`global_max`，每次更新`cur_max`后同步更新`global_max`，无需保存完整动态规划数组，空间可优化到O(1)。（2）代码实现：```cintmaxSubArray(int*nums,intnumsSize){if(numsSize==0)return0;intcur_max=nums[0];intglobal_max=nums[0];for(inti=1;i<numsSize;i++){cur_max=(nums[i]>cur_max+nums[i])?nums[i]:cur_max+nums[i];if(cur_max>global_max)global_max=cur_max;}returnglobal_max;}```（3）时间复杂度：仅遍历数组1次，为O(n)；空间复杂度：仅使用常数个额外变量，为O(1)。43.（计算机组成原理，12分）某计算机采用字节编址，虚拟地址32位，物理地址24位，页大小为4KB，TLB采用4路组相联映射，共16个表项，TLB访问时间为2ns，内存访问时间为20ns，缺页率为0.5%，缺页处理时间为10000ns，TLB命中率为95%。要求：（1）计算虚拟地址中虚拟页号、页内偏移的位数（2分）（2）计算TLB地址中标记、组索引的位数（4分）（3）计算地址翻译的有效访问时间（6分）参考答案：（1）页大小为4KB=2^12B，页内偏移占12位，虚拟页号位数为32-12=20位。（2）TLB共16个表项，4路组相联，组数为16/4=4=2^2，组索引占2位；标记位为虚拟页号减去组索引位数，即20-2=18位。（3）有效访问时间计算：TLB命中时访问时间=2ns+20ns=22nsTLB不命中但页在内存时访问时间=2ns+20ns（查页表）+20ns（访存）=42ns缺页时访问时间=2ns+20ns（查页表）+10000ns（缺页处理）+20ns（访存）=10042ns总有效访问时间=95%×22+(1-95%)×(1-0.5%)×42+(1-95%)×0.5%×10042≈25.5ns44.（计算机组成原理，11分）某程序核心代码如下，数组a、b均为int类型（int占4B），a起始地址为0x1000，b起始地址为0x3000，Cache采用直接映射，块大小为32B，Cache容量为1KB，初始为空。```cfor(inti=0;i<256;i++){a[i]=b[i]+1;}```要求：（1）计算数组a、b各自占用的Cache块数（3分）（2）计算程序执行过程中的Cache命中率（8分）参考答案：（1）每个数组大小为256×4B=1024B=1KB，块大小为32B，因此每个数组占用块数为1024B/32B=32块。（2）Cache容量为1KB，直接映射下共32块。a数组的块映射到Cache块0~31，b数组起始地址偏移0x2000=8KB，因此b数组的块也映射到Cache块0~31，同序号块发生冲突。每个块包含8个int元素，访问顺序为b[i]→a[i]：访问b[0]时不命中，块载入后b[1]~b[7]均命中；访问a[0]时不命中，替换对应Cache块后a[1]~a[7]均命中，以此类推。总访问次数为256×2=512次，不命中次数为32（b的块）+32（a的块）=64次，命中率=(512-64)/512=87.5%。45.（操作系统，8分）某系统采用请求分页存储管理，页大小为4KB，某进程的页表如下（有效位1表示页在内存）：页号有效位块号访问位修改位01101011231120-003150040-01（1）计算该逻辑地址对应的页号（2分）（2）说明需要置换的页号及原因（6分）参考答案：（1）页大小为4KB=0x1000，逻辑地址0x00004A7C的页号为0x4A7C>>12=0x4，对应页号4，有效位为0，触发缺页。（2）改进型Clock置换优先级为：(访问位0,修改位0)>(访问位0,修改位1)>(访问位1,修改位0)>(访问位1,修改位1)。当前内存中的页为0、1、3：页0属于第三优先级，页1属于第四优先级，页3属于第一优先级，因此置换页号3。46.（操作系统，7分）三个进程P1、P2、P3共享两个缓冲区B1、B2，B1最多存放3个产品，B2最多存放2个产