2026年數(shù)據(jù)結(jié)構(gòu)與算法練習(xí)題一、選擇題（每題2分，共20分）說(shuō)明：下列每小題只有一個(gè)正確答案。1.在下列數(shù)據(jù)結(jié)構(gòu)中，最適合用來(lái)表示稀疏矩陣的是（）。A.順序表B.鏈表C.矩陣鏈D.二維數(shù)組2.下列關(guān)于二叉樹(shù)的說(shuō)法中，錯(cuò)誤的是（）。A.完全二叉樹(shù)中，若一個(gè)節(jié)點(diǎn)沒(méi)有左子節(jié)點(diǎn)，則它一定沒(méi)有右子節(jié)點(diǎn)B.滿二叉樹(shù)中，所有內(nèi)部節(jié)點(diǎn)的度均為2C.二叉樹(shù)的遍歷方式包括前序遍歷、中序遍歷和后序遍歷D.堆是一種特殊的二叉樹(shù)，可以是任意形狀3.在快速排序算法中，當(dāng)輸入數(shù)據(jù)已經(jīng)接近有序時(shí)，其時(shí)間復(fù)雜度會(huì)退化到（）。A.O(n)B.O(nlogn)C.O(n2)D.O(logn)4.下列數(shù)據(jù)結(jié)構(gòu)中，最適合用于實(shí)現(xiàn)棧的是（）。A.鏈表B.隊(duì)列C.哈希表D.堆5.在圖的遍歷算法中，深度優(yōu)先搜索（DFS）的時(shí)間復(fù)雜度與廣度優(yōu)先搜索（BFS）的時(shí)間復(fù)雜度相比（）。A.DFS更慢B.BFS更慢C.兩者相同D.取決于具體實(shí)現(xiàn)6.哈希表解決沖突的兩種主要方法是（）。A.開(kāi)放定址法和鏈地址法B.二叉查找樹(shù)法和堆法C.哈希函數(shù)法和中綴法D.插入法和刪除法7.在下列算法中，屬于分治法的是（）。A.冒泡排序B.快速排序C.選擇排序D.插入排序8.在B樹(shù)中，每個(gè)節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量與其子節(jié)點(diǎn)的數(shù)量之間存在什么關(guān)系？（）A.關(guān)鍵字?jǐn)?shù)量是子節(jié)點(diǎn)數(shù)量的2倍B.關(guān)鍵字?jǐn)?shù)量是子節(jié)點(diǎn)數(shù)量的1倍C.關(guān)鍵字?jǐn)?shù)量比子節(jié)點(diǎn)數(shù)量多1D.關(guān)鍵字?jǐn)?shù)量比子節(jié)點(diǎn)數(shù)量少19.在下列數(shù)據(jù)結(jié)構(gòu)中，最適合實(shí)現(xiàn)LRU（最近最少使用）緩存淘汰算法的是（）。A.哈希表B.鏈表C.堆D.雙向鏈表10.在歸并排序中，遞歸的終止條件是（）。A.子數(shù)組長(zhǎng)度為0B.子數(shù)組長(zhǎng)度為1C.子數(shù)組長(zhǎng)度為nD.子數(shù)組無(wú)法再分二、填空題（每空1分，共20分）說(shuō)明：請(qǐng)將答案填寫在橫線上。1.在線性表中，插入一個(gè)元素的最壞時(shí)間復(fù)雜度為_(kāi)_____。2.二叉樹(shù)的深度為h，則其最多有多少個(gè)節(jié)點(diǎn)？______。3.快速排序的平均時(shí)間復(fù)雜度為_(kāi)_____。4.棧是一種______結(jié)構(gòu)，遵循______原則。5.在圖的鄰接矩陣表示中，如果兩個(gè)頂點(diǎn)之間沒(méi)有邊，通常用______表示。6.哈希表的沖突解決方法中，鏈地址法的主要缺點(diǎn)是______。7.B樹(shù)的平衡性體現(xiàn)在每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量相等（除葉節(jié)點(diǎn)外），其關(guān)鍵字?jǐn)?shù)量范圍為_(kāi)_____。8.在堆排序中，堆的調(diào)整過(guò)程稱為_(kāi)_____。9.LRU緩存淘汰算法的核心思想是______。10.歸并排序的空間復(fù)雜度為_(kāi)_____。三、簡(jiǎn)答題（每題5分，共25分）說(shuō)明：請(qǐng)簡(jiǎn)要回答下列問(wèn)題。1.簡(jiǎn)述線性表和鏈表的優(yōu)缺點(diǎn)。2.解釋什么是二叉樹(shù)的完全二叉樹(shù)，并舉例說(shuō)明。3.描述快速排序的基本思想和實(shí)現(xiàn)步驟。4.解釋哈希表的工作原理，并說(shuō)明常見(jiàn)的沖突解決方法。5.簡(jiǎn)述圖的三種基本遍歷方式（DFS、BFS、Dijkstra算法）及其適用場(chǎng)景。四、編程題（每題10分，共30分）說(shuō)明：請(qǐng)用C++或Java實(shí)現(xiàn)下列功能。1.實(shí)現(xiàn)一個(gè)簡(jiǎn)單的棧，支持push、pop和peek操作。要求：使用數(shù)組實(shí)現(xiàn)棧，并處理?xiàng)M和棧空的情況。2.編寫一個(gè)函數(shù)，判斷二叉樹(shù)是否為平衡二叉樹(shù)。要求：平衡二叉樹(shù)定義為任意節(jié)點(diǎn)的左右子樹(shù)高度差不超過(guò)1。3.實(shí)現(xiàn)一個(gè)哈希表，支持插入和查找操作，使用鏈地址法解決沖突。要求：哈希函數(shù)為`hash(key)=key%10`，鏈表節(jié)點(diǎn)包含`key`和`next`字段。五、算法設(shè)計(jì)題（15分）說(shuō)明：請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法解決下列問(wèn)題，并分析其時(shí)間復(fù)雜度。問(wèn)題描述：給定一個(gè)包含重復(fù)元素的數(shù)組，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法找出數(shù)組中所有重復(fù)至少三次的元素，并輸出它們的順序。例如，輸入`[1,2,3,1,2,1,4,5,3,3]`，輸出`[1,3]`。答案與解析一、選擇題答案1.B2.D3.C4.A5.C6.A7.B8.C9.D10.B解析：1.稀疏矩陣適合用鏈表表示，因?yàn)橄∈杈仃囍写蟛糠衷貫?，鏈表可以節(jié)省空間。2.D錯(cuò)誤，堆是特殊的完全二叉樹(shù)，要求除了葉節(jié)點(diǎn)外，所有節(jié)點(diǎn)的度數(shù)均為2。3.快速排序在近乎有序時(shí)，會(huì)退化到O(n2)。4.棧是后進(jìn)先出結(jié)構(gòu)，最適合用鏈表實(shí)現(xiàn)。5.DFS和BFS的時(shí)間復(fù)雜度均為O(V+E)，但實(shí)現(xiàn)方式不同。6.開(kāi)放定址法和鏈地址法是常見(jiàn)沖突解決方法。7.快速排序是典型的分治算法。8.B樹(shù)中，每個(gè)節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量比子節(jié)點(diǎn)數(shù)量多1。9.LRU緩存適合用雙向鏈表實(shí)現(xiàn)。10.歸并排序遞歸終止條件是子數(shù)組長(zhǎng)度為1。二、填空題答案1.O(n)2.2^h-13.O(nlogn)4.后進(jìn)先出；后進(jìn)先出5.∞（表示無(wú)窮大）6.空間復(fù)雜度高7.[ceil(m/2),floor((m-1)/2)]8.堆化9.替換最久未使用的元素10.O(nlogn)解析：1.插入元素最壞情況是每次插入都需要遍歷整個(gè)線性表。2.二叉樹(shù)深度為h時(shí)，最多有2^h-1個(gè)節(jié)點(diǎn)。3.快速排序平均時(shí)間復(fù)雜度為O(nlogn)。4.棧是后進(jìn)先出結(jié)構(gòu)，遵循LIFO原則。5.鄰接矩陣用無(wú)窮大表示無(wú)直接邊。6.鏈地址法沖突解決會(huì)占用更多空間。7.B樹(shù)節(jié)點(diǎn)關(guān)鍵字范圍取決于節(jié)點(diǎn)度數(shù)。8.堆調(diào)整是堆化過(guò)程。9.LRU核心是替換最久未使用元素。10.歸并排序需要額外空間。三、簡(jiǎn)答題答案1.線性表與鏈表優(yōu)缺點(diǎn)：-線性表：順序存儲(chǔ)，隨機(jī)訪問(wèn)快（O(1)），但插入刪除慢（O(n)）；鏈表插入刪除快（O(1)），但隨機(jī)訪問(wèn)慢（O(n)）。2.完全二叉樹(shù)：除最后一層外，其他層節(jié)點(diǎn)數(shù)滿，最后一層節(jié)點(diǎn)從左到右連續(xù)。例如：[1,2,3,4,5,6]。3.快速排序思想：分治思想，選擇基準(zhǔn)元素，將數(shù)組分為小于和大于基準(zhǔn)的兩部分，遞歸排序。4.哈希表原理與沖突解決：通過(guò)哈希函數(shù)將鍵映射到數(shù)組索引，沖突用開(kāi)放定址法或鏈地址法解決。5.圖遍歷方式：-DFS：深度優(yōu)先，適合求連通分量；-BFS：廣度優(yōu)先，適合求最短路徑；-Dijkstra：貪心算法，求單源最短路徑。四、編程題答案1.棧實(shí)現(xiàn)（C++）：cppinclude<vector>include<stdexcept>classStack{private:std::vector<int>data;intcapacity;public:Stack(intsize):capacity(size),data(size){}voidpush(intx){if(size()==capacity)throwstd::overflow_error("Stackfull");data.push_back(x);}intpop(){if(empty())throwstd::underflow_error("Stackempty");intx=data.back();data.pop_back();returnx;}intpeek()const{if(empty())throwstd::underflow_error("Stackempty");returndata.back();}boolempty()const{returndata.empty();}intsize()const{returndata.size();}};2.判斷平衡二叉樹(shù)（Java）：javaclassTreeNode{intval;TreeNodeleft,right;TreeNode(intx){val=x;}}publicclassSolution{publicbooleanisBalanced(TreeNoderoot){returnmaxDepth(root)!=-1;}privateintmaxDepth(TreeNodenode){if(node==null)return0;intleft=maxDepth(node.left);if(left==-1)return-1;intright=maxDepth(node.right);if(right==-1||Math.abs(left-right)>1)return-1;returnMath.max(left,right)+1;}}3.哈希表實(shí)現(xiàn)（C++）：cppinclude<vector>include<list>classHashTable{private:std::vector<std::list<int>>table;intcapacity;public:HashTable(intsize):capacity(size),table(size){}voidinsert(intkey){intidx=key%capacity;table[idx].push_back(key);}boolfind(intkey){intidx=key%capacity;for(intk:table[idx]){if(k==key)returntrue;}returnfalse;}};五、算法設(shè)計(jì)題答案算法思路：1.使用哈希表記錄每個(gè)元素的出現(xiàn)次數(shù)；2.遍歷哈希表，找出出現(xiàn)至少三次的元素，按順序輸出。代碼（C++）：cppinclude<vector>include<unordered_map>std::vector<int>findDuplicates(std::vector<int>&nums){std::unordered_ma