安徽大学2025年数据结构期末考试试卷及答案

安徽大学2025年数据结构期末考试试卷及答案一、单项选择题（每小题2分，共20分）1.已知三个算法的时间复杂度函数分别为T₁(n)=n²+2n+3，T₂(n)=3nlog₂n+5n，T₃(n)=2ⁿ+log₂n。当n足够大时，三者的时间复杂度由低到高的顺序是（）A.T₁<T₂<T₃B.T₂<T₁<T₃C.T₃<T₁<T₂D.T₂<T₃<T₁2.对于长度为n的顺序表，在第i个位置（1≤i≤n+1）插入一个元素的时间复杂度为（）A.O(1)B.O(n)C.O(logn)D.O(n²)3.若元素入栈顺序为1、2、3、4、5，下列不可能的出栈顺序是（）A.5、4、3、2、1B.3、2、5、4、1C.2、3、1、5、4D.4、5、3、2、14.设循环队列的存储空间为Q[0..m-1]，初始时front=rear=0。经过一系列入队和出队操作后，front=20，rear=15（m=50），则队列中元素个数为（）A.5B.35C.45D.155.一棵完全二叉树有100个节点，其中叶子节点的个数是（）A.50B.51C.49D.486.对于有n个顶点和e条边的无向图，邻接表的存储空间复杂度为（）A.O(n)B.O(e)C.O(n+e)D.O(n×e)7.对长度为15的有序表进行二分查找，平均查找长度约为（）（取整）A.3B.4C.5D.68.下列排序算法中，不稳定的是（）A.冒泡排序B.归并排序C.插入排序D.快速排序9.哈希表中解决冲突的方法中，属于开放定址法的是（）A.链地址法B.再哈希法C.公共溢出区法D.线性探测法10.已知大顶堆的数组表示为[90,70,80,30,60,50,40]，删除堆顶元素后，调整后的堆数组为（）A.[80,70,50,30,60,40]B.[80,70,60,30,40,50]C.[70,60,80,30,50,40]D.[80,60,70,30,50,40]二、填空题（每空2分，共20分）1.算法T(n)=nlog₂n+2ⁿ的渐近时间复杂度为__________。2.双向链表中删除节点p（非头非尾）的操作需修改指针：p->prior->next=__________；p->next->prior=__________。3.表达式“3+5×(2-4)/6”的后缀表达式为__________。4.已知二叉树的后序遍历序列为D、E、B、F、C、A，中序遍历序列为D、B、E、A、F、C，则前序遍历序列为__________。5.一个无向连通图有8个顶点，其提供树的边数为__________。6.快速排序在最坏情况下的时间复杂度为__________。7.平衡二叉树中节点的平衡因子是该节点__________的高度差。8.若哈希表长度为11（地址0-10），采用除留余数法（取p=11），关键字47的哈希地址为__________。9.堆排序中建堆的时间复杂度为__________。10.线索二叉树中，节点的右线索指向其__________。三、判断题（每小题1分，共10分。正确填“√”，错误填“×”）1.顺序表的插入操作在表尾的时间复杂度为O(1)。（）2.队列是先进后出的线性结构。（）3.二叉树的前序遍历序列和后序遍历序列可以唯一确定一棵二叉树。（）4.邻接矩阵存储图时，空间复杂度与边数无关。（）5.冒泡排序的时间复杂度与初始序列的有序性无关。（）6.二分查找要求查找表必须是顺序存储的有序表。（）7.哈希表的查找效率主要取决于哈希函数的设计，与处理冲突的方法无关。（）8.堆的结构一定是完全二叉树。（）9.拓扑排序只能用于有向无环图（DAG）。（）10.归并排序的空间复杂度为O(n)。（）四、算法设计题（共30分）1.（10分）用C语言实现单链表的逆置操作。要求：函数原型为LinkListReverseList(LinkListL)，其中L为带头节点的单链表头指针，返回逆置后的链表头指针。2.（10分）编写二叉树中序遍历的非递归算法。要求：函数原型为voidInOrder(BiTreeT)，其中T为二叉树根节点指针，用栈模拟递归过程。3.（10分）实现快速排序的划分函数。要求：函数原型为intPartition(intarr[],intlow,inthigh)，将arr[low..high]划分为两部分，返回基准元素的最终位置。五、综合应用题（共20分）1.（10分）给定括号序列“([)]{}”，用栈判断该序列是否合法。要求：写出每一步栈的状态（栈底到栈顶）及最终结论。2.（10分）已知无向图G的邻接矩阵如下（顶点编号0-4）：\[\begin{bmatrix}0&1&1&0&0\\1&0&0&1&1\\1&0&0&0&1\\0&1&0&0&0\\0&1&1&0&0\\\end{bmatrix}\]（1）画出G的邻接表表示；（2）写出从顶点0出发的广度优先搜索（BFS）序列（假设访问顺序按顶点编号升序）；（3）计算顶点0到顶点3的最短路径长度（边数）。答案一、单项选择题1.B2.B3.C4.B5.A6.C7.B8.D9.D10.B二、填空题1.O(2ⁿ)2.p->next；p->prior3.3524-×6/+4.ABDECF5.76.O(n²)7.左子树与右子树8.4（47%11=4）9.O(n)10.后继节点三、判断题1.√2.×3.×4.√5.×6.√7.×8.√9.√10.√四、算法设计题1.单链表逆置```ctypedefstructLNode{intdata;structLNodenext;}LNode,LinkList;LinkListReverseList(LinkListL){LNodepre=NULL,cur=L->next,next;while(cur!=NULL){next=cur->next;//保存下一个节点cur->next=pre;//反转指针pre=cur;//前驱后移cur=next;//当前节点后移}L->next=pre;//头节点指向原尾节点（现头节点）returnL;}```2.中序遍历非递归算法```ctypedefstructBiTNode{intdata;structBiTNodelchild,rchild;}BiTNode,BiTree;voidInOrder(BiTreeT){BiTreep=T;SqStackS;//假设已定义顺序栈InitStack(S);//初始化栈while(p||!StackEmpty(S)){if(p){//向左走到最左Push(S,p);p=p->lchild;}else{//弹出并访问Pop(S,&p);printf("%d",p->data);//访问节点p=p->rchild;//转向右子树}}}```3.快速排序划分函数```cintPartition(intarr[],intlow,inthigh){intpivot=arr[low];//选择第一个元素为基准while(low<high){while(low<high&&arr[high]>=pivot)high--;arr[low]=arr[high];//比基准小的移到左边while(low<high&&arr[low]<=pivot)low++;arr[high]=arr[low];//比基准大的移到右边}arr[low]=pivot;//基准归位returnlow;//返回基准位置}```五、综合应用题1.括号匹配判断步骤：-初始栈空。-遇到'('，入栈→栈：(-遇到'['，入栈→栈：([-遇到')'，栈顶是'['，不匹配→失败？（实际应为：当前字符是')'，需匹配栈顶的'('，但此时栈顶是'['，故不匹配，序列不合法）。最终结论：序列“([)]{}”不合法