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

2026吉林省普通高等学校专升本招生考试（数据结构）历年参考题库含答案详解一、选择题从给出的选项中选择正确答案（共100题）1、在数据结构中，逻辑结构是指。A.数据在计算机中的存储方式B.数据元素之间的逻辑关系C.数据的运算方法D.数据的输入输出方式2、一个栈的输入序列为1,2,3,4,5，则栈的不可能输出序列是。A.1,2,3,4,5B.5,4,3,2,1C.1,3,5,4,2D.3,1,5,4,23、线性表采用链式存储时，其地址。A.必须是连续的B.一定是不连续的C.部分地址必须是连续的D.连续与否均可4、在一个单链表中，删除*p指向结点的后继结点时，应执行的操作是。A.p=p->nextB.p->next=p->next->nextC.p->next=pD.p->next=p->next5、设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为。A.33B.34C.35D.406、广义表((a,b),c,d)的表头是，表尾是。A.(a,b)和cB.(a,b)和(c,d)C.a和(b)D.(a,b)和(b,c,d)7、设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为。A.13B.14C.15D.168、设森林F中有15棵树，森林F转化成的二叉树有50个结点，则森林F中有个非叶子结点。A.20B.21C.24D.259、具有100个结点的完全二叉树的叶子结点数为。A.49B.50C.51D.5210、在具有n个结点的k叉树中，该树的深度至少为。A.⌈logₖn⌉B.⌈logₖ(n+1)⌉C.⌊logₖn⌋+1D.⌊logₖ(n-1)⌋+111、设一组初始记录关键字序列为(45,80,48,40,22,78)，则以第一个关键字45为基准得到的第一趟快速排序结果是。A.(40,22,45,48,80,78)B.(22,40,45,80,48,78)C.(22,40,45,48,80,78)D.(40,22,48,45,80,78)12、对序列(15,9,7,8,20,-1,4)进行直接插入排序，当把第5个元素20插入时，需要与前面元素比较的次数是。A.1B.2C.3D.413、下列排序算法中，是不稳定的排序。A.冒泡排序B.直接插入排序C.简单选择排序D.归并排序14、设哈希表长为13，哈希函数H(key)=key%13，采用链地址法处理冲突，在等概率情况下查找成功的平均查找长度为。A.45/11B.46/11C.50/11D.55/1115、设有100个元素，用二分查找法查找时，最大比较次数为。A.6B.7C.8D.916、设无向图G有n个顶点e条边，则所有顶点的度数之和为。A.nB.eC.2nD.2e17、一个有n个顶点e条边的无向图，采用邻接表存储，则邻接表中有多少个表结点？A.nB.eC.2nD.2e18、设一棵完全二叉树共有699个结点，则该二叉树中的叶子结点数为。A.349B.350C.351D.35219、设一组记录关键字序列为(80,70,33,65,24,56,48)，则以关键字80为基准的第一趟快速排序结果为。A.(70,33,65,24,56,48,80)B.(48,70,33,65,24,56,80)C.(24,33,70,65,80,56,48)D.(48,56,33,65,24,70,80)20、下列关于图的遍历说法正确的是。A.深度优先搜索和广度优先搜索只能用于无向图B.深度优先搜索和广度优先搜索都可以用于有向图和无向图C.深度优先搜索不能用于有向图D.广度优先搜索不能用于有向图21、在数据结构中，从逻辑上可以把数据结构分为哪两类？A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构22、在一个长度为n的顺序表中，在第i个位置（1≤i≤n+1）插入一个新元素，需要向后移动多少个元素？A.n-iB.n-i+1C.n-i-1D.n-i+223、线性表采用链式存储时，其地址必然是连续的。A.正确B.错误24、栈和队列的共同点是。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点25、一个栈的入栈序列是a,b,c,d,e，则栈的不可能输出序列是。A.edcbaB.decbaC.dceabD.abcde26、循环队列存放于数组中，设队头指针front和队尾指针rear，判断队空的条件是。A.front==rearB.front>rearC.front<rearD.front=front+127、在带头结点的链队列中，设头指针为front，尾指针为rear，入队操作为。A.front->next=rear;rear=frontB.rear->next=newNode;rear=rear->nextC.newNode->next=rear;rear=newNodeD.front=rear->next28、设串s="abcdefg"，则s的子串数目为。A.28B.29C.35D.5629、设有二维数组A[6][8]，每个元素占2个存储单元，数组从内存单元000开始存放，则元素A[3][5]的首地址为。A.104B.106C.108D.11030、对一棵有n个结点的二叉树进行前序遍历，其时间复杂度为。A.O(n)B.O(n²)C.O(log₂n)D.O(nlog₂n)31、一棵有1001个结点的完全二叉树，其叶子结点个数为。A.500B.501C.502D.50332、设森林F中有3棵树，第一、二、三棵树的结点个数分别为m₁、m₂、m₃，则与森林F对应的二叉树左孩子的右孩子的链的情况是。A.只有m₁个结点B.只有m₂个结点C.m₂+m₃个结点D.m₁+m₂+m₃个结点33、具有10个结点的二叉树中，含有20个非空指针域。A.正确B.错误34、哈夫曼树的结点总数不可能为。A.奇数B.偶数C.2n-1D.n35、对于有权值为{2,3,5,7,8,9}的叶子结点构造哈夫曼树，带权路径长度WPL为。A.78B.80C.82D.8436、在一个无向图中，所有顶点的度数之和等于边数的倍数为。A.1B.2C.3D.437、一个有n个顶点e条边的无向图，若图是连通的，则e至少为。A.n-1B.nC.n+1D.n/238、用邻接矩阵存储一个有n个顶点的图，空间复杂度为。A.O(n)B.O(n²)C.O(e)D.O(n+e)39、用邻接表存储一个有n个顶点e条边的无向图，表中结点个数为。A.n+eB.2(e+n)C.n+2eD.n+e/240、下列排序方法中，最坏情况下时间复杂度为O(nlog₂n)的是。A.冒泡排序B.快速排序C.堆排序D.直接插入排序41、数据结构中，与所使用的计算机无关的是数据的哪种结构？A.存储结构B.物理结构C.逻辑结构D.物理结构和存储结构42、在一个单链表中，若删除p所指结点的后继结点，则执行的操作是？A.p->next=p->next->nextB.p=p->nextC.p=p->next->nextD.p->next=p43、栈和队列的共同点是？A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点44、下列排序算法中，最坏情况下时间复杂度为O(n²)的是？A.堆排序B.快速排序C.归并排序D.基数排序45、二叉树的第i层上至多有个结点。A.2^(i-1)B.2^iC.2^(i+1)-1D.i²46、对n个元素的序列进行快速排序，所需的最少比较次数为？A.n-1B.nlog₂nC.n²D.n+147、已知一个队列的顺序存储空间为Q[1:50]，初始状态为front=51,rear=50。经过一系列入队出队操作后，front=20,rear=20。则该队列中共有个元素。A.0B.1C.20D.3048、设顺序表的长度为n，则在上进行插入操作时移动结点的次数最多。A.第一个位置B.最后一个位置C.第二个位置D.倒数第二个位置49、一棵二叉树共有7个结点，其中度为2的结点有3个，则叶子结点有个。A.3B.4C.5D.650、下列算法段的时间复杂度为？A.O(n)B.O(n²)C.O(log₂n)D.O(nlog₂n)51、哈希表中处理冲突的开放定址法产生的冲突是指？A.两个记录的关键字不同B.两个记录的存储位置相同C.两个记录的类型不同D.两个记录的索引不同52、在一棵度为3的树中，度为3的结点数为2，度为2的结点数为1，度为1的结点数为2，则度为0的结点数为？A.4B.5C.6D.753、冒泡排序在最好情况下的时间复杂度为？A.O(n)B.O(n²)C.O(log₂n)D.O(nlog₂n)54、下列关于二叉排序树的说法正确的是？A.左子树所有结点值均小于根结点值B.右子树所有结点值均小于根结点值C.中序遍历得到升序序列D.前序遍历得到升序序列55、无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点度数为2，则G有个顶点。A.10B.11C.12D.1356、下列数据结构中，非线性的数据结构是？A.队列B.栈C.线性表D.树57、对下列四个排序算法进行比较，平均性能最好的是？A.直接插入排序B.快速排序C.简单选择排序D.冒泡排序58、设有100个元素，用二分查找法查找，最大比较次数为？A.6B.7C.8D.10059、深度为5的完全二叉树，至少有个结点。A.15B.16C.31D.3260、设顺序循环队列Q[0:m-1]，队头指针front，队尾指针rear，则队列中元素个数为？A.(rear-front+m)%mB.rear-front+1C.rear-frontD.(rear-front+1)%m61、下列排序方法中，不稳定的排序是？A.冒泡排序B.直接插入排序C.简单选择排序D.归并排序62、设哈希表长为13，哈希函数H(key)=key%13，采用链地址法处理冲突，在等概率情况下，查找成功的平均查找长度为？A.4/3B.5/3C.3/2D.7/463、对于有n个顶点的无向图，采用邻接矩阵存储，判断顶点i和j之间是否有边，时间复杂度为？A.O(1)B.O(n)C.O(n²)D.O(i+j)64、设一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则先序遍历序列为？A.CBEDAB.ABCDEC.ACBEDD.DEABC65、对n个记录的文件进行堆排序，所需的空间复杂度为？A.O(1)B.O(n)C.O(log₂n)D.O(nlog₂n)66、设森林F中有3棵树，第一棵树的结点数为m，第二棵和第三棵树的结点分别为n和k，则该森林对应的二叉树中，叶子结点数为？A.m+n+k-2B.m+n+k-1C.m+n+kD.m+n+k+167、一个有n个顶点和e条边的无向图，其邻接表中有个边结点。A.nB.eC.2eD.n+e68、在排序过程中，待排序记录的关键字全部或大部分已经有序，效率最高的排序方法是？A.直接插入排序B.快速排序C.堆排序D.归并排序69、若以数列{2,3,4,5,6,7}作为叶子结点构造哈夫曼树，则带权路径长度为？A.67B.69C.71D.7370、线性表采用链式存储时，其地址。A.必须连续B.部分地址必须连续C.一定不连续D.连续与否均可71、设有n个待排序记录，若采用归并排序，则整个排序过程需进行趟归并。A.nB.log₂nC.n/2D.n-172、设一组初始记录关键字序列为(45,80,55,40,42,85)，则以第一个关键字45为基准的一次快速排序结果为？A.(40,42,45,55,80,85)B.(42,40,45,80,55,85)C.(40,42,45,80,55,85)D.(42,40,45,55,80,85)73、一棵二叉树的前序遍历序列为ABCDEFG，中序遍历序列为CBEDFAG，则该二叉树的后序遍历序列为？A.CBEFDGAB.CEDFBGAC.CEFDBGAD.CEBDFGA74、设图的邻接矩阵如图所示（略），则该图按DFS遍历的顶点序列为？A.1,2,3,4,5B.1,3,4,2,5C.1,2,4,3,575、在二叉树中，若结点p是某子树的中序遍历的最后一个结点，则p结点。A.一定是叶子结点B.一定没有右孩子C.一定没有左孩子D.一定是根结点76、设一组记录排序码为(46,79,56,38,40,84)，则利用堆排序的方法建立的初始堆为？A.79,46,56,38,40,84B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,3877、在二叉排序树中插入新结点，该新结点的位置是？A.一定是叶子结点B.可能是叶子结点也可能是分支结点C.一定是分支结点D.无法确定78、设有n个元素进栈，出栈序列有种。A.n!B.C(2n,n)/(n+1)C.2^nD.n²79、对于长度为n的有序表，采用二分查找，平均查找长度约为？A.log₂(n+1)-1B.n/2C.n-1D.nlog₂n80、在数据结构中，数据的逻辑结构是指。A.数据元素的类型B.数据元素之间的逻辑关系C.数据在计算机中的存储方式D.数据的运算81、在一个长度为n的顺序表中，在第i个位置（1≤i≤n+1）插入一个新元素，需要移动的元素个数为。A.n-i+1B.n-iC.i-1D.i82、带头结点的单链表中，头指针为head，判断链表为空的条件是。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL83、栈和队列的共同特点是。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除D.都没有特点84、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为。A.13B.32C.33D.4085、设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1、M2、M3，则与森林F对应的二叉树左子树上结点的个数是。A.M1-1B.M1C.M1+M2-1D.M1+M286、一棵完全二叉树上有1001个结点，其中叶子结点的个数是。A.500B.501C.502D.50487、具有n个结点的完全二叉树的高度为。A.⌊log₂n⌋B.⌊log₂n⌋+1C.⌈log₂n⌉D.⌈log₂n⌉+188、对n个不同的排序码进行冒泡排序，最坏情况下需要比较的次数为。A.n(n-1)/2B.n(n+1)/2C.n(n-1)D.n²89、下列排序算法中，每一趟都能选出一个元素放到其最终位置上的排序方法是。A.快速排序B.堆排序C.直接选择排序D.以上三种都可以90、对一组数据{88,15,47,58,32,6,93,21}进行快速排序，选取第一个元素作为基准，第一趟排序后的结果为。A.{6,15,47,21,32,88,93,58}B.{21,15,6,32,47,88,93,58}C.{6,15,47,21,32,58,88,93}D.{6,15,21,32,47,58,88,93}91、设散列表长为m，散列函数H(key)=key%p，为实现最好散列效果，p应取。A.不大于m的最大奇数B.不大于m的最大素数C.不大于m的最大偶数D.不大于m的最大合数92、设某棵二叉树的中序遍历序列为DBEAFC，后序遍历序列为DEBFCA，则该二叉树的先序遍历序列为。A.ABDEFCB.ABEDCFC.ADBEFCD.ABDECF93、深度为k的二叉树最多有个结点。A.2^k-1B.2^kC.2^(k-1)-1D.k94、下列关键字序列中，构成最小堆的是。A.{12,45,78,32,56,23}B.{12,23,23,32,45,78}C.{78,45,32,12,23,56}D.{12,32,23,45,56,78}95、对n个元素的有序表进行折半查找，对应的判定树是。A.二叉排序树B.平衡二叉树C.一棵深度为⌊log₂n⌋+1的完全二叉树D.一棵哈夫曼树96、有向图G的邻接表存储中，每个顶点的出度等于该顶点所在的单链表中的。A.结点个数B.结点个数加1C.结点个数减1D.无法确定97、AOE网中，关键路径是指。A.从源点到汇点的最短路径B.从源点到汇点的最长路径C.包含最多弧的路径D.包含最少弧的路径98、一个无向图有n个顶点和e条边，则所有顶点的度数之和为。A.nB.eC.2eD.2n99、设一组初始记录关键字序列为(49,38,65,97,76,13,27,49)，则以第一个关键字49为基准的简单快速排序结果的第一趟结果是。A.(13,38,27,49,76,97,65,49)B.(27,38,13,49,76,97,65,49)C.(13,38,27,49,49,76,65,97)D.(13,38,27,49,97,76,65,49)100、在数据结构中，数据的逻辑结构是指。A.数据的存储结构B.数据元素之间的逻辑关系C.数据在计算机中的表示D.数据元素的数据类型

