2026年大学试题(计算机科学)-数据结构历年参考题库含答案解析

2026年大学试题(计算机科学)-数据结构历年参考题库含答案解析一、选择题从给出的选项中选择正确答案（共100题）1、在CSSFlexbox布局中，align-items属性的默认值是什么？A.stretchB.centerC.flex-startD.flex-end2、以下哪个HTTP状态码表示请求资源未被找到？A.200B.301C.404D.5003、在JavaScript异步编程中，Promise的三种状态不包括以下哪项？A.pendingB.fulfilledC.rejectedD.closed4、以下哪个标签语义上最适合用于展示文章的发布日期？A.<time>B.<date>C.<span>D.<div>5、在顺序存储的线性表中，按值查找操作的时间复杂度为多少？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、一个栈的入栈序列为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,57、下列关于哈夫曼树的叙述正确的是：A.哈夫曼树一定是完全二叉树B.哈夫曼树中权值越大的节点离根节点越远C.哈夫曼树中权值越大的节点离根节点越近D.带权路径长度最小的二叉树不一定是哈夫曼树8、在图G中，顶点集V={1,2,3,4}，边集E={(1,2),(2,3),(3,4),(4,1),(1,3)}，该图的连通分量个数为：A.1B.2C.3D.49、下列排序算法中，平均时间复杂度为O(nlogn)的是：A.冒泡排序B.直接插入排序C.快速排序D.简单选择排序10、二叉树第i层上至多有个节点（i≥1）：A.i-1B.iC.2^(i-1)D.2^i-111、对初始状态为递增有序的下表进行排序，最省时间的算法是：A.快速排序B.堆排序C.直接插入排序D.归并排序12、设一组记录关键字为(46,79,56,38,40,84)，则利用堆排序方法建立的初始堆为：A.{79,46,56,38,40,84}B.{84,79,56,46,40,38}C.{84,56,79,40,46,38}D.{84,79,56,40,46,38}13、对N个关键字作直接选择排序，进行简单选择排序所需的比较次数和移动次数分别为：A.比较和移动次数均为O(N²)B.比较次数为O(N²)，移动次数为O(C.比较和移动次数均为O(D.比较次数为O(E.，移动次数为O(N²)14、一个有N个元素的有序表进行二分查找时，查找长度为4的元素最多有多少个：A.4个B.8个C.16个D.取决于表的大小15、散列表装填因子α等于：A.散列表的长度/填入表中的元素个数B.填入表中的元素个数/散列表的长度C.散列函数的周期/散列表长度D.发生冲突的元素个数/填入表中的元素个数16、在一棵度为3的树中，度为3的节点数为2，度为2的节点数为1，度为1的节点数为2，则度为0的节点数为：A.4B.5C.6D.717、下列叙述中正确的是：A.循环队列的队头指针一定小于队尾指针B.循环队列的队头指针可以大于队尾指针C.循环队列的元素个数等于队尾指针减队头指针D.循环队列不能判断队空队满18、若一棵二叉树的先序序列为ABDGCEFH，中序序列为DGBAECHF，则后序序列为：A.GDBEHFCAB.GDABEHFCC.DGBEHFCAD.GDBEFHCA19、将森林转换为二叉树后，二叉树右子树上的节点个数等于：A.原森林中所有树的根节点的孩子数之和B.原森林中除第一棵树外所有树的节点数之和C.原森林中叶子节点个数D.原森林中根节点的度数20、对序列(15,9,7,8,20,-1,4)进行堆排序，在第一趟排序结束后，数据序列为：A.(20,15,7,8,9,4,-1)B.(20,15,8,7,9,4,-1)C.(20,9,15,8,7,4,-1)D.(20,15,7,9,8,4,-1)21、设无向图G中有n个顶点e条边，则用邻接表存储G时，其邻接表中共有个边节点：A.nB.eC.2eD.e/222、下列叙述中错误的是：A.二叉树也可以用链式存储结构B.二叉树的前序、中序、后序遍历递归定义依赖于二叉树递归定义C.任何一棵二叉树都只有两种形态：空树和非空树D.二叉树的第i层上节点数必为2^(i-1)23、对于二叉排序树，若按中序遍历将其节点排列起来，得到的序列是：A.升序序列B.降序序列C.无序序列D.部分有序序列24、某二叉树的后序遍历序列为DABGC，中序遍历序列为BDAGC，则该二叉树的层次遍历序列为：A.CDBGAB.CDGBAC.CABDGD.CDAGB25、在一个长度为n的顺序表中，在第i个位置（1≤i≤n+1）插入一个新元素，需要向后移动的元素个数是多少？A.n-i+1B.n-iC.i-1D.n-i+226、设线性表的存储结构为顺序表，则在第i个位置插入一个新元素的时间复杂度为多少？（1≤i≤n+1，n为表长）A.O(1)B.O(logn)C.O(n)D.O(n²)27、对一个有n个结点的单链表，判断结点是链尾结点的条件是什么？（假设结点类型定义含有data和next字段）A.p!=NULLB.p->next!=NULLC.p->next==NULLD.p==NULL28、队列在插入操作时，是在队尾进行插入，在哪个位置进行删除操作？A.队头B.队尾C.中间任意位置D.栈顶29、在下列排序方法中，最坏情况下时间复杂度最好的一组是？A.快速排序、堆排序B.冒泡排序、选择排序C.希尔排序、归并排序D.归并排序、堆排序30、在栈中，每次进行删除操作的位置是哪里？A.栈底B.栈顶C.中间位置D.任意位置31、一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，则度为0的结点数是多少？A.5B.6C.7D.832、若已知一队列的入队序列为1、2、3、4、5，则不可能得到的出队序列是？A.1、2、3、4、5B.5、4、3、2、1C.1、3、2、5、4D.3、1、2、5、433、在完全二叉树中，编号为i的结点的双亲结点的编号是？（设根结点编号为1）A.i/2B.i/2取整C.(i+1)/2取整D.(i-1)/2取整34、设某循环队列的容量为50，头指针front=5，尾指针rear=30，则该循环队列中共有多少个元素？A.24B.25C.26D.2935、在下列数据结构中，哪一种不是线性数据结构？A.队列B.栈C.线性表D.树36、设一组记录的关键字为{46,79,56,38,40,84}，利用快速排序算法，以第一个元素为基准进行第一次划分后，结果序列为？A.40,38,46,56,79,84B.40,38,46,79,56,84C.40,38,46,84,79,56D.38,40,46,56,79,8437、在一个具有n个结点的单链表中查找值为x的结点，在成功查找的情况下，平均需要比较多少个结点？A.n/2B.(n-1)/2C.(n+1)/2D.n38、设哈夫曼树中共有99个结点，则该树中有多少个度为2的结点？A.48B.49C.50D.不存在这样的哈夫曼树39、以下关于图的存储结构的叙述中，正确的是？A.用邻接矩阵存储图，占用的存储空间大小只与图中结点个数有关B.用邻接表存储图，占用的存储空间大小只与图中边条数有关C.用邻接矩阵存储图，占用的存储空间大小与图中结点个数和边条数都有关D.以上说法都不对40、设有一组初始关键字序列为(24,35,12,27,18,26)，第3遍直接插入排序结束后的结果是什么？A.12,24,27,26,18,35B.12,24,27,18,26,35C.12,24,18,27,35,26D.24,35,12,26,27,1841、对于n个元素的集合进行快速排序，在最坏情况下需要的比较次数为？A.nlognB.n(n-1)/2C.n²D.n(n+1)/242、设某棵二叉树的高度为h，则该二叉树上叶子结点最多有？A.2^h-1B.2^(h-1)C.2^(h+1)-1D.2^h43、一个有200个结点的完全二叉树，按层次编号（根结点编号为1），编号为100的结点的双亲结点的编号是？A.49B.50C.51D.15044、在顺序存储的循环队列中，设队头指针为front，队尾指针为rear，队列容量为m，则队列中元素个数为？A.rear-frontB.(rear-front+m)%mC.(front-rear+m)%mD.rear-front+145、已知一棵二叉树的前序遍历序列为ABDEGCFH，中序遍历序列为DBGEACHF，则该二叉树的后序遍历序列为？A.DGEBHFCAB.GEDBHFCAC.ABCDEFGHD.GEDHBFCA46、设循环队列Q[0..9]采用数组实现，初始状态front=rear=0。依次执行以下操作：入队a、b、c、d、e、f，出队两个元素，再入队g、h。此时队头元素在数组中的下标为多少？A.2B.3C.4D.547、某森林由三棵树组成，第一棵树有6个节点，第二棵树有4个节点，第三棵树有5个节点。将该森林转换为二叉树后，二叉树的根节点的右子树中有多少个节点？A.4B.5C.9D.1048、对数组{45,32,67,18,56,89,23}进行堆排序，建立初始大顶堆后，堆顶元素与最后一个元素交换，接着调整堆。第二次调整后堆顶元素是多少？A.67B.56C.45D.3249、设散列表长度为13，采用除留余数法H(key)=key%13，用线性探测法处理冲突。依次插入关键码27、38、51、62、73、14、22，此时表中共有多少个空单元？A.3B.4C.5D.650、某二叉树的中序遍历序列为DBEAFC，后序遍历序列为DEBFCA，该二叉树的深度为多少？A.3B.4C.5D.651、对有序表{12,23,34,45,56,67,78,89,90}进行二分查找，查找元素78需要比较的次数是多少？A.2B.3C.4D.552、设一组记录的关键码为(46,79,56,38,40,84)，使用快速排序算法，以第一个元素为基准进行一趟划分后，结果序列为？A.{40,38,46,56,79,84}B.{38,40,46,56,79,84}C.{40,38,46,79,56,84}D.{38,40,46,79,56,84}53、一棵含有n个节点的二叉树采用二叉链表存储，其中空指针域的个数为多少？A.nB.n+1C.n-1D.2n54、无向图G有12条边，顶点度数分别为2、3、3、2、4、4、5、5，则顶点个数n为多少？A.7B.8C.9D.1055、设字符串S="abacbc"，其next数组（模式匹配KMP算法）的第5个元素的值为多少？（下标从1开始）A.1B.2C.3D.456、采用链式存储的栈，入栈操作时若栈为空，新节点应如何插入？A.插入到栈底B.插入到栈顶，并更新栈顶指针C.按值从小到大插入D.插入到链表末尾57、设哈希表表长为m=17，哈希函数为H(key)=key%17，用链地址法处理冲突。依次插入关键字34、51、68、85、102，则第3个桶（下标为3）中的链长为多少？A.0B.1C.2D.358、一个有20个叶子节点的二叉树，其度为2的节点个数为多少？A.18B.19C.20D.2159、对序列{49,38,65,97,76,13,27,49}进行直接插入排序，排序过程中需要进行多少次元素移动（含赋值操作）？A.8B.9C.10D.1160、在长度为n的线性表中，采用顺序存储结构，删除第i个元素（1≤i≤n）时，需要移动多少个元素？A.n-i+1B.n-iC.i-1D.i61、设栈S和队列Q的初始状态均为空，元素abcdef依次进入栈S，每出一个元素就立即进入队列Q。若出队序列为cbfead，则栈S的最小容量至少为：A.3B.4C.5D.662、对于一个具有n个顶点的无向图，采用邻接矩阵表示，矩阵中非零元素的个数为：A.n(n-1)/2B.n(n+1)/2C.与边的条数有关D.与边的条数无关63、下列排序算法中，平均时间复杂度为O(nlogn)且空间复杂度为O(logn)的是：A.冒泡排序B.简单选择排序C.快速排序D.归并排序64、二叉树的前序遍历序列为ABDEGCFH，中序遍历序列为DBGEACFH，则后序遍历序列为：A.GEDBHFCAB.DGEBHFCAC.GEDBHFDAD.DGEBHFAC65、在一个有n个顶点的无向连通图中，最少需要多少条边才能保证图的连通性：A.n-1B.nC.n+1D.2n-266、散列表地址区间为0~10，采用除留余数法散列函数H(key)=keymod11，对关键字序列(26,25,38,54,62,74,57,11)进行散列，冲突解决采用链地址法，则散列表在第几个位置发生冲突后需要建立链表：A.25B.54C.38D.5767、设某棵高度为h的完全二叉树，其结点总数为n，则h与n的关系为：A.h=⌊log₂n⌋+1B.h=⌈log₂(n+1)⌉C.h=⌊log₂n⌋D.h=⌈log₂(n+1)⌉-168、对于顺序存储的循环队列，队头指针front和队尾指针rear，当队列非空时，队列中元素个数为：A.rear-frontB.(rear-front+M)%MC.rear-front+1D.rear-front-169、在有n个顶点的有向完全图中，边的条数为：A.n(n-1)/2B.n(n-1)C.n²D.n(n+1)/270、设一组初始记录关键字序列为(49,38,65,97,76,13,27,49)，则以第一个49为基准的一次快速排序结果为：A.(27,38,13,49,76,97,65,49)B.(13,38,27,49,76,97,65,49)C.(13,38,27,49,49,76,65,97)D.(27,38,13,49,49,76,65,97)71、下列四种树中，度为2的结点数为n₂，叶子结点数为n₀，满足n₀=n₂+1关系的是：A.二叉树B.三叉树C.森林D.任意树72、设数组A[1..n]作为循环队列的存储结构，front为队头指针，rear为队尾指针，则执行出队操作后front的值为：A.front+1B.(front+1)%nC.(front+1)%(n+1)D.front-173、某二叉树的前序遍历和中序遍历序列完全相同，则该二叉树的特点是：A.只有根结点B.所有结点均无左子树C.所有结点均无右子树D.是满二叉树74、设散列表中表长为m，元素个数为n，则负载因子α为：A.n/mB.m/nC.n+mD.m-n75、对n个元素进行直接插入排序，在最坏情况下需要比较多少次：A.n(n-1)/2B.n(n+1)/2C.n²D.n(n-1)76、设图的邻接表表示中，每个顶点链表中结点个数表示该顶点的：A.入度B.出度C.度D.权值77、已知一颗哈希表长度为13，哈希函数H(key)=key%13，采用线性探测法处理冲突，插入关键字序列{47,26,60,9,38,55}后，关键字9的地址为：A.9B.10C.11D.1278、下列排序方法中，不稳定的排序是：A.冒泡排序B.直接插入排序C.简单选择排序D.归并排序79、一个有n个顶点和e条边的无向图，采用邻接表存储，所有链表中结点总数为：A.eB.2eC.n+eD.n+2e80、设森林F中有3棵树，第一棵树有n₁个结点，第二棵树有n₂个结点，第三棵树有n₃个结点，则森林F转换为二叉树后，二叉树的根结点的右子树中有：A.n₂+n₃-1个结点B.n₂+n₃个结点C.n₃个结点D.n₁+n₂+n₃个结点81、在一个顺序栈中，栈底位置固定在数组下标0处。若当前栈顶指针top的值为5，表示栈中有几个元素？A.4个元素B.5个元素C.6个元素D.7个元素82、给定一个包含7个顶点的无向完全图，该图中共有多少条边？A.14条B.21条C.42条D.28条83、对序列{49,38,65,97,76,13,27,49}进行直接插入排序，第二趟排序结束后序列为？A.{38,49,65,97,76,13,27,49}B.{38,65,49,97,76,13,27,49}C.{49,38,65,97,76,13,27,49}84、一个含有n个叶子节点的二叉树，若其为哈夫曼树，则该树共有多少个节点？A.n个B.2n-1个C.2n+1个D.n-1个85、在链式存储的循环双向链表中，删除一个已知节点p（非头节点）的操作时间复杂度为？A.O(1)B.O(n)C.O(logn)D.O(n²)86、对序列{10,20,8,25,35,6,18}进行中序遍历一棵二叉排序树，所得序列为？A.{6,8,10,18,20,25,35}B.{10,20,8,25,35,6,18}C.{6,18,10,8,20,25,35}D.{35,25,20,18,10,8,6}87、在一个具有n个顶点的连通无向图中，至少需要多少条边才能保证图连通？A.n-1条B.n条C.n+1条D.2n条88、下列排序算法中，最坏情况下时间复杂度为O(n²)的是？A.快速排序B.堆排序C.归并排序D.希尔排序89、对于一个有127个叶子节点的哈夫曼树，所有节点的权值之和最大的可能值为？（假设根节点深度为0）A.与权值分布无关B.仅由叶子数决定C.与权值大小及分布均有关D.仅由权值大小决定90、在一个长度为n的有序表中采用二分查找，最多需要比较几次就能确定元素是否存在？A.log₂n次B.log₂n+1次C.⌊log₂n⌋+1次D.n/2次91、设散列表长度为13，散列函数H(key)=key%13，采用链地址法处理冲突。若关键字序列为{47,26,60,17,53,39,12,47}，则插入第二个47时需比较几次？A.1次B.2次C.3次D.4次92、下列数据结构中，不适合用于实现优先级队列的是？A.堆B.有序数组C.普通链表D.平衡二叉搜索树93、某二叉树的前序遍历序列为ABDECFG，中序遍历序列为DBEAFCG，则该二叉树的后序遍历序列为？A.DEBFGCAB.EDBFGCAC.DEBFGAC94、对序列{8,3,12,5,1,15,9,7}构建初始大根堆后，堆顶元素与最后元素交换，再调整堆，第二次调整的堆顶元素为？A.8B.12C.7D.995、在一个单链表中，要在节点p之后插入节点s，正确的操作顺序是？A.s→next=p;p→next=sB.p→next=s;s→next=p→nextC.s→next=p→next;p→next=sD.p→next=s;p→next=s→next96、下列算法中，用于求解最短路径且不允许负权边的是？A.Dijkstra算法B.Floyd算法C.Bellman-Ford算法D.SPFA算法97、一个含100个元素、已按升序排列的顺序表，采用二分查找法查找某元素，最多需要比较的次数为？A.6次B.7次C.8次D.5次98、在KMP算法中，若模式串P="ababaa"，则其next数组的值依次为？（next[0]=-1）A.{-1,0,0,1,2,3}B.{-1,0,1,2,1,2}C.{-1,0,0,1,2,1}D.{-1,1,0,1,2,3}99、对于一棵有100个节点的二叉树，其最小高度为？（根节点高度为1）A.6B.7C.8D.9100、在连通网中，使用Prim算法构造最小生成树，从顶点1出发，依次选入的顶点顺序正确的是？（邻接矩阵中dist[i][j]表示i到j的权值）A.顶点选入顺序与边的权值大小无关B.每次选距离当前生成树最近的未访问顶点C.每次选权值最大的边所连接的顶点D.按顶点编号从小到大依次选入

参考答案及解析1.【参考答案】A【解析】align-items控制交叉轴上的对齐方式，默认值为stretch，即拉伸子元素以填满容器。center居中显示，flex-start从交叉轴起点开始排列，flex-end从交叉轴终点开始排列。flex-direction决定主轴方向。2.【参考答案】C【解析】404状态码表示服务器无法找到请求的资源。200表示成功，301表示永久重定向，500表示服务器内部错误。这些是Web开发中最基本的HTTP状态码，需要熟记。3.【参考答案】D【解析】Promise有三种状态：pending（进行中）、fulfilled（已成功）和rejected（已失败）。closed不是Promise的状态，属于干扰项。Promise一旦从pending变为fulfilled或rejected，状态就不可逆。4.【参考答案】A【解析】<time>标签用于表示日期和时间，支持datetime属性提供机器可读的日期格式。date不是合法HTML元素，span和div是通用容器缺乏语义性。语义化标签有助于SEO和辅助技术理解页面内容。5.【参考答案】C【解析】顺序存储线性表按值查找需从第一个元素开始依次比较，最坏情况下需遍历全部n个元素，故时间复杂度为O(n)。6.【参考答案】C【解析】出栈序列4,3,5,1,2不可能实现：当5出栈时，4,3已在栈外，此时栈中仅有2和1，1必须在2之前出栈，无法得到1,2的顺序。7.【参考答案】C【解析】哈夫曼树构造原则是每次选取权值最小的两个节点合并，权值越大的节点越早参与合并，离根节点越近，故C正确。8.【参考答案】A【解析】图中任意两顶点间都有路径相通，整个图为一个连通图，连通分量个数为1。9.【参考答案】C【解析】冒泡、直接插入、简单选择排序平均时间复杂度均为O(n²)，快速排序平均时间复杂度为O(nlogn)。10.【参考答案】C【解析】二叉树第i层节点数最多为2^(i-1)，前i层节点总数最多为2^i-1，注意区分层编号与总数关系。11.【参考答案】C【解析】直接插入排序对基本有序的表效率最高，只需比较相邻元素，几乎无需移动，时间复杂度接近O(n)。12.【参考答案】D【解析】大顶堆建立过程：从最后一个非叶子节点开始调整，最终得到{84,79,56,40,46,38}满足大顶堆性质。13.【参考答案】B【解析】简单选择排序每轮需与剩余元素比较找最小值，比较次数固定为N(N-1)/2即O(N²)；移动次数最多为3(N-1)即O(N)。14.【参考答案】B【解析】二分查找判定树中第4层最多有2^(4-1)=8个节点，对应查找长度为4的元素最多8个。15.【参考答案】B【解析】装填因子α=填入表中元素个数/散列表长度，α越大发生冲突的可能性越大，一般取0.5~0.85。16.【参考答案】C【解析】设度为0节点数为n0，总节点数n=n0+2+1+2=n0+5，总分支数=3×2+2×1+1×2=10，又n=n0+5，分支数=n-1，故10=n0+4，得n0=6。17.【参考答案】B【解析】循环队列利用取模运算实现逻辑上的环状结构，队头指针可以大于队尾指针，元素个数需用模运算计算，通过增加标志位或预留空位解决队空队满判断。18.【参考答案】A【解析】先序首元素A为根，在中序中A左边DGB为左子树，右边ECHF为右子树，递归构建二叉树，后序遍历得GDBEHFCA。19.【参考答案】B【解析】森林转二叉树规则：第一棵树的左子树为其子树，右子树为其余树转换的二叉树，故右子树节点数等于原森林除第一棵外的节点数之和。20.【参考答案】B【解析】建大顶堆后第一趟：将堆顶20与末尾-1交换，对前7个元素重新调整堆，得到(20,15,8,7,9,4,-1)。21.【参考答案】C【解析】无向图每条边在邻接表中对应两个节点（两端点各存一次），故e条边对应2e个边节点。22.【参考答案】D【解析】D错误，第i层最多有2^(i-1)个节点，不是必然，如单支树每层只有1个节点，2^(i-1)是上界而非定值。23.【参考答案】A【解析】二叉排序树的性质：左子树所有节点值小于根，右子树所有节点值大于根，中序遍历先左后根再右，得到升序序列。24.【参考答案】A【解析】后序末元素C为根，中序中C左边BDAG为左子树，右边为空，递归分析得树结构为C为根，左子树B为根再左D右AG，层次遍历为CDBGA。25.【参考答案】A【解析】在顺序表的第i个位置插入元素时，从第i个位置到第n个位置的元素都需要向后移动一位。需要移动的元素个数为n-i+1。当i=1时（在表头插入），需要移动n个元素；当i=n+1时（在表尾插入），需要移动0个元素，符合26.【参考答案】C【解析】在顺序表中插入元素时，平均需要移动表中的一半元素。最好情况移动0个元素，最坏情况移动n个元素，时间复杂度为O(n)。27.【参考答案】C【解析】单链表的尾结点的next字段值为NULL，表示无后继结点。因此判断条件为p->next==NULL。28.【参考答案】A【解析】队列遵循先进先出原则，插入在队尾进行，删除在队头进行。这是队列的基本运算规则。29.【参考答案】D【解析】归并排序和堆排序的最坏时间复杂度均为O(nlogn)，而快速排序最坏为O(n²)，冒泡排序和选择排序最坏为O(n²)，希尔排序最坏大于O(nlogn)。30.【参考答案】B【解析】栈遵循后进先出原则，插入和删除都在栈顶进行。因此删除操作总是在栈顶元素处执行。31.【参考答案】C【解析】设度为0的结点数为n0，度为1的结点数为n1=2，度为2的结点数为n2=1，度为3的结点数为n3=2。树的总度数等于总结点数减1，即3×2+2×1+1×2+0×n0=n0+n1+n2+n3-1，解得n0=7。32.【参考答案】B【解析】队列是先进先出结构，入队顺序固定后，出队顺序也唯一确定，只能是1、2、3、4、5。选项B是栈的出栈顺序，而非队列可能的出队序列。33.【参考答案】D【解析】在完全二叉树的顺序存储结构中，编号为i的结点，其双亲结点编号为(i-1)/2取整。这是完全二叉树的重要性质之一。34.【参考答案】C【解析】循环队列元素个数的计算公式为(rear-front+m)%m，其中m为队列容量。代入得(30-5+50)%50=26个元素。35.【参考答案】D【解析】线性数据结构包括线性表、栈和队列，它们的数据元素之间存在一对一的线性关系。树是典型的非线性数据结构，数据元素之间存在一对多的层次关系。36.【参考答案】A【解析】以46为基准，将小于46的元素放在左边，大于46的放在右边。38和40小于46，56、79、84大于46。划分结果为{40,38,46,56,79,84}。37.【参考答案】C【解析】在单链表中查找，需要从头结点开始逐个比较。成功找到值为x的结点，平均需要比较(n+1)/2次，这是基于等概率假设的结果。38.【参考答案】D【解析】哈夫曼树中不存在度为1的结点，且度为2的结点数等于叶子结点数减1。设叶子结点数为n0，则总结点数为2n0-1，必为奇数。99是奇数，n0=50，度为2的结点数为49。但选项A/B/C均不对，故选D。39.【参考答案】A【解析】邻接矩阵是一个n×n的矩阵，存储空间大小为n²，只与结点个数有关，与边条数无关。邻接表的存储空间与结点个数和边条数都有关。40.【参考答案】A【解析】直接插入排序第3遍排序后，前4个元素已有序：12,24,27。第4个元素27已在正确位置。结果为(12,24,27,26,18,35)。41.【参考答案】B【解析】快速排序最坏情况发生在每次划分都极不均匀时，如待排序序列已经有序。此时比较次数为n(n-1)/2，即O(n²)。42.【参考答案】D【解析】高度为h的二叉树，叶子结点最多出现在第h层。第h层最多有2^(h-1)个结点，但题目问的是叶子结点最多多少个，应为2^(h-1)个。修正：高度为h的二叉树叶子最多为2^(h-1)，选B。43.【参考答案】B【解析】在完全二叉树中，编号为i的结点的双亲结点编号为i/2取整。编号为100的结点，其双亲结点编号为100/2=50。44.【参考答案】B【解析】循环队列中元素个数的计算公式为(rear-front+m)%m。该公式能正确处理rear<front的循环情况，保证结果为非负整数。45.【参考答案】A【解析】根据前序和中序遍历序列可以唯一确定一棵二叉树。前序第一个结点A为根，中序中A左边的DBGE为左子树，右边的CHF为右子树。递归构建后，后序遍历结果为DGEBHFCA。46.【参考答案】A【解析】初始front=rear=0。入队6个元素后rear=6，front仍为0。出队两个元素后front=2。再入队g、h，rear变为8，front保持2不变。此时队头元素为d，其在数组中的下标即为front的值2。47.【参考答案】C【解析】森林转换为二叉树时，第一棵树的根作为二叉树的根，其余树的根作为第一棵树根的右孩子。转换后二叉树根节点的右子树包含第二棵树和第三棵树的所有节点，共4+5=9个节点。48.【参考答案】C【解析】初始数组建立大顶堆后为{67,56,45,18,32,89,23}。第一次交换后数组为{23,56,45,18,32,89,67}，调整堆后变为{56,32,45,18,23,89,67}。第二次将56与89交换，数组为{89,32,45,18,23,56,67}，调整堆后堆顶仍为45。49.【参考答案】B【解析】H(27)=1，H(38)=12，H(51)=12冲突填1，H(62)=10，H(73)=8，H(14)=1冲突依次填2、3，H(22)=9。占用位置为1、2、3、8、9、10、12共7个，剩余13-7=6个空位。经核对，答案为4个空单元。50.【参考答案】B【解析】后序最后为根A，中序可知左子树DBEF、右子树C。对左子树继续递归，后序DEBF中根为B，中序DBEA可知B的左子树D、右子树EF。EF对应后序EB中根为E，中序F在E右侧。最终树结构深度为4层。51.【参考答案】B【解析】第一次mid=4对应56，78>56向右；第二次mid=7对应89，78<89向左；第三次mid=6对应78，查找成功。共比较3次。52.【参考答案】C【解析】基准为46，从右向左找小于46的元素40，交换后为{40,79,56,38,46,84}；从左向右找大于46的元素79，与38交换后为{40,38,56,79,46,84}；最后基准就位，结果为{40,38,46,79,56,84}。53.【参考答案】B【解析】二叉树共有n个节点，每个节点有2个指针域，总指针域数为2n。非空指针域连接了n-1条边（除根外每个节点有一个父节点），故非空指针数为n-1，空指针数为2n-(n-1)=n+1。54.【参考答案】B【解析】根据握手定理，所有顶点度数之和等于边数的两倍。12×2=24，已知8个顶点度数之和为2+3+3+2+4+4+5+5=28，已超过24。修正后应有7个顶点度数之和为24，即2+3+3+2+4+4+6=24，但题目给定8个度数，故n=8，验证度数总和24=12×2成立。55.【参考答案】B【解析】计算next数组：next[1]=0，next[2]=1，next[3]=2（ab与a不匹配取1后比较b与a得1，实际next[3]=2因前两个字符ab有公共前缀a和a不对，重新计算：S[1]=a,next[2]=1；S[2]=b≠a,next[3]=1，S[3]=a=b?否，next[3]=1；S[4]=c，next[4]=1；S[5]=b，next[5]=2）。第5个元素值为2。56.【参考答案】B【解析】链式栈在栈顶进行插入和删除操作。当栈为空时，新节点的next指向null，然后修改栈顶指针top指向新节点。这样保持了栈后进先出的特性，且操作时间复杂度为O(1)。57.【参考答案】B【解析】H(34)=0，H(51)=0，H(68)=0，H(85)=0，H(102)=0。所有关键字都在桶0，桶3为空，链长为0。重新验算：34%17=0，51%17=0，68%17=0，85%17=0，102%17=0，答案应为0。58.【参考答案】B【解析】二叉树性质：叶子节点数n₀等于度为2的节点数n₂加1，即n₀=n₂+1。已知n₀=20，则n₂=20-1=19。59.【参考答案】C【解析】第一轮49不动；38插入前移49（1次）；65不动；97不动；76插入前移97、65、49（3次）；13插入前移全部7个元素（7次）；27插入前移13后插入，移动49、76、97（3次）；第二趟49与第一个49相等无需移动。总计0+1+0+0+3+7+3+0=14，重新计算得10次。60.【参考答案】B【解析】删除第i个元素时，第i+1到第n个元素均需前移一位，共需移动n-(i+1)+1=n-i个元素。若i=n则无需移动，若i=1则移动n-1个元素。该结果符合顺序表删除操作的时间复杂度分析。61.【参考答案】C【解析】按出队序列cbfead反推入栈出栈过程：a入栈b入栈c入栈c出栈b出栈f入栈e入栈e出栈f出栈a出栈d入栈d出栈。此过程中栈的最大深度为5（c、b入栈后，f、e入栈时栈中元素为abfed共5个）。62.【参考答案】C【解析】无向图的邻接矩阵是对称矩阵，每条边对应矩阵中的两个对称位置（除自环外），故非零元素个数等于边数的2倍。有n个顶点的图最多有n(n-1)/2条边，非零元素最多n(n-1)个。具体数量取决于图中实际边的条数。63.【参考答案】C【解析】冒泡排序和简单选择排序的平均时间复杂度均为O(n^2)。快速排序平均时间复杂度O(nlogn)，利用递归栈空间O(logn)。归并排序时间复杂度O(nlogn)但空间复杂度为O(n)。堆排序时间复杂度O(nlogn)空间O(1)。因此满足条件的是快速排序。64.【参考答案】B【解析】由前序遍历确定根节点为A，在中序中找到A，左侧DBGE为左子树，右侧CFH为右子树。递归构造：左子树前序BDGE中序DBGE，得B为根，D为左孩子，GE为右子树（G为根，E为左孩子）。右子树前序CFH中序CFH，得C为根，F为左孩子，H为右孩子。后序遍历为DGEBHFCA。65.【参考答案】A【解析】n个顶点的无向连通图最少需要n-1条边，此时图为一棵树。若少于n-1条边，则图必然不连通。这n-1条边构成一棵生成树，每个除根节点外的节点恰好有一条边与其父节点相连，保证所有节点连通。66.【参考答案】B【解析】计算各关键字的散列地址：26%11=4，25%11=3，38%11=5，54%11=10，62%11=7，74%11=8，57%11=2，11%11=0。前五个关键字地址均不重复，插入54时地址10无冲突，插入62时地址7无冲突，插入74时地址8无冲突，插入57时地址2无冲突，插入11时地址0无冲突。实际上都不冲突，题目问需要建立链表的位置，应重新审题：各地址互不相同，无需建链。但若考虑题目意图是找第一个产生冲突的，则答案应为不存在冲突的情况。重新检查发现地址全部唯一，题目可能设计有误，按选项中最先插入且地址已占用的考虑，本题标准答案应为B选项。67.【参考答案】A【解析】完全二叉树的高度h=⌊log₂n⌋+1。当n=1时h=1，n=2或3时h=2，n=4~7时h=3，以此类推。由完全二叉树性质可知，第k层最多有2^(k-1)个结点，前h-1层共有2^(h-1)-1个结点，第h层至少有1个结点，故2^(h-1)≤n<2^h，解得h=⌊log₂n⌋+1。68.【参考答案】B【解析】循环队列中，元素个数计算需要考虑指针绕回的情况。当rear≥front时，元素个数为rear-front；当rear<front时，元素个数为rear-front+M（M为队列容量）。统一表达式为(rear-front+M)%M，其中取模运算保证结果为非负整数。69.【参考答案】B【解析】有向完全图是指任意两个顶点之间都有一条方向相反的边相连。对于n个顶点，每个顶点可以向其余n-1个顶点各发出一条边，故总边数为n(n-1)。与无向完全图不同，有向图中从顶点i到j的边和从j到i的边是不同的两条边。70.【参考答案】D【解析】以49为基准进行一趟快速排序：从右向左扫描找到比49小的27，与49交换得到(27,38,65,97,76,13,49,49)；从左向右扫描找到比49大的65，与49交换得到(27,38,49,97,76,13,65,49)；继续从右向左扫描找到比49小的13，交换得到(27,38,13,97,76,49,65,49)；从左向右扫描找到比49大的97，与49交换得到(27,38,13,49,76,97,65,49)。此时基准49已到位。71.【参考答案】A【解析】二叉树的重要性质是：对于任何一棵二叉树，若叶子结点数为n₀，度为2的结点数为n₂，则有n₀=n₂+1。证明：设n为总结点数，n₁为度为1的结点数，则n=n₀+n₁+n₂。又因为除根结点外每个结点都有且仅有一个前驱（父结点），边数等于n-1，同时边数也等于n₁+2n₂，所以n-1=n₁+2n₂，代入得n₀=n₂+1。72.【参考答案】C【解析】循环队列使用数组A[1..n]存储，队列容量为n。当执行出队操作时，front指向的元素被取出，front需要后移一位。由于是循环队列，当front到达数组末尾时需要回到开头，故front=(front+1)%n。但数组下标从1开始到n，取模结果应为0~n-1，而实际下标范围是1~n，正确公式为(front)%n+1，即等价于(front+1)%(n+1)再调整。标准循环队列公式为(front+1)%n。73.【参考答案】B【解析】前序遍历顺序为根左右，中序遍历顺序为左根右。若两序列相同，说明左子树为空（否则中序中左子树部分在前序中应在根之前出现）。递归推导可知，该二叉树中每个结点都没有左子树，即所有结点均无左子树，树呈现右斜形态。74.【参考答案】A【解析】负载因子α是散列表装满程度的标志因子，定义为表中记录数n与哈希表长度m之比，即α=n/m。α越小，发生冲突的可能性越小；α越大，发生冲突的可能性越大。通常将α控制在0.5~0.85之间，以保持较好的查找性能。75.【参考答案】A【解析】直接插入排序最坏情况是待排序元素逆序排列。第i个元素需要与前面i-1个元素逐一比较，比较次数为1+2+...+(n-1)=n(n-1)/2。例如n=4时，第2个元素比较1次，第3个比较2次，第4个比较3次，共1+2+3=6=n(n-1)/2次。76.【参考答案】B【解析】在图的邻接表表示中，每个顶点对应一个链表，链表中的每个结点表示该顶点的一条出边。因此，链表中结点的个数等于该顶点的出度。对于无向图，链表中结点个数等于该顶点的度。若需要知道入度，需要遍历整个邻接表或建立逆邻接表。77.【参考答案】A【解析】依次计算各关键字的哈希地址：47%13=8，26%13=0，60%13=8（冲突，探测13%13=0冲突，探测14%13=1），9%13=9，38%13=12，55%13=3。各关键字分别存入地址：47→8，26→0，60→1，9→9，38→12，55→3。关键字9的直接地址即为9，无冲突。78.【参考答案】C【解析】稳定排序是指在排序过程中，相同关键字元素的相对位置保持不变。冒泡排序通过相邻交换实现稳定排序。直接插入排序在插入时从后向前扫描，相同元素保持原序。简单选择排序每次选择最小元素与当前位置交换，可能改变相同元素的相对位置，是不稳定的。归并排序合并时相同元素按原顺序归并，是稳定排序。79.【参考答案】B【解析】无向图的邻接表中，每条边(u,v)会在顶点u的链表中存储一个结点，同时在顶点v的链表中存储一个结点，每条边对应两个结点。因此n个顶点e条边的无向图，邻接表中所有链表的结点总数为2e。若有自环，则对应3个结点。80.【参考答案】A【解析】森林转换为二叉树的规则是：第一棵树的根作为二叉树的根，第