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³)2.若一个长度为n的顺序表的表尾插入操作的时间复杂度为O(1)，则该操作（）A.必须移动所有元素B.不需要移动任何元素C.移动元素的次数为n-1D.移动元素的次数为13.设循环队列的存储空间为Q(1:m)，初始时front=rear=m。经过一系列入队和出队操作后，front=2，rear=1。此时队列中的元素个数为（）A.m-1B.mC.1D.04.一棵完全二叉树有100个节点，其中叶子节点的个数为（）A.49B.50C.51D.525.对图G进行广度优先搜索（BFS）时，若使用队列存储待访问节点，则同一层的节点被访问的顺序是（）A.任意顺序B.从左到右C.先进先出D.后进先出6.下列排序算法中，空间复杂度为O(1)且不稳定的是（）A.冒泡排序B.快速排序C.归并排序D.堆排序7.哈希表中解决冲突的链地址法（拉链法）本质上是将哈希表的每个单元转换为一个（）A.顺序表B.链表C.二叉树D.哈希表8.若在平衡二叉树（AVL树）中插入一个节点导致失衡，且失衡节点的左孩子的右子树高度更高，则应进行（）A.LL型旋转B.RR型旋转C.LR型旋转D.RL型旋转9.对关键字序列{23,14,35,42,10,5}进行直接插入排序，第三趟排序后的序列为（）A.{14,23,35,42,10,5}B.{10,14,23,35,42,5}C.{14,23,10,35,42,5}D.{10,14,23,42,35,5}10.若有向图的邻接矩阵中主对角线元素均为0，其余元素为1，则该图（）A.是完全图B.存在环C.所有节点入度等于出度D.是强连通图二、填空题（每空2分，共20分）1.对于n个元素的线性表，顺序表的随机访问时间复杂度为______，单链表的随机访问时间复杂度为______。2.一个栈的输入序列为1,2,3,4,5，若输出序列的第一个元素是3，则最后一个输出元素可能是______（写出一个即可）。3.一棵二叉树的中序遍历序列为D,B,A,E,C,F，后序遍历序列为D,B,E,F,C,A，则其根节点为______，左子树的中序遍历序列为______。4.无向图G有10个顶点，若其边数为15，则G的补图有______条边（完全图边数公式：n(n-1)/2）。5.对长度为n的有序表进行二分查找，最坏情况下的时间复杂度为______；若表中元素存储在单链表中，则二分查找______（填“可行”或“不可行”）。6.堆排序的建堆过程时间复杂度为______，堆排序的总时间复杂度为______。三、判断题（每题2分，共10分。正确打√，错误打×）1.线性表的顺序存储结构比链式存储结构更节省存储空间。（）2.队列的“假溢出”现象可以通过循环队列解决。（）3.哈夫曼树中权值最小的两个节点一定是兄弟节点。（）4.拓扑排序只能用于有向无环图（DAG）。（）5.基数排序的时间复杂度与关键字的位数无关。（）四、应用题（共40分）1.（8分）已知单链表L的头节点为head（带头节点），其元素为整数。设计一个算法，删除L中所有值为偶数的节点，并返回修改后的链表头节点。要求：用文字描述算法步骤，并用C语言伪代码实现。2.（10分）给定二叉树的前序遍历序列为A,B,D,G,C,E,F，中序遍历序列为D,B,G,A,E,C,F。（1）画出该二叉树的逻辑结构；（2）写出该二叉树的后序遍历序列；（3）计算该二叉树的高度（根节点为第1层）。3.（10分）图G的邻接表表示如下（边权均为正整数）：节点0：→1(3)→2(5)节点1：→0(3)→3(2)→4(4)节点2：→0(5)→3(6)节点3：→1(2)→2(6)→4(1)节点4：→1(4)→3(1)（1）画出图G的逻辑结构（用节点0-4表示，边权标注）；（2）使用Dijkstra算法求节点0到其他所有节点的最短路径，写出每一步的距离数组和选中的节点。4.（12分）对关键字序列{45,32,67,18,25,50,73,8}进行快速排序，以第一个元素为基准（枢轴）。（1）写出第一趟划分后的序列；（2）描述快速排序的递归过程（用子序列范围表示）；（3）若序列初始已按升序排列，快速排序的时间复杂度为______，此时可通过______优化方法提高效率。五、算法设计题（共10分）设计一个算法，判断一个二叉树是否为完全二叉树。要求：（1）用文字描述算法思路；（2）用C语言编写二叉树节点结构体，并给出具体实现代码（需处理空树情况）。答案一、单项选择题1.C2.B3.A4.B5.C6.D7.B8.C9.A10.D二、填空题1.O(1)；O(n)2.1或2或4或5（任意一个）3.A；D,B4.20（完全图边数为45，45-15=30？原题计算错误，正确应为n=10时完全图边数是45，补图边数=45-15=30，此处修正为30）5.O(logn)；不可行6.O(n)；O(nlogn)三、判断题1.×（链式存储可能有指针开销）2.√3.√4.√5.×（与位数有关）四、应用题1.算法步骤：（1）初始化前驱指针pre为头节点，当前指针p为头节点的下一个节点；（2）遍历链表，若p的值为偶数，则pre的next指向p的next，释放p，p移动到pre的next；（3）若p的值为奇数，则pre和p均后移一位；（4）重复直到p为空，返回头节点。伪代码：```ctypedefstructLNode{intdata;structLNodenext;}LNode,LinkList;LinkListdeleteEven(LinkListhead){if(head->next==NULL)returnhead;//空表直接返回LNodepre=head,p=head->next;while(p!=NULL){if(p->data%2==0){//偶数节点pre->next=p->next;free(p);p=pre->next;}else{//奇数节点pre=p;p=p->next;}}returnhead;}```2.（1）二叉树结构：```A/\BC/\/\DGEF```（2）后序遍历序列：D,G,B,E,F,C,A（3）高度：4（根A为第1层，B、C为第2层，D、G、E、F为第3层，无第4层节点？实际高度应为3，根到最远叶子的路径长度：A→B→D（3层），或A→C→F（3层），故高度为3）3.（1）图G结构：节点0连1（3）、2（5）；节点1连0（3）、3（2）、4（4）；节点2连0（5）、3（6）；节点3连1（2）、2（6）、4（1）；节点4连1（4）、3（1）。（2）Dijkstra算法步骤（初始距离数组dist=[0,∞,∞,∞,∞]，已选集合S=∅）：-第1步：选节点0（dist=0），更新邻接节点：dist[1]=3，dist[2]=5，其余∞；S={0}-第2步：选节点1（最小dist=3），更新邻接节点：3的dist=3+2=5（原∞），4的dist=3+4=7；当前dist=[0,3,5,5,7]；S={0,1}-第3步：选节点2或3（dist均为5），选节点2：更新节点3的dist=5+6=11（原5更小，不更新）；dist不变；S={0,1,2}-第4步：选节点3（dist=5），更新节点4的dist=5+1=6（原7更小，更新为6）；当前dist=[0,3,5,5,6]；S={0,1,2,3}-第5步：选节点4（dist=6），无未更新节点；最终最短路径：0→1（3），0→2（5），0→1→3（5），0→1→3→4（6）4.（1）第一趟划分（基准45）：初始化low=0（45），high=7（8）；-high左移找<45的数：8（索引7），交换low和high，序列{8,32,67,18,25,50,73,45}，low=0→1，high=7→6-low右移找>45的数：67（索引2），交换low和high，序列{8,32,73,18,25,50,67,45}，low=2→3，high=6→5-high左移找<45的数：50（索引5）>45，继续到25（索引4）<45，交换low和high，序列{8,32,25,18,73,50,67,45}，low=3→4，high=4→3（low≥high，结束）最终基准位置为4，序列：{8,32,25,18,45,50,67,73}（2）递归过程：-左子序列：0~3（{8,32,25,18}）-右子序列：5~7（{50,67,73}）左子序列递归划分，右子序列递归划分，直到子序列长度≤1。（3）O(n²)；三数取中法（或随机选择枢轴）五、算法设计题1.算法思路：完全二叉树的特点是除最后一层外，其他层节点满，最后一层节点从左到右连续。使用层序遍历，遇到第一个空节点后，后续所有节点必须为空。具体步骤：（1）若树为空，是完全二叉树；（2）初始化队列，将根节点入队；（3）标记是否遇到空节点（初始为false）；（4）循环出队：-若当前节点为空，标记为true；-若当前节点非空且已标记过空节点，返回false；-将当前节点的左右子节点入队（无论是否为空）；（5）遍历结束后返回true。2.代码实现：```ctypedefstructBiTNode{intdata;structBiTNodelchild,rchild;}BiTNode,BiTree;boolisCompleteTree(BiTreeT){if(T==NULL)returntrue;//空树是完全二叉树BiTreequeue[100];//假设队列足够大intfront=0,rear=0;boolflag=false;//标记是否遇到空节点queue[rear++]=T;while(front<rear){BiTreep=queue[front++];