2026年计算机类试题(附答案)

2026年计算机类试题(附答案)一、单项选择题（本大题共40小题，每小题2分，共80分）1.下列关于大端和小端存储方式的描述中，正确的是（）A.大端模式下，数据的低字节存放在内存的低地址，高字节存放在高地址B.小端模式下，ARM架构默认采用小端存储，X86架构默认采用大端存储C.对于32位数据0x12345678，若起始地址为0x0000，小端模式下地址0x0003存放的数据是0x12D.网络协议传输数据时默认采用小端模式，因此主机需要进行字节序转换2.下列关于栈和队列的描述中，错误的是（）A.栈和队列都属于线性存储结构，都可以采用顺序存储和链式存储两种实现方式B.若一个栈的输入序列为1、2、3、4、5，则不可能得到输出序列3、1、2、4、5C.循环队列判断队空的条件是(rear+1)%MaxSize==front，队满的条件是rear==frontD.栈的出栈操作时间复杂度为O(1)，链式队列的出队操作时间复杂度为O(1)3.某系统采用分页存储管理，页大小为4KB，页表项大小为4字节，采用一级页表，逻辑地址空间大小为2^32，则进程的页表占用的物理内存大小为（）A.4MBB.8MBC.16MBD.32MB4.下列关于TCP和UDP协议的描述中，正确的是（）A.TCP是面向无连接的，UDP是面向连接的B.TCP提供可靠的字节流传输，UDP提供不可靠的数据报传输C.TCP和UDP都使用端口号区分应用层进程，端口号范围都是0~1023为熟知端口，1024~65535都可自由使用D.TCP的拥塞控制采用慢启动、拥塞避免、快速转发三种机制5.若一棵二叉树的前序遍历序列为a、b、d、e、c、f、g，中序遍历序列为d、b、e、a、f、c、g，则该二叉树的后序遍历序列为（）A.d、e、b、f、g、c、aB.d、e、f、g、b、c、aC.d、e、b、f、g、a、cD.e、d、b、g、f、c、a6.某CPU主频为2GHz，采用四级指令流水线，每个流水段的延迟分别是200ps、300ps、200ps、100ps，不考虑流水线阻塞和转发，则完成1000条指令的实际吞吐率为（）A.约2.5×10^9条/秒B.约3.3×10^9条/秒C.约5×10^9条/秒D.约6.7×10^9条/秒7.下列排序算法中，平均时间复杂度为O(nlogn)，且空间复杂度为O(1)的是（）A.快速排序B.堆排序C.归并排序D.希尔排序8.下列关于进程和线程的描述中，正确的是（）A.进程是操作系统资源分配的基本单位，线程是调度的基本单位B.同一进程内的多个线程共享进程的地址空间，不共享堆和栈段C.进程上下文切换比线程上下文切换的开销更小D.多进程并发一定比多线程并发的执行效率更高9.在OSI七层参考模型中，负责路由选择和异构网络互连的层次是（）A.数据链路层B.网络层C.传输层D.应用层10.已知一棵平衡二叉树（AVL树）的结点总数为15，则该树的最小高度为（根节点在第1层）（）A.3B.4C.5D.611.某存储系统中，主存容量是Cache容量的128倍，Cache采用直接映射方式，主存地址为18位，则Cache标记字段的位数是（）A.6B.7C.11D.1212.下列磁盘调度算法中，会产生饥饿问题的是（）A.FCFS调度B.SCAN调度C.CSCAN调度D.SSTF调度13.以太网使用的CSMA/CD机制中，冲突检测的最大等待时间是（）A.传播时延B.传播时延的一半C.两倍传播时延D.四倍传播时延14.下列关于哈希查找的描述中，正确的是（）A.哈希查找的时间复杂度为O(1)，与装填因子无关B.线性探测法解决冲突时，装填因子越大，查找效率越高C.链地址法解决冲突时，不会出现聚集问题D.哈希函数的选取原则是尽可能减少冲突概率15.下列指令中，一定不会发生控制冒险的是（）A.跳转指令B.调用指令C.返回指令D.加法指令二、简答题（本大题共5小题，每小题10分，共50分）1.请简述快表（TLB）在分页存储管理中的作用，说明快表未命中时地址变换的完整过程。2.已知一个有序顺序表存储了n个整数，请设计一个时间复杂度低于O(n)的算法，找出表中值等于目标值k的元素的下标，若不存在则返回-1，写出算法思想和核心代码（不限编程语言），分析时间复杂度。3.请简述TCP三次握手建立连接的过程，说明为什么三次握手不能简化为两次握手。4.请说明指令寻址和数据寻址的区别，列举三种常见的数据寻址方式并说明其特点。5.请简述银行家算法的基本思想，说明银行家算法能够避免死锁的原因。三、综合应用题（本大题共3小题，共70分）1.（22分）设一棵无向带权图G的顶点集为V={v1,v2,v3,v4,v5,v6}，邻接矩阵如下（A[i][j]表示顶点vi到vj的权值，不存在边时为∞）：A=[[0,6,1,5,∞,∞],[6,0,5,∞,3,∞],[1,5,0,∞,∞,4],[5,∞,∞,0,2,1],[∞,3,∞,2,0,∞],[∞,∞,4,1,∞,0]]请回答下列问题：（1）画出该图的邻接表存储结构；（6分）（2）分别给出从v1出发的深度优先遍历（DFS）和广度优先遍历（BFS）的顶点序列（假设访问邻接点按顶点编号从小到大选择）；（6分）（3）分别用Prim算法（从v1开始构造）和Kruskal算法构造该图的最小生成树，给出构造过程，画出最终的最小生成树，计算最小生成树的总权值。（10分）2.（24分）某计算机主存地址空间大小为1GB，按字节编址，数据Cache容量为32KB，Cache行大小为64B，采用四路组相联映射，替换算法为LRU，写回策略，回答下列问题：（1）主存地址分为三个字段，分别计算三个字段的位数，说明每个字段的含义；（8分）（2）计算数据Cache总共需要多少位存储容量来标记和替换管理（不包含数据区的容量）；（6分）（3）若CPU依次访问以下地址：0x000080、0x000088、0x000180、0x000188、0x000280，说明每次访问后Cache的命中情况，若不命中请说明调入后的组内分配情况（假设初始时Cache为空）。（10分）3.（24分）设某系统共有5个进程P0、P1、P2、P3、P4，三类资源A、B、C，当前系统的资源分配情况如下表所示：进程已分配资源（A,B,C）最大需求资源（A,B,C）可用资源（A,B,C）P0(0,1,0)(7,5,3)(3,3,2)P1(2,0,0)(3,2,2)P2(3,0,2)(9,0,2)P3(2,1,1)(2,2,2)P4(0,0,2)(4,3,3)（1）计算每个进程的剩余需求资源，说明当前系统是否处于安全状态，如果是，给出一个安全序列；（12分）（2）若进程P1此时发起请求，请求资源为(1,0,2)，按照银行家算法，判断系统能否分配资源给P1，说明理由；（6分）（3）若进程P4此时发起请求，请求资源为(3,3,0)，判断系统能否分配，说明理由。（6分）参考答案及解析一、单项选择题答案与解析1.答案：C解析：大端模式的规则是数据的高字节存放在内存低地址，低字节存放在高地址，小端模式与之相反，因此A选项错误；X86架构和ARM架构默认都采用小端存储，因此B选项错误；32位数据0x12345678，小端模式下地址从低到高依次存放0x78、0x56、0x34、0x12，起始地址为0x0000，因此地址0x0003存放的数据是0x12，C选项正确；网络协议传输默认采用大端模式（网络字节序），因此主机字节序与网络字节序不同时需要进行字节序转换，D选项错误。2.答案：C解析：栈和队列都是操作受限的线性表，都支持顺序存储和链式存储两种实现方式，A选项正确；输出序列3出栈时，栈内从栈底到栈顶依次为1、2，3出栈后下一个出栈的元素只能是2，不可能是1，因此无法得到输出序列3、1、2、4、5，B选项正确；循环队列通常牺牲一个存储单元区分队空和队满，队空的条件是`rear==front`，队满的条件是`(rear+1)%MaxSize==front`，选项描述颠倒，因此C选项错误，符合题意；栈的出栈操作仅修改栈顶指针，链式队列的出队操作仅修改队头指针，时间复杂度都为O(1)，D选项正确。3.答案：A解析：页大小为4KB=2^12B，因此页内偏移占12位，逻辑地址空间大小为2^32，因此页号占32-12=20位，页表项总个数为2^20个，每个页表项大小为4字节，因此页表总大小为2^20×4B=4MB，因此A选项正确。4.答案：B解析：TCP是面向连接的传输层协议，UDP是无连接的，A选项错误；TCP通过确认、重传、流量控制等机制保证可靠的字节流传输，UDP不保证可靠交付，仅提供尽最大努力交付的不可靠数据报服务，B选项正确；端口号划分中，0~1023为熟知端口，1024~49151为登记端口，49152~65535为动态/私有端口，不是所有1024以上端口都可自由使用，C选项错误；TCP拥塞控制包括慢启动、拥塞避免、快速重传、快速恢复四种核心机制，没有快速转发，D选项错误。5.答案：A解析：根据前序遍历根-左-右的顺序，第一个节点为根节点，因此根节点为a；根据中序遍历左-根-右的顺序，根节点a左侧的d、b、e为左子树节点，右侧的f、c、g为右子树节点；左子树的前序第一个节点为b，因此左子树根为b，d在b左侧，e在b右侧；同理右子树根为c，f在c左侧，g在c右侧；后序遍历顺序为左-右-根，遍历结果为d、e、b、f、g、c、a，因此A选项正确。6.答案：B解析：非均匀流水线的周期由最慢的流水段决定，本题中四个流水段的最大延迟为300ps，因此流水线周期Δt=300×10^-12s；完成n条指令的总时间为`(k+n-1)Δt`，其中k为流水段数，本题k=4，n=1000，总时间T=(4+1000-1)×300e-12=3.009×10^-7s；吞吐率TP=n/T=1000/(3.009×10^-7)≈3.3×10^9条/秒，因此B选项正确。7.答案：B解析：快速排序平均时间复杂度为O(nlogn)，最坏为O(n²)，空间复杂度为O(logn)，不符合要求；堆排序平均和最坏时间复杂度都是O(nlogn)，空间复杂度为O(1)，符合要求；归并排序时间复杂度为O(nlogn)，空间复杂度为O(n)，不符合要求；希尔排序平均时间复杂度约为O(n^1.3)，不符合要求，因此B选项正确。8.答案：A解析：进程是操作系统资源分配的基本单位，线程是CPU调度的基本单位，A选项正确；同一进程内的多个线程共享进程的代码段、数据段、堆空间，每个线程有独立的栈空间，因此B选项错误；进程切换需要切换地址空间、保存更多上下文，开销比线程切换大，C选项错误；多线程并发因为切换开销小、共享地址空间通信效率高，通常在IO密集型场景下比多进程效率更高，D选项错误。9.答案：B解析：OSI七层模型中，数据链路层负责相邻节点之间的帧传输，网络层负责路由选择和异构网络互连，传输层负责端到端的通信，应用层为用户提供应用服务，因此B选项正确。10.答案：B解析：平衡二叉树的高度h和最少结点数n(h)满足关系n(h)=n(h-1)+n(h-2)+1，初始条件n(0)=0，n(1)=1，计算得n(1)=1，n(2)=2，n(3)=4，n(4)=7，n(5)=12，因此高度为4时最少结点数为7，最多结点数为2^4-1=15，结点总数为15时最小高度为4，因此B选项正确。11.答案：B解析：主存容量是Cache的128倍，即2^7倍，直接映射中标记字段的位数等于主存地址位数减去Cache地址位数，主存地址18位，因此标记字段为7位，B选项正确。12.答案：D解析：SSTF（最短寻道时间优先）调度算法总是优先处理离当前磁头最近的请求，可能导致远离磁头的请求长期得不到服务，产生饥饿问题，因此D选项正确。13.答案：C解析：CSMA/CD中，信号从一端传输到另一端需要一个传播时延，若发送端在发送数据后经过两倍传播时延仍未检测到冲突，就说明数据成功发送，因此冲突检测的最大等待时间是两倍传播时延，C选项正确。14.答案：D解析：哈希查找的时间复杂度和装填因子直接相关，装填因子越大冲突概率越高，查找效率越低，A、B选项错误；线性探测法会产生聚集问题，链地址法也会出现多个元素映射到同一链表的聚集问题，只是概率更低，C选项错误；哈希函数选取的核心原则是尽可能让关键字散列均匀，减少冲突概率，D选项正确。15.答案：D解析：控制冒险是指指令跳转导致流水线预取的指令错误，跳转、调用、返回指令都会改变程序计数器的值，产生控制冒险，加法指令是顺序执行的普通运算指令，不会产生控制冒险，因此D选项正确。二、简答题参考答案1.答：快表（TLB，翻译后备缓冲器）是集成在CPU中的高速专用存储单元，用于缓存进程最近访问过的页表项，作用是减少地址变换过程中访问内存的次数，降低地址变换的时间开销，解决分页存储管理中多级页表访存次数多导致的性能下降问题。（4分）快表未命中时的地址变换过程：①CPU生成逻辑地址，拆分得到页号和页内偏移，查询快表中对应页号的页表项，未找到匹配项；②按页表映射规则从内存中读取对应页表项，得到物理页号；③将新读取的页表项写入快表，若快表已满则根据预设替换算法淘汰一个旧的页表项；④用物理页号拼接页内偏移得到最终物理地址，访问主存对应单元。（6分）2.答：有序数组查找目标值，要求时间复杂度低于O(n)，可采用二分查找算法，算法思想：①初始化查找区间左右边界low=0，high=n-1；②每次取区间中点mid=low+(high-low)/2，避免整数溢出，比较中点元素与目标值k；③若中点元素等于k，返回mid；若中点元素大于k，说明目标在左半区间，更新high=mid-1；若中点元素小于k，说明目标在右半区间，更新low=mid+1；④当low>high时退出循环，说明不存在目标值，返回-1。（3分）核心代码（C语言描述）：```cintbinarySearch(intarr[],intn,intk){intlow=0,high=n-1;while(low<=high){intmid=low+(high-low)/2;if(arr[mid]==k)returnmid;elseif(arr[mid]>k)high=mid-1;elselow=mid+1;}return-1;}```（4分）时间复杂度分析：每次查找都会将查找区间缩小一半，最多查找log2(n)次即可结束查找，因此时间复杂度为O(logn)，满足低于O(n)的要求。（3分）3.答：TCP三次握手建立连接的过程：①第一次握手：客户端发送SYN报文（SYN=1，序号seq=x），客户端进入SYN_SENT状态，等待服务器确认；②第二次握手：服务器收到客户端的SYN报文，确认客户端的连接请求（确认号ack=x+1），同时发送自身的SYN报文（SYN=1，序号seq=y），此时报文SYN和ACK都置1，服务器进入SYN_RCVD状态；③第三次握手：客户端收到服务器的SYN+ACK报文，向服务器发送确认报文（ACK=1，ack=y+1），客户端和服务器都进入ESTABLISHED状态，连接建立完成。（6分）不能简化为两次握手的原因：两次握手无法防止过期的连接请求报文导致服务器错误建立连接，浪费资源。例如：客户端发送的第一个连接请求报文因网络延迟滞留，直到连接释放后才到达服务器，若采用两次握手，服务器收到失效SYN报文后会直接建立连接，客户端不会响应也不会发送数据，服务器会一直空等浪费资源；三次握手情况下，服务器发送SYN+ACK后收不到客户端的确认，就会判断连接未建立，回收资源，不会造成浪费。（4分）4.答：指令寻址是确定下一条要执行的指令的地址，数据寻址是确定指令所需操作数的有效地址，二者寻址的对象不同。（3分）三种常见数据寻址方式及特点：①立即寻址：操作数直接存放在指令的地址字段中，不需要访问内存，执行速度快，只能用于小常量操作；（2分）②直接寻址：地址字段存放操作数的有效地址，直接根据地址访问内存，寻址过程简单，不需要计算，但是地址空间受限，不能访问大空间；（2分）③间接寻址：地址字段存放操作数有效地址所在的存储单元地址，需要两次访问内存，寻址范围大，支持多指针操作，但是速度慢。（3分）5.答：银行家算法的基本思想：系统预先保存所有进程的资源分配信息，每次进程发起资源请求时，先判断该请求是否合法，再试探性分配资源，之后检测分配后系统是否存在安全序列，若存在则分配资源，若不存在则拒绝分配，让进程等待。（4分）银行家算法避免死锁的核心原因：死锁产生的四个必要条件之一是循环等待，银行家算法保证分配资源后系统始终存在至少一个安全序列，即所有进程都可以按安全序列的顺序顺利完成，不会出现所有进程都占有资源且等待其他进程释放资源的循环等待状态，因此可以避免死锁。（6分）三、综合应用题参考答案1.（1）邻接表存储结构：每个顶点对应一个单链表，存储该顶点的所有邻接边，结构如下（表头结点按v1到v6顺序排列）：v1->(v2,6)->(v3,1)->(v4,5)->^v2->(v1,6)->(v3,5)->(v5,3)->^v3->(v1,1)->(v2,5)->(v6,4)->^v4->(v1,5)->(v5,2)->(v6,1)->^v5->(v2,3)->(v4,2)->^v6->(v3,4)->(v4,1)->^（6分，结构正确即可得分）（2）DFS序列：v1→v2→v3→v5→v4→v6；BFS序列：v1→v2→v3→v4→v5→v6。（6分）（3）Prim算法构造过程：从v1出发，初始顶点集合U={v1}，每次选U到V-U的最小权边：①最小边为v1-v3，权1，加入U，U={v1,v3}，总权=1；②最小边为v3-v6，权4，加入U，U={v1,v3,v6}，总权=1+4=5；③最小边为v6-v4，权1，加入U，U={v1,v3,v6,v4}，总权=5+1=6；④最小边为v4-v5，权2，加入U，U={v1,v3,v6,v4,v5}，总权=6+2=8；⑤最小边为v5-v2，权3，加入U，所有顶点加入完成，总权=8+3=11。Kruskal算法构造过程：按权从小到大依次选边，不构成环则保留：①权1的边v1-v3、v4-v6，都不构成环，保留，总权=1+1=2；②权2的边v4-v5，不构成环，保留，总权=2+2=4；③权3的边v2-v5，不构成环，保留，总权=4+3=7；④权4的边v3-v6，不构成环，保留，总权=7+4=11，所有顶点连通，构造完成。最终最小生成树总权值为11，结构为v1-v3-v6-v4-v5-v2。（10分）2.（1）主存地址空间1GB=2^30B，按字节编址，主存地址共30位；Cache容量32KB=2^15B，Cache行大小64B=2^6B，因此块内偏移占6位，用于表示Cache行内的字节地址；Cache行数=32KB/64B=512=2^9行，四路组相联，组数=512/4=128=2^7组，因此组号占7位，用于标记数据映射到Cache的组号；标记位位数=30-7-6=17位，用于标记当前Cache行存放的主存块编号。（8分）（2）每个Cache行需要17位标记+1位有效位+1位脏位（写回法需要脏位），共19位；每组4行，LRU替换需要log2(4)=2位记录替换信息，共128组；总存储容量=128组×4行×19位+128组×2位=9728+256=9984位。（6分）（3）