2025年python數(shù)據(jù)結(jié)構(gòu)考試題庫數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)章節(jié)試題(附答案)一、線性表1.選擇題：以下關(guān)于順序表和鏈表的描述，錯(cuò)誤的是（）A.順序表的存儲(chǔ)空間連續(xù)，鏈表的存儲(chǔ)空間可能不連續(xù)B.在順序表中隨機(jī)訪問元素的時(shí)間復(fù)雜度為O(1)，鏈表為O(n)C.順序表插入元素的平均時(shí)間復(fù)雜度為O(n)，鏈表頭插的時(shí)間復(fù)雜度為O(1)D.順序表的空間利用率一定高于鏈表2.填空題：一個(gè)長度為n的順序表，若要在第i個(gè)位置（1≤i≤n+1）插入一個(gè)元素，需移動(dòng)______個(gè)元素；若刪除第i個(gè)位置的元素（1≤i≤n），需移動(dòng)______個(gè)元素。3.簡答題：簡述單鏈表中“頭指針”和“頭結(jié)點(diǎn)”的區(qū)別及各自的作用。4.編程題：已知單鏈表L的結(jié)點(diǎn)結(jié)構(gòu)為（data,next），其中data為整型。請(qǐng)用Python編寫函數(shù)，將L中所有值為奇數(shù)的結(jié)點(diǎn)移動(dòng)到偶數(shù)結(jié)點(diǎn)之前，保持奇數(shù)和偶數(shù)內(nèi)部的相對(duì)順序。例如，輸入L:3→1→4→2→5，輸出應(yīng)為3→1→5→4→2。二、棧與隊(duì)列5.選擇題：若一個(gè)棧的輸入序列是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,26.填空題：設(shè)循環(huán)隊(duì)列的容量為50（下標(biāo)0~49），隊(duì)頭指針front=15，隊(duì)尾指針rear=30（rear指向隊(duì)尾元素的下一個(gè)位置），則隊(duì)列中元素的個(gè)數(shù)為______；若采用犧牲一個(gè)存儲(chǔ)單元的方式判斷隊(duì)滿，當(dāng)隊(duì)列滿時(shí)front和rear的關(guān)系為______。7.簡答題：請(qǐng)說明棧在括號(hào)匹配問題中的應(yīng)用邏輯，并舉例說明如何判斷字符串“([)]”是否合法。8.編程題：用Python實(shí)現(xiàn)一個(gè)雙端隊(duì)列（Deque），要求支持以下操作：add_front(item)（頭部添加）、add_rear(item)（尾部添加）、remove_front()（頭部刪除）、remove_rear()（尾部刪除）、is_empty()（判斷空）。三、樹與二叉樹9.選擇題：一棵完全二叉樹有100個(gè)結(jié)點(diǎn)，其葉子結(jié)點(diǎn)的個(gè)數(shù)是（）A.49B.50C.51D.5210.填空題：已知某二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其前序遍歷序列為______；該二叉樹對(duì)應(yīng)的森林中樹的棵數(shù)等于其______的數(shù)目。11.簡答題：簡述二叉排序樹（BST）的定義，并說明插入一個(gè)新結(jié)點(diǎn)的具體步驟。12.編程題：請(qǐng)用Python實(shí)現(xiàn)二叉樹的層次遍歷（廣度優(yōu)先搜索），要求輸出格式為二維列表，每層元素放在一個(gè)子列表中。例如，輸入二叉樹：```3/\920/\157```輸出應(yīng)為[[3],[9,20],[15,7]]。四、圖13.選擇題：一個(gè)有向圖的鄰接表存儲(chǔ)中，每個(gè)頂點(diǎn)的出邊鏈表長度為該頂點(diǎn)的出度。若圖中有n個(gè)頂點(diǎn)，e條邊，則鄰接表的空間復(fù)雜度為（）A.O(n)B.O(e)C.O(n+e)D.O(n×e)14.填空題：在無向圖中，若從頂點(diǎn)v到頂點(diǎn)u存在路徑，則稱v和u是連通的；______的無向圖稱為連通圖。若一個(gè)無向圖有5個(gè)頂點(diǎn)，要保證其連通，至少需要______條邊。15.簡答題：Dijkstra算法用于求解什么問題？其核心思想是什么？該算法是否適用于帶負(fù)權(quán)邊的圖？16.編程題：已知無向圖的鄰接矩陣為：```[[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]]```（頂點(diǎn)編號(hào)0~3），請(qǐng)用Python編寫函數(shù)，輸出所有從頂點(diǎn)0出發(fā)到頂點(diǎn)3的簡單路徑（路徑中無重復(fù)頂點(diǎn)）。五、查找17.選擇題：在哈希表中，解決沖突的方法不包括（）A.開放定址法B.鏈地址法C.再哈希法D.二分查找法18.填空題：對(duì)長度為n的有序數(shù)組進(jìn)行二分查找，最壞情況下的時(shí)間復(fù)雜度為______；若數(shù)組元素為[2,5,8,12,16,23,30]，查找元素16時(shí)，需要比較______次（從中間元素開始計(jì)數(shù)）。19.簡答題：簡述哈希表負(fù)載因子（α）的定義及其對(duì)哈希表性能的影響。20.編程題：用Python實(shí)現(xiàn)一個(gè)哈希表，要求使用鏈地址法處理沖突，支持插入（put(key,value)）和查找（get(key)）操作，哈希函數(shù)采用除留余數(shù)法（取表長為質(zhì)數(shù)）。六、排序21.選擇題：下列排序算法中，時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(nlogn)的是（）A.快速排序B.堆排序C.冒泡排序D.插入排序22.填空題：對(duì)序列[5,3,8,6,4,2]進(jìn)行快速排序，以第一個(gè)元素為樞軸，第一趟排序后的結(jié)果為______；若采用歸并排序，初始序列的歸并段長度為1，第一趟歸并后的結(jié)果為______。23.簡答題：比較冒泡排序和快速排序的異同點(diǎn)（至少列出3點(diǎn)）。24.編程題：用Python實(shí)現(xiàn)堆排序算法，要求將數(shù)組[7,3,9,5,1,6,2,4]按升序排列，并輸出每一趟建堆后的數(shù)組狀態(tài)。答案1.D（順序表需要預(yù)分配空間，可能存在空間浪費(fèi)；鏈表每個(gè)結(jié)點(diǎn)有指針域，若數(shù)據(jù)域較小，空間利用率可能更低）2.ni+1；ni3.頭指針是指向鏈表第一個(gè)結(jié)點(diǎn)的指針（若有頭結(jié)點(diǎn)則指向頭結(jié)點(diǎn)），是鏈表的標(biāo)識(shí)；頭結(jié)點(diǎn)是附加在第一個(gè)數(shù)據(jù)結(jié)點(diǎn)前的結(jié)點(diǎn)，用于簡化插入/刪除首元結(jié)點(diǎn)的操作，使所有結(jié)點(diǎn)的操作統(tǒng)一。4.參考代碼：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmove_odd_before_even(head):odd_dummy=ListNode()even_dummy=ListNode()odd=odd_dummyeven=even_dummywhilehead:ifhead.val%2==1:odd.next=headodd=odd.nextelse:even.next=headeven=even.nexthead=head.nextodd.next=even_dummy.nexteven.next=None斷開原鏈表尾部returnodd_dummy.next```5.C（若輸出2,3,1，則棧狀態(tài)為：壓入1、2，彈出2；壓入3，彈出3；此時(shí)棧頂為1，無法彈出1后再壓入4、5并彈出5、4）6.15；(rear+1)%50==front7.邏輯：遍歷字符串，遇到左括號(hào)入棧，遇到右括號(hào)時(shí)彈出棧頂左括號(hào)并判斷是否匹配。若?？栈虿黄ヅ鋭t非法?！?[)]”中，遍歷到‘)’時(shí)棧頂是‘[’，不匹配，故非法。8.參考代碼：```pythonclassDeque:def__init__(self):self.items=[]defadd_front(self,item):self.items.insert(0,item)defadd_rear(self,item):self.items.append(item)defremove_front(self):returnself.items.pop(0)ifnotself.is_empty()elseNonedefremove_rear(self):returnself.items.pop()ifnotself.is_empty()elseNonedefis_empty(self):returnlen(self.items)==0```9.B（完全二叉樹葉子結(jié)點(diǎn)數(shù)為?n/2?，100/2=50）10.CEBDA；根結(jié)點(diǎn)的兄弟結(jié)點(diǎn)（或第一棵樹的根結(jié)點(diǎn)以外的根結(jié)點(diǎn)）11.定義：左子樹所有結(jié)點(diǎn)值≤根結(jié)點(diǎn)值，右子樹所有結(jié)點(diǎn)值≥根結(jié)點(diǎn)值，左右子樹均為BST。插入步驟：從根開始比較，若小于當(dāng)前結(jié)點(diǎn)則進(jìn)入左子樹，大于則進(jìn)入右子樹，直到找到空位置插入。12.參考代碼：```pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeflevel_order(root):ifnotroot:return[]result=[]q=deque([root])whileq:level=[]for_inrange(len(q)):node=q.popleft()level.append(node.val)ifnode.left:q.append(node.left)ifnode.right:q.append(node.right)result.append(level)returnresult```13.C（鄰接表存儲(chǔ)n個(gè)頂點(diǎn)表結(jié)點(diǎn)和e條邊表結(jié)點(diǎn)）14.任意兩個(gè)頂點(diǎn)都連通；4（n1條邊構(gòu)成樹）15.求解單源最短路徑問題。核心思想：每次選擇當(dāng)前距離最短的頂點(diǎn)，更新其鄰接頂點(diǎn)的距離。不適用于負(fù)權(quán)邊，因無法保證已確定的最短路徑不被后續(xù)更小的權(quán)值更新。16.參考代碼：```pythondeffind_paths(adj_matrix,start,end):n=len(adj_matrix)visited=[False]npaths=[]defdfs(current,path):visited[current]=Truepath.append(current)ifcurrent==end:paths.append(path.copy())else:foriinrange(n):ifadj_matrix[current][i]andnotvisited[i]:dfs(i,path)path.pop()visited[current]=Falsedfs(start,[])returnpaths調(diào)用示例：find_paths([[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]],0,3)輸出：[[0,1,2,3],[0,3]]```17.D（二分查找是查找方法，非沖突解決方法）18.O(logn)；3（第一次比較8，第二次比較16）19.負(fù)載因子α=表中元素個(gè)數(shù)/哈希表長度。α越大，沖突概率越高，查找時(shí)間越長；α越小，空間利用率越低。20.參考代碼：```pythonclassHashTable:def__init__(self,size=11):self.size=sizeself.table=[[]for_inrange(size)]defhash_func(self,key):returnkey%self.sizedefput(self,key,value):index=self.hash_func(key)fori,(k,v)inenumerate(self.table[index]):ifk==key:self.table[index][i]=(key,value)returnself.table[index].append((key,value))defget(self,key):index=self.hash_func(key)fork,vinself.table[index]:ifk==key:returnvreturnNone```21.B（堆排序的時(shí)間復(fù)雜度始終為O(nlogn)）22.[2,3,4,5,8,6]；[3,5,6,8,1,4,2]（注：快速排序第一趟以5為樞軸，小于5的放左，大于的放右；歸并排序第一趟將相鄰元素兩兩歸并）23.相同點(diǎn)：均通過比較交換元素；均為內(nèi)排序。不同點(diǎn)：冒泡是穩(wěn)定排序，快速不穩(wěn)定；冒泡時(shí)間復(fù)雜度O(n2)，快速平均O(nlogn)；冒泡是順序掃描，快速是分治遞歸。24.參考代碼及每趟狀態(tài)：```pythondefheap_sort(arr):defheapify(n,i):largest=ileft=2i+1right=2i+2ifleft<nandarr[left]>arr[largest]:largest=leftifright<nandarr[right