(2025年)数据结构期末复习(试卷)库题附答案

(2025年)数据结构期末复习(试卷)库题附答案一、单项选择题（每题2分，共20分）1.已知某算法的时间复杂度递推式为T(n)=2T(n/2)+n²，T(1)=1，则该算法的时间复杂度为（）A.O(n²)B.O(nlogn)C.O(n³)D.O(n²logn)2.若长度为n的顺序表中，在第i个位置（1≤i≤n+1）插入一个元素，需移动的元素个数为（）A.n-i+1B.n-iC.i-1D.i3.设循环队列的容量为50（下标从0到49），当前队头指针front=15，队尾指针rear=20（rear指向队尾元素的下一个位置），则队列中元素个数为（）A.5B.15C.20D.354.一个链栈的栈顶指针为top，若要删除栈顶元素并将其值保存到变量x中，正确的操作是（）A.x=top->data;top=top->next;B.top=top->next;x=top->data;C.x=top->data;free(top);D.free(top);x=top->data;5.已知一棵二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则后序遍历序列为（）A.DEBFCAB.DEBFCAC.DEBCFAD.DEFBAC6.具有n个节点的完全二叉树的深度为（）（深度从1开始计算）A.⎣log₂n⎦B.⎡log₂n⎤C.⎣log₂n⎦+1D.⎡log₂(n+1)⎤7.若图的邻接矩阵中主对角线元素均为0，其余元素为1，则该图一定是（）A.无向完全图B.有向完全图C.树D.环8.对关键字序列{55,33,44,77,22,66}进行冒泡排序（升序），第一趟排序后得到的序列是（）A.33,44,55,22,66,77B.33,55,44,22,66,77C.33,44,22,55,66,77D.33,22,44,55,66,779.哈希表采用链地址法处理冲突时，查找成功的平均查找长度取决于（）A.哈希表的装填因子B.哈希函数C.冲突次数D.表长10.对有序表{12,23,34,45,56,67,78,89}进行折半查找，查找元素67时，依次比较的元素是（）A.45,67B.56,67C.45,56,67D.56,78,67二、填空题（每空2分，共20分）1.数据结构的三要素包括逻辑结构、存储结构（物理结构）和__________。2.对于长度为n的顺序表，删除第i个元素（1≤i≤n）时，需向前移动__________个元素。3.若一个栈的输入序列是1,2,3,4，则其可能的输出序列中，最大的元素4不可能在第__________个位置（输出顺序从1开始计数）。4.一棵二叉树中，度为0的节点数为n₀，度为2的节点数为n₂，则n₀=__________。5.无向图的邻接表中，每条边被存储了__________次。6.对关键字序列{49,38,65,97,76,13,27}进行快速排序，以第一个元素为枢轴，第一趟划分后的序列为__________。7.高度为h的平衡二叉树（AVL树）的最小节点数为__________（用递推式表示）。8.已知哈希函数H(key)=keymod7，关键字序列{25,14,36,5,19}，采用线性探测法处理冲突，哈希表长度为7，则关键字19的存储地址是__________。9.拓扑排序适用于__________图（填“有向无环”或“无向”）。10.堆排序的时间复杂度为__________。三、判断题（每题2分，共20分）1.线性表的链式存储结构可以随机访问任意节点。（）2.队列的“假溢出”现象是由于队列中元素个数超过了数组容量。（）3.中序线索二叉树中，节点的右线索指向其后继节点。（）4.完全二叉树的叶子节点只能在最后两层出现。（）5.有向图的强连通分量是极大强连通子图。（）6.直接插入排序的时间复杂度在最好情况下为O(n)。（）7.哈希表的查找效率仅与哈希函数的设计有关。（）8.树的后序遍历序列与其对应的二叉树的后序遍历序列相同。（）9.归并排序是一种不稳定的排序算法。（）10.稀疏矩阵的三元组表存储方式可以节省存储空间，但会降低查找效率。（）四、应用题（每题8分，共40分）1.已知双向链表节点结构为prior|data|next，头指针为L，当前节点为p（非头节点，非尾节点），请画出删除p节点的指针调整过程，并写出关键操作语句。2.给定二叉树的层次遍历序列为ABCDEFG，中序遍历序列为DBEAFGC，画出该二叉树的结构，并写出其先序遍历和后序遍历序列。3.有向图G的邻接表如下（边为A→B,A→C,B→D,C→D,C→E,D→E），要求：（1）画出该图的邻接矩阵；（2）从节点A出发，写出深度优先搜索（DFS）和广度优先搜索（BFS）的遍历序列（假设节点按字母顺序访问）。4.构造权值为{3,5,7,9,11}的哈夫曼树，计算其带权路径长度（WPL）。5.对序列{23,14,56,37,9,82,41}进行希尔排序，取增量序列为{3,1}，写出每一趟排序后的结果。五、综合题（每题10分，共20分）1.设计一个算法，判断一个链表是否为回文链表（即正向和反向读取的序列相同）。要求用文字描述算法思路，并给出关键步骤的伪代码。2.已知某图的顶点集合为{V1,V2,V3,V4,V5}，边的权值矩阵如下（∞表示无直接边）：\[\begin{bmatrix}0&4&∞&2&∞\\4&0&5&∞&∞\\∞&5&0&1&3\\2&∞&1&0&6\\∞&∞&3&6&0\\\end{bmatrix}\]使用Dijkstra算法求V1到其他各顶点的最短路径，要求写出每一步的距离数组和前驱节点。答案一、单项选择题1.D（主定理：a=2,b=2,f(n)=n²，n^(log_ba)=n^1<n²，故T(n)=O(n²logn)）2.A（插入位置i后有n-i+1个元素需后移）3.A（(rear-front+50)%50=5）4.A（先保存栈顶数据，再移动栈顶指针）5.B（先序确定根A，中序划分左右子树DBE和FC，递归构造后序为DEBFCA）6.C（完全二叉树深度为⎣log₂n⎦+1）7.B（有向完全图任意两节点间有双向边，邻接矩阵非对角线全为1）8.B（第一趟比较5次，55与33交换→33,55,44,77,22,66；55与44交换→33,44,55,77,22,66；55与77不交换；77与22交换→33,44,55,22,77,66；77与66交换→33,44,55,22,66,77，实际第一趟结束应为33,44,55,22,66,77？但选项中B更接近，可能题目数据调整）9.A（链地址法的平均查找长度与装填因子α=n/m有关）10.C（初始low=1,high=8,mid=4（45）；67>45，low=5,mid=6（56）；67>56，low=7,mid=7（67））二、填空题1.数据的运算（或操作）2.n-i3.1（输出序列中4最早在第4位，如1,2,3,4；最晚在第4位，不可能在第1位）4.n₂+1（二叉树性质n₀=n₂+1）5.2（无向图每条边在两个顶点的邻接表中各存一次）6.{27,38,13,49,76,97,65}（以49为枢轴，比49小的放左边，大的放右边）7.F(h)=F(h-1)+F(h-2)+1（F(1)=1,F(2)=2）8.5（25→4,14→0,36→1（36mod7=1）,5→5,19→19mod7=5，冲突后探测5+1=6（空），但5的位置被5占用，19mod7=5，5已被占，线性探测下一个位置6？原题可能计算错误，正确应为：25→4,14→0,36→1,5→5,19→19%7=5（冲突），探测6（空），故地址6？需重新计算：哈希表地址0-6。25%7=4→地址4；14%7=0→地址0；36%7=1→地址1；5%7=5→地址5；19%7=5（冲突），探测地址6（未被占），故19存地址6。可能题目答案为6）9.有向无环10.O(nlogn)三、判断题1.×（链式存储只能顺序访问）2.×（假溢出是由于队头指针未归零，实际容量未满）3.√（中序线索的右线索指向后继）4.√（完全二叉树叶子节点只能在最后一层或倒数第二层）5.√（强连通分量是极大强连通子图）6.√（最好情况已有序，比较n-1次，移动0次，时间O(n)）7.×（还与处理冲突的方法、装填因子有关）8.×（树的后序遍历对应二叉树的中序遍历）9.×（归并排序是稳定的）10.√（三元组表只存非零元素，查找需遍历）四、应用题1.指针调整过程：p的前驱节点的next指向p的后继节点；p的后继节点的prior指向p的前驱节点。关键语句：p->prior->next=p->next;p->next->prior=p->prior;free(p);2.二叉树结构：根A，左子树层次遍历B，中序DBE→B为根，左子树D，右子树E；右子树层次遍历C，中序FGC→C为根，左子树F，右子树G。结构：A/\BC/\/\DEFG先序遍历：ABDECFG；后序遍历：DEBFGCA3.（1）邻接矩阵（行/列：A,B,C,D,E）：\[\begin{bmatrix}0&1&1&0&0\\0&0&0&1&0\\0&0&0&1&1\\0&0&0&0&1\\0&0&0&0&0\\\end{bmatrix}\]（2）DFS序列：A→B→D→E→C（或A→C→D→E→B）；BFS序列：A→B→C→D→E（按字母顺序）4.哈夫曼树构造步骤：-选3,5→8（父节点），剩余7,8,9,11-选7,8→15（父节点），剩余9,11,15-选9,11→20（父节点），剩余15,20-选15,20→35（根）树结构：根35，左15（左7，右8（左3，右5）），右20（左9，右11）WPL=3×3+5×3+7×2+9×2+11×2=9+15+14+18+22=785.希尔排序过程：增量3：分组为{23,37,41},{14,9,82},{56}各组排序：23,9,56,37,14,82,41→第一趟后：9,14,56,23,37,82,41增量1（直接插入排序）：插入14（已序）→9,14,56,23,37,82,41插入56（已序）→9,14,56,23,37,82,41插入23：14后插入→9,14,23,56,37,82,41插入37：56前插入→9,14,23,37,56,82,41插入82（已序）→9,14,23,37,56,82,41插入41：56前插入→9,14,23,37,41,56,82最终结果：9,14,23,37,41,56,82五、综合题1.算法思路：使用快慢指针找到链表中点，反转后半部分链表，比较前后两部分是否相同。伪代码：functionisPalindrome(head):ifheadisnullorhead.nextisnull:returntrueslow=headfast=headwhilefast.nextandfast.next.next:slow=slow.nextfast=fast.next.next//反转后半部分prev=nullcurr=slow.nextwhilecurr:next=curr.nextcurr.next=prevprev=currcurr=next//比较前后部分p1=headp2=prevwhilep2:ifp1.dat