2026年程序員面試：數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題一、選擇題（共5題，每題2分）說(shuō)明：下列每題只有一個(gè)正確答案。1.題目：在以下數(shù)據(jù)結(jié)構(gòu)中，最適合進(jìn)行快速插入和刪除操作的是？A.數(shù)組B.鏈表C.棧D.堆2.題目：快速排序的平均時(shí)間復(fù)雜度是？A.O(n2)B.O(nlogn)C.O(n)D.O(logn)3.題目：以下哪個(gè)不是圖的遍歷算法？A.深度優(yōu)先搜索（DFS）B.廣度優(yōu)先搜索（BFS）C.插入排序D.Dijkstra算法4.題目：哈希表解決沖突的常用方法不包括？A.開(kāi)放地址法B.鏈地址法C.二分查找法D.哈希函數(shù)改進(jìn)5.題目：二叉搜索樹(shù)中，刪除一個(gè)節(jié)點(diǎn)后，可能需要進(jìn)行的調(diào)整不包括？A.節(jié)點(diǎn)旋轉(zhuǎn)B.重新計(jì)算樹(shù)的平衡因子C.節(jié)點(diǎn)合并D.哈希映射二、填空題（共5題，每題2分）說(shuō)明：請(qǐng)將答案填寫(xiě)在橫線上。1.題目：在棧中，最后被插入的元素通常是_______。____________2.題目：二分查找算法適用于_______的數(shù)據(jù)結(jié)構(gòu)。____________3.題目：平衡二叉樹(shù)（如AVL樹(shù)）要求任意節(jié)點(diǎn)的左右子樹(shù)高度差不超過(guò)_______。____________4.題目：圖的鄰接矩陣適用于表示_______的圖。____________5.題目：在鏈表中，刪除一個(gè)節(jié)點(diǎn)需要修改其前驅(qū)節(jié)點(diǎn)的_______指針。____________三、簡(jiǎn)答題（共4題，每題5分）說(shuō)明：請(qǐng)簡(jiǎn)要回答下列問(wèn)題。1.題目：簡(jiǎn)述快速排序和歸并排序的優(yōu)缺點(diǎn)，并說(shuō)明在什么情況下選擇哪種算法。2.題目：解釋哈希表的時(shí)間復(fù)雜度為什么通常接近O(1)，以及可能導(dǎo)致時(shí)間復(fù)雜度下降到O(n)的情況。3.題目：什么是二叉搜索樹(shù)（BST）？它和普通二叉樹(shù)有什么區(qū)別？4.題目：為什么鏈表適合用于實(shí)現(xiàn)棧和隊(duì)列？與數(shù)組實(shí)現(xiàn)相比，優(yōu)缺點(diǎn)是什么？四、編程題（共3題，每題15分）說(shuō)明：請(qǐng)根據(jù)要求實(shí)現(xiàn)代碼或邏輯描述。1.題目：設(shè)計(jì)一個(gè)函數(shù)，實(shí)現(xiàn)二分查找的遞歸版本。輸入為一個(gè)有序數(shù)組和一個(gè)目標(biāo)值，輸出目標(biāo)值的索引（若不存在則返回-1）。2.題目：實(shí)現(xiàn)一個(gè)簡(jiǎn)單的LRU（最近最少使用）緩存，使用雙向鏈表和哈希表存儲(chǔ)鍵值對(duì)，支持`get`和`put`操作。3.題目：給定一個(gè)無(wú)向圖，用鄰接表表示，編寫(xiě)DFS算法遍歷該圖，并打印遍歷順序。假設(shè)圖用字典表示，鍵為節(jié)點(diǎn)，值為鄰接節(jié)點(diǎn)列表。五、算法設(shè)計(jì)題（共2題，每題20分）說(shuō)明：請(qǐng)?jiān)敿?xì)描述算法邏輯，并分析時(shí)間復(fù)雜度。1.題目：假設(shè)你有一個(gè)包含重復(fù)元素的數(shù)組，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法找出所有重復(fù)次數(shù)超過(guò)一半的元素，要求時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。2.題目：給定一個(gè)字符串，判斷它是否是另一個(gè)字符串的子序列。例如，"abc"是"ahbgdc"的子序列，但"axc"不是。請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，時(shí)間復(fù)雜度盡可能低。答案與解析一、選擇題答案1.B（鏈表允許快速插入刪除，數(shù)組需要移動(dòng)元素）2.B（快速排序平均時(shí)間復(fù)雜度為O(nlogn)，最壞為O(n2)）3.C（插入排序是排序算法，非圖遍歷）4.C（二分查找法用于有序數(shù)組，非哈希表沖突解決）5.D（哈希映射與二叉搜索樹(shù)無(wú)關(guān)）二、填空題答案1.棧底（LIFO原則）2.有序數(shù)組3.14.稠密圖5.next（或尾指針，取決于單向/雙向鏈表）三、簡(jiǎn)答題解析1.快速排序與歸并排序的優(yōu)缺點(diǎn)-快速排序：優(yōu)點(diǎn)：平均時(shí)間復(fù)雜度O(nlogn)，空間復(fù)雜度O(logn)（遞歸棧），不穩(wěn)定排序。缺點(diǎn)：最壞情況O(n2)，對(duì)小型數(shù)據(jù)集效率低于插入排序。適用場(chǎng)景：大數(shù)據(jù)集，內(nèi)存足夠時(shí)。-歸并排序：優(yōu)點(diǎn)：穩(wěn)定排序，時(shí)間復(fù)雜度O(nlogn)，最壞情況下仍保持穩(wěn)定。缺點(diǎn)：需要額外內(nèi)存空間O(n)，適合鏈表排序。適用場(chǎng)景：需要穩(wěn)定排序或鏈表數(shù)據(jù)時(shí)。2.哈希表時(shí)間復(fù)雜度分析-理想情況下，哈希函數(shù)均勻分布，每次查找、插入、刪除時(shí)間復(fù)雜度為O(1)。-沖突解決導(dǎo)致時(shí)間復(fù)雜度下降到O(n)：-開(kāi)放地址法：當(dāng)大量沖突時(shí)，可能需要遍歷整個(gè)哈希表。-鏈地址法：沖突節(jié)點(diǎn)鏈表過(guò)長(zhǎng)時(shí)，時(shí)間復(fù)雜度接近O(n)。3.二叉搜索樹(shù)（BST）及其與普通二叉樹(shù)的區(qū)別-BST定義：左子樹(shù)所有節(jié)點(diǎn)值小于根節(jié)點(diǎn)，右子樹(shù)所有節(jié)點(diǎn)值大于根節(jié)點(diǎn)，且無(wú)重復(fù)值。-區(qū)別：BST具有排序性質(zhì)，而普通二叉樹(shù)無(wú)順序性。4.鏈表實(shí)現(xiàn)棧/隊(duì)列的優(yōu)缺點(diǎn)-棧（LIFO）：鏈表支持尾插尾刪（棧操作），數(shù)組需要移動(dòng)元素。優(yōu)點(diǎn)：快速操作，空間靈活。缺點(diǎn)：無(wú)隨機(jī)訪問(wèn)能力。-隊(duì)列（FIFO）：鏈表頭插頭刪（隊(duì)列操作），數(shù)組需要移動(dòng)元素。優(yōu)點(diǎn)：高效操作。缺點(diǎn)：相比數(shù)組實(shí)現(xiàn)，緩存友好性較低。四、編程題參考實(shí)現(xiàn)1.二分查找遞歸版pythondefbinary_search(arr,left,right,target):ifleft>right:return-1mid=(left+right)//2ifarr[mid]==target:returnmidelifarr[mid]>target:returnbinary_search(arr,left,mid-1,target)else:returnbinary_search(arr,mid+1,right,target)2.LRU緩存實(shí)現(xiàn)pythonclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.head,self.tail=Node(0,0),Node(0,0)self.head.next=self.tailself.tail.prev=self.headdef_add_node(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_move_to_head(self,node):self._remove_node(node)self._add_node(node)defget(self,key):node=self.cache.get(key,None)ifnotnode:return-1self._move_to_head(node)returnnode.valuedefput(self,key,value):node=self.cache.get(key)ifnotnode:newNode=Node(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self.tail.prevself._remove_node(tail)delself.cache[tail.key]else:node.value=valueself._move_to_head(node)3.DFS遍歷圖pythondefdfs(graph,start,visited=None):ifvisitedisNone:visited=set()visited.add(start)print(start,end='')forneighboringraph[start]:ifneighbornotinvisited:dfs(graph,neighbor,visited)示例輸入：`graph={'A':['B','C'],'B':['A','D'],'C':['A'],'D':['B']}`五、算法設(shè)計(jì)題解析1.重復(fù)次數(shù)超過(guò)一半的元素-思路：摩爾投票算法-初始化候選值和計(jì)數(shù)器，遍歷數(shù)組：-若計(jì)數(shù)器為0，設(shè)當(dāng)前元素為候選值，計(jì)數(shù)器設(shè)為1。-否則，若當(dāng)前元素等于候選值，計(jì)數(shù)器加1；否則減1。-最后驗(yàn)證候選值是否滿足條件。-時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。2.子序列判斷-思路：雙指針?lè)?初始化兩個(gè)指針，分別指向兩個(gè)字符串的開(kāi)始。-遍歷較長(zhǎng)字符串，若字符匹配，移動(dòng)較短字符串指針。-若較短字