2026年程序設(shè)計面試題庫及答案一、編程實現(xiàn)題（每題15分，共3題）1.編寫一個函數(shù)，實現(xiàn)快速排序算法（QuickSort）要求：-輸入一個整數(shù)數(shù)組，返回排序后的數(shù)組。-不能使用現(xiàn)成的排序庫函數(shù)（如Python的`sorted()`或Java的`Arrays.sort()`）。-請展示核心代碼和測試用例。答案：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)測試用例test_arr=[3,6,8,10,1,2,1]print(quick_sort(test_arr))#輸出:[1,1,2,3,6,8,10]解析：-快速排序采用分治法，核心思想是選擇一個基準值（pivot），將數(shù)組分為三部分：小于基準值的、等于基準值的、大于基準值的。-遞歸地對左右兩部分繼續(xù)排序，最終合并。-時間復(fù)雜度：平均O(nlogn)，最壞O(n2)（當(dāng)基準值選擇不均勻時）。2.編寫一個函數(shù)，實現(xiàn)二叉樹的深度優(yōu)先遍歷（DFS）要求：-輸入一個二叉樹的根節(jié)點，返回前序遍歷的結(jié)果列表。-不能使用現(xiàn)成的庫函數(shù)（如Python的`collections.deque`）。-請展示核心代碼和測試用例。答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpreorder_dfs(root):ifnotroot:return[]result=[]stack=[root]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult測試用例root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)print(preorder_dfs(root))#輸出:[1,2,4,5,3]解析：-前序遍歷的順序是：根節(jié)點->左子樹->右子樹。-使用棧實現(xiàn)DFS，先訪問右子節(jié)點是因為棧是后進先出（LIFO），需要先處理右子樹。-時間復(fù)雜度：O(n)，每個節(jié)點訪問一次。3.編寫一個函數(shù)，實現(xiàn)LRU（LeastRecentlyUsed）緩存機制要求：-使用Python實現(xiàn)，不能使用現(xiàn)成的`collections.OrderedDict`。-支持兩個操作：`get(key)`和`put(key,value)`。-請展示核心代碼和測試用例。答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeynotinself.cache:return-1self.order.remove(key)self.order.append(key)returnself.cache[key]defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest_key=self.order.pop(0)delself.cache[oldest_key]self.cache[key]=valueself.order.append(key)測試用例cache=LRUCache(2)cache.put(1,1)cache.put(2,2)print(cache.get(1))#返回1cache.put(3,3)#去除鍵2print(cache.get(2))#返回-1cache.put(4,4)#去除鍵1print(cache.get(1))#返回-1print(cache.get(3))#返回3print(cache.get(4))#返回4解析：-LRU緩存通過記錄訪問順序，每次訪問或插入時移動節(jié)點到尾部，最久未訪問的節(jié)點在頭部。-使用列表`self.order`記錄順序，字典`self.cache`存儲鍵值對。-時間復(fù)雜度：`get`和`put`均為O(1)。二、算法設(shè)計題（每題20分，共2題）1.設(shè)計一個算法，判斷一個無向圖是否是二分圖（BipartiteGraph）要求：-輸入圖的鄰接表表示，返回布爾值及顏色分配（用0和1表示兩種顏色）。-不能使用現(xiàn)成的庫函數(shù)（如Python的`networkx`）。-請展示核心代碼和測試用例。答案：pythondefis_bipartite(graph):color={}fornodeingraph:ifnodenotincolor:stack=[node]color[node]=0whilestack:current=stack.pop()forneighboringraph[current]:ifneighbornotincolor:color[neighbor]=1-color[current]stack.append(neighbor)elifcolor[neighbor]==color[current]:returnFalsereturnTrue,color測試用例graph1={0:[1,3],1:[0,2],2:[1,3],3:[0,2]}print(is_bipartite(graph1))#輸出:(True,{0:0,1:1,2:1,3:0})graph2={0:[1,2],1:[0,3],2:[0],3:[1]}print(is_bipartite(graph2))#輸出:(False,{0:0,1:1,2:0,3:1})解析：-二分圖可以分成兩個集合，其中任何兩個相鄰節(jié)點顏色不同。-使用DFS遍歷圖，用`color`字典記錄顏色，初始節(jié)點設(shè)為0，相鄰節(jié)點設(shè)為1。-如果發(fā)現(xiàn)相鄰節(jié)點顏色相同，則不是二分圖。-時間復(fù)雜度：O(n+m)，n為節(jié)點數(shù)，m為邊數(shù)。2.設(shè)計一個算法，實現(xiàn)字符串的編輯距離（LevenshteinDistance）計算要求：-輸入兩個字符串`s1`和`s2`，返回最小編輯距離。-不能使用現(xiàn)成的庫函數(shù)（如Python的`difflib.SequenceMatcher`）。-請展示核心代碼和測試用例。答案：pythondeflevenshtein_distance(s1:str,s2:str)->int:m,n=len(s1),len(s2)dp=[[0](n+1)for_inrange(m+1)]foriinrange(m+1):dp[i][0]=iforjinrange(n+1):dp[0][j]=jforiinrange(1,m+1):forjinrange(1,n+1):ifs1[i-1]==s2[j-1]:dp[i][j]=dp[i-1][j-1]else:dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1returndp[m][n]測試用例print(levenshtein_distance("kitten","sitting"))#輸出:3print(levenshtein_distance("garden","garde"))#輸出:1解析：-編輯距離是指將一個字符串轉(zhuǎn)換為另一個字符串所需的最少單字符編輯（插入、刪除、替換）。-使用動態(tài)規(guī)劃，`dp[i][j]`表示`s1[:i]`到`s2[:j]`的編輯距離。-初始化邊界條件：空字符串到任何字符串的編輯距離等于字符串長度。-時間復(fù)雜度：O(mn)，m和n分別為兩個字符串的長度。三、系統(tǒng)設(shè)計題（每題25分，共1題）1.設(shè)計一個簡單的短鏈接（TinyURL）生成系統(tǒng)要求：-輸入一個長URL，返回一個短URL。-支持反向解析，輸入短URL返回原始長URL。-請展示核心設(shè)計思路、數(shù)據(jù)結(jié)構(gòu)及偽代碼。答案：核心設(shè)計思路：1.使用隨機生成或哈希算法將長URL映射為短URL。2.使用數(shù)據(jù)庫或內(nèi)存存儲映射關(guān)系，確保唯一性和快速查詢。3.短URL使用62進制（a-z,A-Z,0-9）表示，長度固定（如6位）。數(shù)據(jù)結(jié)構(gòu)：-字典`url_map`：`{長URL:短URL}`-字典`reverse_map`：`{短URL:長URL}`偽代碼：pythonimportbase64importhashlibclassTinyURL:def__init__(self):self.url_map={}self.reverse_map={}self.base_url="/"def_encode(self,num):chars="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"base=len(chars)encoded=""whilenum>0:encoded=chars[num%base]+encodednum//=basereturnencoded.zfill(6)#確保長度為6def_decode(self,short_url):hash_part=short_url[len(self.base_url):]returnint.from_bytes(base64.urlsafe_b64decode(hash_part),byteorder='big')definsert(self,long_url:str)->str:iflong_urlinself.url_map:returnself.url_map[long_url]hash_value=hashlib.sha256(long_url.encode()).hexdigest()num=int(hash_value,16)short_url=self.base_url+self._encode(num)self.url_map[long_url]=short_urlself.reverse_map[short_url]=long_urlreturnshort_urldefget(self,short_url:str)->str:returnself.reverse_map.get(short_url,"URLnotfound")測試用例tiny=