2026年程序員算法與數(shù)據(jù)結(jié)構(gòu)練習(xí)題一、選擇題（共10題，每題2分，合計(jì)20分）1.題目：在下列數(shù)據(jù)結(jié)構(gòu)中，插入和刪除操作最方便的是（）。A.鏈表B.數(shù)組C.棧D.隊(duì)列2.題目：下列哪個(gè)不是樹(shù)的特性？（）A.有且只有一個(gè)根節(jié)點(diǎn)B.每個(gè)節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)C.可以有多個(gè)根節(jié)點(diǎn)D.沒(méi)有循環(huán)引用3.題目：快速排序的平均時(shí)間復(fù)雜度是（）。A.O(n)B.O(nlogn)C.O(n2)D.O(logn)4.題目：下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)適合實(shí)現(xiàn)LRU（最近最少使用）緩存？（）A.哈希表B.堆C.雙向鏈表+哈希表D.棧5.題目：二叉搜索樹(shù)中，任意節(jié)點(diǎn)的左子樹(shù)中的所有節(jié)點(diǎn)值都小于該節(jié)點(diǎn)的值，右子樹(shù)中的所有節(jié)點(diǎn)值都大于該節(jié)點(diǎn)的值，這個(gè)性質(zhì)稱為（）。A.完全性B.平衡性C.對(duì)稱性D.二分性6.題目：下列哪個(gè)算法的時(shí)間復(fù)雜度與輸入數(shù)據(jù)的初始順序無(wú)關(guān)？（）A.冒泡排序B.選擇排序C.快速排序D.插入排序7.題目：圖的鄰接矩陣表示法適用于稠密圖，其時(shí)間復(fù)雜度為（）。A.O(n)B.O(n2)C.O(nlogn)D.O(logn)8.題目：下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)是先進(jìn)先出（FIFO）的？（）A.棧B.隊(duì)列C.鏈表D.堆9.題目：在哈希表中，解決哈希沖突的常見(jiàn)方法不包括（）。A.開(kāi)放尋址法B.鏈地址法C.二叉搜索樹(shù)法D.哈希函數(shù)優(yōu)化10.題目：下列哪個(gè)算法可以用于查找無(wú)序數(shù)組中的第k?。ɑ虼螅┑脑兀浚ǎ〢.快速排序B.堆排序C.希爾排序D.二分查找二、填空題（共5題，每題2分，合計(jì)10分）1.題目：在二叉樹(shù)中，節(jié)點(diǎn)的深度是從根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑上的邊數(shù)，而節(jié)點(diǎn)的高度是根節(jié)點(diǎn)的高度為0，其他節(jié)點(diǎn)的高度是其子樹(shù)的高度中的最大值加1。2.題目：堆是一種特殊的完全二叉樹(shù)，分為最大堆和最小堆。在最大堆中，父節(jié)點(diǎn)的值總是大于或等于其子節(jié)點(diǎn)的值；在最小堆中，父節(jié)點(diǎn)的值總是小于或等于其子節(jié)點(diǎn)的值。3.題目：哈希表的平均查找時(shí)間為O(1)，但在最壞情況下（如哈希沖突嚴(yán)重）會(huì)退化到O(n)。常見(jiàn)的哈希沖突解決方法有鏈地址法和開(kāi)放尋址法。4.題目：圖的深度優(yōu)先搜索（DFS）是一種遍歷圖的方法，其基本思想是：從根節(jié)點(diǎn)出發(fā)，先訪問(wèn)該節(jié)點(diǎn)，然后遞歸地訪問(wèn)其未訪問(wèn)過(guò)的鄰接節(jié)點(diǎn)。廣度優(yōu)先搜索（BFS）則按層次遍歷圖。5.題目：二分查找要求數(shù)據(jù)必須是有序的。其基本思想是：比較中間元素與目標(biāo)值，若中間元素等于目標(biāo)值則查找成功，否則根據(jù)大小關(guān)系縮小查找范圍，重復(fù)上述過(guò)程。三、簡(jiǎn)答題（共5題，每題4分，合計(jì)20分）1.題目：簡(jiǎn)述棧和隊(duì)列的主要區(qū)別，并舉例說(shuō)明它們?cè)趯?shí)際應(yīng)用中的場(chǎng)景。2.題目：解釋二叉搜索樹(shù)（BST）的中序遍歷結(jié)果是什么？并給出一個(gè)二叉搜索樹(shù)的中序遍歷示例。3.題目：什么是圖的拓?fù)渑判颍窟m用于哪些場(chǎng)景？4.題目：哈希表的負(fù)載因子是什么？為什么負(fù)載因子不宜過(guò)高或過(guò)低？5.題目：快速排序的基本步驟是什么？為什么它被稱為“分治”算法？四、算法設(shè)計(jì)題（共3題，每題10分，合計(jì)30分）1.題目：設(shè)計(jì)一個(gè)算法，判斷一個(gè)無(wú)向圖是否是二分圖（即可以將圖的節(jié)點(diǎn)分成兩個(gè)集合，使得每條邊的兩個(gè)端點(diǎn)分別屬于不同的集合）。要求：-輸入：鄰接矩陣表示的無(wú)向圖。-輸出：是或否，以及可能的劃分方案（如果存在）。2.題目：給定一個(gè)包含重復(fù)數(shù)字的數(shù)組，設(shè)計(jì)一個(gè)算法找出所有不重復(fù)的組合，且組合中的數(shù)字按升序排列。例如，輸入`[1,2,2]`，輸出`[[1],[2],[1,2],[1,2]]`。3.題目：設(shè)計(jì)一個(gè)算法，實(shí)現(xiàn)LRU緩存。要求：-支持`get(key)`和`put(key,value)`操作。-`get(key)`：若存在，返回值并更新訪問(wèn)順序；若不存在，返回-1。-`put(key,value)`：若已存在，更新值并調(diào)整順序；若不存在，插入鍵值對(duì)，若緩存已滿則刪除最久未使用的鍵值對(duì)。五、代碼實(shí)現(xiàn)題（共2題，每題15分，合計(jì)30分）1.題目：實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)，支持以下操作：-`insert(key)`：插入一個(gè)鍵值對(duì)。-`search(key)`：查找一個(gè)鍵值對(duì)。-`delete(key)`：刪除一個(gè)鍵值對(duì)。-要求：`delete`操作需保持二叉搜索樹(shù)的性質(zhì)。2.題目：實(shí)現(xiàn)一個(gè)最小堆，支持以下操作：-`insert(val)`：插入一個(gè)元素。-`extract_min()`：彈出并返回最小元素。-`get_min()`：返回最小元素但不刪除。-要求：使用數(shù)組實(shí)現(xiàn)，并保持堆的性質(zhì)。答案與解析一、選擇題答案1.A-解析：鏈表支持在任意位置進(jìn)行插入和刪除操作，時(shí)間復(fù)雜度為O(1)；數(shù)組插入和刪除操作需要移動(dòng)元素，時(shí)間復(fù)雜度為O(n)。2.C-解析：樹(shù)的特點(diǎn)是有且只有一個(gè)根節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)（除根節(jié)點(diǎn)），且沒(méi)有循環(huán)引用?？梢杂卸鄠€(gè)根節(jié)點(diǎn)的結(jié)構(gòu)稱為森林。3.B-解析：快速排序的平均時(shí)間復(fù)雜度為O(nlogn)，但最壞情況下為O(n2)（如已排序數(shù)組）。4.C-解析：LRU緩存需要快速訪問(wèn)和刪除最久未使用的元素，雙向鏈表支持O(1)的刪除操作，結(jié)合哈希表實(shí)現(xiàn)O(1)的查找。5.D-解析：二叉搜索樹(shù)的性質(zhì)是“二分性”，即左子樹(shù)和右子樹(shù)分別包含小于和大于該節(jié)點(diǎn)的值。6.C-解析：快速排序的平均時(shí)間復(fù)雜度為O(nlogn)且與輸入順序無(wú)關(guān)；其他排序算法的時(shí)間復(fù)雜度與輸入順序相關(guān)。7.B-解析：圖的鄰接矩陣表示法中，每個(gè)元素表示兩個(gè)節(jié)點(diǎn)之間是否有邊，共有n2個(gè)元素，時(shí)間復(fù)雜度為O(n2)。8.B-解析：隊(duì)列是先進(jìn)先出（FIFO）的結(jié)構(gòu)，棧是先進(jìn)后出（LIFO）。9.C-解析：二叉搜索樹(shù)法不是哈希表的沖突解決方法，其他三種都是。10.A-解析：快速排序的分治思想可以找到第k小元素；其他算法不直接支持。二、填空題答案1.高度-解析：二叉樹(shù)的高度是節(jié)點(diǎn)深度的最大值加1，用于衡量樹(shù)的“伸展”程度。2.堆-解析：堆是一種特殊的完全二叉樹(shù)，分為最大堆和最小堆，常用于優(yōu)先隊(duì)列。3.O(1)/O(n)-解析：哈希表的平均查找時(shí)間為O(1)，但沖突嚴(yán)重時(shí)退化到O(n)。4.深度優(yōu)先搜索（DFS）/廣度優(yōu)先搜索（BFS）-解析：DFS和BFS是圖遍歷的兩種基本方法，分別按深度和廣度順序訪問(wèn)節(jié)點(diǎn)。5.二分查找-解析：二分查找是一種高效的查找算法，適用于有序數(shù)據(jù)，時(shí)間復(fù)雜度為O(logn)。三、簡(jiǎn)答題答案1.棧和隊(duì)列的主要區(qū)別及應(yīng)用場(chǎng)景-區(qū)別：-棧是LIFO（后進(jìn)先出），隊(duì)列是FIFO（先進(jìn)先出）。-棧的操作限制在棧頂，隊(duì)列的操作限制在隊(duì)首和隊(duì)尾。-應(yīng)用場(chǎng)景：-棧：函數(shù)調(diào)用棧、表達(dá)式求值、括號(hào)匹配、深度優(yōu)先搜索。-隊(duì)列：廣度優(yōu)先搜索、消息隊(duì)列、任務(wù)調(diào)度。2.二叉搜索樹(shù)的中序遍歷-中序遍歷結(jié)果：按升序排列所有節(jié)點(diǎn)值。-示例：給定BST`[5,3,7,2,4,6,8]`，中序遍歷為`[2,3,4,5,6,7,8]`。3.圖的拓?fù)渑判?定義：對(duì)有向無(wú)環(huán)圖（DAG）的節(jié)點(diǎn)進(jìn)行線性排序，使得對(duì)于每條有向邊`(u,v)`，節(jié)點(diǎn)`u`在排序中位于`v`之前。-應(yīng)用場(chǎng)景：任務(wù)調(diào)度、依賴關(guān)系處理（如課程安排、工程依賴）。4.哈希表的負(fù)載因子-定義：負(fù)載因子`λ=n/m`，其中n是哈希表中的元素?cái)?shù)量，m是哈希表的大小。-原因：-過(guò)高：沖突增多，查找時(shí)間退化到O(n)。-過(guò)低：空間利用率低，浪費(fèi)內(nèi)存。5.快速排序的步驟及分治思想-步驟：1.選擇一個(gè)基準(zhǔn)（pivot）。2.分區(qū)：將數(shù)組分成兩部分，左邊的元素都小于基準(zhǔn)，右邊的都大于基準(zhǔn)。3.遞歸：對(duì)左右兩部分分別進(jìn)行快速排序。-分治思想：將大問(wèn)題分解為小問(wèn)題，逐個(gè)解決，最終合并結(jié)果。四、算法設(shè)計(jì)題答案1.二分圖判斷算法-方法：使用染色法，將節(jié)點(diǎn)分為兩種顏色（如紅色和藍(lán)色），依次遍歷每個(gè)節(jié)點(diǎn)，若發(fā)現(xiàn)相鄰節(jié)點(diǎn)顏色相同則不是二分圖。-偽代碼：pythondefis_bipartite(graph):color={}fornodeingraph:ifnodenotincolor:color[node]=0#0:uncolored,1:red,-1:bluequeue=[node]whilequeue:current=queue.pop(0)forneighboringraph[current]:ifneighbornotincolor:color[neighbor]=-color[current]queue.append(neighbor)elifcolor[neighbor]==color[current]:returnFalsereturnTruereturnTrue2.不重復(fù)組合算法-方法：回溯法，先排序數(shù)組，避免重復(fù)，使用標(biāo)記數(shù)組記錄已訪問(wèn)的元素。-偽代碼：pythondeffind_combinations(nums):nums.sort()result=[]path=[]used=[False]len(nums)defbacktrack():result.append(path.copy())foriinrange(len(nums)):ifused[i]:continueifi>0andnums[i]==nums[i-1]andnotused[i-1]:continuepath.append(nums[i])used[i]=Truebacktrack()path.pop()used[i]=Falsebacktrack()returnresult3.LRU緩存實(shí)現(xiàn)-方法：使用雙向鏈表記錄訪問(wèn)順序，哈希表記錄鍵值對(duì)。-偽代碼：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key):ifkeyinself.cache:node=self.cache[key]self._move_to_front(node)returnnode.valuereturn-1defput(self,key,value):ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_front(node)else:iflen(self.cache)==self.capacity:self._remove_LRU()new_node=Node(key,value)self.cache[key]=new_nodeself._add_to_front(new_node)def_move_to_front(self,node):self._remove_node(node)self._add_to_front(node)def_add_to_front(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_remove_LRU(self):lru=self.tail.prevself._remove_node(lru)delself.cache[lru.key]五、代碼實(shí)現(xiàn)題答案1.二叉搜索樹(shù)實(shí)現(xiàn)-代碼：pythonclassTreeNode:def__init__(self,key):self.key=keyself.left=Noneself.right=NoneclassBST:def__init__(self):self.root=Nonedefinsert(self,key):ifnotself.root:self.root=TreeNode(key)else:self._insert(self.root,key)def_insert(self,node,key):ifkey<node.key:ifnode.left:self._insert(node.left,key)else:node.left=TreeNode(key)else:ifnode.right:self._insert(node.right,key)else:node.right=TreeNode(key)defsearch(self,key):returnself._search(self.root,key)def_search(self,node,key):ifnotnode:returnNoneifkey==node.key:returnnodeelifkey<node.key:returnself._search(node.left,key)else:returnself._search(node.right,key)defdelete(self,key):self.root=self._delete(self.root,key)def_delete(self,node,key):ifnotnode:returnnodeifkey<node.key:node.left=self._delete(node.left,key)elifkey>node.key:node.right=self._delete(node.right,key)else:ifnotnode.left:returnnode.rightelifnotnode.right:returnnode.leftelse:min_larger_node=self._find_min(node.right)node.key=min_larger_node.keynode.right=self._delete(node.right,min_larger_node.key)returnnodedef_find_min(self,node):whilenode.left:node=node.leftreturnnode2.最小堆實(shí)現(xiàn)-代碼：pythonclassMinHeap:def__init__(self):self.heap=[]definsert(self,val):self.heap.append(val)self._heapify_up(len(self.heap)-1)defextract_min(self):ifnotself.heap:returnNoneiflen(self.heap)==1:returnself.heap.pop()min_val=self.heap[0]self.heap[0]=self.he