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

2025年大学数据结构期末试卷及答案一、选择题（每题2分，共20分）1.已知算法中某段代码的执行次数为T(n)=n+2nlog₂n+3n²，则其时间复杂度为（）A.O(n)B.O(nlog₂n)C.O(n²)D.O(n³)2.若进栈序列为1,2,3,4,5，且进栈和出栈操作可交替进行，则不可能的出栈序列是（）A.5,4,3,2,1B.3,2,5,4,1C.2,3,5,1,4D.1,2,3,4,53.一棵完全二叉树有100个结点，其中叶子结点的个数是（）A.49B.50C.51D.524.对于无向图的邻接矩阵存储，以下说法正确的是（）A.邻接矩阵的空间复杂度为O(n+e)B.邻接矩阵中第i行非零元素个数等于顶点i的入度C.邻接矩阵的对角线元素一定为0D.邻接矩阵适用于稀疏图5.对序列{3,1,4,1,5,9,2,6}进行快速排序，以第一个元素为枢轴，一次划分后的结果是（）A.{1,1,2,3,5,9,4,6}B.{2,1,1,3,5,9,4,6}C.{1,1,3,2,5,9,4,6}D.{1,1,2,3,4,9,5,6}6.若某哈希表的装填因子α=0.8，表长m=10，则哈希表中元素个数为（）A.6B.8C.10D.127.以下排序算法中，不稳定的是（）A.冒泡排序B.归并排序C.直接插入排序D.快速排序8.线索二叉树中，某结点的右线索指向其（）A.右孩子B.前驱C.后继D.父结点9.一个有向图的邻接表中有5个边结点，其中顶点A的邻接表包含2个边结点，则顶点A的出度为（）A.2B.3C.5D.不确定10.对长度为n的有序表进行二分查找，最坏情况下的时间复杂度为（）A.O(n)B.O(n²)C.O(log₂n)D.O(nlog₂n)二、填空题（每空2分，共20分）1.一个栈的输入序列为a,b,c,d，若输出序列的第一个元素是c，则第四个输出元素可能是______（写出一个即可）。2.一棵深度为5的满二叉树，其叶子结点数为______。3.已知某二叉树的后序遍历序列为d,e,b,f,c,a，中序遍历序列为d,b,e,a,f,c，则前序遍历序列为______。4.对于图的邻接表存储，若要删除边(u,v)，需要在u的邻接表中删除v的结点，并在______的邻接表中删除u的结点（无向图）。5.对序列{5,3,8,6,7,2,1,4}进行希尔排序，取增量序列为4,2,1，第一趟（增量4）排序后的序列为______。6.一个带权无向图的最小提供树可能不唯一，但其______一定唯一。7.若用循环队列存储元素，队列长度为m，队头指针为front，队尾指针为rear（指向队尾元素的下一个位置），则队列中元素个数为______。8.已知哈希函数H(key)=key%7，采用线性探测法处理冲突，将关键字序列{15,23,37,42,55}依次插入初始为空的哈希表（表长7），则关键字55的存储地址为______。9.高度为h的平衡二叉树（根结点高度为1），最少结点数为______（用斐波那契数列表示）。10.对n个元素进行堆排序，构建初始堆的时间复杂度为______。三、判断题（每题1分，共10分。正确打√，错误打×）1.顺序表的插入操作时间复杂度一定为O(n)。（）2.队列的链式存储不会出现假溢出。（）3.二叉树的前序遍历序列和后序遍历序列可以唯一确定一棵二叉树。（）4.图的深度优先搜索遍历序列是唯一的。（）5.快速排序的枢轴选择会影响其时间复杂度。（）6.哈希表的查找效率主要取决于哈希函数的设计。（）7.堆是一种完全二叉树。（）8.中序线索二叉树中，左线索一定指向当前结点的前驱。（）9.稀疏矩阵的压缩存储会丢失原矩阵的信息。（）10.归并排序是一种稳定的排序算法。（）四、算法设计题（每题10分，共30分）1.设计一个算法，将带头结点的单链表L逆置（要求空间复杂度为O(1)）。2.编写一个非递归算法，实现二叉树的中序遍历。3.已知无向图G采用邻接表存储，设计一个递归算法，判断G是否为连通图。五、综合应用题（每题10分，共20分）1.用栈实现中缀表达式“3+5((2-4)/6+7)”的求值，要求写出转换为后缀表达式的过程及最终计算结果。2.给定权值集合{7,5,2,4,9}，构造哈夫曼树，计算其带权路径长度（WPL），并给出每个权值对应的哈夫曼编码。答案一、选择题1.C2.C3.B4.C5.A6.B7.D8.C9.A10.C二、填空题1.d（或a、b等，合理即可）2.163.a,b,d,e,c,f4.v5.{2,3,1,4,7,5,8,6}6.总权值7.(rear-front+m)%m8.5（计算过程：15%7=1，23%7=2，37%7=2（冲突，探测3），42%7=0，55%7=6（无冲突）→原答案错误，正确应为6？需重新计算：15→1，23→2，37→2冲突→3，42→0，55→55%7=55-77=55-49=6，无冲突，故地址6）9.F(h+2)-1（F为斐波那契数列，F(1)=1,F(2)=2）10.O(n)三、判断题1.×（若插入位置在表尾，时间复杂度为O(1)）2.√3.×（前序和后序无法唯一确定，如单支树）4.×（遍历顺序与访问邻接点顺序有关）5.√6.×（还与冲突处理和装填因子有关）7.√8.√9.×（压缩存储保留非零元素信息）10.√四、算法设计题1.单链表逆置算法（迭代法）：```cvoidReverseList(LinkList&L){LNodepre=NULL,cur=L->next,next;while(cur!=NULL){next=cur->next;//保存下一个结点cur->next=pre;//反转指针pre=cur;//前驱后移cur=next;//当前结点后移}L->next=pre;//头结点指向原尾结点（新头结点）}```2.二叉树中序遍历非递归算法：```cvoidInOrderNonRec(BiTreeT){SqStackS;InitStack(S);BiTNodep=T;while(p!=NULL||!StackEmpty(S)){if(p!=NULL){//根结点入栈，访问左子树Push(S,p);p=p->lchild;}else{//左子树为空，弹出根结点访问，转向右子树Pop(S,p);visit(p);//访问结点（假设visit已定义）p=p->rchild;}}}```3.无向图连通性判断递归算法（DFS实现）：```cboolisConnected(ALGraphG){boolvisited[MAX_VERTEX_NUM]={false};intcount=0;DFS(G,0,visited,count);//从顶点0开始DFSreturncount==G.vexnum;//遍历顶点数等于总顶点数则连通}voidDFS(ALGraphG,intv,boolvisited[],int&count){visited[v]=true;count++;ArcNodep=G.vertices[v].firstarc;while(p!=NULL){if(!visited[p->adjvex]){DFS(G,p->adjvex,visited,count);}p=p->nextarc;}}```五、综合应用题1.中缀转后缀及求值过程：中缀表达式：3+5((2-4)/6+7)步骤：①初始化操作符栈S，输出队列Q。②扫描字符：-'3'→Q:[3]-'+'→S空，入栈S:[+]-'5'→Q:[3,5]-''→S顶为'+'（优先级低），入栈S:[+,]-'('→入栈S:[+,,(]-'('→入栈S:[+,,(,(]-'2'→Q:[3,5,2]-'-'→S顶为'(',入栈S:[+,,(,(,-]-'4'→Q:[3,5,2,4]-')'→弹出'-'到Q，弹出'('，S:[+,,(]；Q:[3,5,2,4,-]-'/'→S顶为'(',入栈S:[+,,(,/]-'6'→Q:[3,5,2,4,-,6]-')'→弹出'/'到Q，弹出'(',S:[+,]；Q:[3,5,2,4,-,6,/]-'+'→S顶为''（优先级高），弹出''到Q，S:[+]；当前'+'与S顶'+'优先级相同，弹出'+'到Q，S空，入栈当前'+'；Q:[3,5,2,4,-,6,/,,+]-'7'→Q:[3,5,2,4,-,6,/,,+,7]-扫描结束，弹出栈中剩余'+'到Q→后缀表达式：3524-6/7++求值过程：栈操作：-3,5,2,4→2-4=-2→栈：3,5,-2-6→-2/6≈-0.333→栈：3,5,-0.333-5(-0.333)≈-1.665→栈：3,-1.665-7→-1.665+7=5.335→栈：3,5.335-3+5.335=8.335→最终结果≈8.33（或精确分数25/3）2.哈夫曼树构造与编码：权值：2,4,5,7,9步骤：①选最小2和4，合并为6（