2025年计算机考研408真题深度解析

2025年计算机考研408真题深度解析考试时间：______分钟总分：______分姓名：______一、1.线性表采用链式存储结构时，其主要优点是（）。A.插入删除操作方便，但查找困难B.查找操作方便，但插入删除困难C.逻辑结构简单，物理结构复杂D.逻辑结构复杂，物理结构简单2.设栈S和队列Q的初始状态均为空，依次对栈S和队列Q进行以下操作：push(S,a),push(S,b),pop(S),enqueue(Q,a),push(S,c),dequeue(Q),pop(S),enqueue(Q,b)。执行完毕后，栈S中的元素是（）。A.a,bB.b,cC.cD.a,c3.已知一棵二叉树的先根遍历序列为ABCD，后根遍历序列为DCBA，则该二叉树根结点的右子树中的结点个数是（）。A.0B.1C.2D.34.在内部排序方法中，平均时间复杂度最低的是（）。A.冒泡排序B.选择排序C.插入排序D.快速排序5.已知一棵完全二叉树的结点个数为50，则在该二叉树中至少有（）个叶结点。A.25B.26C.12D.136.哈希表解决冲突的链地址法是将所有哈希地址为i的元素存储在（）。A.线性链表中B.哈希表中C.二叉树中D.索引表中7.采用顺序存储结构存储线性表时，删除第i个元素（1≤i≤n），需要向前移动（）个元素。A.iB.i-1C.n-iD.n-i+18.在下列数据结构中，适合表示稀疏矩阵的是（）。A.顺序表B.线性链表C.二叉树D.以上都不是9.在树形结构中，每个结点（除根结点）有且仅有一个直接前驱，每个结点（除叶子结点）有且仅有一个直接后继，这种结构称为（）。A.树B.二叉树C.图D.队列10.下列关于递归算法的说法中，错误的是（）。A.递归算法必须调用自身B.递归算法必须有终止条件C.递归算法可以提高程序的可读性D.递归算法执行效率一定高于非递归算法二、1.设计一个算法，判断给定的栈S是否为空。如果为空，返回True；否则，返回False。请用伪代码或C/C++/Java语言描述该算法。2.设计一个算法，将一个栈中的元素逆序。要求只能使用栈S本身以及一个辅助的栈T，不能使用其他数据结构。请用伪代码或C/C++/Java语言描述该算法。3.给定一个不含重复元素的整数数组arr，设计一个算法，找出数组中第三大的数，并返回该数。如果数组中的有效数字少于三个，则返回最大的数。请用伪代码或C/C++/Java语言描述该算法。4.已知一棵二叉搜索树，请设计一个算法，查找并返回树中值最大的结点。要求算法不能使用递归。5.请解释什么是二叉搜索树？简述在二叉搜索树中插入一个新结点的过程。三、1.假设有一个线性表L，采用顺序存储结构，存储空间为data[1..100]，当前长度为n（n≤100）。请设计一个算法，在L的第i个位置（1≤i≤n+1）插入一个新元素x。如果插入位置不合法（即i<1或i>n+1），则不进行插入。请用伪代码或C/C++/Java语言描述该算法，并分析该算法在最坏情况下的时间复杂度。2.请解释什么是队列？简述队列的“先进先出”特性。如果使用数组实现队列，如何避免“假溢出”问题？请简述方法并说明其原理。四、1.计算下列二叉树的深度（树的高度）。```A/\BC//\DEF```2.假设使用哈希函数H(key)=keymod11，将元素15,38,21,27,66,35依次存入一个哈希表（初始为空，采用链地址法解决冲突）。请画出最终的哈希表结构图。假设发生冲突时，新元素总是添加到链表的头部。五、1.在计算机中，数据最终是以二进制形式存储的。请简述将一个十进制数N（例如N=123）转换为二进制数的过程。2.什么是计算机的指令系统？简述指令格式通常包含哪些主要字段。六、1.CPU执行一条指令大致需要经过哪些主要阶段？请按顺序列出。2.什么是存储器的层次结构？为什么需要设计多级存储器层次结构？简述高速缓存（Cache）的作用。七、1.什么是操作系统？简述操作系统的基本功能（至少列举三项）。2.什么是进程？进程与程序有什么区别？简述进程的三种基本状态。八、1.简述IP地址的分类方法（A、B、C类）。每个类别的主要特点是什么？2.解释什么是ARP协议？它的主要功能是什么？九、1.在TCP协议中，三次握手过程是为了保证什么？请简述三次握手的步骤。2.什么是网络拥塞？简述TCP协议中常用的拥塞控制方法（至少列举两种）。十、1.请简述计算机硬件系统的基本组成（至少包括CPU、存储器、输入设备、输出设备等主要部件）。2.什么是总线？简述总线在计算机系统中的作用。---试卷答案一、1.A2.B3.C4.D5.D6.A7.C8.B9.A10.D二、1.functionisEmpty(S)://栈为空的条件是栈顶指针指向存储空间的起始位置或-1ifS.top==-1:returnTrueelse:returnFalse2.functionreverseStack(S,T)://辅助栈T用于存放逆序元素whilenotisEmpty(S):x=pop(S)push(T,x)//将辅助栈T的元素重新放回栈SwhilenotisEmpty(T):x=pop(T)push(S,x)3.functionthirdLargest(arr):first=second=third=-infinityforifrom0tolength(arr)-1:ifarr[i]>first:third=secondsecond=firstfirst=arr[i]elseifarr[i]>secondandarr[i]<first:third=secondsecond=arr[i]elseifarr[i]>thirdandarr[i]<second:third=arr[i]ifthird==-infinity://如果第三大的数不存在returnfirstelse:returnthird4.functionfindMaxNode(root):current=rootmaxNode=nullwhilecurrent!=null:ifmaxNode==nullorcurrent.data>maxNode.data:maxNode=current//如果是右子树，向右遍历ifcurrent.right!=null:current=current.rightelse:breakreturnmaxNode//或者非递归查找最大值也可以从根开始一直向右子树走//functionfindMaxNodeIterative(root)://ifroot==null://returnnull//whileroot.right!=null://root=root.right//returnroot5.二叉搜索树（BST）是一种特殊的二叉树，满足对于树中的任何一个结点，其左子树上所有结点的值均小于它的根结点的值，其右子树上所有结点的值均大于它的根结点的值，并且它的左、右子树也都是二叉搜索树。插入过程：1.如果树为空，新结点成为根结点。2.如果树非空，将新结点与根结点比较。3.如果新结点值小于根结点值，去左子树继续比较；如果大于，去右子树继续比较。4.重复步骤3，直到找到一个空位置，将新结点插入为叶子结点。三、1.functioninsertInOrder(L,i,x):ifi<1ori>length(L)+1://插入位置不合法return//申请新空间存放新元素L.rear=L.rear+1//从最后一个元素开始，向后移动元素j=length(L)whilej>=i:L[j]=L[j-1]j=j-1//在第i个位置插入新元素xL[i-1]=x//长度增加1L.length=L.length+1//最坏情况时间复杂度：i=1，需要移动n个元素，为O(n)2.队列是一种先进先出（FIFO）的线性数据结构。其特性是先入队的元素先出队。使用数组实现队列时，会遇到数组空间用尽但前面有已出队元素占用的“假溢出”问题。解决方法：1.循环队列：将数组首尾相连，出队时头指针加一（模数组长度），入队时尾指针加一（模数组长度）。原理：利用模运算使指针在到达数组末尾时“绕回”数组开头，继续使用未使用的空间。2.动态数组：当数组满时，创建一个更大的数组，将旧数组中的元素复制到新数组中，并更新头尾指针。四、1.该二叉树的深度是从根结点到最远叶子结点的路径长度。路径：A->B->D(深度3)，A->C->E(深度3)，A->C->F(深度3)。最远叶子结点为D、E、F，深度均为3。所以该二叉树的深度为3。2.哈希函数H(key)=keymod11，链地址法。-15mod11=4->[15]-38mod11=5->[38]-21mod11=10->[21]-27mod11=5->在地址5处链入[38,27]-66mod11=0->[66]-35mod11=2->[35]最终哈希表结构（假设哈希表大小为11，用数组表示，空位用null或特殊标记表示）：地址:0:[66]1:null2:[35]3:null4:[15]5:[38,27]6:null7:null8:null9:null10:[21]五、1.十进制转二进制：不断除以2，记录余数，逆序排列余数序列。123/2=61余1；61/2=30余1；30/2=15余0；15/2=7余1；7/2=3余1；3/2=1余1；1/2=0余1。逆序排列余数：1111011。所以123的二进制表示为1111011。2.指令系统是计算机能够识别和执行的指令集合，是计算机硬件能够直接执行的操作命令的规格说明。指令格式通常包含：操作码字段（指定指令要执行的操作，如加、减、传送、跳转等）、地址码字段（指定操作数的位置，可以是寄存器编号、内存地址或地址偏移量等）。六、1.CPU执行一条指令通常经过以下主要阶段：取指阶段（Fetch）：从内存中读取下一条指令；译码阶段（Decode）：分析指令的操作码和地址码，确定要执行的操作和操作数地址；执行阶段（Execute）：执行指令规定的操作（如进行运算、数据传送、控制转移等）；访存阶段（MemoryAccess）：如果指令需要访问内存，则在此阶段读取或写入数据；写回阶段（Writeback）：将执行结果写回到寄存器或内存中。2.存储器层次结构是为了解决CPU速度与内存速度不匹配、内存成本与容量之间的矛盾而设计的。原因：高速缓存（Cache）比主存速度快但容量小、成本高；主存比辅存（如硬盘）速度快但容量小、成本高。通过层次结构，用小容量、高速、高成本的存储器存放频繁使用的程序和数据，用大容量、低速、低成本的存储器存放不常用的程序和数据，折中成本和性能。高速缓存（Cache）的作用是作为CPU和主存之间的缓冲，存储CPU近期最可能访问的数据副本，当CPU需要某数据时，首先在Cache中查找，如果命中（Hit），则直接从Cache获取（速度极快），如果未命中（Miss），则再去主存中获取数据，并可能将数据调入Cache。七、1.操作系统（OS）是一段控制和管理计算机硬件与软件资源的系统软件，并为用户和应用程序提供方便、有效、安全的工作环境。基本功能包括：进程管理（创建、调度、终止进程，处理进程间通信与同步）、内存管理（分配和回收内存空间，实现内存保护与共享）、文件管理（负责文件的创建、删除、读写、目录管理）、设备管理（管理输入输出设备，提供设备驱动程序和接口）、提供用户接口（命令接口、图形接口）。2.进程是计算机系统中正在运行的程序的一个实例。程序是静态的代码，进程是动态的执行过程，具有状态（创建、就绪、运行、阻塞、终止）、拥有资源（CPU时间、内存、I/O设备等）、可以被调度执行。进程与程序的区别：程序是静态的，进程是动态的；程序是存储在磁盘上的文件，进程是内存中的数据结构。进程的基本状态：运行态（正在占用CPU执行）、就绪态（准备好执行，等待CPU分配）、阻塞态（因等待某个事件发生而暂停执行，如等待I/O完成）。八、1.IP地址分类方法基于网络规模和地址结构。A类地址：网络号占8位，主机号占24位。特点：适用于大型网络，全球范围的网络号很少。B类地址：网络号占16位，主机号占16位。特点：适用于中型网络，适用于组织内部网络。C类地址：网络号占24位，主机号占8位。特点：适用于小型网络，如局域网。还有D类（多播）和E类（保留）地址。2.ARP（AddressResolutionProtocol，地址解析协议）运行在数据链路层。它的主要功能是根据已知的IP地址找到对应的物理地址（MAC地址），以便在局域网内正确传输数据帧。当一台主机需要向另一台位于同一网络段的主机发送数据时，它知道对方的IP地址，但不知道对方的MAC地址，此时就需要使用ARP协议查询ARP表或向网络中的所有主机广播ARP请求，获取目标IP地址对应的MAC地址后，才能将数据帧封装好，通过以太网等局域网技术发送出去。九、1.TCP（TransmissionControlProtocol）的三次握手是为了确保客户端和服务器双方都确认了彼此的连接请求和接收能力，建立可靠的连接。步骤：1.SYN：客户端发送一个SYN（Synchronize）报文段给服务器，请求建立连接，SYN标志位为1，包含初始序列号seq=x。2.SYN-ACK：服务器收到SYN报文后，如果同意连接，回复一个SYN-ACK报文段，ACK（Acknowledgment）标志位为1，确认号为ack=x+1，SYN标志位为1，包含初始序列号seq=y。3.ACK：客户端收到SYN-ACK报文后，发送一个ACK报文段给服务器，ACK标志位为1，确认号为ack=y+1，SYN标志位为0。服务器收到此ACK报文后，连接建立成功。这三次握手确保了双方都知晓对方的存在，并且双方的初始序列号都得到了确认。2.网络拥塞是指当网络中的数据流量超过了网络链路或节点的处理能力时，导致数据传输效率下降、延迟增加、丢包率升高等现象。TCP协议中常用的拥塞控制方法：1.