ACM數據結構試題與答案解析

ACM數據結構試題與答案解析考試時間：______分鐘總分：______分姓名：______選擇題1.下列關于順序表和鏈表的描述，正確的是（）A.順序表的插入和刪除操作時間復雜度均為O(1)B.鏈表的隨機訪問時間復雜度為O(1)C.順序表需要預分配存儲空間，鏈表按需分配D.鏈表相比順序表，更適合頻繁插入但訪問較少的場景2.在包含n個節點的平衡二叉樹（AVL樹）中，插入一個新節點可能導致失衡，最壞情況下需要旋轉的次數是（）A.1次B.2次C.O(logn)次D.O(n)次3.下列排序算法中，時間復雜度與初始序列無關的是（）A.快速排序B.冒泡排序C.堆排序D.插入排序4.在棧的應用中，表達式求值通常使用（）A.前綴表達式B.中綴表達式C.后綴表達式D.逆波蘭表達式5.隊列的循環隊列實現中，判隊滿的條件是（）A.rear==frontB.rear==front-1C.rear==maxsize-1D.rear==front&&rear!=06.在二叉樹的層序遍歷中，使用的數據結構是（）A.棧B.隊列C.哈希表D.優先隊列7.圖的鄰接表存儲中，查找一個頂點的所有鄰接頂點的時間復雜度是（）A.O(1)B.O(n)C.O(e)D.O(n^2)8.哈希表的負載因子α增大時，平均查找長度（）A.減小B.增大C.不變D.不確定9.在快速排序的partition過程中，基準元素的選擇影響算法效率，最壞情況下時間復雜度為（）A.O(n)B.O(nlogn)C.O(n^2)D.O(2^n)10.下列數據結構中，支持動態擴容的是（）A.順序表B.鏈表C.靜態數組D.棧填空題1.快速排序的partition過程中，選取最后一個元素為基準，將小于基準的元素移到左側，大于基準的移到右側。若初始序列為`[3,1,4,1,5,9,2,6]`，第一趟partition后的結果為______，基準的最終位置為______。2.已知一棵二叉樹的前序遍歷為`ABDEHCFIG`，中序遍歷為`DBHEAFICG`，其后序遍歷結果為______。3.在包含n個頂點的帶權無向圖中，使用Prim算法求最小生成樹的時間復雜度為______（用鄰接矩陣存儲）______（用鄰接表存儲）。4.哈希表的負載因子α=______，當α增大時，鏈地址法查找成功的平均查找長度為______。5.在Dijkstra算法中，若使用優先隊列優化，時間復雜度為______（e為邊數）。編程題1.二叉樹的直徑給定一棵二叉樹的根節點`root`，計算樹的直徑。二叉樹的直徑是樹中任意兩個節點路徑長度中的最大值。該路徑可能經過根節點，也可能不經過根節點。路徑長度=邊數（即節點數-1）。示例：輸入：`root=[1,2,3,4,5]`輸出：3解釋：最長路徑為`4-2-1-3`或`5-2-1-3`，長度為3（邊數）。2.Dijkstra算法求單源最短路徑給定一個帶權有向圖`graph`，其中`graph[i][j]`表示頂點`i`到頂點`j`的邊的權值（若不存在邊，權值為-1）。給定源頂點`src`，計算從`src`到其他所有頂點的最短路徑，返回一個數組`dist`，其中`dist[i]`表示`src`到`i`的最短路徑長度，若不可達則返回-1。示例：輸入：`graph=[[0,2,1,-1],[1,0,3,4],[1,1,0,1],[-1,-1,-1,0]]`，`src=0`輸出：`[0,2,1,2]`解釋：0→2→3（長度1+1=2），0→1（長度2），0→2（長度1）。試卷答案選擇題1.D解析：順序表在中間插入刪除需移動元素，時間復雜度O(n)；鏈表隨機訪問需遍歷，O(n)；順序表需預分配空間，鏈表動態分配但需額外存儲指針；鏈表插入只需修改指針，適合頻繁插入，故D正確。2.B解析：AVL樹插入節點后最多失衡2層，每次失衡需1-2次旋轉，最壞2次，與n無關，故選B。3.C解析：快速排序最壞O(n2)，冒泡和插入排序最壞O(n2)，堆排序無論初始序列均為O(nlogn)，故選C。4.C解析：表達式求值通常使用后綴表達式（逆波蘭表達式），因為它不需要括號且易于用棧處理。5.D解析：循環隊列判隊滿條件為rear==front且rear!=0（犧牲一個空間），故選D。6.B解析：層序遍歷按層次從上到下、從左到右，需隊列實現，故選B。7.C解析：鄰接表中每個頂點對應一個鏈表，查找鄰接頂點需遍歷鏈表，時間復雜度與該頂點的度數相關，平均為O(e/n)，但最壞為O(n)（若一個頂點連接所有頂點），但通常認為O(e)（e為邊數）。8.B解析：負載因子α=表中元素數/表長度，α增大意味著沖突增多，平均查找長度增大（鏈地址法為1+α/2）。9.C解析：快速排序最壞情況（如初始序列有序或逆序）每次partition只能劃分一個元素，時間復雜度O(n2)。10.B解析：順序表和靜態數組需要預分配空間，棧通常基于順序表實現（靜態擴容），但鏈表本身支持動態擴容（插入時動態分配節點），故選B。填空題1.[3,1,4,1,5,2,6,9]，6（索引6）解析：基準為最后一個元素6，partition過程將小于6的移到左側，大于6的移到右側，最終基準位置在索引6。2.DHEBIFGCA解析：根據前序和中序遍歷遞歸重建二叉樹，后序遍歷為左右根，重建過程為：根A，左子樹DBHE（根B，左D，右HE（根E，左H）），右子樹FICG（根F，左I，右CG（根G，左C）），后序為左子樹DHEB，右子樹IFGC，根A，組合為DHEBIFGCA。3.O(n2)，O(e+nlogn)解析：鄰接矩陣需遍歷所有頂點找最小權值，O(n2)；鄰接表用優先隊列，每次操作O(logn)，共e條邊，O(e+nlogn)。4.表中記錄數/表長度，1+α/2解析：負載因子α=表中記錄數/表長度，鏈地址法查找成功的平均查找長度為1+α/2。5.O(elogn)解析：使用優先隊列優化Dijkstra算法，每條邊最多入隊一次，每次堆操作O(logn)，共e條邊，O(elogn)。編程題1.二叉樹的直徑代碼：classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightclassSolution:defdiameterOfBinaryTree(self,root:TreeNode)->int:self.max_diameter=0defdepth(node):ifnotnode:return0left_depth=depth(node.left)right_depth=depth(node.right)self.max_diameter=max(self.max_diameter,left_depth+right_depth)returnmax(left_depth,right_depth)+1depth(root)returnself.max_diameter解析：遞歸計算每個節點的左右子樹深度，同時更新最大直徑（左右深度之和），返回最大值。2.Dijkstra算法求單源最短路徑代碼：importheapqdefdijkstra(graph,src):n=len(graph)dist=[float('inf')]*ndist[src]=0heap=[(0,src)]visited=set()whileheap:current_dist,u=heapq.heappop(heap)ifuinvisited:continuevisited.add(u)forvinrange(n):ifgraph[u][v]!=-1andvnotinvisited:new_dist=current_dist+graph[u][v]ifnew_dist<dist[v]:dist[v]=new_distheapq.hea