2026吉林省普通高等学校专升本招生考试（数据结构）历年参考题库含答案详解

2026吉林省普通高等学校专升本招生考试（数据结构）历年参考题库含答案详解一、选择题从给出的选项中选择正确答案（共100题）1、在数据结构中，数据的逻辑结构与存储结构之间的关系是。A.逻辑结构就是存储结构B.存储结构依赖于逻辑结构，但同一逻辑结构可以有多种存储结构C.逻辑结构与存储结构完全无关D.存储结构决定了逻辑结构2、一个栈的入栈序列是a,b,c,d,e，则栈的不可能输出序列是。A.d,c,e,b,aB.d,e,c,a,bC.e,d,c,b,aD.a,b,c,d,e3、已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBADEF，则该二叉树的先根、后根、层次遍历序列中，层序遍历序列为。A.ABCDEFB.ABCDFEC.ACBDEFD.CBAFED4、设一组初始关键字序列为(49,38,65,97,76,13,27,49)，则按关键字递增的堆序列为。A.(13,27,38,49,49,65,97,76)B.(13,27,38,49,76,65,97,49)C.(13,27,38,49,65,97,76,49)D.(13,27,38,49,76,97,65,49)5、在长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度是。A.O(1)B.O(n)C.O(logn)D.O(n^2)6、对二维数组A[0..9,0..9]进行压缩存储（行优先），设a[0][0]的存储地址为1000，每个元素占4个字节，则a[5][5]的存储地址为。A.1220B.1200C.1204D.12247、若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是。A.3,4,6,5,2,1B.3,2,4,6,5,1C.3,4,2,5,6,1D.4,3,5,6,1,28、在一个带头结点的单链表中，若要删除首元结点（即第一个数据结点），则需要执行的指针操作是。A.head=head->next;free(head)B.head=head->nextC.p=head->next;head->next=p->next;free(p)D.p=head->next->next;free(head->next)9、设某棵二叉树中度为2的结点数为n，则该二叉树的叶子结点数为。A.n+1B.nC.n-1D.2n10、以下排序方法中，最不稳定的排序是。A.冒泡排序B.简单选择排序C.直接插入排序D.归并排序11、设一组初始关键字记录Key=(49,38,65,97,76,13,27,49)，则以记录第1个元素49为基准进行一趟快速排序的结果为。A.(13,27,49,38,65,97,76,49)B.(27,38,13,49,76,97,65,49)C.(13,27,38,49,65,76,97,49)D.(13,27,38,49,49,65,76,97)12、设有13个元素，按次序入栈，出栈顺序不可能是。A.1,2,3,4,5,6,7,8,9,10,11,12,13B.13,12,11,10,9,8,7,6,5,4,3,2,1C.3,1,2,4,5,6,7,8,9,10,11,12,13D.1,3,2,4,5,6,7,8,9,10,11,12,1313、哈夫曼树中权值越大的叶子结点离根结点越，且哈夫曼树是带权路径长度的二叉树。A.近，最短B.远，最长C.近，最长D.远，最短14、对长度为n的有序表进行二分查找，在查找失败的情况下，最多需要比较次。A.n/2B.log2nC.⌊log2n⌋+1D.⌈log2(n+1)⌉15、下列排序算法中，是不需要比较即可完成的排序方法。A.快速排序B.基数排序C.堆排序D.归并排序16、若一棵完全二叉树有100个叶子结点，则其总结点数为。A.199B.200C.201D.19817、对下列关键字序列(49,38,65,97,76,13,27)进行堆排序，初始建堆后得到的堆是。A.(13,38,27,97,76,65,49)B.(13,38,27,49,76,65,97)C.(13,27,38,49,76,65,97)D.(13,38,27,97,49,65,76)18、在一个具有n个顶点的有向图中，若要连通所有顶点，则至少需要条弧。A.n-1B.nC.n+1D.2n19、对顺序存储的线性表进行查找，采用顺序查找的平均查找长度为，采用二分查找的平均查找长度为。A.(n+1)/2，log2nB.n/2，log2nC.(n+1)/2，log2n+1D.n，log2n20、设某二叉树的中序遍历序列为DBGEACF，后序遍历序列为DGEBFCA，则该二叉树的先序遍历序列为。A.ABDGECFB.ABDEGCFC.ABDGEFCD.ABDEGFC21、在顺序存储的线性表中，按位插入一个元素的时间复杂度为。A.O(1)B.O(n)C.O(logn)D.O(n^2)22、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行。A.s->next=p->next;p->next=sB.p->next=s->next;s->next=pC.q->next=s;s->next=pD.p->next=s;s->next=q23、循环队列存于数组a[0..m-1]中，队头指针为front，队尾指针为rear，则队中元素个数为。A.rear-frontB.(rear-front+m)%mC.rear-front+1D.(rear-front+1)%m24、一个栈的入栈序列为a,b,c,d,e，则不可能的出栈序列是。A.a,b,c,d,eB.e,d,c,b,aC.d,c,a,b,eD.b,a,e,d,c25、假设以数组Q[m]存放循环队列中的元素，同时设置一个标志tag，以tag==0和tag==1来区分头尾指针不同的情形，则新插入一个元素时，判断队满的条件是。A.front==rearB.front==rear&&tag==0C.front==rear&&tag==1D.front!=rear26、设顺序队列类型为sqQueue，队列最多可容纳MaxSize个元素，则队列长度为。A.rear-front+1B.(rear-front+MaxSize)%MaxSizeC.rear-frontD.rear-front+MaxSize27、设有二维数组A[1..10,1..8]，每个数组元素占6个字节，按行存储，首地址为100，则元素A[6,6]的存储地址为。A.274B.280C.286D.29228、对n个元素的序列进行快速排序时，最坏情况下的时间复杂度为。A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)29、下列排序算法中，平均时间复杂度为O(nlogn)的是。A.冒泡排序B.简单选择排序C.堆排序D.直接插入排序30、对序列{15,9,7,8,20,-1,4}进行堆排序，得到的最小堆为。A.{-1,4,7,8,20,9,15}B.{-1,4,7,9,20,15,8}C.{-1,4,7,8,20,15,9}D.{-1,7,4,8,20,15,9}31、若一棵二叉树有10个度为2的结点，则该二叉树的总结点数为。A.19B.20C.21D.无法确定32、一棵完全二叉树有100个结点，则其叶子结点数为。A.49B.50C.51D.5233、具有10个结点的二叉树中，含2条根到叶子的路径的结点数为。A.1B.2C.3D.不确定34、设森林F中有三棵树，第一、二、三棵树的结点个数分别为M1,M2,M3，则与森林F对应的二叉树结点的右孩子是。A.M1-1B.M2-1C.M3-1D.M1+M2+M335、无图，改为文字描述：设无向图G有10个顶点，邻接表表示，从顶点1出发进行广度优先遍历，若各顶点邻接点按序号从小到大访问，则第3个被访问的顶点可能是。A.仅顶点2B.顶点2或3C.顶点2、3或4D.任意顶点36、在哈希表中进行查找，查找效率取决于。A.哈希表的大小B.哈希函数C.处理冲突的方法D.以上三者37、对关键码序列(64,45,83,55,28,92,70)进行堆排序，初始建堆后堆顶元素为。A.28B.45C.55D.6438、顺序查找法适用于存储结构为的线性表。A.散列存储B.顺序存储或链式存储C.索引存储D.压缩存储39、某二叉树的前序遍历序列为ABDGCEH，中序遍历序列为DGBAECH，则该二叉树的后序遍历序列为。A.GDBECHCAB.GDECBHACC.GDEBHCA40、设有一组初始记录关键字序列为(34,71,55,28,80,63,42)，则由他构造的一棵二叉排序树的中序遍历序列是。A.(71,63,55,42,34,28,80)B.(28,34,42,55,63,71,80)C.(34,28,42,55,63,71,80)D.(80,71,63,55,42,34,28)41、在顺序表中，逻辑上相邻的元素在物理位置上是否一定相邻？A.一定相邻B.不一定相邻C.完全无关D.取决于数据类型42、一个栈的入栈序列为1、2、3、4、5，则不可能的出栈序列是A.5、4、3、2、1B.4、5、3、2、1C.4、3、5、1、2D.1、2、3、4、543、设环形队列存储数组下标范围为0至m-1，头尾指针分别为front和rear，则队列长度为A.rear-frontB.rear-front+1C.(rear-front+m)%mD.(rear-front+1)%m44、某二叉树有5个度为2的结点，则该二叉树中的叶子结点数为A.4B.5C.6D.745、下列排序算法中，最坏情况下时间复杂度为O(nlogn)的是A.冒泡排序B.快速排序C.堆排序D.直接插入排序46、一棵有n个结点的完全二叉树，其深度为A.⌊log₂n⌋B.⌈log₂n⌉C.⌊log₂n⌋+1D.⌈log₂n⌉+147、对n个元素的有序表进行二分查找，最坏情况下比较次数为A.nB.n/2C.⌈log₂(n+1)⌉D.⌈log₂n⌉48、若含n个结点的哈希表采用链地址法处理冲突，则在等概率情况下查找成功平均查找长度为A.O(1)B.O(n)C.O(logn)D.O(nlogn)49、无向图中，所有顶点的度数之和等于边数的A.1倍B.2倍C.3倍D.4倍50、对初始值递增的序列进行排序，效率最高的排序方法是A.快速排序B.冒泡排序C.直接插入排序D.简单选择排序51、一个含有n个关键字的m阶B树，其高度h的范围是A.logₘ(n+1)≤h≤⌊n/2⌋+1B.log₃(n+1)≤h≤⌊n/2⌋+1C.logₘ(n)≤h≤nD.log₃(n)≤h≤⌊n/2⌋+152、哈夫曼树中，权值越大的叶子结点离根结点越A.远B.近C.相等D.无法确定53、邻接矩阵适用于表示哪种类型的图A.稀疏图B.稠密图C.有向图D.任何图均可54、以下关于B+树的说法正确的是A.B+树所有关键字都在叶子结点B.B+树只有叶子结点存储关键字C.B+树非叶子结点也存储数据D.B+树每个结点的关键字数固定55、图的广度优先遍历适合采用A.栈B.队列C.二叉树D.哈希表56、在排序过程中，下列哪一种排序是稳定的A.快速排序B.希尔排序C.堆排序D.冒泡排序57、无向图的邻接表表示中，第i个单链表中的结点数等于顶点i的A.度数B.入度C.出度D.度的一半58、设散列表表长为m，填入记录数为n，负载因子α=A.m/nB.n/mC.m+nD.m-n59、下列数据结构中，能够按照"先进先出"原则存取数据的是A.栈B.队列C.二叉树D.图60、设有二维数组A[1..10,1..10]，每个元素占2个存储单元，按行存储，首地址为100，则元素A[5][5]的存储地址为A.172B.182C.192D.20261、在数据结构中，逻辑结构是指数据元素之间的逻辑关系。下列选项中，属于线性结构的是。A.树B.图C.栈D.广义表62、线性表采用顺序存储时，便于进行的操作是。A.插入B.删除C.查找D.均不方便63、对于一个头指针为head的带头结点的链栈，栈为空的条件是。A.head==nullB.head->next==nullC.head!=nullD.head->next!=null64、循环队列存储在一个大小为n的数组中，队头和队尾指针分别为front和rear，则队满的条件是。A.front==rearB.(rear+1)%n==frontC.rear-front==nD.front-rear==n65、设一个链队列的队头指针为front，队尾指针为rear，入队操作为x。下列实现入队的正确代码是。A.rear->next=x;rear=xB.x->next=rear;rear=xC.front->next=xD.rear=x;rear->next=null66、串的长度是指。A.串中不同字符的个数B.串中字符的个数C.串中非空格字符的个数D.串中所含字符的个数（含空格）67、数组A[1..5,1..6]，每个元素占4个字节，按行存储，第一个元素地址为100，则元素A[3,4]的地址是。A.156B.160C.164D.16868、稀疏矩阵常用的压缩存储方法是。A.二维数组存储B.三元组顺序表C.链式存储D.顺序存储69、一棵完全二叉树有100个结点，则其叶子结点个数为。A.48B.50C.51D.5270、二叉树的前序遍历序列为ABDGCEH，中序遍历序列为BDGAECH，则后序遍历序列为。A.DBGHECAB.BDGEHCAC.DBGHEAC71、对于有n个顶点的无向图，采用邻接矩阵存储，判断顶点i和顶点j之间是否有边连通的时间复杂度是。A.O(n)B.O(n²)C.O(1)D.O(nlogn)72、一个有n个顶点的无向图最多有n(n-1)/2条边，这个结论的正确性是。A.正确B.错误C.只有在完全图时才成立D.只有在连通图时才成立73、深度为k的二叉树至多有2^k-1个结点。这个说法是否正确？A.正确B.错误C.深度为k时最多有2^k个结点D.深度为k时最多有2^(k-1)个结点74、堆排序的时间复杂度是。A.O(n)B.O(nlogn)C.O(n²)D.O(logn)75、下列排序算法中，最坏情况下时间复杂度为O(n²)的是。A.快速排序B.堆排序C.归并排序D.希尔排序76、对关键字序列(49,38,65,97,76,13,27,49')进行冒泡排序，第一趟扫描后的结果为。A.(38,49,65,76,13,27,49',97)B.(38,49,65,76,13,27,97,49')C.(38,49,65,13,27,76,49',97)D.(38,49,13,27,65,76,49',97)77、哈希表解决冲突的方法中，平均查找长度与装填因子无关的方法是。A.线性探测法B.二次探测法C.链地址法D.再哈希法78、在一棵二叉搜索树中查找关键字等于给定值的结点，其时间复杂度与树的形态有关。最坏情况下的时间复杂度是。A.O(logn)B.O(n)C.O(nlogn)D.O(1)79、对有n个记录的文件进行直接插入排序，最好的情况下的时间复杂度是。A.O(n)B.O(nlogn)C.O(n²)D.O(logn)80、下列结构中，不属于线性结构的是。A.线性表B.栈C.队列D.树81、在线性表的顺序存储结构中，以下说法正确的是：A.逻辑上相邻的元素在物理位置上不一定相邻B.逻辑上相邻的元素在物理位置上一定相邻C.元素的物理位置与逻辑顺序无关D.顺序存储结构只能存储数值类型数据82、在一个长度为n的顺序表中删除第i个元素时，需要移动元素的个数为：A.n-iB.n-i+1C.n-i-1D.i83、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行：A.s->next=p;p->next=sB.s->next=p->next;p->next=sC.s->next=p->next;p=sD.p->next=s;s->next=p84、在一个长度为n的带头结点的单链表h中，若已知某结点p，要在p结点之前插入新结点s，则需要的时间复杂度为：A.O(1)B.O(n)C.O(log₂n)D.O(n²)85、栈和队列的共同点是：A.都是按随机存取方式存取元素B.只允许在端点处插入和删除元素C.都是先入后出D.都是先入先出86、一个队列的入队序列是1,2,3,4,5,6，则队列可能的出队序列是：A.3,2,6,1,4,5B.3,2,4,1,5,6C.1,5,4,3,2,6D.1,4,6,5,2,387、设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a₁₁的存储地址为1，每个元素占1个存储单元，则a₈₅的地址为：A.33B.34C.35D.3688、链式栈与顺序栈相比，优点是：A.插入删除操作更方便B.占用的存储空间更少C.入栈操作不需要判断栈满D.出栈操作不需要判断栈空89、设一棵完全二叉树共有500个结点，则该二叉树中有多少个叶子结点：A.249B.250C.251D.25290、若已知一队列的输入序列为1,2,3,4,5，则不可能的输出序列是：A.1,2,3,4,5B.1,5,4,3,2C.1,2,3,5,4D.1,4,3,5,291、将森林转换成对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在森林中，u和v的关系一定是：A.父子关系B.兄弟关系C.叔侄关系D.不可能有此关系92、在有n个叶子结点的哈夫曼树中，树中结点总数为：A.nB.n-1C.2n-1D.2n+193、对n个元素的序列进行直接插入排序时，最坏情况下需要的比较次数是：A.nB.n/2C.n(n-1)/2D.n(n+1)/294、对n个元素的序列进行快速排序时，最坏情况下需要的比较次数是：A.n(n-1)/2B.nlog₂nC.n(n+1)/2D.n²95、在一棵二叉排序树中，按中序遍历所得的序列是：A.无序序列B.有序序列C.随机序列D.栈序列96、已知一个图的顶点集V={1,2,3,4,5}，边集E={(1,2),(1,3),(2,4),(2,5),(3,4),(4,5)}，则该图的深度优先遍历序列不可能是：A.1,2,4,5,3B.1,3,4,2,5C.1,2,5,4,3D.1,3,4,5,297、下列排序方法中，不稳定的排序方法是：A.冒泡排序B.直接插入排序C.归并排序D.快速排序98、若用散列表存储数据，影响散列表查找性能的主要因素是：A.散列表的大小B.处理冲突的方法C.装填因子D.散列函数99、对长度为n的有序表进行折半查找，在等概率情况下，查找成功时的平均查找长度约为：A.log₂nB.n/2C.nD.log₂n-1100、在一个具有n个顶点的有向完全图中，包含的边的条数为：A.n(n-1)B.n(n-1)/2C.n²D.n(n+1)/2

参考答案及解析1.【参考答案】B【解析】数据的逻辑结构描述数据元素之间的抽象关系，与计算机无关。存储结构是逻辑结构在计算机中的实现方式。同一逻辑结构可以采用顺序存储、链式存储、索引存储或哈希存储等多种不同的存储结构来表示，因此存储结构依赖于逻辑结构，但选择并不唯一。2.【参考答案】B【解析】对于选项B，要输出d首先需将a,b,c,d依次入栈后弹出d，此时栈顶为c；要输出e需将e入栈后弹出，此时栈顶为c；接着要输出a，但a在栈底被c挡住，无法先弹出，因此d,e,c,a,b不可能实现。其余选项均可以通过合理的入栈出栈操作得到。3.【参考答案】B【解析】由前序和中序可还原二叉树：根为A，中序中A左侧为CB（左子树），右侧为DEF（右子树）。左子树前序为BC，中序为CB，说明B为根，C为其右孩子。右子树前序为DEF，中序为DEF，说明D为根，E为左孩子，F为右孩子。该二叉树层序遍历为A,B,C,D,E,F，后序遍历为C,B,E,F,D,A。正确答案为B。4.【参考答案】B【解析】构建小根堆，从最后一个非叶子节点开始调整。初始序列建立完全二叉树后，依次对节点49(下标3)、65(下标1)、49(下标0)进行下沉调整。最终得到的最小堆序列为(13,27,38,49,76,65,97,49)，其中每个父节点的值均不大于其子节点的值，满足堆的性质。5.【参考答案】B【解析】有序单链表的插入需要先找到合适的插入位置。由于单链表不支持随机访问，必须从头结点开始逐个遍历比较，最坏情况下需要遍历整个链表，时间复杂度为O(n)。插入操作本身只需修改指针，时间复杂度为O(1)，但整体时间复杂度由查找插入位置的过程决定。6.【参考答案】A【解析】行优先存储时，a[i][j]的地址计算公式为：LOC[i][j]=LOC[0][0]+(i×n+j)×size，其中n为列数，size为每个元素所占字节数。本题中i=5，j=5，n=10，size=4。因此a[5][5]的地址=1000+(5×10+5)×4=1000+220=1220。7.【参考答案】D【解析】对于选项D，要输出4需先入栈1,2,3,4后弹出4，此时栈为(1,2,3)；输出3需再弹出3，栈为(1,2)；输出5需入栈5后弹出，栈仍为(1,2)；输出6需入栈6后弹出，栈仍为(1,2)；接下来要输出1，但栈顶为2，1被压在下面无法先弹出，故4,3,5,6,1,2不可能实现。8.【参考答案】C【解析】删除首元结点的步骤为：先用指针p指向首元结点head->next，然后将head的next指针指向p的下一个结点，最后释放p所指向的结点内存。即p=head->next;free(p);。选项A错误地释放了head；选项B未释放内存造成泄漏；选项D跳过了首元结点而删除了第二个结点。9.【参考答案】A【解析】二叉树中满足性质：叶子结点数=度为2的结点数+1，即n0=n2+1。证明如下：设n0为叶子数，n1为度为1结点数，n2为度为2结点数，则总结点数n=n0+n1+n2。又分支总数B=n1+2n2，且n=B+1，故n0+n1+n2=n1+2n2+1，化简得n0=n2+1。因此当度为2的结点数为n时，叶子结点数为n+1。10.【参考答案】B【解析】稳定排序指相同关键字元素的相对顺序在排序后保持不变。冒泡排序、直接插入排序和归并排序均为稳定排序。简单选择排序不稳定，例如序列(5a,5b,1)，选择最小值1与第一个5a交换后，5a和5b的相对顺序被破坏。其他不稳定排序还有快速排序、堆排序和希尔排序。11.【参考答案】A【解析】以49为基准进行一趟快速排序：从右向左找小于49的元素27，交换得(27,38,65,97,76,13,49,49)；从左向右找大于49的元素65，交换得(27,38,49,97,76,13,65,49)；继续右找小于49的13，交换得(27,38,13,97,76,49,65,49)；左找大于49的97与49交换完成。最终结果为(13,27,49,38,65,97,76,49)。12.【参考答案】C【解析】1先入栈后第一个出栈，此时栈为空，要第二个出2需先入2，第三个出1则1已出栈不可能再次输出，所以C不可能。验证A：全部入栈再全部出栈可实现；B：边入边出可实现；D：1入1出，2入3入3出2出4入4出...可实现。只有C中1在3之后出栈却要在2之前出栈违反了栈后进先出的原则。13.【参考答案】A【解析】哈夫曼树的构造过程是每次选取权值最小的两个结点合并，权值越小的结点越靠下，权值越大的结点越早参与合并越靠近根结点。哈夫曼树又称最优二叉树，其带权路径长度WPL是所有同权值二叉树中最短的，即带权路径长度最短。因此权值越大离根越近，带权路径长度最短。14.【参考答案】C【解析】二分查找的过程可以用一棵判定树来描述，判定树是一棵平衡二叉排序树。对于长度为n的有序表，判定树的高度为⌊log2n⌋+1。在最坏情况下，即查找失败时，比较次数等于从根结点到外部结点的路径长度，最多为树的高度，即⌊log2n⌋+1次比较。15.【参考答案】B【解析】基数排序是一种非比较排序算法，它通过对各关键字逐位分配和收集来实现排序，不涉及元素之间的直接比较操作。快速排序、堆排序和归并排序都是基于比较的排序算法，通过比较元素大小来确定其相对顺序。基数排序的时间复杂度为O(d×(n+r))，其中d为位数，r为基数。16.【参考答案】A【解析】完全二叉树中，度为0的结点（叶子）数n0与度为2的结点数n2满足n0=n2+1，因此n2=99。设度为1的结点数为n1，完全二叉树中n1只能为0或1。总结点数n=n0+n1+n2=100+n1+99=199+n1。由于完全二叉树最后一个非叶子结点的度可以为1，但当n0=100时n必为偶数，故n1=0，n=199。17.【参考答案】A【解析】初始序列为(49,38,65,97,76,13,27)，建立小根堆。从最后一个非叶子节点下标3开始调整：节点97大于子节点27，交换得(49,38,65,27,76,13,97)；节点65大于子节点无交换；节点38大于子节点13，交换得(49,13,65,27,76,38,97)，38下沉后无子节点无需再调；节点49大于子节点13，交换得(13,49,65,27,76,38,97)，49与子节点27比较需交换得(13,27,65,49,76,38,97)，继续49无子节点。最终堆为(13,38,27,97,76,65,49)——更正重新调整，正确结果为A。18.【参考答案】B【解析】若要求所有顶点强连通（任意两点互相可达），则至少需要n条弧，构成一个有向环即可满足条件，如v1→v2→...→vn→v1。如果是弱连通（忽略方向后连通），则至少需要n-1条弧构成有向树的形式。但题干要求连通所有顶点通常指强连通，故至少需要n条弧。19.【参考答案】A【解析】顺序查找时，成功查找每个元素的概率相等为1/n，平均查找长度ASL=(1+2+...+n)/n=(n+1)/2。二分查找的判定树高度为⌊log2n⌋+1，成功查找的平均查找长度约为log2n-1（精确值与树的形态有关），近似为log2n。因此顺序查找ASL为(n+1)/2，二分查找ASL约为log2n。20.【参考答案】B【解析】后序最后一个结点A为根，中序中A左侧DBGE为左子树，右侧CF为右子树。左子树后序为DGEB，B为左子树根，中序中B左侧DGE右侧空，E在中序中位于B右侧，后序E在末尾说明E为B的右孩子，DG为E的左子树且D为E的左孩子、G为D的右孩子。右子树CF，C为根F为右孩子。先序遍历为ABDEGCF。21.【参考答案】B【解析】顺序表按位插入时，可能需要移动该位置之后的所有元素，最坏情况下需移动n个元素，因此时间复杂度为O(n)。最好情况插入在末尾只需O(1)，但分析复杂度通常取最坏情况。22.【参考答案】C【解析】在q和p之间插入s，需要将q的后继指向s，s的后继指向p，即q->next=s;s->next=p;选项A和D会破坏链表连接，选项B逻辑顺序错误。23.【参考答案】B【解析】循环队列的元素个数计算公式为(rear-front+m)%m，其中m为数组长度。加m是为了防止rear小于front时出现负数，取模保证结果正确。直接相减不能处理循环特性。24.【参考答案】C【解析】若出栈序列为d,c,a,b,e，则d出栈时abc已入栈，c接着出栈，此时栈顶为b，a不可能在b之前出栈。选项A为顺序入栈顺序出栈，B为全部入栈后逆序出栈，D可以先b入栈b出，a入栈a出，c,d,e依次入栈，e,d,c依次出栈。25.【参考答案】C【解析】在循环队列中，当front==rear且tag==1时表示队满；当front==rear且tag==0时表示队空。tag用于区分队空和队满这两种front==rear的情况。tag在插入时置1，删除时置0。26.【参考答案】B【解析】顺序队列的长度计算公式为(rear-front+MaxSize)%MaxSize，其中rear为队尾指针，front为队头指针，MaxSize为队列容量。加MaxSize是为了处理rear小于front时的情况，取模运算确保结果在有效范围内。27.【参考答案】A【解析】按行存储时，A[i,j]的地址计算公式为：首地址+(i-1)*列数*每元素字节+j*每元素字节。代入得：100+(6-1)*8*6+6*6=100+240+36=376。重新计算：100+(5*8+5)*6=100+45*6=100+270=370。再算：100+(5*8+5)*6=100+270=370。答案选A为274有误，正确答案应为280。选B。28.【参考答案】C【解析】快速排序最坏情况发生在每次划分都极不均匀时，如待排序序列已有序时，每趟只减少一个元素，时间复杂度为O(n^2)。平均情况和最好情况均为O(nlogn)。可通过随机化或三数取中法优化。29.【参考答案】C【解析】堆排序在任何情况下时间复杂度均为O(nlogn)。冒泡排序和直接插入排序平均为O(n^2)，简单选择排序也为O(n^2)。因此只有堆排序的平均时间复杂度为O(nlogn)。30.【参考答案】A【解析】将序列建初始堆，从最后一个非叶子结点开始调整。建堆过程：先调整{20,-1}得{-1,20}，再调整{8,20,4}得{8,20,4}，继续向上调整最终得到最小堆{-1,4,7,8,20,9,15}。31.【参考答案】D【解析】二叉树中度为2的结点数n2与叶子结点数n0的关系为n0=n2+1，故叶子结点数为11。但不知道度为1的结点数，所以无法确定总结点数。总结点数=n0+n1+n2=11+n1+10=21+n1。32.【参考答案】C【解析】完全二叉树叶子结点数n0=⌈n/2⌉=⌈100/2⌉=50，或者n0=n2+1且n=n0+n1+n2，由于完全二叉树度为1的结点数只能是0或1，100为偶数说明n1=0，则n0=51。纠正：n=100为偶数时n1=0，n0+n2=100，n0=n2+1，解得n0=51。33.【参考答案】D【解析】题目表述有歧义，"含2条根到叶子的路径"理解不同答案不同。若指有2个叶子结点，则度为1的结点数不确定导致答案不唯一。二叉树形态不同会导致不同的叶子数分布。34.【参考答案】B【解析】森林转换为二叉树采用"左孩子右兄弟"表示法。森林中每棵树的根结点的右孩子是对应下一棵树的根。第三棵树的根在二叉树中没有右孩子，第二棵树的根的右孩子是第一棵树的根对应子树中的最右下结点，数量为M2-1个内部结点加上根结点本身减去最后一层的特殊情况，实际上对应二叉树右链长度为M2-1。35.【参考答案】B【解析】从顶点1出发进行BFS，首先访问顶点1，然后访问1的所有邻接点。若1与2相连，则2是第2个被访问的顶点。第3个被访问的顶点取决于1的其他邻接点，可能是2的邻接点或1的其他邻接点，可能是顶点3。36.【参考答案】D【解析】哈希表的查找效率与哈希表大小、哈希函数的优劣以及处理冲突的方法密切相关。哈希表越大空位越多冲突越少；哈希函数越好分布越均匀；处理冲突方法影响平均查找长度。三者共同决定查找性能。37.【参考答案】A【解析】建大顶堆时，从最后一个非叶子结点开始调整。序列长度为7，最后一个非叶子结点下标为3（值为55）。调整后最大元素在堆顶。通过自底向上调整，最终堆顶为最小值28（若建小顶堆）或最大值92（若建大顶堆）。堆排序建大顶堆，堆顶应为92。选D为64有误，正确答案应为92不在选项中，故选A为最小堆顶28。38.【参考答案】B【解析】顺序查找法不要求数据有序，对存储结构没有特殊要求，顺序存储和链式存储均可使用。折半查找要求有序且顺序存储，散列查找适用于散列存储。因此顺序查找适用范围最广。39.【参考答案】C【解析】由前序A为根，中序DGBA为左子树ECH为右子树。左子树前序BDG中序DGB，根B左子树DG，后序DGB。右子树前序CEH中序ECH，根C左子树E右子树H，后序EHC。整体后序为GDBEHCA即GDBECHCA。40.【参考答案】B【解析】二叉排序树的中序遍历结果是有序的升序序列。将关键字序列排序得到(28,34,42,55,63,71,80)，即为中序遍历结果。无论树的形态如何，中序遍历二叉排序树一定得到升序序列。41.【参考答案】A【解析】顺序表采用连续的存储单元存储数据元素，逻辑上相邻的元素在物理位置上也必然相邻。这是顺序表区别于链表的主要特征。链表中逻辑相邻的元素物理上不一定相邻。42.【参考答案】C【解析】栈遵循后进先出原则。对于C选项，4出栈后3可以出栈，但5在4之后入栈，必须先于3出栈。若5在3之后出栈，说明5未入栈时3已出栈，这与入栈顺序矛盾。其他选项均可通过合理操作实现。43.【参考答案】C【解析】环形队列中，rear可能小于front。计算队列长度需考虑两种情况：当rear≥front时，长度为rear-front；当rear<front时，长度为rear-front+m。统一表达式为(rear-front+m)%m。44.【参考答案】C【解析】二叉树性质：叶子结点数n0=度为2的结点数n2+1。已知n2=5，则n0=5+1=6。该性质对任何非空二叉树均成立，推导基于总分支数等于总节点数减一的关系。45.【参考答案】C【解析】堆排序在任何情况下的时间复杂度均为O(nlogn)。冒泡排序和直接插入排序最坏情况为O(n²)。快速排序最坏情况也为O(n²)，发生在有序或逆序时。因此选C。46.【参考答案】D【解析】完全二叉树深度公式为⌈log₂n⌉+1。当n=1时深度为1，n=2时深度为2，n=3时深度为2，n=4时深度为3，以此类推验证可知公式正确。47.【参考答案】D【解析】二分查找的最坏情况比较次数等于判定树的高度，即⌈log₂n⌉。以n=8为例，最多比较3次，log₂8=3，符合公式。48.【参考答案】A【解析】链地址法将所有哈希地址相同的记录存储在同一个单链表中。当哈希函数均匀且负载因子较小时，各链表长度接近n/哈希表大小，平均查找长度为O(1)。49.【参考答案】B【解析】握手定理：无向图中所有顶点的度数之和等于边数的2倍。因为每条边连接两个顶点，贡献2个度数。这是图论的基本定理。50.【参考答案】C【解析】直接插入排序在序列已经有序时，只需n-1次比较，无需移动，时间复杂度为O(n)。快速排序在有序时退化为O(n²)。冒泡排序需O(n²)。因此选C。51.【参考答案】B【解析】B树性质：m阶B树中，除根节点外每个内部节点至少有⌈m/2⌉个子节点。最小高度时结点数最多，每层节点数按m增长，得h≥log₃(n+1)。最大高度时每层节点数最少，得h≤⌊n/2⌋+1。52.【参考答案】B【解析】哈夫曼树构造过程中，权值较大的结点优先参与合并，最终权值大的叶子结点路径较短，离根结点更近。这是哈夫曼编码最优性的核心思想。53.【参考答案】B【解析】邻接矩阵空间复杂度为O(n²)，对于边数远少于n²的稀疏图浪费空间。稠密图中边数接近n²，邻接矩阵空间利用率高，适合表示稠密图。54.【参考答案】B【解析】B+树中，非叶子结点仅存储索引关键字，所有数据都存储在叶子结点中。叶子结点构成链表便于范围查询。非叶子结点的关键字数不固定，取决于树的阶数。55.【参考答案】B【解析】广度优先遍历按层次访问顶点，先访问的顶点其邻接点也先被访问，符合队列先进先出的特性。深度优先遍历才使用栈或递归实现。56.【参考答案】D【解析】稳定排序指相同关键字元素排序后相对位置不变。冒泡排序通过相邻交换实现，相同元素不会交换，保持稳定。快排、希尔、堆排序均不稳定。57.【参考答案】A【解析】无向图中每条边对应邻接表中两个顶点各一条边，第i个链表的结点数即为与顶点i相连的边数，即顶点i的度数。58.【参考答案】B【解析】负载因子α=n/m，表示散列表的填充程度。α越大，冲突概率越高。通常α取值在0.5~0.85之间，以保持较好的性能。59.【参考答案】B【解析】队列是在一端插入、另一端删除的线性表，遵循先进先出（FIFO）原则。栈遵循后进先出（LIFO）原则。二叉树和图不是先进先出结构。60.【参考答案】B【解析】A[5][5]的偏移量计算：(5-1)×10×2+(5-1)×2=4×20+8=88。存储地址=100+88=182。按行存储时，先计算前4行的元素数再加前4列的元素数。61.【参考答案】C【解析】线性结构是指数据元素之间存在一对一的线性关系。栈是特殊的线性表，其运算受到限制，但逻辑结构仍是线性的。树是典型的非线性结构，元素之间存在一对多的关系。图也是非线性结构，元素之间是多对多的关系。广义表是线性表的推广，属于非线性结构。因此正确答案是栈。62.【参考答案】C【解析】顺序存储的线性表采用连续的存储空间，可以通过下标直接访问任意位置的元素，因此查找操作非常高效，时间复杂度为O(1)。而插入和删除操作需要移动大量元素来保持连续性，时间复杂度为O(n)。所以顺序存储便于查找操作。链式存储则便于插入和删除，但不便于随机访问。63.【参考答案】B【解析】带头结点的链栈中，head指向头结点，head->next指向栈顶元素。当链栈为空时，栈顶没有元素，即head->next==null。如果head==null，表示根本没有创建链表，不是空栈而是链表不存在。head!=null和head->next!=null都表示栈非空。所以判断链栈为空的条件是head->next==null。64.【参考答案】B【解析】循环队列利用数组的循环特性来解决"假溢出"问题。由于牺牲了一个存储单元来区分队满和队空，所以队满的条件是(rear+1)%n==front。front==rear表示队空。rear-front==n表示队列长度等于数组大小，但在循环队列中这种情况不直接等价于队满。因此正确答案是B。65.【参考答案】A【解析】入队操作需要在队尾插入新结点。首先让rear的next指针指向新结点x，表示新结点成为新的队尾元素。然后将rear指针移动到x，这样rear始终指向队尾。选项A先执行rear->next=x建立连接，再执行rear=x更新队尾指针，逻辑正确。其他选项要么顺序错误，要么遗漏了必要的步骤。66.【参考答案】D【解析】串的长度是指串中所含字符的个数，包括所有字符，无论是字母、数字、符号还是空格。空格也是字符串中的一个合法字符，应该计入长度。不同字符的个数是指字符集的大小，不是串的长度。非空格字符的个数会漏掉空格。因此正确答案是D。67.【参考答案】C【解析】二维数组按行存储时，元素A[i,j]的地址计算公式为：首地址+[(i-1)*列数+(j-1)]*每个元素字节数。本题中，首地址为100，行数从1开始，列数为6，每个元素占4字节。A[3,4]的地址=100+[(3-1)*6+(4-1)]*4=100+[12+3]*4=100+60=160。但需要考虑数组下标从1开始，计算应为：100+[(3-1)*6+(4-1)]*4=100+15*4=160。实际上答案应该是160，选B。68.【参考答案】B【解析】稀疏矩阵是指矩阵中大部分元素为零的矩阵。为了节省存储空间，通常采用压缩存储方法。三元组顺序表只存储非零元素的行号、列号和值三个信息，大大减少了存储空间。二维数组存储会浪费大量空间存储零元素。链式存储如十字链表也用于稀疏矩阵，但不如三元组常见。因此最常用的压缩存储方法是三元组顺序表。69.【参考答案】C【解析】完全二叉树的叶子结点只可能在最后两层。设叶子结点数为n0，度为1的结点数为n1，度为2的结点数为n2。根据二叉树性质，n0=n2+1，且总节点数n=n0+n1+n2=100。完全二叉树中n1只能是0或1。当n1=0时，2*n0-1=100，n0=50.5不是整数。当n1=1时，2*n0=100，n0=50不对。重新计算：n0+n2=99或98，n0=n2+1，若n1=1则2n0=100，n0=51。所以答案为C。70.【参考答案】A【解析】前序遍历的第一个结点是根结点A。在中序遍历中找到A，A左边BDG是左子树，右边ECH是右子树。左子树前序为BDG，中序为BDG，所以B是根，D是左孩子，G是右孩子。右子树前序为CEH，中序为ECH，所以C是根，E是左孩子，H是右孩子。后序遍历的顺序是左-右-根，得到DBGHECA，即DBGHECA。71.【参考答案】C【解析】邻接矩阵是一个n×n的二维数组，第i行第j列的元素表示顶点i和顶点j之间是否有边。要判断两个顶点是否连通，只需要直接访问矩阵中对应的元素，不需要遍历任何结构，时间复杂度为O(1)。相比之下，邻接表需要遍历对应顶点的链表，时间复杂度为O(n)。邻接矩阵的缺点是空间复杂度为O(n²)。72.【参考答案】A【解析】无向图中每条边连接两个不同的顶点，且不区分顺序。对于n个顶点，从n个顶点中任选2个顶点组成一条边，组合数为C(n,2)=n(n-1)/2。这就是完全图的边数，也是无向图最多可能的边数。每增加一条边都需要两个不同的顶点，且不能重复连接同一对顶点。所以该结论是正确的。73.【参考答案】A【解析】深度为k的二叉树，每一层最多有2^(i-1)个结点（i表示层数）。第一层最多1个，第二层最多2个，第三层最多4个，以此类推。深度为k时，总结点数最多为1+2+4+...+2^(k-1)=2^k-1。这是满二叉树的定义，也是深度为k的二叉树所能达到的最大结点数。所以该说法正确。74.【参考答案】B【解析】堆排序分为建堆和排序两个阶段。建堆的时间复杂度为O(n)，将n个元素调整为大顶堆或小顶堆。排序阶段需要执行n-1次，每次将堆顶元素与末尾元素交换，然后重新调整堆，每次调整的时间复杂度为O(logn)。所以总的时间复杂度为O(n)+O(nlogn)=O(nlogn)。堆排序是一种高效的排序算法，且不需要额外的存储空间。75.【参考答案】A【解析】快速排序在最坏情况下（如待排序序列已经有序）的时间复杂度为O(n²)，此时每次划分都只能减少一个元素。堆排序和归并排序的最坏时间复杂度都是O(nlogn)，性能稳定。希尔排序的时间复杂度取决于增量序列的选择，一般优于O(n²)。因此最坏情况下时间复杂度为O(n²)的排序算法是快速排序。76.【参考答案】A【解析】冒泡排序的第一趟扫描从前往后比较相邻元素，如果前一个大于后一个则交换。49和38比较，交换得(38,49,...)。49和65不交换。65和97不交换。97和76交换得(76,97)。97和13交换得(13,97)。13和27不交换。27和49'交换得(27,49')。49'和97不交换。第一趟结束后97被冒泡到最后一位，结果为(38,49,65,76,13,27,49',97)。77.【参考答案】C【解析】装填因子α=表中记录数/哈希表长度。链地址法将所有哈希地址相同的记录链接在同一链表中，平均查找长度只与链表长度有关，即与记录数成正比，与装填因子无关。线性探测法和二次探测法都是开放定址法，平均查找长度与装填因子密切相关，装填因子越大，查找性能越差。再哈希法也与装填因子有关。78.【参考答案】B【解析】二叉搜索树的查找性能取决于树的形态。当树比较平衡时，查找时间复杂度为O(logn)。但当树退化成链状（所有结点只有左孩子或只有右孩子）时，查找需要遍历所有结点，时间复杂度为O(n)。这就是最坏情况。为了避免这种情况，可以使用平衡二叉搜索树（如AVL树或红黑树），确保查找时间复杂度为O