2026年全国硕士研究生招生考试真题练习卷

2026年全国硕士研究生招生考试真题练习卷一、单项选择题：下列每题给出的四个选项中，只有一个选项是符合题目要求的。请在答题卡上将所选项的字母涂黑。1.若算法的时间复杂度为O(A.执行时间等于B.执行时间与同阶C.问题规模最大为D.执行时间必小于c(c为常数)2.设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s4,s3,s6,s5,s1，则栈的容量至少应该是（）。A.2B.3C.4D.53.在单链表中，已知指针p指向某结点，若要在p之后插入一个由指针s指向的新结点，则需要执行的语句序列是（）。A.p->next=s;s->next=p->next;B.s->next=p->next;p->next=s;C.p->next=s->next;p->next=s;D.s->next=p;p->next=s;4.循环队列存储在数组A[0..m]中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)5.一棵完全二叉树有1001个结点，其叶子结点的个数是（）。A.500B.501C.251D.2506.在一棵非空二叉树的中序遍历序列中，根结点的右边（）。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的所有结点D.只有左子树上的部分结点7.在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A.1/2B.1C.2D.48.用邻接表表示图进行广度优先遍历时，通常借助的辅助数据结构是（）。A.栈B.队列C.树D.图9.在最坏情况下，下列排序算法中时间复杂度最低的是（）。A.冒泡排序B.简单选择排序C.直接插入排序D.快速排序10.对线性表进行二分查找时，要求线性表必须（）。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储且元素有序D.以链接方式存储且元素有序11.设哈希表长为14，哈希函数H(A.2B.8C.3D.1012.以下数据结构中，（）是非线性数据结构。A.树B.字符串C.队列D.栈13.某二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，其前序遍历序列为（）。A.CEDBAB.ACBEDC.DECABD.DEABC14.在一个无向图中，若两个顶点之间有路径相连，则称这两个顶点是（）。A.稀疏的B.密度的C.连通的D.强连通的15.快速排序在最坏情况下的时间复杂度为（）。A.OB.OC.OD.O16.串是一种特殊的线性表，其特殊性体现在（）。A.数据元素是一个字符B.数据元素可以是多个字符C.数据元素不可相同D.数据元素必须有序17.对于哈希表，解决冲突的常用方法不包括（）。A.开放定址法B.链地址法C.再哈希法D.广度优先搜索法18.已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为（）。A.CBEFDAB.CBAEDFC.ABEDCFD.CBEDFA19.在有序表{12,18,24,35,47,50,62,83,90}中，用二分查找法查找值90，需要比较的次数为（）。A.2B.3C.4D.520.设有一个最小堆（小根堆），其存储在数组中为{10,15,30,40,50,100,40}，现在插入元素8，调整后的数组可能为（）。A.{8,10,30,15,50,100,40,40}B.{8,15,10,40,50,100,40,30}C.{8,10,15,40,50,100,40,30}D.{10,8,30,40,50,100,40,15}二、综合应用题41.(10分)设顺序表L中的元素递增有序。试设计一个算法，删除顺序表中所有值介于mink与maxk之间的元素（mink和maxk为给定参数，且mink<maxk），并释放被删结点的空间。注意：mink和maxk可能不存在于表中，或者部分存在。要求算法的时间复杂度为O(n)42.(15分)已知一棵二叉树采用二叉链表存储，结点结构为(lchild,data,rchild)。设计一个算法，求该二叉树中值为x的结点所在的层数（根结点为第1层）。若不存在值为x的结点，则返回0。要求使用递归或非递归方式均可，但需注明时间复杂度。43.(15分)某带权有向图G采用邻接矩阵存储，矩阵元素A[i][j]表示顶点i到顶点j的边的权值，若不存在边则为∈f44.(10分)设散列表的长度为13，散列函数为H((1)试画出采用线性探测再散列解决冲突时的散列表。(2)计算在等概率查找情况下的平均查找长度（ASL）。45.(11分)已知序列{503,087,512,061,908,170,897,275,653,426}。(1)请给出利用堆排序建立初始堆（大根堆）的过程。(2)请给出进行一趟堆排序（输出堆顶元素并将剩余元素调整为新堆）后的序列状态。三、参考答案及解析一、单项选择题1.答案：B解析：大O记号描述的是算法执行时间的上界，表示随着问题规模n的增大，算法执行时间的增长趋势与同阶。它并不表示具体的执行时间，也不涉及具体的常数c或具体的最大规模。2.答案：B解析：模拟进出栈过程：s1进(栈:s1)s2进(栈:s1,s2)s2出(栈:s1)->输出s2s3进(栈:s1,s3)s4进(栈:s1,s3,s4)s4出(栈:s1,s3)->输出s4s3出(栈:s1)->输出s3s5进(栈:s1,s5)s6进(栈:s1,s5,s6)s6出(栈:s1,s5)->输出s6s5出(栈:s1)->输出s5s1出(栈:空)->输出s1过程中栈中元素最多达到3个（如s1,s3,s4），故容量至少为3。3.答案：B解析：在单链表中p之后插入s，需要先将s的next指向p的next（即s->next=p->next），然后将p的next指向s（即p->next=s）。顺序不能颠倒，否则会丢失p原来的后继结点。4.答案：D解析：循环队列通常少用一个空间来区分队空和队满，或者使用tag标记。若数组大小为m+1（即下标0到m），则模运算的基数应为m+1。通常定义队尾指针rear指向队尾元素的下一个位置，入队操作为rear=(rear+1)%(m+1)。5.答案：B解析：设完全二叉树结点数为n，叶子结点数为，度为2的结点数为，度为1的结点数为。对于完全二叉树，只能为0或1。性质：=+n=代入n=1001：若=0，则1001若=1，则1001故叶子结点个数为501。6.答案：A解析：中序遍历的顺序是：左子树->根->右子树。因此，在中序序列中，根结点右边的所有结点都属于其右子树（假设无重复值）。7.答案：C解析：在无向图中，每条边连接两个顶点，因此每条边会给这两个顶点的度数各贡献1。所以所有顶点的度数之和等于边数的2倍。8.答案：B解析：广度优先搜索（BFS）是按层遍历图的，需要先进先出（FIFO）的数据结构来保存当前层的邻居结点，以便按顺序访问下一层，因此通常使用队列作为辅助结构。深度优先搜索（DFS）才使用栈。9.答案：D解析：冒泡排序：最坏O简单选择排序：最坏O直接插入排序：最坏O快速排序：最坏O()（当基本有序时），但平均题目中问的是“时间复杂度最低”，这通常考察平均性能或渐进性能的比较。但在最坏情况下，前三者严格为O()。如果题目隐含考察平均性能，D是最佳。若严格考察最坏情况，D也是O()。但在考研语境下，常考察算法的综合性能对比，或者题目意图是考察快速排序在一般情况下优于其他修正思路：题目可能意在考察堆排序或归并排序（O(nlog另一种可能：题目考察的是希尔排序或堆排序，但选项没给。再读题：选项D是快速排序。在考研真题中，常出现“快速排序是目前基于比较的排序中平均性能最好的”。如果题目强调“最坏情况下”，D也是O(然而，仔细对比，如果这是一道严谨的题目，且没有堆排序/归并排序，可能题目有瑕疵。但在单选题中，必须选一个。通常快速排序被视为优于冒泡、选择和插入。注：如果题目选项中包含堆排序或归并排序，应选之。此处只能选D。10.答案：C解析：二分查找要求元素必须有序，且由于需要随机访问中间位置的元素，因此必须支持随机存取，即顺序存储结构。链表无法高效地进行随机访问。11.答案：A解析：H(地址1已被占用。线性探测：H(检查地址2，题目说已有4个结点在1,5,6,7，地址2空闲。故插入地址为2。12.答案：A解析：线性数据结构包括数组、链表、栈、队列、字符串等。树是一种层次结构，一个结点可以对应多个后继，属于非线性数据结构。13.答案：A解析：后序：DABEC（左右根）->根是C中序：DEBAC（左根右）->根是C结合：C是根。中序中C左边是DEBA，右边为空。说明右子树为空。后序中DABE是左子树部分。对左子树：后序片段：DABE->根是E中序片段：DEBA->根是E结合：E是左子树的根。中序中E左边是D，右边是BA。后序中DAB对应D(左)和BA(右)。对E的右子树（中序BA，后序BA）：后序BA->根A中序BA->根A结合：A是根。中序A左边B，右边空。结构还原：Root(C)>Left(ChildE)>Left(ChildD)>Right(ChildA)>Left(ChildB)前序遍历（根左右）：C->E->D->A->B。序列为CEDAB。选项A符合。14.答案：C解析：在无向图中，若顶点v到顶点u有路径，则称v和u是连通的。对于有向图，称为可达。强连通通常用于有向图。15.答案：C解析：快速排序的最坏情况发生在待排序序列基本有序（正序或逆序）时，此时划分操作极度不平衡，递归树深度为n，时间复杂度为O(16.答案：A解析：串是字符串的简称，其数据元素限定为字符。这是它与一般线性表（元素可以是任意类型）的主要区别。17.答案：D解析：常见的冲突解决方法有开放定址法（包括线性探测、二次探测等）、链地址法、再哈希法（双散列）和建立公共溢出区。广度优先搜索是图的遍历算法，与哈希表冲突处理无关。18.答案：A解析：前序：ABCDEF->根A中序：CBAEDF->根A结合：A是根。中序A左边CB，右边EDF。前序BCDEF对应CB(左)和EDF(右)。左子树（前序BC，中序CB）：前序BC->根B中序CB->根B结合：B是根。中序B左边C，右边空。右子树（前序DEF，中序EDF）：前序DEF->根D中序EDF->根D结合：D是根。中序D左边E，右边F。结构：Root(A)>Left(ChildB)>Left(ChildC)>Right(ChildD)>Left(ChildE)>Right(ChildF)后序（左右根）：左：C->B右：E->F->D根：A结果：CBEFDA。选项A符合。19.答案：C解析：二分查找过程：Low=0,High=8,Mid=(0+8)/2=4,A[4]=47<90.Low=5.Low=5,High=8,Mid=(5+8)/2=6,A[6]=62<90.Low=7.Low=7,High=8,Mid=(7+8)/2=7,A[7]=83<90.Low=8.Low=8,High=8,Mid=8,A[8]=90==90.Found.共比较4次。20.答案：A解析：最小堆性质：父节点值<=子节点值。原堆：{10,15,30,40,50,100,40}(完全二叉树层级)10(0)15(1)40(3)50(4)30(2)100(5)40(6)插入8：放在数组末尾，即下标7位置。数组变为：{10,15,30,40,50,100,40,8}进行上调（SiftUp）：比较8(下标7)和其父节点40(下标(7-1)/2=3)。8<40，交换。数组变为：{10,15,30,8,50,100,40,40}比较8(下标3)和其父节点15(下标(3-1)/2=1)。8<15，交换。数组变为：{10,8,30,15,50,100,40,40}比较8(下标1)和其父节点10(下标0)。8<10，交换。数组变为：{8,10,30,15,50,100,40,40}8到达堆顶，停止。故结果为{8,10,30,15,50,100,40,40}。注：选项A为{8,10,30,15,50,100,40,40}，符合推导。二、综合应用题41.参考答案及解析：算法设计：题目要求删除顺序表中值在[mink,maxk]之间的元素，且时间复杂度O(n)C++代码描述：```cppvoidDeleteRange(SeqList&L,intmink,intmaxk){intk=0;//k用于记录当前保留下来的元素个数，也即新数组的下标for(inti=0;i<L.length;i++){//遍历整个顺序表if(L.data[i]<mink||L.data[i]>maxk){//如果元素不在删除范围内，则保留L.data[k]=L.data[i];k++;}//如果在范围内，直接跳过（即不执行复制操作，相当于删除）}L.length=k;//更新表长}```解析：1.时间复杂度：算法只对顺序表进行了一次遍历，循环体内部操作为常数时间，故总时间复杂度为O(n)2.空间复杂度：仅使用了常数个辅助变量（i,k），故空间复杂度为O(3.正确性：指针i扫描原表，指针k指向新表的当前末尾。每当遇到不需要删除的元素，就将其复制到k的位置并递增k。遇到需要删除的元素，i继续前进而k不动，从而实现了“覆盖”删除的效果。最后更新表长。42.参考答案及解析：算法设计：采用递归方式。递归函数参数为当前结点指针、当前层数、目标值x。若当前结点为空，返回0（未找到）。若当前结点值等于x，返回当前层数。否则，先在左子树中查找，若找到则返回层数；若未找到，则在右子树中查找并返回结果。C++代码描述：```cpptypedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;intGetLevel(BiTreeT,intx,intlevel){//T:当前根结点//x:目标值//level:当前结点所在的层数if(T==NULL){return0;//空树，未找到}if(T->data==x){returnlevel;//找到目标，返回当前层数}//递归在左子树查找intleftLevel=GetLevel(T->lchild,x,level+1);if(leftLevel!=0){returnleftLevel;//左子树找到了，直接返回}//左子树没找到，递归在右子树查找returnGetLevel(T->rchild,x,level+1);}//封装调用接口intFindNodeLevel(BiTreeT,intx){returnGetLevel(T,x,1);//从根结点第1层开始}```解析：1.时间复杂度：在最坏情况下（如所有结点值均为x且x在最后一个访问的结点，或x不存在），算法需要遍历树的所有结点。时间复杂度为O(n)2.空间复杂度：递归调用栈的深度取决于树的高度。最坏情况下（单支树），高度为n，故空间复杂度为O(n)3.逻辑：标准的深度优先搜索（DFS）逻辑。一旦在子树中找到目标，通过返回值非0来判断并停止搜索另一侧子树。43.参考答案及解析：算法思路：哈密顿回路问题是NP完全问题，没有已知的多项式时间解法。对于考试中的算法设计题，通常要求使用回溯法（Backtracking）来解决小规模数据。基本思路：1.从任意顶点出发，将其加入路径path，并标记为已访问。2.递归搜索下一个未访问的邻接顶点。3.如果路径长度等于顶点总数V，且最后一个顶点与起始顶点有边相连，则找到哈密顿回路。4.如果当前路径无法延伸到解，则回溯（撤销上一步的选择，尝试其他分支）。伪代码描述：```cpp//全局变量或类成员intpath[MAX_V];//存储路径boolvisited[MAX_V];//访问标记intV;//顶点数intG[MAX_V][MAX_V];//邻接矩阵boolfound=false;//找到解的标志voidHamiltonian(intu,intdepth){path[depth]=u;//记录当前顶点if(depth==V-1){//路径已包含所有顶点，检查是否形成回路if(G[u][path[0]]!=INF&&G[u][path[0]]!=0){found=true;PrintPath();//输出path}return;}for(intv=0;v<V;v++){//寻找u的未访问邻接点if(!visited[v]&&G[u][v]!=INF&&G[u][v]!=0){visited[v]=true;Hamiltonian(v,depth+1);visited[v]=false;//回溯if(found)return;//剪枝：若只需找一个解，找到后直接返回}}}voidSolve(){//初始化for(inti=0;i<V;i++)visited[i]=false;//从每个顶点尝试开始（因为图可能不连通，或从特定点出发无解）//题目通常暗示只需判断是否存在，可从0开始visited[0]=true;Hamiltonian(0,0);if(!found)cout<<"NoHamiltonianCycle"<<endl;}```解析：1.该算法利用深度优先搜索遍历所有可能的路径组合。2.时间复杂度极高，为O(3.题目要求“判断是否存在...若存在输出路径”，上述伪代码满足了要求。44.参考答案及解析：题目分析：表长m=13，关键字：{16,74,60,43,54,90,46,31,29,40}。采用线性探测再散列：(k(1)散列表构建过程：1.16:16。地址3空。放入3。表：[_,_,_,16,_,_,_,_,_,_,_,_,_]2.74:74。地址9空。放入9。表：[_,_,_,16,_,_,_,_,_,74,_,_,_]3.60:60。地址8空。放入8。表：[_,_,_,16,_,_,_,_,60,74,_,_,_]4.43:43。地址4空。放入4。表：[_,_,_,16,43,_,_,_,60,74,_,_,_]5.54:54。地址2空。放入2。表：[_,_,54,16,43,_,_,_,60,74,_,_,_]6.90:90。地址12空。放入12。表：[_,_,54,16,43,_,_,_,60,74,_,_,90]7.46:46。地址7空。放入7。表：[_,_,54,16,43,_,_,46,60,74,_,_,90]8.31:31。地址5空。放入5。表：[_,_,54,16,43,31,46,60,74,_,_,_,90](注：上一步46在7，这里31在5，中间有空位6)修正表状态：Index:0123456789101112Value:..54164331.466074..909.29:29。冲突！探测下一个：(3探测下一个：(3探测下一个：(3表：[_,_,54,16,43,31,29,46,60,74,_,_,90]10.40:40。地址1空。放入1。表：[_,40,54,16,43,31,29,46,60,74,_,_,90]最终散列表：下标0123456789101112关键字40541643312946607490(2)计算平均查找长度(ASL)：计算每个关键字的查找次数（比较次数）：16:1次(H=3)74:1次(H=9)60:1次(H=8)43:1次(H=4)54:1次(H=2)90:1次(H=12)46:1次(H=7)31:1次(H=5)29:4次(H=3->4->5->6)40:1次(H=1)总比较次数C=元素个数n=A45.参考答案及解析：题目分析：序列：{503,087,512,061,908,170,897,275,653,426}建立大根堆：堆序性要求≥且≥（假设下标从1开始）。若下标从0开始，≥且≥。通常将数组视为完全二叉树，从最后一个非叶子结点开始，依次进行“筛选”（SiftDown）。n=10，下标0~9。最后一个非叶子结点下标为(1)建立初始堆过程：初始数组（逻辑结构）：```503(0)/\087(1)512(2)/\/\061908170897(3)(4)(5)(6)/\275653(7)(8)|426(9)```1.调整i=4(元素908)：左孩子653(8)，右孩子426(9)。908最大，无需交换。数组不变。2.调整i=3(元素061)：左孩子275(7)，右孩子653(8)。最大孩子为653。061<653，交换061和653。交换后653到了位置3，位置3的孩子是7,8，已处理过，无需继续下沉。数组部分变动：[...,653,...,061,...]3.调整i=2(元素512)：左孩子