2026年大学(工学)数据结构试题及解析

2026年大学(工学)数据结构试题及解析一、单项选择题（每题2分，共20分）1.若顺序表采用动态扩容策略，当表长为n且容量已满时执行一次插入操作，其平均时间复杂度为A.O(1)B.O(logn) C.O(n) D.O(n²)答案：C解析：扩容需复制原n个元素到新数组，复制代价为O(n)，均摊到n+1次插入，平均O(n)。2.对一棵含n个结点的AVL树，最坏情况下查找成功的比较次数为A.log₂(n+1)B.1.44log₂(n+1)C.2log₂(n+1)D.n答案：B解析：AVL树高度h≤1.44log₂(n+1)，故最坏比较次数即树高。3.下列排序算法中，稳定且最坏时间复杂度为O(nlogn)的是A.快速排序 B.堆排序 C.归并排序 D.希尔排序答案：C解析：归并排序稳定，最坏O(nlogn)；快排不稳定，堆排不稳定。4.用邻接矩阵存储无向图G，若G有n个顶点、e条边，则矩阵中非零元素个数为A.n B.2e C.e D.n²答案：B解析：无向图邻接矩阵对称，每条边对应两个1，共2e个非零元素。5.对长度为20的有序表进行二分查找，最多需要的比较次数为A.4 B.5 C.6 D.7答案：B解析：⌈log₂(20+1)⌉=5。6.循环队列存储在A[0..m-1]中，队头指针front指向队首元素前一个位置，队尾指针rear指向队尾元素，则队列长度为A.(rear−front+m)%m B.(rear−front+m+1)%m C.rear−front D.rear−front+1答案：B解析：front指向“前一个”，元素个数=(rear−front+m+1)%m。7.对关键字序列{5,3,8,2,9,1}建小根堆，初始堆为A.{1,2,8,5,9,3} B.{1,2,5,3,9,8} C.{1,3,2,5,9,8} D.{1,2,3,5,9,8}答案：B解析：自底向上筛选，根为1，左右子树分别满足堆性质。8.一棵度为4的树，度为1、2、3、4的结点个数分别为4、3、2、1，则叶子结点数为A.8 B.9 C.10 D.11答案：C解析：总度数=1×4+2×3+3×2+4×1=20，边数=20，总结点数=21，叶子=21−(4+3+2+1)=11，再减去度不为0的10个，得11−1=10。9.对稀疏矩阵进行快速转置算法时，需预先统计A.每行非零元个数 B.每列非零元个数 C.总行数 D.总列数答案：B解析：快速转置需预知每列非零元数目以定位转置后位置。10.在并查集按秩合并与路径压缩优化下，m次操作序列最坏时间复杂度为A.O(m) B.O(mlogn) C.O(mα(n)) D.O(mn)答案：C解析：Tarjan证明为O(mα(n))，α为反阿克曼函数。二、多项选择题（每题3分，共15分，多选少选均不得分）11.下列关于B+树的说法正确的是A.叶结点通过指针链接 B.非叶结点仅起索引作用 C.叶结点包含全部关键字 D.插入可能引起叶结点分裂答案：ABCD解析：B+树所有关键字存于叶结点，叶结点链表连接，非叶仅索引，插入分裂可发生在叶。12.对无向连通图G，下列说法正确的是A.G的生成树边数为n−1 B.G的割边一定在任意生成树中 C.G的割点一定在任意生成树中 D.G的DFS树无横叉边答案：AD解析：割边不一定在生成树（可替换），割点不一定在生成树（叶子割点可不在），DFS树无横叉边。13.下列算法中，空间复杂度为O(1)的有A.堆排序 B.折半插入排序 C.快速排序（非递归） D.二路归并排序答案：AB解析：堆排、折半插入仅需常数辅助空间；非递归快排需栈O(logn)；归并需O(n)。14.对关键字序列{12,23,34,45,56,67,78,89}进行查找，采用A.顺序查找平均查找长度ASL为4.5 B.折半查找ASL为2.61 C.斐波那契查找ASL为2.61 D.插值查找ASL为2.61答案：ABC解析：均匀分布下插值查找ASL≈loglogn，远小于2.61，故D错。15.下列关于红黑树性质正确的是A.根到叶最长路径不超过最短路径两倍 B.黑高度相同 C.红结点父结点必为黑 D.插入修复最多需2次旋转答案：ABC解析：插入修复最多2次旋转，但某些情况需1次，D表述“最多”正确，但题目允许多选，故ABCD均对。三、填空题（每空2分，共20分）16.对长度为n的线性表，采用单链表实现，在位置i（1≤i≤n+1）插入一个新结点，时间复杂度为________。答案：O(n)解析：需找到第i−1个结点，链表无随机访问。17.一棵完全二叉树第6层（根为第1层）最多有________个结点。答案：32解析：第k层最多2^{k−1}，2^5=32。18.对稀疏矩阵采用三元组表存储，若矩阵A为1000×1000，非零元t=5000，则三元组表所需存储单元数为________。答案：15000解析：每个三元组存行、列、值，3×5000=15000。19.对关键字序列{7,6,5,4,3,2,1}进行冒泡排序，需进行________趟才能完成排序。答案：6解析：每趟沉底一个最小值，n−1=6。20.已知广义表LS=(a,(b,c),((d)))，其表尾为________。答案：((b,c),((d)))解析：表尾为除去第一个元素后的剩余部分。21.对n个顶点的有向图，其邻接矩阵中第i行1的个数等于顶点i的________。答案：出度22.采用Floyd算法求所有点对最短路径，第k轮迭代时，若dist[i][j]更新，则中间结点必为________。答案：k解析：k为允许的最大中间点编号。23.对一棵哈夫曼树，若叶结点权值为{2,3,5,7,11}，则其带权路径长度WPL为________。答案：67解析：构造得WPL=2×3+3×3+5×2+7×2+11×1=67。24.在B树插入过程中，若某结点分裂，其父亲结点关键字个数最多增加________。答案：1解析：分裂后中间关键字上提，父结点增1。25.对循环链表L，仅设尾指针rear，则判断L为空的条件是________。答案：rear==NULL或rear->next==rear（视实现而定，标准答案rear==NULL）四、简答题（共25分）26.（6分）给出将二叉搜索树T转换为有序双向链表的算法思想，要求原地转换，O(1)额外空间。答案：采用中序线索化思想，递归过程中维护前驱指针prev。访问当前结点curr时，将prev的右指针指向curr，curr的左指针指向prev，更新prev=curr。最后首尾相连成环。时间O(n)，空间O(1)（递归栈O(h)可改为Morris遍历实现真O(1)）。27.（6分）说明为何快速排序最坏时间复杂度为O(n²)，并给出一种避免最坏情况的方法。答案：当输入已有序且每次选最左元素为基准，划分极度不平衡，递归深度n，每层O(n)，总O(n²)。避免方法：随机化选基准，或采用“三者取中”法，期望划分平衡，期望复杂度O(nlogn)。28.（6分）比较邻接表与邻接矩阵在存储无向图时的空间复杂度，并指出各自适合的场景。答案：邻接矩阵O(n²)，邻接表O(n+2e)。稠密图e≈n²/2用矩阵节省空间且支持O(1)边查询；稀疏图e≈n用邻接表节省空间，遍历邻接点高效。29.（7分）阐述并查集“按秩合并”与“路径压缩”两种优化的原理，并证明它们同时使用时单次操作时间复杂度为O(α(n))。答案：按秩合并令小树挂在大树下，保持树高O(logn)；路径压缩使查找路径上所有结点直接指向根，树高急剧降低。Tarjan证明m次操作总时间为O(mα(n))，α(n)增长极慢，可视为常数。五、应用题（共40分）30.（10分）哈希表设计设关键字集合为{10,22,31,4,15,28,17,88,59,46}，表长m=13，采用双散列法解决冲突，散列函数h₁(k)=kmod13，h₂(k)=1+(kmod11)。（1）依次插入上述关键字，给出最终哈希表状态。（2）计算成功查找的平均查找长度ASL。答案：（1）0:221:592:153:284:45:176:887:468:—9:1010:3111:—12:—（2）各关键字探查次数：10→1，22→1，31→2，4→1，15→1，28→1，17→2，88→1，59→2，46→2。ASL=(1+1+2+1+1+1+2+1+2+2)/10=1.4。31.（10分）图算法给定带权有向图G的邻接矩阵如下（∞表示无边，对角线为0）：1234105∞102∞03∞3∞∞014∞∞∞0（1）用Dijkstra算法求顶点1到其余各点最短距离，写出每一步的dist数组。（2）给出最短路径树。答案：（1）初始：dist=[0,5,∞,10]选2：dist=[0,5,8,10]选3：dist=[0,5,8,9]选4：dist=[0,5,8,9]（2）树边：1→2，2→3，3→4。32.（10分）动态规划最长公共子序列LCS：X=“ABCBDAB”，Y=“BDCABA”。（1）给出LCS长度。（2）输出一个LCS。答案：（1）长度=4（2）一个LCS为“BCAB”或“BDAB”。33.（10分）B树操作一棵5阶B树初始为空，依次插入关键字{1,4,7,10,17,21,31,25,19,20,28,42}。（1）画出最终B树结构。（2）删除关键字20，画出结果树。答案：（1）最终树（略图描述）：根：[10,21]左：[1,4,7] 中：[17,19,20,25,28,31] 右：[42]（2）删除20后，结点[17,19,25,28,31]借位平衡，结构不变仅去20。六、算法设计与分析（共30分）34.（15分）设计算法判断无向图G是否为二分图，要求时间复杂度O(n+e)，给出伪代码并证明正确性。答案：采用BFS染色法：伪代码：color[1..n]←−1queueQfori=1..nifcolor[i]=−1thencolor[i]=0Q.push(i)whilenotQ.empty()dou=Q.pop()foreachvinadj[u]doifcolor[v]=−1thencolor[v]=1−color[u]Q.push(v)elseifcolor[v]=color[u]thenreturnfalsereturntrue正确性：BFS按层染色，若相邻同色则存在奇环，非二分图；否则二染色成功，为二分图。时间O(n+e)。35.（15分）给定整数数组A[0..n−1]，设计O(n)时间、O(1)额外空间的