2025年数据结构c语言版期末试题及答案

2025年数据结构c语言版期末试题及答案一、选择题（每题2分，共20分）1.以下数据结构中，属于非线性结构的是（）。A.循环队列B.双向链表C.二叉排序树D.顺序栈2.已知某算法的时间复杂度递推式为T(n)=2T(n/2)+n（n>1），T(1)=1，则其时间复杂度为（）。A.O(n)B.O(nlogn)C.O(n²)D.O(n³)3.对于长度为n的顺序表，删除第i个元素（1≤i≤n）时，需向前移动的元素个数为（）。A.n-iB.n-i+1C.n-i-1D.i4.设栈的输入序列为1,2,3,4,5，则不可能的输出序列是（）。A.5,4,3,2,1B.3,2,5,4,1C.2,3,1,5,4D.1,5,4,3,25.若用数组data[0...maxsize-1]存储循环队列，front和rear分别表示队头和队尾指针，则队满的条件是（）。A.(rear+1)%maxsize==frontB.rear==frontC.(rear-1)%maxsize==frontD.rear+1==front6.一棵深度为k的完全二叉树（根节点深度为1），其节点数最少为（）。A.2^(k-1)B.2^k-1C.2^(k-1)+1D.2^k7.对图G进行广度优先搜索（BFS）时，通常采用的辅助数据结构是（）。A.栈B.队列C.二叉树D.哈希表8.对关键字序列{55,34,89,21,67,12}进行直接插入排序，第三趟排序后的序列是（）。A.{21,34,55,89,67,12}B.{12,21,34,55,67,89}C.{34,55,89,21,67,12}D.{21,34,55,67,89,12}9.对于哈希表，若采用链地址法处理冲突，则平均查找长度（）。A.与哈希表的装填因子有关B.仅与哈希函数有关C.与表长无关D.恒等于110.若有向图的邻接矩阵中，主对角线元素均为0，其余元素全为1，则该图一定是（）。A.强连通图B.完全图C.有环图D.稀疏图二、填空题（每空2分，共20分）1.数据的逻辑结构分为线性结构和__________。2.单链表中，已知指针p指向某节点，若要在p之后插入指针q指向的新节点，需执行的操作是__________。3.一个栈的输入序列为a,b,c,d，若输出序列的第一个元素是c，则第四个输出元素可能是__________（写出一个即可）。4.若二叉树的前序遍历序列为ABDECFG，中序遍历序列为DBEAFCG，则后序遍历序列为__________。5.对于n个顶点的无向连通图，其提供树至少包含__________条边。6.对序列{45,38,66,90,88,10,25}进行快速排序，以第一个元素为枢轴，第一趟划分后的序列为__________。7.设哈希表长度为11（地址0~10），哈希函数为H(key)=key%11，采用线性探测法处理冲突。若依次插入关键字25、37、16、48，则关键字48的存储地址是__________。8.一个满二叉树有63个节点，其叶子节点数为__________。9.设循环队列的容量为50（下标0~49），初始时front=rear=20。若执行15次入队操作和5次出队操作后，front=__________，rear=__________。三、判断题（每题1分，共10分）1.顺序存储结构的优点是存储密度高，且便于插入和删除操作。（）2.栈和队列都是操作受限的线性表，栈的删除操作在表尾，队列的删除操作在表头。（）3.完全二叉树的叶子节点只能出现在最后两层。（）4.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）5.直接选择排序是一种稳定的排序算法。（）6.中序遍历二叉排序树可以得到一个有序序列。（）7.拓扑排序只能用于有向无环图（DAG）。（）8.二分查找的时间复杂度为O(logn)，因此比顺序查找更适用于所有情况。（）9.用Prim算法和Kruskal算法求最小提供树，得到的提供树边权之和一定相同。（）10.哈希表的查找效率主要取决于哈希函数的设计和冲突处理方法。（）四、应用题（共30分）1.（8分）已知带头节点的单链表L存储整数，设计一个算法删除表中所有值为奇数的节点。要求：（1）写出算法的基本思路；（2）用C语言实现该算法（结构体定义：typedefstructLNode{intdata;structLNodenext;}LNode,LinkList）。2.（8分）已知二叉树的后序序列为DEBFGCA，中序序列为DBEAFCG。（1）画出该二叉树的逻辑结构；（2）写出其前序遍历序列。3.（7分）对图1所示的无向图，用Dijkstra算法求顶点A到其他各顶点的最短路径（要求写出每一步的距离数组和前驱节点）。图1：无向图结构（顶点：A,B,C,D,E；边：A-B(2),A-C(5),B-C(1),B-D(4),C-E(3),D-E(1)）4.（7分）设关键字序列为{23,14,35,42,56,17,28}，哈希表长度为13，哈希函数H(key)=key%13，采用链地址法处理冲突。（1）构造哈希表；（2）计算查找成功时的平均查找长度（ASL）。五、综合题（共20分）1.（12分）设计一个算法，判断两个二叉树是否相似（相似指结构相同，节点值无关）。要求：（1）写出算法的递归思路；（2）用C语言实现（二叉树结构体定义：typedefstructBiTNode{intdata;structBiTNodelchild,rchild;}BiTNode,BiTree）；（3）分析算法的时间复杂度。2.（8分）假设用两个栈S1和S2模拟一个队列，队列的入队操作由S1完成，出队操作由S2完成。（1）简述入队和出队的操作步骤；（2）分析该模拟队列可能出现的异常情况。答案一、选择题1.C2.B3.A4.C5.A6.A7.B8.A9.A10.C二、填空题1.非线性结构2.q->next=p->next;p->next=q3.a（或d）4.DEBFGCA5.n-16.{25,38,10,45,88,90,66}（或其他正确划分结果）7.6（计算过程：25%11=3；37%11=4；16%11=5；48%11=4（冲突），探测5（冲突），探测6，存储地址6）8.32（满二叉树叶子节点数为2^(h-1)，63=2^6-1，h=6，叶子数2^5=32）9.25；35（front=20+5=25，rear=20+15=35，模50后不变）三、判断题1.×2.√3.√4.×5.×6.√7.√8.×9.√10.√四、应用题1.（1）思路：遍历链表，用前驱指针跟踪当前节点的前驱，若当前节点值为奇数，则删除该节点（前驱指针的next指向当前节点的next，释放当前节点）；否则继续遍历。（2）代码：```cvoidDeleteOdd(LinkListL){LNodepre=L,p=L->next;while(p!=NULL){if(p->data%2!=0){pre->next=p->next;free(p);p=pre->next;}else{pre=p;p=p->next;}}}```2.（1）二叉树结构：根为A，左子树中根为B（左子树D，右子树E），右子树中根为C（左子树F，右子树G）。（2）前序序列：ABDECFG3.Dijkstra算法步骤（初始距离数组：A到A=0，其余∞；前驱均为-1）：第1步选A（距离0），更新邻接点：B(2)、C(5)，距离数组[A:0,B:2,C:5,D:∞,E:∞]，前驱[-,A,A,-,-]第2步选B（距离2），更新邻接点：C(2+1=3<5)、D(2+4=6)，距离数组[A:0,B:2,C:3,D:6,E:∞]，前驱[-,A,B,B,-]第3步选C（距离3），更新邻接点：E(3+3=6)，距离数组[A:0,B:2,C:3,D:6,E:6]，前驱[-,A,B,B,C]第4步选D（距离6），更新邻接点：E(6+1=7>6，不更新)，距离数组不变第5步选E（距离6），无更新。最终最短路径：A→B(2)，A→B→C(3)，A→B→D(6)，A→B→C→E(6)4.（1）哈希表结构（地址0~12）：地址0：空；地址1：14→27（17%13=4，28%13=2，此处修正：17%13=4，28%13=2，原序列为23(10)、14(1)、35(9)、42(3)、56(4)、17(4)、28(2)。正确链地址：地址1:14；地址2:28；地址3:42；地址4:56→17；地址9:35；地址10:23；其余空。（2）ASL=(1+1+1+2+1+1+2)/7=9/7≈1.29五、综合题1.（1）递归思路：若两棵树均为空，相似；若一棵空另一棵非空，不相似；否则递归判断左子树和右子树是否分别相似。（2）代码：```cboolIsSimilar(BiTreeT1,BiTreeT2){if(T1==NULL&&T2==NULL)returntrue;if(T1==NULL||T2==NULL)returnfalse;returnIsSim