2026年數(shù)據(jù)結(jié)構(gòu)與算法實(shí)踐考試題目一、單選題（共10題，每題2分，共20分）1.在以下數(shù)據(jù)結(jié)構(gòu)中，最適合插入和刪除操作的是（）。A.數(shù)組B.鏈表C.棧D.隊(duì)列2.快速排序的平均時(shí)間復(fù)雜度是（）。A.O(n)B.O(nlogn)C.O(n2)D.O(logn)3.下列哪個(gè)不是二叉樹的性質(zhì)？（）A.每個(gè)節(jié)點(diǎn)至多有兩個(gè)子節(jié)點(diǎn)B.左子樹和右子樹是遞歸定義的C.必須有根節(jié)點(diǎn)D.可以有多個(gè)根節(jié)點(diǎn)4.在哈希表中，解決沖突的常用方法不包括（）。A.開放定址法B.鏈地址法C.二分查找法D.雙哈希法5.下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)是先進(jìn)先出（FIFO）的？（）A.棧B.隊(duì)列C.隊(duì)列和棧D.樹6.冒泡排序的時(shí)間復(fù)雜度在最壞情況下是（）。A.O(n)B.O(nlogn)C.O(n2)D.O(logn)7.在以下數(shù)據(jù)結(jié)構(gòu)中，適合表示稀疏矩陣的是（）。A.數(shù)組B.鏈表C.矩陣壓縮存儲(chǔ)（如三元組表）D.棧8.堆排序的時(shí)間復(fù)雜度是（）。A.O(n)B.O(nlogn)C.O(n2)D.O(logn)9.在以下算法中，屬于分治法的是（）。A.冒泡排序B.選擇排序C.快速排序D.插入排序10.二分查找的時(shí)間復(fù)雜度是（）。A.O(n)B.O(nlogn)C.O(n2)D.O(logn)二、填空題（共10題，每題1分，共10分）1.在鏈表中，插入和刪除操作的時(shí)間復(fù)雜度是________。2.堆是一種特殊的________結(jié)構(gòu)，可以是最大堆或最小堆。3.哈希表的理想情況是________沖突。4.棧是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，其基本操作包括________、________和________。5.快速排序的核心思想是________。6.二叉樹的深度為h，其最多有________個(gè)節(jié)點(diǎn)。7.在二分查找中，數(shù)組必須________排序。8.堆排序的時(shí)間復(fù)雜度在最好、最壞和平均情況下均為________。9.隊(duì)列是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，其基本操作包括________和________。10.圖的兩種基本表示方法是________和________。三、簡(jiǎn)答題（共5題，每題4分，共20分）1.簡(jiǎn)述棧和隊(duì)列的區(qū)別。2.解釋快速排序的基本步驟。3.描述哈希表的沖突解決方法。4.說明二叉搜索樹（BST）的性質(zhì)。5.比較堆排序和快速排序的優(yōu)缺點(diǎn)。四、算法設(shè)計(jì)題（共3題，每題10分，共30分）1.題目：設(shè)計(jì)一個(gè)算法，將一個(gè)棧逆序。輸入一個(gè)棧（用數(shù)組表示），輸出逆序后的棧。要求：不能使用額外的棧，只能利用棧的基本操作。2.題目：設(shè)計(jì)一個(gè)算法，判斷一個(gè)無向圖是否存在環(huán)。輸入圖的鄰接矩陣，輸出是否存在環(huán)。要求：可以使用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS）實(shí)現(xiàn)。3.題目：設(shè)計(jì)一個(gè)算法，實(shí)現(xiàn)二分查找的遞歸版本。輸入一個(gè)有序數(shù)組和一個(gè)目標(biāo)值，輸出目標(biāo)值的索引（如果不存在，返回-1）。五、編程題（共2題，每題15分，共30分）1.題目：實(shí)現(xiàn)一個(gè)哈希表，支持插入和查找操作。假設(shè)哈希函數(shù)為`hash(key)=key%10`，使用鏈地址法解決沖突。輸入一系列鍵值對(duì)，輸出查找結(jié)果。要求：使用Python或C++實(shí)現(xiàn)。2.題目：實(shí)現(xiàn)一個(gè)二叉搜索樹（BST），支持插入和刪除操作。輸入一系列節(jié)點(diǎn)值，構(gòu)建BST，然后刪除一個(gè)指定節(jié)點(diǎn)，輸出刪除后的BST（用中序遍歷表示）。要求：使用Python或C++實(shí)現(xiàn)。答案與解析一、單選題答案1.B2.B3.D4.C5.B6.C7.C8.B9.C10.D解析：1.鏈表支持動(dòng)態(tài)插入和刪除，時(shí)間復(fù)雜度為O(1)；數(shù)組插入刪除需要移動(dòng)元素，時(shí)間復(fù)雜度為O(n)。2.快速排序平均時(shí)間復(fù)雜度為O(nlogn)，最壞為O(n2)。3.二叉樹必須有唯一根節(jié)點(diǎn)，不能有多個(gè)根節(jié)點(diǎn)。4.二分查找法用于有序數(shù)組，不是哈希表沖突解決方法。5.隊(duì)列是FIFO，棧是LIFO。6.冒泡排序最壞情況為O(n2)。7.稀疏矩陣適合三元組表等壓縮存儲(chǔ)方式。8.堆排序時(shí)間復(fù)雜度為O(nlogn)。9.快速排序是分治法典型應(yīng)用。10.二分查找時(shí)間復(fù)雜度為O(logn)。二、填空題答案1.O(1)2.樹3.無4.入棧、出棧、查看棧頂5.分治6.2^h-17.有序8.O(nlogn)9.入隊(duì)、出隊(duì)10.鄰接矩陣、鄰接表解析：1.鏈表插入刪除時(shí)間復(fù)雜度為O(1)。2.堆是特殊的樹形結(jié)構(gòu)。3.理想哈希表無沖突。4.棧操作包括入棧（push）、出棧（pop）和查看棧頂（peek）。5.快速排序通過分治思想實(shí)現(xiàn)。6.高度為h的二叉樹最多2^h-1個(gè)節(jié)點(diǎn)。7.二分查找要求數(shù)組有序。8.堆排序時(shí)間復(fù)雜度穩(wěn)定為O(nlogn)。9.隊(duì)列操作包括入隊(duì)和出隊(duì)。10.圖的兩種表示方法是鄰接矩陣和鄰接表。三、簡(jiǎn)答題答案1.棧：后進(jìn)先出（LIFO），只能在一端（棧頂）操作；隊(duì)列：先進(jìn)先出（FIFO），兩端（隊(duì)頭和隊(duì)尾）操作。2.快速排序步驟：-選擇基準(zhǔn)值（pivot），通常取第一個(gè)或最后一個(gè)元素；-分區(qū)操作，將數(shù)組分為小于基準(zhǔn)值和大于基準(zhǔn)值的兩部分；-遞歸對(duì)兩部分進(jìn)行快速排序。3.沖突解決方法：-開放定址法：線性探測(cè)、二次探測(cè)等；-鏈地址法：將沖突的鍵值對(duì)存儲(chǔ)在鏈表中；-雙哈希法：使用多個(gè)哈希函數(shù)解決沖突。4.BST性質(zhì)：-左子樹所有節(jié)點(diǎn)值小于根節(jié)點(diǎn)；-右子樹所有節(jié)點(diǎn)值大于根節(jié)點(diǎn)；-左右子樹均為BST；-無重復(fù)節(jié)點(diǎn)。5.堆排序vs快速排序：-堆排序：時(shí)間穩(wěn)定O(nlogn)，空間O(1)，但建堆過程較慢；-快速排序：平均O(nlogn)，但最壞O(n2)，空間O(logn)。四、算法設(shè)計(jì)題答案1.棧逆序算法（遞歸）：pythondefreverse_stack(s):ifnots:returntop=s.pop()reverse_stack(s)insert_at_bottom(s,top)definsert_at_bottom(s,item):ifnots:s.append(item)else:temp=s.pop()insert_at_bottom(s,item)s.append(temp)解析：通過遞歸出棧，再反向插入實(shí)現(xiàn)逆序。2.圖環(huán)判斷（DFS）：pythondefhas_cycle(graph):visited=[False]len(graph)rec_stack=[False]len(graph)foriinrange(len(graph)):ifnotvisited[i]:ifdfs_cycle(i,visited,rec_stack):returnTruereturnFalsedefdfs_cycle(v,visited,rec_stack):visited[v]=Truerec_stack[v]=Trueforneighboringraph[v]:ifnotvisited[neighbor]:ifdfs_cycle(neighbor,visited,rec_stack):returnTrueelifrec_stack[neighbor]:returnTruerec_stack[v]=FalsereturnFalse解析：DFS中若遇到已訪問且在遞歸棧中的節(jié)點(diǎn)，則存在環(huán)。3.二分查找遞歸版本：pythondefbinary_search(arr,low,high,target):ifhigh>=low:mid=(low+high)//2ifarr[mid]==target:returnmidelifarr[mid]>target:returnbinary_search(arr,low,mid-1,target)else:returnbinary_search(arr,mid+1,high,target)else:return-1解析：遞歸二分查找通過縮小搜索范圍實(shí)現(xiàn)。五、編程題答案1.哈希表實(shí)現(xiàn)（Python）：pythonclassHashTable:def__init__(self):self.size=10self.table=[[]for_inrange(self.size)]def_hash(self,key):returnkey%self.sizedefinsert(self,key):index=self._hash(key)self.table[index].append(key)defsearch(self,key):index=self._hash(key)forkinself.table[index]:ifk==key:returnTruereturnFalse解析：使用鏈地址法解決沖突，插入時(shí)直接添加到鏈表。2.BST實(shí)現(xiàn)（Python）：pythonclassTreeNode:def__init__(self,key):self.left=Noneself.right=Noneself.val=keyclassBST:definsert(self,root,key):ifrootisNone:returnTreeNode(key)ifkey<root.val:root.left=self.insert(root.left,key)else:root.right=self.insert(root.right,key)returnrootdefdelete(self,root,key):ifrootisNone:returnrootifkey<root.val:root.left=self.delete(root.left,key)elifkey>root.val:root.right=self.delete(root.right,key)else:ifroot.leftisNone:returnroot.rightelifroot.rightisNone:returnroot.lefttemp=self.min_value_node(root.right)root.val=temp.valroot.right=self.delete(root.right,temp.val)returnrootdefmin_value_node(self,node):current=nodewhilecurren