2025年數(shù)據(jù)結(jié)構(gòu)python期末考試題及答案一、單項(xiàng)選擇題（每題2分，共20分）1.已知線性表L的長度為n，若要在第i個位置（1≤i≤n+1）插入一個新元素，需要移動的元素個數(shù)為（）A.n-i+1B.n-iC.iD.i-12.設(shè)棧S的初始狀態(tài)為空，元素a、b、c、d、e依次入棧，出棧序列可能的是（）A.a、c、b、e、dB.b、d、c、a、eC.c、b、a、d、eD.e、d、c、b、a3.若某完全二叉樹的深度為h（根節(jié)點(diǎn)深度為1），則該樹最少有（）個節(jié)點(diǎn)A.2^(h-1)B.2^(h-1)-1C.2^(h-1)+1D.2^h-14.對圖G進(jìn)行廣度優(yōu)先搜索（BFS）時，采用的數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊(duì)列C.優(yōu)先隊(duì)列D.二叉樹5.對于哈希表，若采用鏈地址法處理沖突，哈希表的平均查找長度主要取決于（）A.哈希函數(shù)B.負(fù)載因子C.處理沖突的方法D.表長6.下列排序算法中，時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(nlogn)的是（）A.快速排序B.堆排序C.冒泡排序D.直接插入排序7.若一個二叉樹的前序遍歷序列為ABCDE，中序遍歷序列為BADCE，則后序遍歷序列為（）A.BDECAB.BEDCAC.BDAECD.BDEAC8.設(shè)循環(huán)隊(duì)列的存儲空間為Q[0..m-1]，初始時front=rear=m，當(dāng)隊(duì)列滿時，rear的值為（）A.frontB.(front+1)%mC.(front-1)%mD.(front+1)%(m+1)9.對于n個節(jié)點(diǎn)的無向連通圖，其提供樹至少包含（）條邊A.nB.n-1C.n+1D.2n-110.已知一個有序表為[12,23,34,45,56,67,78,89]，若用二分查找法查找元素56，需要比較（）次A.2B.3C.4D.5二、填空題（每題2分，共20分）1.一個算法的時間復(fù)雜度為O(n3+2n2logn)，其漸近時間復(fù)雜度可表示為__________。2.設(shè)單鏈表節(jié)點(diǎn)結(jié)構(gòu)為（data,next），頭指針為head，若要刪除頭節(jié)點(diǎn)，需執(zhí)行的操作為__________（用Python偽代碼表示）。3.若某二叉樹有20個葉子節(jié)點(diǎn)，且有30個節(jié)點(diǎn)僅有一個子節(jié)點(diǎn)，則該二叉樹總節(jié)點(diǎn)數(shù)為__________。4.對序列[5,3,8,4,6]進(jìn)行直接插入排序，第三趟（假設(shè)從0開始計(jì)數(shù)）排序后的序列是__________。5.設(shè)哈希表長度為11，哈希函數(shù)H(key)=key%11，采用線性探測法處理沖突。依次插入鍵值38、49、11、57、3，哈希表中鍵值57的存儲位置是__________。6.已知一個有向圖的鄰接矩陣為：[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]該圖的強(qiáng)連通分量個數(shù)為__________。7.一個滿二叉樹的第k層（根為第1層）有__________個節(jié)點(diǎn)。8.隊(duì)列的“假溢出”現(xiàn)象是指__________。9.對n個元素進(jìn)行歸并排序，遞歸調(diào)用的層數(shù)為__________（取整）。10.設(shè)有向無環(huán)圖G的拓?fù)渑判蛐蛄袨関1→v2→v3→v4，其鄰接表中v2的鄰接點(diǎn)可能包含__________（寫出所有可能）。三、算法設(shè)計(jì)題（每題10分，共30分）1.編寫一個Python函數(shù)，實(shí)現(xiàn)單鏈表的逆序操作。要求：不能使用額外的數(shù)據(jù)結(jié)構(gòu)（如列表）存儲節(jié)點(diǎn)，只能通過調(diào)整節(jié)點(diǎn)指針完成。單鏈表節(jié)點(diǎn)類定義如下：classListNode:def__init__(self,val=0,next=None):self.val=valself.next=next2.給定一棵二叉樹的根節(jié)點(diǎn)root，編寫Python函數(shù)返回其層次遍歷的結(jié)果（即逐層從左到右訪問所有節(jié)點(diǎn)）。要求用非遞歸方法實(shí)現(xiàn)。二叉樹節(jié)點(diǎn)類定義如下：classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right3.實(shí)現(xiàn)Dijkstra算法，求有向圖中從源點(diǎn)v到所有其他頂點(diǎn)的最短路徑。要求：圖用鄰接表表示（頂點(diǎn)用0~n-1編號），返回一個距離數(shù)組dist，其中dist[i]表示v到i的最短距離。四、綜合應(yīng)用題（每題15分，共30分）1.括號匹配問題擴(kuò)展：輸入一個包含大括號{}、中括號[]、小括號()的字符串，判斷是否合法。合法條件：①所有類型的括號必須正確閉合；②嵌套的括號必須按順序閉合（如"([)]"不合法，"([])"合法）。要求用棧結(jié)構(gòu)實(shí)現(xiàn)，編寫Python函數(shù)is_valid(s:str)返回布爾值。2.學(xué)提供績管理系統(tǒng)設(shè)計(jì)：使用二叉搜索樹（BST）存儲學(xué)提供績（成績?yōu)檎麛?shù)），支持以下操作：插入新成績（insert）查詢是否存在某成績（search）刪除指定成績（delete）要求：①定義二叉搜索樹節(jié)點(diǎn)類；②實(shí)現(xiàn)insert方法（遞歸或迭代均可）；③實(shí)現(xiàn)delete方法（需處理三種情況：節(jié)點(diǎn)無子女、有一個子女、有兩個子女）。答案一、單項(xiàng)選擇題1.A2.D3.A4.B5.B6.B7.A8.B9.B10.A二、填空題1.O(n3)2.head=head.next（假設(shè)鏈表非空）3.69（葉子節(jié)點(diǎn)數(shù)=度為2的節(jié)點(diǎn)數(shù)+1，總節(jié)點(diǎn)數(shù)=20+30+19=69）4.[3,5,4,8,6]（第三趟處理元素4，插入到5前）5.3（H(38)=5,H(49)=5→6,H(11)=0,H(57)=5→6→7→8→3？計(jì)算錯誤，正確應(yīng)為：38→5；49→5沖突→6；11→0；57→57%11=2（57/11=511=55，余2），所以位置2）（更正：原計(jì)算錯誤，正確H(57)=57%11=57-511=57-55=2，無沖突，位置2）6.1（該圖是一個環(huán)，所有節(jié)點(diǎn)互相可達(dá)）7.2^(k-1)8.隊(duì)列尾部已到達(dá)數(shù)組末尾，但頭部之前有空閑空間，導(dǎo)致無法繼續(xù)入隊(duì)的現(xiàn)象9.log?n（向上取整）10.v3、v4（拓?fù)渑判蛑泻罄m(xù)節(jié)點(diǎn)）三、算法設(shè)計(jì)題1.單鏈表逆序函數(shù)```pythondefreverse_list(head:ListNode)->ListNode:prev=Nonecurrent=headwhilecurrent:next_node=current.next保存下一個節(jié)點(diǎn)current.next=prev反轉(zhuǎn)指針prev=current前驅(qū)后移current=next_node當(dāng)前節(jié)點(diǎn)后移returnprev新頭節(jié)點(diǎn)是原尾節(jié)點(diǎn)```2.二叉樹層次遍歷（非遞歸）```pythonfromcollectionsimportdequedeflevel_order(root:TreeNode)->list[list[int]]:ifnotroot:return[]result=[]queue=deque([root])whilequeue:level=[]level_size=len(queue)for_inrange(level_size):node=queue.popleft()level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(level)returnresult```3.Dijkstra算法實(shí)現(xiàn)```pythondefdijkstra(graph,start):n=len(graph)dist=[float('inf')]ndist[start]=0visited=[False]nfor_inrange(n):找到當(dāng)前未訪問的最短距離節(jié)點(diǎn)u=-1min_dist=float('inf')foriinrange(n):ifnotvisited[i]anddist[i]<min_dist:min_dist=dist[i]u=iifu==-1:breakvisited[u]=True更新鄰接節(jié)點(diǎn)距離forv,weightingraph[u]:ifdist[v]>dist[u]+weight:dist[v]=dist[u]+weightreturndist```（注：鄰接表格式示例：graph[u]=[(v1,w1),(v2,w2),...]）四、綜合應(yīng)用題1.擴(kuò)展括號匹配函數(shù)```pythondefis_valid(s:str)->bool:stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:右括號，檢查棧頂是否匹配top=stack.pop()ifstackelse''?？諘r用表示不匹配ifmapping[char]!=top:returnFalseelse:左括號入棧stack.append(char)所有左括號必須被匹配returnnotstack```2.二叉搜索樹實(shí)現(xiàn)```pythonclassTreeNode:def__init__(self,val=0):self.val=valself.left=Noneself.right=NoneclassBST:def__init__(self):self.root=Nonedefinsert(self,val):ifnotself.root:self.root=TreeNode(val)returnself._insert_recursive(self.root,val)def_insert_recursive(self,node,val):ifval<node.val:ifnotnode.left:node.left=TreeNode(val)else:self._insert_recursive(node.left,val)else:ifnotnode.right:node.right=TreeNode(val)else:self._insert_recursive(node.right,val)defsearch(self,val):returnself._search_recursive(self.root,val)def_search_recursive(self,node,val):ifnotnode:returnFalseifval==node.val:returnTrueelifval<node.val:returnself._search_recursive(node.left,val)else:returnself._search_recursive(node.right,val)defdelete(self,val):self.root=self._delete_recursive(self.root,val)def_delete_recursive(self,node,val):ifnotnode:return