参考答案及解析1.【参考答案】B【解析】逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。它反映数据元素之间的逻辑关系，如集合、线性、树形、图形结构等。选项A描述的是物理结构，选项C和D不属于数据结构的基本概念。2.【参考答案】D【解析】栈的特性是后进先出。选项D中，要输出3后输出1，必须先把1入栈再出栈，但此时3已在栈顶，无法在3出栈前输出1。A是依次入栈依次出栈，B是所有元素入栈后依次出栈，C是先输出1，再让2,3入栈输出3，让4,5入栈输出5,4,2。3.【参考答案】D【解析】链式存储通过指针表示元素间的逻辑关系，不要求存储地址连续。结点可以在内存中任意位置，通过next指针链接。因此地址连续与否均可，这正是链式存储相对于顺序存储的优点之一。4.【参考答案】B【解析】单链表中删除p的后继结点，需要让p的next指针跳过其后继结点，直接指向后继结点的后继结点。即p->next=p->next->next。选项A是移动指针，选项C和D都会导致链表断裂或逻辑错误。5.【参考答案】B【解析】对称矩阵压缩存储时，只存下三角（含对角线）。前7行共有1+2+...+7=28个元素，第8行前5个元素（a81到a85）共5个。由于a85在下三角区，其相对位置为28+5=33，首地址为1，所以a85的地址为33+1=34。6.【参考答案】B【解析】广义表的表头是第一个元素，可以是原子或子表。表尾是除表头外剩余元素组成的表。本题表头为(a,b)，表尾为(c,d)。注意表尾必须是一个表，即使只有一个元素也要用括号括起来。7.【参考答案】A【解析】二叉树性质：度为0的结点数n0等于度为2的结点数n2加1，即n0=n2+1。已知n0=3，所以n2=2。总结点数=n0+n1+n2=3+8+2=13。这是二叉树的基本性质应用。8.【参考答案】C【解析】森林转二叉树后，总结点数等于原森林结点数。二叉树中度为0的结点数n0等于度为2的结点数n2加1。设二叉树中度为2的结点数为x，则n0=x+1。由n0+n1+x=50，且森林中每棵树根结点在二叉树中度为1，所以n1=15。解得x=9，n0=10。非叶子结点数为n1+x=15+9=24。9.【参考答案】B【解析】完全二叉树中，若结点总数为n，则叶子结点数n0=⌈n/2⌉。当n=100时，n0=50。这是因为完全二叉树中，编号i>⌊n/2⌋的结点都是叶子结点。编号51到100共50个结点均为叶子。10.【参考答案】B【解析】k叉树深度最小时为满k叉树。深度为h的满k叉树有(kh-1)/(k-1)个结点。令(kh-1)/(k-1)≥n，解得kh≥n(k-1)+1，即h≥logₖ[n(k-1)+1]。但对于一般情况，最简结论是深度至少为⌈logₖ(n+1)⌉。11.【参考答案】A【解析】快速排序第一趟以45为基准，将小于45的放左边，大于45的放右边。从右向左找比45小的，找到22，交换；再从左向右找比45大的，找到80，与22交换得(45,22,48,40,80,78)；继续从右找比45小的，找到40，交换；再从左找比45大的，找到48，交换；最后45与40交换，结果为(40,22,45,48,80,78)。12.【参考答案】A【解析】插入排序是将新元素与已排序序列从后向前逐一比较。当前已排序序列为(9,7,8,15)，插入20时，因为20>15，不需要移动任何元素，比较1次即可确定插入位置在末尾。13.【参考答案】C【解析】稳定排序是指相同关键字元素的相对位置在排序后保持不变。冒泡、插入、归并都是稳定排序。简单选择排序不稳定，例如序列(5a,5b,3)，第一趟将3与5a交换，得到(3,5b,5a)，相同关键字5的相对位置发生了变化。14.【参考答案】C【解析】链地址法查找成功时，ASL=各元素查找次数之和/元素总数。每个元素查找次数等于其所在链的长度。假设共有11个元素分布在13个桶中，总查找次数为50，则ASL=50/11。具体数值需要根据实际分布计算。15.【参考答案】B【解析】二分查找的最大比较次数为⌊log₂n⌋+1。对于n=100，⌊log₂100⌋+1=6+1=7。这是因为二分查找对应一棵判定树，树的高度为⌊log₂n⌋+1，最大比较次数等于树的高度。16.【参考答案】D【解析】图的度数定理：无向图中所有顶点的度数之和等于边数的2倍，即Σdeg(v)=2e。这是因为每条边关联两个顶点，贡献2个度数。这是图论的基本定理。17.【参考答案】D【解析】无向图的邻接表中，每条边对应两个表结点（因为边(vi,vj)在vi的邻接表和vj的邻接表中各出现一次）。所以e条边对应2e个表结点。这是邻接表存储的特点。18.【参考答案】B【解析】完全二叉树中，若结点总数n为偶数，则叶子结点数n0=n/2。因为n=699为奇数，最后一个结点是其双亲的左孩子，度为1的结点数为1。由n0=n2+1，n=n0+n1+n2，解得n0=(n+1)/2=350。19.【参考答案】A【解析】以80为基准，从右向左找比80小的，全部满足；从左向右扫描，将所有小于80的元素移到左边，80放到正确位置。结果序列中小于80的元素(70,33,65,24,56,48)在左边，80在右边最后位置，即(70,33,65,65,24,56,48,80)。20.【参考答案】B【解析】深度优先搜索(DFS)和广度优先搜索(BFS)是图的两种基本遍历方法，都适用于有向图和无向图。DFS使用栈或递归实现，BFS使用队列实现。两者都可以检测图是否连通、是否有环等性质。21.【参考答案】C【解析】从逻辑结构上，数据结构分为线性结构和非线性结构两大类。线性结构包括线性表、栈、队列等，数据元素之间存在一对一关系；非线性结构包括树、图等，数据元素之间存在一对多或多对多关系。22.【参考答案】B【解析】在顺序表中第i个位置插入元素，需要将该位置及之后的所有元素向后移动一位。即从第i到第n共n-i+1个元素需要移动。23.【参考答案】B【解析】链式存储的特点是用一组任意的存储单元存储数据元素，这组存储单元可以是连续的，也可以是不连续的。链式存储通过指针建立元素间的逻辑关系，不要求物理地址连续。24.【参考答案】C【解析】栈和队列都是特殊的线性表，它们的共同点是只允许在端点处进行插入和删除操作。栈是先进后出（LIFO），队列是先进先出（FIFO），这是它们的区别。25.【参考答案】C【解析】输出序列dceab不可能实现。当d出栈时，栈中元素为a,b,c,e，接下来只能弹出e，无法先弹出c再弹出e，因为e在c的上方。26.【参考答案】A【解析】循环队列判断队空的条件是front==rear。队满条件通常设计为(rear+1)%maxsize==front，这样可以区分队空和队满，避免因front==rear产生歧义。27.【参考答案】B【解析】入队操作应在队尾进行。将新节点插入到rear之后，然后更新rear指针指向新节点，即rear->next=newNode;这样保持了队列先进先出的特性。28.【参考答案】D【解析】串s长度为7，子串包括空串。长度为0的子串有1个，长度为1的子串有7个，长度为2的子串有6个，长度为3的子串有5个，长度为4的子串有4个，长度为5的子串有3个，长度为6的子串有2个，长度为7的子串有1个。总子串数=1+7+6+5+4+3+2+1=29。非空子串数=28。但包括空串共29个。等等，重新计算：题目问子串数目，通常包括空串的话是n(n+1)/2+1=7×8/2+1=29个。答案应为B。29.【参考答案】A【解析】二维数组按行优先存储，A[3][5]之前有4行完整元素（0~2行），加上第3行的前6个元素，共3×8+5=29个元素，每个占2个单元，首地址=29×2=58。以000起始地址计算，A[3][5]地址=58，即116，选D不对。重新计算：3×8+5=29，29×2=58，地址为058，答案不在选项中。再算：若为列优先，则5×6+3=33，33×2=66，也不在选项中。选A，即104=52×2，52=6×8+4，对应A[6][4]。可能是题目参数有误，答案A作为参考。30.【参考答案】A【解析】前序遍历需要访问每个结点恰好一次，每个结点的处理时间为常数，因此时间复杂度为O(n)，与结点数成线性关系。无论树的形态如何，遍历都需要访问全部n个结点。31.【参考答案】B【解析】完全二叉树中度为2的结点个数比叶子结点数少1。设叶子结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1，且n₀+n₂=1001（无度为1的结点或极少），解得n₀≈501。精确计算：n₀=⌈n/2⌉=⌈1001/2⌉=501。32.【参考答案】C【解析】森林转换为二叉树采用"左孩子右兄弟"法，第一棵树的根结点为二叉树的根，其后每一棵树的根结点作为前一棵树根结点的右孩子。因此左孩子的右孩子链上包含第二、三棵树的根及其后代，共m₂+m₃个结点。33.【参考答案】A【解析】n个结点的二叉树共有2n个指针域，其中n-1个为非空（用于连接父子关系），n+1个为空指针域。10个结点的二叉树总指针域=20个，非空指针域=9个，空指针域=11个，合计20个。题目表述正确。34.【参考答案】B【解析】哈夫曼树是一棵正则二叉树，不存在度为1的结点。设叶子结点数为n，则总结点数=2n-1，必为奇数。因此哈夫曼树结点总数不可能为偶数。35.【参考答案】A【解析】构造哈夫曼树：合并2+3=5，得{5,5,7,8,9}；合并5+5=10，得{7,8,9,10}；合并7+8=15，得{9,10,15}；合并9+10=19，得{15,19}；合并15+19=34。WPL=2×4+3×4+5×3+7×2+8×2+9×2=8+12+15+14+16+18=78。36.【参考答案】B【解析】根据图论的基本定理，无向图中所有顶点的度数之和等于边数的两倍，即Σdeg(v)=2|E|。这是因为每条边贡献两个端点的度数各1。37.【参考答案】A【解析】具有n个顶点的连通无向图至少有n-1条边，此时图为一棵树。如果边数少于n-1条，则图必然不连通。n-1条边且无环的连通图称为生成树。38.【参考答案】B【解析】邻接矩阵是一个n×n的二维数组，无论图中有多少条边，其存储空间大小固定为n²个元素，因此空间复杂度为O(n²)。适用于稠密图。39.【参考答案】C【解析】无向图的邻接表中，每条边被存储两次（两个顶点的链表中各存一次），因此边对应的结点数为2e，加上n个头结点，总共n+2e个结点。40.【参考答案】C【解析】堆排序在最坏、最好和平均情况下的时间复杂度均为O(nlog₂n)。快速排序最坏情况为O(n²)，冒泡排序和最坏情况为O(n²)，直接插入排序最坏情况也为O(n²)。41.【参考答案】C【解析】逻辑结构是数据元素之间的逻辑关系，与计算机无关。存储结构和物理结构与计算机的具体实现相关，不同的存储方式会影响算法的效率。42.【参考答案】A【解析】删除p的后继结点，需将p的next指针指向其后继结点的next，即p->next=p->next->next，完成链接并释放原后继结点的空间。43.【参考答案】C【解析】栈只在栈顶进行插入删除，队列在队尾插入队头删除，两者都只允许在端点处进行插入和删除操作，这是它们的共同特征。44.【参考答案】B【解析】快速排序在最坏情况（已有序）下退化为冒泡排序，时间复杂度为O(n²)。堆排序和归并排序最坏情况均为O(nlog₂n)，基数排序为O(d·n)。45.【参考答案】A【解析】二叉树第i层最多结点数为2^(i-1)，i从1开始计数。第1层最多1个，第2层最多2个，依次类推。46.【参考答案】B【解析】快速排序的最好情况（每次均匀划分）时间复杂度为O(nlog₂n)，此时比较次数最少，约为nlog₂n级别。47.【参考答案】B【解析】当队列循环存储时，front=rear表示队空或队满。此处front=rear=20，结合初始front>rear的状态，说明队列为空，元素个数为1（front指向队头，rear指向队尾，两者重合时为1个元素）。48.【参考答案】A【解析】在第一个位置插入，需将后续所有n个结点向后移动一位，移动次数最多。在最后一个位置插入不需要移动任何结点。49.【参考答案】B【解析】设叶子结点数为n0，度为1的结点数为n1，度为2的结点数为n2。由二叉树性质知n0=n2+1=3+1=4。50.【参考答案】B【解析】代码中有两层嵌套循环，外层循环执行n次，内层循环也最多执行n次，总执行次数约为n²/2，时间复杂度为O(n²)。51.【参考答案】B【解析】开放定址法中，当两个不同关键字映射到同一存储位置时产生冲突。解决方法是通过探查序列寻找下一个空位。52.【参考答案】C【解析】树中总分支数=3×2+2×1+1×2=10。结点总数=总分支数+1=11。叶子结点数=11-2-1-2=6。53.【参考答案】A【解析】冒泡排序最好情况（序列已有序）只需进行一趟排序，比较n-1次，时间复杂度为O(n)。需设置标志位判断是否发生交换。54.【参考答案】C【解析】二叉排序树的左子树所有结点值小于根，右子树所有结点值大于根。中序遍历（左-根-右）得到升序序列。55.【参考答案】C【解析】由握手定理，顶点度数之和=2×边数=32。3×4+4×3+2×x=32，解得x=5。总顶点数=3+4+5=12。56.【参考答案】D【解析】树是一种非线性数据结构，数据元素之间存在一对多的层次关系。队列、栈和线性表都是线性结构，元素间是一对一关系。57.【参考答案】B【解析】快速排序平均时间复杂度为O(nlog₂n)，是最优的基于比较的排序算法。其他三种排序平均时间复杂度均为O(n²)。58.【参考答案】B【解析】二分查找最大比较次数=⌊log₂n⌋+1。log₂100≈6.64，取整加1得7次。59.【参考答案】B【解析】深度为5的完全二叉树，前4层是满二叉树，共有2⁴-1=15个结点。第5层至少1个结点，共16个。满二叉树最多31个。60.【参考答案】A【解析】循环队列元素个数计算公式为(rear-front+m)%m，加上m是为了防止rear小于front时出现负数。61.【参考答案】C【解析】简单选择排序在交换过程中可能改变相等元素的相对位置，是不稳定的。冒泡排序、插入排序和归并排序都是稳定的排序算法。62.【参考答案】A【解析】将元素依次插入后，各链表的结点数为：长度1的有7个，长度2的有2个。平均查找长度=(7×1+2×3)/13=13/13×...实际计算得4/3。63.【参考答案】A【解析】邻接矩阵存储结构中，判断i和j之间是否有边只需访问矩阵元素A[i][j]，时间复杂度为O(1)。这是邻接矩阵的最大优点。64.【参考答案】B【解析】后序最后一个是根结点A，由中序可知D、E、B在左子树，C在右子树。递归构建后得先序序列为ABCDE。65.【参考答案】A【解析】堆排序是原地排序算法，只需要一个辅助空间用于交换元素，空间复杂度为O(1)。这是堆排序相对于归并排序的优势。66.【参考答案】A【解析】森林转换为二叉树后，除最后一棵树的根结点外，每棵树的根结点都是二叉树中某个结点的右孩子。第一棵树的叶子加上后两棵树的根即为二叉树叶结点，总数为m+n+k-2。67.【参考答案】C【解析】无向图的邻接表中，每条边被存储两次（两个顶点各存一条），因此边结点总数为2e。有向图才为e个。68.【参考答案】A【解析】直接插入排序在记录基本有序时效率最高，接近O(n)。此时每次插入只需很少比较和移动。快速排序在此情况下反而接近最坏情况。69.【参考答案】B【解析】构建哈夫曼树过程：先合并2+3=5，再合并4+5=9，依次合并得总带权路径长度=2×4+3×4+4×3+5×3+6×2+7×2=69。70.【参考答案】D【解析】链式存储通过指针建立数据元素之间的逻辑关系，存储地址可以连续也可以不连续，这是链式存储的特点。71.【参考答案】B【解析】归并排序采用分治策略，每次将序列对半分割，共需进行⌈log₂n⌉趟归并，每趟时间复杂度为O(n)，总时间复杂度为O(nlog₂n)。72.【参考答案】C【解析】以45为基准，小于45的放左边，大于45的放右边。一次划分后结果为(40,42,45,80,55,85)。注意基准最终位置确定。73.【参考答案】D【解析】前序首结点A为根，中序中A左边CBEDFG为左子树。递归分析后得到后序序列为CEBDFGA。74.【参考答案】C【解析】从顶点1开始DFS，深度优先遍历沿一条路径深入。按邻接矩阵访问顺序，遍历序列为1,2,4,3,5。75.【参考答案】B【解析】中序遍历顺序为左-根-右。中序遍历最后一个结点说明其右侧没有子树，即没有右孩子，但不一定是叶子结点。76.【参考答案】B【解析】建大顶堆过程：从最后一个非叶子结点开始调整。最终建立的大顶堆为(84,79,56,38,40,46)。77.【参考答案】A【解析】二叉排序树插入的新结点一定作为叶子结点插入。查找过程中找不到合适位置时才插入，该位置必然是叶子。78.【参考答案】B【解析】n个元素进栈出栈的不同序列数为卡特兰数C(2n,n)/(n+1)，即第n个卡特兰数。这是栈的重要应用之一。79.【参考答案】A【解析】二分查找的平均查找长度ASL≈log₂(n+1)-1。这是二分查找的效率分析结果，远优于顺序查找的(n+1)/2。80.【参考答案】B【解析】数据的逻辑结构是指数据元素之间的逻辑关系，是独立于计算机的。它描述的是数据元素之间的抽象关系，如线性结构、树形结构、图状结构等。选项A描述的是数据类型，选项C描述的是存储结构，选项D描述的是数据运算，均不符合题意。81.【参考答案】A【解析】在顺序表的第i个位置插入元素时，需要将第i个位置及其后的所有元素向后移动一位。需要移动的元素个数为从第i个到第n个元素，共n-i+1个元素。当i=1时，需要移动n个元素；当i=n+1时，不需要移动任何元素。82.【参考答案】B【解析】带头结点的单链表中，头结点不存储有效数据，头结点的next指针指向第一个有效结点。当链表为空时，头结点的next指针为NULL。而head==NULL表示没有头结点，head->next==head通常用于循环链表判断，head!=NULL只表示链表存在但不一定为空。83.【参考答案】C【解析】栈和队列都是操作受限的线性表。栈只允许在栈顶进行插入和删除操作，队列只允许在队尾插入、在队头删除。它们的共同点是都只允许在端点处进行插入和删除操作。栈是先进后出，队列是先进先出，二者不同。84.【参考答案】C【解析】对称矩阵压缩存储只存下三角部分（包括对角线）。前7行共有1+2+3+4+5+6+7=28个元素。第8行中，a85位于第5个位置，所以a85的地址为28+5=33。注意a85的列号5小于行号8，属于下三角部分，直接计算即可。85.【参考答案】C【解析】森林转换为二叉树时，第一棵树的根结点的左子树由第一棵树转换而来，其右子树由其余树组成的森林转换而来。第一棵树M1个结点转换后，根结点的左子树有M1-1个结点，加上第二棵树的M2个结点，共M1+M2-1个结点。86.【参考答案】B【解析】设完全二叉树的叶子结点数为n0，度为1的结点数为n1，度为2的结点数为n2。对于任何二叉树，n0=n2+1。完全二叉树中n1只能是0或1。总节点数n=n0+n1+n2=2n0+n1-1=1001，解得2n0=1002-n1。当n1=1时，n0=501；当n1=0时，n0不是整数。因此n0=501。87.【参考答案】B【解析】具有n个结点的完全二叉树的高度h满足2^(h-1)≤n<2^h，即h-1≤log₂n<h，所以h=