2025年《数据结构》期末考试试卷试题及答案

2025年《数据结构》期末考试试卷试题及答案一、单项选择题（每题2分，共20分）1.已知某算法的时间复杂度函数为T(n)=2n³+3n²logn+5n+7，其渐近时间复杂度为（）。A.O(n³)B.O(n²logn)C.O(n²)D.O(nlogn)2.若需频繁在链表中间插入或删除元素，最不适合的存储结构是（）。A.单链表B.双向链表C.循环链表D.顺序表3.一个栈的输入序列为1,2,3,4,5，不可能的输出序列是（）。A.5,4,3,2,1B.3,4,1,5,2C.2,3,1,5,4D.1,3,2,5,44.若用数组Q[0..m-1]实现循环队列，队列头指针为front，尾指针为rear，则队列中元素个数为（）。A.(rear-front+1)%mB.(rear-front+m)%mC.(rear-front)%mD.rear-front5.一棵完全二叉树有100个节点，其叶子节点数为（）。A.49B.50C.51D.526.对于图G=(V,E)，若从顶点v出发进行广度优先搜索（BFS）能访问所有顶点，则G一定是（）。A.无向图B.强连通图C.连通图D.有向图7.哈希表采用开放定址法解决冲突时，若插入新元素发生冲突，则需继续寻找下一个空槽。若哈希函数为H(key)=key%11，冲突处理函数为H_i=(H(key)+i²)%11（二次探测），则插入关键字25时，探测的第二个位置是（）。A.3B.4C.5D.68.对序列{23,14,56,37,8,91,45}进行快速排序，以第一个元素为基准，一次划分后的结果是（）。A.{8,14,23,37,56,91,45}B.{8,14,37,23,56,91,45}C.{8,14,23,56,37,91,45}D.{8,14,23,37,56,45,91}9.若二叉排序树中插入一个新节点后仍保持二叉排序树的性质，则该节点的位置由（）决定。A.前序遍历B.中序遍历C.节点值的大小D.后序遍历10.对n个元素进行归并排序，其空间复杂度为（）。A.O(1)B.O(n)C.O(nlogn)D.O(n²)二、填空题（每空2分，共20分）1.数据的逻辑结构分为集合、线性结构、树形结构和__________。2.一个单链表中，已知指针p指向某个节点，若要删除p的后继节点（假设存在），需执行操作：__________。3.若一个栈的输入序列长度为n，则其可能的输出序列共有__________种（用卡特兰数表示）。4.深度为h的满二叉树中，叶子节点数为__________。5.无向图的邻接矩阵是__________矩阵（填“对称”或“非对称”）。6.对于有序表{5,12,23,35,47,58,69,80}，采用二分查找法查找元素58时，需比较__________次。7.堆排序的时间复杂度为__________。8.线索二叉树中，每个节点的右线索指向其__________（填“前驱”或“后继”）。9.拓扑排序适用于__________图（填“有向无环”或“无向连通”）。10.若哈希表的装填因子α=0.75，表长为16，则最多可存储__________个元素。三、判断题（每题2分，共10分。正确填“√”，错误填“×”）1.顺序存储的线性表可以随机访问，链式存储的线性表只能顺序访问。（）2.队列的“假溢出”是由于队列中元素个数超过数组长度导致的。（）3.二叉树的前序遍历序列和后序遍历序列可以唯一确定一棵二叉树。（）4.强连通图中任意两个顶点之间都存在两条方向相反的路径。（）5.直接插入排序在最好情况下（已有序）的时间复杂度为O(n)。（）四、应用题（共40分）1.（10分）已知二叉树的中序遍历序列为DBEAFC，后序遍历序列为DEBFCA。（1）画出该二叉树的结构；（2）写出其前序遍历序列。2.（10分）图G的邻接表表示如下（顶点编号为1-5，边权为正整数）：1:(2,3)→(3,5)→null2:(1,3)→(4,2)→null3:(1,5)→(4,4)→(5,1)→null4:(2,2)→(3,4)→(5,6)→null5:(3,1)→(4,6)→null（1）画出图G的无向图结构（假设边是无向的）；（2）使用Kruskal算法求G的最小提供树，写出选边顺序及最终总权值。3.（10分）对序列{42,15,36,28,50,12,48}进行希尔排序，初始增量d=3，后续增量依次为d=2、d=1。（1）写出各趟排序后的序列；（2）比较希尔排序与直接插入排序的优缺点。4.（10分）设哈希表表长m=13，哈希函数H(key)=key%13，采用链地址法处理冲突。将关键字序列{25,38,16,47,52,63,71}依次插入哈希表。（1）画出最终的哈希表结构；（2）计算查找成功时的平均查找长度（ASL）。五、算法设计题（共10分）设计一个算法，判断一个单链表是否为回文链表（即链表正读和反读相同）。要求时间复杂度为O(n)，空间复杂度为O(1)。（注：单链表节点结构为structNode{intdata;Nodenext;};）答案一、单项选择题1-5:ADBBB6-10:CBACB二、填空题1.图状结构（或网状结构）2.p->next=p->next->next;（需先保存p->next的后继）3.C(2n,n)/(n+1)（或卡特兰数表达式）4.2^(h-1)5.对称6.37.O(nlogn)8.后继9.有向无环10.12三、判断题1.√2.×3.×4.√5.√四、应用题1.（1）二叉树结构：A/\BC/\/DEF（2）前序遍历序列：ABDECF2.（1）无向图结构（顶点1-5，边权对应邻接表）：1-2(3),1-3(5),2-4(2),3-4(4),3-5(1),4-5(6)（2）Kruskal选边顺序（按权值从小到大）：3-5(1)→2-4(2)→1-2(3)→3-4(4)→总权值=1+2+3+4=10（最后一条边1-3(5)会形成环，不选）3.（1）各趟排序：初始序列：42,15,36,28,50,12,48（n=7，d=3）d=3时，子序列为[42,28,48],[15,50],[36,12]排序后子序列：[28,42,48],[15,50],[12,36]合并后序列：28,15,12,42,50,36,48d=2时，子序列为[28,12,50,48],[15,42,36]排序后子序列：[12,28,48,50],[15,36,42]合并后序列：12,15,28,36,48,42,50d=1时，直接插入排序后：12,15,28,36,42,48,50（2）希尔排序优点：利用分组插入减少逆序对，时间效率高于直接插入；缺点：时间复杂度依赖增量选择，不稳定。直接插入排序优点：简单稳定，最好情况O(n)；缺点：最坏情况O(n²)，效率低。4.（1）哈希表结构（链地址法，m=13）：索引0:52（52%13=0）索引1:63（63%13=11→63-13×4=11？计算错误，正确H(63)=63%13=11（13×4=52,63-52=11），H(25)=25%13=12，H(38)=38%13=12（38-2×13=12），H(16)=16%13=3，H(47)=47%13=8（13×3=39,47-39=8），H(52)=52%13=0，H(63)=63%13=11，H(71)=71%13=6（13×5=65,71-65=6）。修正后各关键字的哈希地址：25→12，38→12（冲突，链在25后），16→3，47→8，52→0，63→11，71→6。哈希表结构：0:52→null1:null2:null3:16→null4:null5:null6:71→null7:null8:47→null9:null10:null11:63→null12:25→38→null（2）ASL计算：各关键字查找次数为1（52,16,47,71,63）、2（25）、2（38）。总次数=1×5+2×2=9，ASL=9/7≈1.29。五、算法设计题思路：快慢指针找中点→反转后半部分链表→比较前后两部分是否相同。算法步骤：1.初始化快指针fast和慢指针slow，均指向头节点；2.快指针每次走两步，慢指针每次走一步，直到fast或fast->next为null，此时slow指向中点（奇数长度时为中间节点，偶数时为前半部分末尾）；3.反转slow之后的链表（后半部分）；4.同时遍历原链表前半部分和反转后的后半部分，比较节点值是否全部相同；5.若全部相同则返回true，否则返回false；最后恢复原链表（可选）。代码实现：```cppboolisPalindrome(Nodehead){if(head==nullptr||head->next==nullptr)returntrue;//找中点Nodeslow=head;Nodefast=head;while(fast->next!=nullptr&&fast->next->next!=nullptr){slow=slow->next;fast=fast->next->next;}//反转后半部分Nodeprev=nullptr;Nodecurr=slow->next;while(curr!=nullptr){Nodenext=curr->next;curr->next=prev;prev=curr;curr=next;}slow->nex