2026年重庆理工大学攻读硕士学位研究生入学考试试题及答案

2026年重庆理工大学攻读硕士学位研究生入学考试试题及答案一、单项选择题（本题共10小题，每小题2分，共20分。在每小题给出的四个选项中，只有一项是符合题目要求的）1.在数据结构中，从逻辑上可以把数据结构分为（）。A.紧凑结构和非紧凑结构B.线性结构和非线性结构C.内部结构和外部结构D.动态结构和静态结构2.若一个栈的输入序列为1,2,3,4,5，则不可能得到的输出序列是（）。A.2,3,4,1,5B.5,4,3,2,1C.4,3,2,1,5D.2,5,3,4,13.设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（）。A.2B.3C.4D.54.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的叶子结点数为（）。A.4B.5C.6D.75.在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A.1/2B.1C.2D.46.设散列表长为14，散列函数H(A.2B.7C.8D.97.下列排序算法中，最坏情况下时间复杂度为O(A.归并排序B.堆排序C.快速排序D.基数排序8.对于有序顺序表（从小到大），若采用折半查找，则查找失败时的平均查找长度（ASL）约为（）。A.nB.nC.lD.l9.设一组初始关键字记录为(50,40,95,20,15,70,60,45)，则以增量d=4进行一趟希尔排序后的结果为（）。A.(40,50,20,15,60,95,70,45)B.(15,40,50,20,45,60,70,95)C.(50,15,60,20,40,95,70,45)D.(15,20,40,45,50,60,70,95)10.一棵二叉树的前序遍历序列为A,B,D,E,C,F，中序遍历序列为D,B,E,A,F,C，则后序遍历序列为（）。A.D,E,B,F,C,AB.D,E,F,B,C,AC.D,E,B,F,A,CD.E,D,B,F,C,A二、填空题（本题共10小题，每小题2分，共20分）11.数据的逻辑结构被分为线性结构和__________。12.设循环队列存储在数组A[0..m]中，则队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素的位置，则队列满的条件是__________。13.在单链表中，已知指针p指向某结点，若要在p之后插入一个由s指向的新结点，则需要执行的语句序列是s->next=p->next;p->next=s;。14.广义表L=(a,(b,c),d)，则Head(Tail(L))的结果是__________。15.深度为k的二叉树至多有__________个结点（假设k≥16.在一个无向图中，若采用邻接矩阵存储，则该邻接矩阵是一个__________矩阵。17.设哈希表长为m，哈希函数为H(key)18.快速排序在最好情况下的时间复杂度为__________。19.若一个串的长度小于一个常数，则采用__________存储方式最节省空间。20.在一棵二叉排序树中，按中序遍历得到的结点序列是一个__________序列。三、判断题（本题共10小题，每小题1分，共10分。正确的打“√”，错误的打“×”）21.数据元素是数据的最小单位。（）22.栈和队列都是限制存取点的线性结构。（）23.顺序存储的线性表可以随机存取，链式存储的线性表也可以随机存取。（）24.在一个循环双链表中，若指针p的后继的后继是p，则该链表可能只有一个结点或为空表。（）25.完全二叉树一定存在度为1的结点。（）26.用邻接矩阵存储图时，矩阵元素的个数与顶点的个数有关，与边的个数无关。（）27.拓扑排序算法可以用于判断有向图中是否存在环。（）28.折半查找只适用于有序顺序表，不适用于有序链表。（）29.堆排序是一种稳定的排序方法。（）30.任何一棵二叉树都可以通过中序遍历和前序遍历序列唯一确定。（）四、简答题（本题共4小题，每小题5分，共20分）31.简述栈和队列的主要区别，并各举一个实际应用例子。32.已知一棵二叉树的前序序列为：A,B,D,G,C,E,F,H，中序序列为：D,G,B,A,E,C,H,F。请画出这棵二叉树，并写出其后序遍历序列。33.设散列函数H(k)34.简述快速排序的基本思想。对于待排序序列{49,38,65,97,76,13,27}，请写出以第一个元素49为枢轴进行一趟快速排序后的结果。五、算法设计题（本题共2小题，每小题15分，共30分）注意：算法描述可以使用类C语言或类Pascal语言，要求逻辑清晰，关键步骤有注释。35.设顺序表L中的元素递增有序。试设计一个高效算法，删除顺序表中所有值介于min和max之间（含min和max）的元素。要求：(1)给出算法的基本设计思想。(2)根据设计思想，用C/C++或Pascal语言描述算法。(3)分析算法的时间复杂度和空间复杂度。36.已知二叉树采用二叉链表存储结构（结点结构为：lchild,data,rchild）。试编写一个算法，计算该二叉树中度为1的结点的个数。要求：(1)给出算法的基本设计思想。(2)根据设计思想，用C/C++或Pascal语言描述算法。(3)简要说明算法的执行过程。六、综合应用题（本题共3小题，共50分）37.（15分）已知带权无向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，E={(v1,v2):5,(v1,v3):1,(v2,v3):2,(v2,v4):3,(v2,v5):6,(v3,v4):4,(v3,v5):7,(v4,v5):8,(v4,v6):2,(v5,v6):4}。(1)请画出该图的邻接矩阵存储结构。(2)利用Prim算法（从v1开始构造）构造该图的最小生成树，请画出构造过程或列出边的加入顺序。(3)利用Dijkstra算法求顶点v1到图中其余各顶点的最短路径长度，请列出计算过程表格。38.（15分）设关键字序列为{503,087,512,061,908,170,897,275,653,426}。(1)请写出利用基数排序（LSD）进行排序的每一趟分配和收集的结果。(2)请写出利用堆排序将该序列调整为初始大根堆的过程，并图示或描述调整后的堆结构。(3)比较基数排序和堆排序的稳定性及时间复杂度。39.（20分）已知模式串t="abaabcac"，主串s="ababaabcacabcab"。(1)计算模式串t的next函数值（假设next数组下标从1开始，next[1]=0）。(2)利用KMP算法进行模式匹配，列出每一趟匹配时的s和t指针位置及比较结果。(3)若采用朴素的模式匹配算法（BF算法），总的比较次数是多少？KMP算法的比较次数是多少？并分析KMP算法在此例中的优势。参考答案与解析一、单项选择题1.B解析：数据结构的逻辑结构分为线性结构和非线性结构（包括树形结构和图状结构）。A、C、D均为存储结构或实现方式的分类。2.D解析：栈的特性是“后进先出”（LIFO）。A:1进,2进,2出,3进,3出,4进,4出,1出,5进,5出->可行。B:全进全出->可行。C:1进,2进,3进,4进,4出,3出,2出,1出,5进,5出->可行。D:输出2,5时，说明5必须在2之后进栈且在5出栈前2不能出栈，但序列中2先出，5后出，中间有3,4。若要输出2,5，意味着2进栈后出栈，然后5进栈。但此时1还在栈底。接着要输出3,4。若3,4在5之前进栈，则5被压住出不来；若3,4在5之后进栈，则5先出。无法满足2,5,3,4的顺序。故D不可行。3.B解析：s1进；s2进,s2出；s3进,s3出；s4进,s4出；s5进,s6进,s6出,s5出；s1出。栈中元素最多时为s1,s5,s6，共3个。故容量至少为3。4.C解析：树的性质：在树中，结点数=度数之和+1。设度为0的结点数为。n度数之和=1n=n5.C解析：在无向图中，每条边连接两个顶点，对这两个顶点的度数各贡献1。故所有顶点的度数之和等于边数的2倍。6.A解析：H(线性探测：下一个地址(17.C解析：归并排序、堆排序最坏时间复杂度均为O(nlog8.D解析：折半查找的判定树是一棵平衡二叉树。查找成功时的ASL≈lo(9.A解析：希尔排序按增量分组。增量d=4，分为4组：(50,15)->排序后(15,50)(40,70)->排序后(40,70)(95,60)->排序后(60,95)(20,45)->排序后(20,45)合并结果：15,40,60,20,50,70,95,45。对应选项A。10.A解析：由前序和中序确定二叉树。前序：A(根),B(左子树根),D,E,C(右子树根),F中序：D,B,E(左子树),A,F,C(右子树)递归分析：左子树：前序B,D,E，中序D,B,E。B是根，左D，右E。右子树：前序C,F，中序F,C。C是根，左F。树结构：A左孩子B，右孩子C；B左D右E；C左F。后序遍历：左->右->根。即(D,E,B)->(F,C)->A。结果：D,E,B,F,C,A。二、填空题11.非线性结构12.(rear+1)%m==front注：若front指向队头，rear指向队尾后一位置，则条件为(rear+1)%m==front。题目描述为front指向前一，rear指向尾，故满条件亦为(rear+1)%m==front。13.s->next=p->next;p->next=s;14.(b,c)解析：Tail(L)得到((b,c),d)。Head(...)得到(b,c)。15.−16.对称17.开放定址法18.O19.定长顺序20.有序三、判断题21.×解析：数据项是数据的最小单位，数据元素是数据的基本单位。22.√23.×解析：链式存储结构只能顺序存取，不能随机存取。24.√解析：循环双链表中，若只有一个结点A，则A->next=A,A->prior=A。p->next->next即A->next->next=A->next=A=p。故成立。25.×解析：完全二叉树可能没有度为1的结点（如满二叉树），也可能有1个度为1的结点。26.√27.√28.√29.×解析：堆排序是不稳定的排序算法。30.√四、简答题31.答：主要区别：栈遵循“后进先出”（LIFO）原则，只允许在表尾（栈顶）进行插入和删除；队列遵循“先进先出”（FIFO）原则，允许在表尾（队尾）插入，在表头（队头）删除。应用例子：栈常用于函数调用的递归实现、表达式求值（如后缀表达式）、浏览器的后退功能；队列常用于操作系统中的进程调度、打印机任务缓冲池、广度优先搜索（BFS）。32.答：二叉树画法：1.前序第一个A为根。2.中序中A左侧D,G,B为左子树，右侧E,C,H,F为右子树。3.左子树：前序B,D,G。B为根。中序D,G,B->B左侧D,G为左子树，右为空。B的左子树：前序D,G。D为根。中序D,G->D右侧G为右子树。故左子树结构：B->左D->右G。4.右子树：前序C,E,F,H。C为根。中序E,C,H,F->C左侧E为左子树，右侧H,F为右子树。C的左子树为E。C的右子树：前序F,H。F为根。中序H,F->F左侧H为左子树。故右子树结构：C->左E，右F->左H。5.整体树：A/\BC//\DEF\/GH后序遍历序列：G,D,B,E,H,F,C,A。33.答：线性探测再散列表：19:19。Addr6。14:14。Addr1。23:23。Addr10。1:1。冲突。(168:68。Addr3。20:20。Addr7。84:84。冲突。(6+127:27。冲突。2冲突。3冲突。4。Addr4。55:55。冲突。4冲突。5。Addr5。11:11。Addr11。表：[null,14,1,68,27,55,19,20,84,null,23,11,null,null,null,null]链地址法：0:null1:14->12:null3:684:null5:null6:19->847:208:null9:null10:2311:1112:nullASL计算（线性探测）：查找长度：19(1),14(1),23(1),1(2),68(1),20(1),84(3),27(4),55(3),11(1)。总和=1+1+1+2+1+1+3+4+3+1=18。ASL=18/10=1.8。34.答：基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。一趟快速排序结果：枢轴pivot=49。设low=0,high=6。从high向前找比49小的：27。交换49和27。{27,38,65,97,76,13,49}。low++。从low向后找比49大的：65。交换49和65。{27,38,49,97,76,13,65}。high--。从high向前找比49小的：13。交换49和13。{27,38,13,97,76,49,65}。low++。从low向后找比49大的：97。交换49和97。{27,38,13,49,76,97,65}。high--。low==high，结束。结果：{27,38,13,49,76,97,65}。五、算法设计题35.解：(1)设计思想：由于顺序表是有序的，所有介于min和max之间的元素必然是连续的。我们可以利用双指针法或直接遍历统计需要删除的元素个数，然后移动元素覆盖删除区域。高效的做法是：遍历表，找到第一个大于等于min的元素位置start，和第一个大于max的元素位置en(2)算法描述（C++）：```cppvoidDeleteRange(SeqList&L,intmin,intmax){intk=0;//记录需要保留的元素个数（或者记录当前应该放置的位置）for(inti=0;i<L.length;i++){if(L.data[i]<min||L.data[i]>max){//如果元素不在删除范围内，则保留L.data[k]=L.data[i];k++;}}L.length=k;//更新表长}```(3)复杂度分析：时间复杂度：算法遍历了一次数组，时间复杂度为O(空间复杂度：仅使用了常数个辅助变量，空间复杂度为O(36.解：(1)设计思想：采用递归或非递归的方式遍历二叉树。对于每一个结点，判断其度数。若结点的左孩子非空且右孩子空，或者左空右非空，则度为1。累加统计。(2)算法描述（C++）：```cppintCountDegree1(BinTree*T){if(T==NULL){return0;}intcount=0;//判断当前结点度是否为1if((T->lchild!=NULL&&T->rchild==NULL)||(T->lchild==NULL&&T->rchild!=NULL)){count=1;}//递归统计左右子树returncount+CountDegree1(T->lchild)+CountDegree1(T->rchild);}```(3)执行过程说明：算法采用后序遍历的逻辑（虽然此处是先统计当前再加子树，顺序不影响总和）。首先检查当前结点是否满足度为1的条件，满足则计数加1。然后递归进入左子树查找度为1的结点，再递归进入右子树查找。最终返回三部分的和。六、综合应用题37.解：(1)邻接矩阵：[05(2)Prim算法构造最小生成树（从v1开始）：初始集合U={v1}。找U到V-U最短边：v1-v3(1)。加入v3。U={v1,v3}。找U到V-U最短边：v3-v2(2)。加入v2。U={v1,v3,v2}。找U到V-U最短边：v2-v4(3)。加入v4。U={v1,v3,v2,v4}。找U到V-U最短边：v4-v6(2)。加入v6。U={v1,v3,v2,v4,v6}。找U到V-U最短边：v6-v5(4)(注意：v4-v5是8，v2-v5是6，v3-v5是7)。加入v5。边的加入顺序：(v1,v3,1),(v3,v2,2),(v2,v4,3),(v4,v6,2),(v6,v5,4)。(3)Dijkstra算法求v1到各点最短路径：步骤S(已确定)U(待确定)及dist[]最短路径初始{v1}v2(5),v3(1),v4($\infty$),v5($\infty$),v6($\infty$)v1->v3:11{v1,v3}v2(3viav3),v4(4viav3),v5(7viav3),v6($\infty$)v1->v2:3.v1->v3->v22{v1,v3,v2}v4(3viav2),v5(6viav2),v6($\infty$)v1->v4:3.v1->v3->v2->v43{v1,v3,v2,v4}v5(6viav2),v6(5viav4)v1->v6:5.v1->v3->v2->v4->v64{v1,v3,v2,v4,v6}v5(6viav2)v1->v5:6.v1->v3->v2->v5结果v1->v1:0,v1->v2:3,v1->v3:1,v1->v4:3,v1->v5:6,v1->v6:538.解：(1)基数排序（LSD）过程：初始：503,087,512,061,908,170,897,275,653,426按个位分配：0:1701:0612:5123:503,6534:5:2756:4267:087,8978:9089:收集：170,061,512,503,653,275,426,087,897,908按十位分配：0:503,9081:5122:4263:4:5:6536:061,170,8977:275,0878:9:收集：503,908,512,426,653,061,170,897,275,087按百位分配：0:061,0871:1702:2753:4:4265:503,5126:6537:8:8979:908收集：061,087,170,275,426,503,512,653,897,908(2)堆排序（初始大根堆建立）：序列：503,087,512,061,908,170,897,275,653,426(下标0-9)从最后一个非叶子结点（下标4，即908）开始调整，908比孩子大，不动。下标3（061）：孩子275,653。最大653。交换061和653。...503,087,512,653,908,170,897,275,061,426下标2（512）：孩子170,897。最大897。交换512和897。...503,087,897,653,908,170,512,275,061,426下标1（087）：孩子653,908。最大908。交换087和908。087下沉到下标4。孩子061,426。最大426。交换087和426。...503,908,897,653,426,170,512,275,061,087下标0（503）：孩子908,897。最大908。交换503和908。503下沉到下标1。孩子653,426。最大653。交换503和653。503下沉到下标3。孩子275,061。不动。...908,653,897,503,426,170,512,275,061,087初始大根堆：908,653,897,503,426,170,512,275,061,087。(3)比较：稳定性：基数排序是稳定的（需注意分配收集时保持顺序）；堆排序是不稳定的。时间复杂度：基数排序为O(d(39.解：(1)Next函数值：模式串t=abaabcacj=1:next[1]=0j=2:前缀'a',后缀'b'.无公共.next[2]=1j=3:'ab','ba'.无.next[3]=1j=4:'aba','aab'.'a'.next[4]=2j=5:'abaa','aaba'.'a'.next[5]=2j=6:'abaab','abaac'.'ab'.next[6]=3j=7:'abaabc','bcaac'.无.next[7]=1j=8:'abaabca','abcac'.'a'.next[8]=2Next数组：{0,1,1,2,2,3,1,2}(2)KMP匹配过程：S:ababaabcacabcabT:abaabcac第1趟：i=1..5匹配"ababa"，i=6时s[6]=a,t[6]=c失配。t[5]=b,next[5]=2。t回退到2。当前比较：s[6]vst[2](b)。失配。t[1]=a,next[1]=0。t回退到1，s指针回退到6（或保持6，i重置为6-1+1=6）。比较s[6]vst[1](a)。匹配。重新开始匹配：i=6(a)vsj=1(a)OK.i=7(b)vsj=2(b)OK.i=8(c)vsj=3(a)失配。t[2]=b,next[2]=1。j=1。i=8(c)vsj=1(a)失配。j=0。i++->i=9。i=9(a)vsj=1(a)OK.i=10(c)vsj=2(b)失配。j=0。i++->i=11。i=11(a)vsj=1(a)OK....匹配后续...简化描述：当s指针指到第6个字符'a'时，模式串前5个字符匹配，第6个'c'不匹配。根据nextval或next，j调整。实际上，KMP的优势在于i指针不回溯。匹配成功位置：主串第5个字符开始。过程：1.i=1..5,j=1..5匹配。i=6,j=6失配(a!=c)。next[6]=3。j=3。2.i=6,j=3比较(a!=a)。失配。next[3]=1。j=1。3.i=6,j=1比较(a==a)。匹配。4.i=7,j=2(