2026年計(jì)算機(jī)編程入門與進(jìn)階：算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)練習(xí)題一、選擇題（共10題，每題2分，合計(jì)20分）1.數(shù)據(jù)結(jié)構(gòu)中，最適合進(jìn)行快速插入和刪除操作的是（）。A.數(shù)組B.鏈表C.棧D.堆2.以下哪個(gè)排序算法的平均時(shí)間復(fù)雜度為O(nlogn)，且為不穩(wěn)定排序？（）A.快速排序B.歸并排序C.堆排序D.冒泡排序3.在二叉搜索樹中，新插入的節(jié)點(diǎn)總是被添加在（）。A.根節(jié)點(diǎn)左側(cè)B.根節(jié)點(diǎn)右側(cè)C.任意葉子節(jié)點(diǎn)位置D.最接近的葉子節(jié)點(diǎn)位置4.下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)適合實(shí)現(xiàn)李氏最小生成樹算法？（）A.隊(duì)列B.棧C.優(yōu)先隊(duì)列D.哈希表5.在深度優(yōu)先搜索（DFS）中，用于記錄已訪問節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)通常是（）。A.數(shù)組B.鏈表C.哈希集合D.棧6.快速排序的劃分過程中，選擇哪個(gè)元素作為“基準(zhǔn)”（pivot）會(huì)影響其性能？（）A.第一個(gè)元素B.最后一個(gè)元素C.中間元素D.隨機(jī)元素7.在哈希表中，解決哈希沖突的常見方法不包括（）。A.開放地址法B.鏈地址法C.二分搜索法D.雙哈希法8.以下哪個(gè)算法不屬于動(dòng)態(tài)規(guī)劃的經(jīng)典應(yīng)用？（）A.最長公共子序列B.0-1背包問題C.快速排序D.斐波那契數(shù)列9.在圖的遍歷中，廣度優(yōu)先搜索（BFS）通常使用哪種數(shù)據(jù)結(jié)構(gòu)？（）A.棧B.隊(duì)列C.哈希表D.樹10.在樹形結(jié)構(gòu)中，一個(gè)節(jié)點(diǎn)的“深度”是指（）。A.從根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑長度B.該節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量C.該節(jié)點(diǎn)的父節(jié)點(diǎn)數(shù)量D.樹的最大高度二、填空題（共10題，每題2分，合計(jì)20分）1.在二叉搜索樹中，任何節(jié)點(diǎn)的左子樹只包含小于該節(jié)點(diǎn)的值，右子樹只包含大于該節(jié)點(diǎn)的值。2.堆排序是一種基于二叉堆的排序算法，分為最大堆和最小堆兩種。3.在圖的鄰接矩陣表示中，若兩個(gè)頂點(diǎn)之間有邊，則對應(yīng)的矩陣元素為1，否則為0。4.動(dòng)態(tài)規(guī)劃的核心思想是將問題分解為重疊子問題，并存儲(chǔ)子問題的解以避免重復(fù)計(jì)算。5.快速排序的平均時(shí)間復(fù)雜度為O(nlogn)，但在最壞情況下會(huì)退化到O(n^2)。6.哈希表的負(fù)載因子（loadfactor）定義為已存儲(chǔ)元素?cái)?shù)量與總桶數(shù)量的比值，通常應(yīng)保持在0.7以下。7.深度優(yōu)先搜索（DFS）是一種基于棧的遍歷算法，適用于查找路徑和連通性分析。8.在樹形結(jié)構(gòu)中，一個(gè)節(jié)點(diǎn)的子樹是指以該節(jié)點(diǎn)為根的所有節(jié)點(diǎn)的集合。9.最小生成樹（MST）的克魯斯卡爾算法適用于無向圖，而普里姆算法適用于有向圖。10.二分搜索算法的前提是待搜索序列必須有序，其時(shí)間復(fù)雜度為O(logn)。三、簡答題（共5題，每題4分，合計(jì)20分）1.簡述快速排序的基本思想及其優(yōu)缺點(diǎn)。2.解釋哈希表的工作原理，并說明常見的哈希沖突解決方法。3.比較深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）的異同點(diǎn)。4.什么是二叉搜索樹（BST）？請說明其插入和查找操作的時(shí)間復(fù)雜度。5.什么是動(dòng)態(tài)規(guī)劃？請舉例說明其適用場景。四、編程題（共3題，每題10分，合計(jì)30分）1.編寫一個(gè)函數(shù)，實(shí)現(xiàn)單鏈表的逆序操作。輸入：鏈表1->2->3->4->5輸出：5->4->3->2->12.實(shí)現(xiàn)一個(gè)哈希表，支持插入和查找操作。要求：使用鏈地址法解決哈希沖突，哈希函數(shù)為`hash(key)=key%10`。3.給定一個(gè)無向圖，編寫代碼實(shí)現(xiàn)普里姆算法計(jì)算最小生成樹。輸入：圖的鄰接矩陣輸出：最小生成樹的邊集合五、算法設(shè)計(jì)題（共2題，每題15分，合計(jì)30分）1.設(shè)計(jì)一個(gè)算法，判斷一個(gè)字符串是否為回文。例如：輸入"madam"，輸出true；輸入"hello"，輸出false。2.給定一個(gè)數(shù)組，設(shè)計(jì)一個(gè)算法找出數(shù)組中的最長遞增子序列（LIS）。例如：輸入[10,9,2,5,3,7,101,18]，輸出[2,5,7,101]。答案與解析一、選擇題答案與解析1.B解析：鏈表支持動(dòng)態(tài)插入和刪除操作，時(shí)間復(fù)雜度為O(1)，而數(shù)組插入和刪除需要O(n)時(shí)間。2.A解析：快速排序的平均時(shí)間復(fù)雜度為O(nlogn)，但在最壞情況下（如已排序數(shù)組）會(huì)退化到O(n^2)。此外，它是不穩(wěn)定排序。3.D解析：二叉搜索樹的插入操作遵循“左小右大”原則，新節(jié)點(diǎn)會(huì)添加在最接近的葉子節(jié)點(diǎn)位置。4.C解析：克魯斯卡爾算法和普里姆算法都需要優(yōu)先隊(duì)列來選擇當(dāng)前最小邊，時(shí)間復(fù)雜度為O(ElogV)。5.C解析：DFS使用棧或遞歸實(shí)現(xiàn)，但記錄已訪問節(jié)點(diǎn)通常用哈希集合以O(shè)(1)時(shí)間檢查。6.D解析：隨機(jī)選擇基準(zhǔn)可以減少快速排序在極端輸入下的性能退化。7.C解析：二分搜索法是查找算法，不是哈希沖突解決方法。8.C解析：快速排序是分治算法，不屬于動(dòng)態(tài)規(guī)劃范疇。9.B解析：BFS使用隊(duì)列實(shí)現(xiàn)層序遍歷，而DFS使用棧。10.A解析：節(jié)點(diǎn)深度是從根到該節(jié)點(diǎn)的路徑長度，與子節(jié)點(diǎn)或父節(jié)點(diǎn)數(shù)量無關(guān)。二、填空題答案與解析1.小于，大于解析：二叉搜索樹的定義要求左子樹所有值小于節(jié)點(diǎn)值，右子樹所有值大于節(jié)點(diǎn)值。2.二叉堆，最大堆，最小堆解析：堆排序基于二叉堆，最大堆節(jié)點(diǎn)值大于子節(jié)點(diǎn)，最小堆反之。3.1，0解析：鄰接矩陣用0和1表示頂點(diǎn)間是否存在邊。4.重疊子問題解析：動(dòng)態(tài)規(guī)劃的核心是分解為重疊子問題，如斐波那契數(shù)列。5.O(nlogn)，O(n^2)解析：快速排序平均為O(nlogn)，最壞為O(n^2)。6.負(fù)載因子解析：負(fù)載因子影響哈希表的沖突概率，過高時(shí)需擴(kuò)容。7.棧解析：DFS基于棧的遞歸或顯式棧實(shí)現(xiàn)。8.子樹解析：子樹是以節(jié)點(diǎn)為根的所有后代節(jié)點(diǎn)集合。9.克魯斯卡爾算法，無向圖；普里姆算法，有向圖解析：克魯斯卡爾算法適用于無向圖，普里姆算法適用于有向圖（此處修正原題錯(cuò)誤，普里姆算法也適用于無向圖）。10.有序，O(logn)解析：二分搜索要求序列有序，時(shí)間復(fù)雜度為O(logn)。三、簡答題答案與解析1.快速排序的基本思想及其優(yōu)缺點(diǎn)思想：選擇一個(gè)基準(zhǔn)（pivot），將數(shù)組分為兩部分，左部分所有元素小于基準(zhǔn)，右部分所有元素大于基準(zhǔn)，然后遞歸對兩部分進(jìn)行排序。優(yōu)點(diǎn)：平均時(shí)間復(fù)雜度O(nlogn)，空間復(fù)雜度O(logn)，原地排序。缺點(diǎn)：最壞情況O(n^2)，不穩(wěn)定排序。2.哈希表的工作原理及沖突解決方法原理：通過哈希函數(shù)將鍵映射到數(shù)組索引，實(shí)現(xiàn)快速查找。沖突解決方法：開放地址法（線性探測、二次探測）、鏈地址法（每個(gè)桶用鏈表存儲(chǔ)沖突元素）。3.DFS與BFS的異同點(diǎn)相同點(diǎn)：都是圖遍歷算法，可求連通性、路徑等。不同點(diǎn)：DFS用棧（遞歸或顯式棧），BFS用隊(duì)列；DFS可深入探索，BFS逐層探索。4.二叉搜索樹（BST）及其操作復(fù)雜度定義：左子樹所有值小于節(jié)點(diǎn)值，右子樹所有值大于節(jié)點(diǎn)值。插入和查找：時(shí)間復(fù)雜度均為O(h)，平均為O(logn)，最壞為O(n)（退化成鏈表）。5.動(dòng)態(tài)規(guī)劃及其適用場景定義：通過解決子問題并存儲(chǔ)結(jié)果避免重復(fù)計(jì)算，適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)問題。適用場景：背包問題、最長公共子序列、斐波那契數(shù)列等。四、編程題答案與解析1.單鏈表逆序pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev2.哈希表實(shí)現(xiàn)pythonclassHashTable:def__init__(self,size=10):self.size=sizeself.table=[[]for_inrange(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)returnkeyinself.table[index]3.普里姆算法最小生成樹pythondefprim(graph):n=len(graph)in_mst=[False]nparent=[-1]nkey=[float('inf')]nkey[0]=0for_inrange(n):u=-1forvinrange(n):ifnotin_mst[v]and(u==-1orkey[v]<key[u]):u=vin_mst[u]=Trueforvinrange(n):ifgraph[u][v]andnotin_mst[v]andgraph[u][v]<key[v]:parent[v]=ukey[v]=graph[u][v]returnparent五、算法設(shè)計(jì)題答案與解析1.判斷回文pythondefis_palindrome(s):returns==s[::-1]2.最長遞增子序列（LI