2026年程序設(shè)計基礎(chǔ)與算法進(jìn)階題一、選擇題（共10題，每題2分，合計20分）1.關(guān)于數(shù)據(jù)結(jié)構(gòu)的時間復(fù)雜度，下列說法正確的是：A.順序表插入操作的時間復(fù)雜度為O(1)B.哈希表查找操作的時間復(fù)雜度最壞情況下為O(n)C.二叉搜索樹查找操作的時間復(fù)雜度平均為O(logn)D.隊列的刪除操作的時間復(fù)雜度為O(n)2.下列哪種排序算法在最壞情況下時間復(fù)雜度始終為O(nlogn)？A.快速排序B.冒泡排序C.簡單選擇排序D.堆排序3.在C++中，以下關(guān)于類的描述，錯誤的是：A.構(gòu)造函數(shù)可以帶有參數(shù)B.析構(gòu)函數(shù)可以重載C.類成員可以聲明為靜態(tài)D.類成員可以聲明為私有4.下列哪個函數(shù)是Python中用于處理異常的標(biāo)準(zhǔn)庫函數(shù)？A.`try`B.`except`C.`raise`D.`assert`5.在Java中，以下哪個集合類不允許重復(fù)元素？A.`ArrayList`B.`HashSet`C.`LinkedList`D.`HashMap`6.以下哪種設(shè)計模式屬于創(chuàng)建型模式？A.觀察者模式B.工廠方法模式C.策略模式D.責(zé)任鏈模式7.關(guān)于算法的遞歸實(shí)現(xiàn)，以下說法正確的是：A.遞歸一定會導(dǎo)致棧溢出B.遞歸比循環(huán)更高效C.遞歸需要終止條件D.遞歸只適用于簡單問題8.在SQL中，以下哪個語句用于聯(lián)合兩個數(shù)據(jù)表？A.`JOIN`B.`WHERE`C.`GROUPBY`D.`ORDERBY`9.以下哪種數(shù)據(jù)結(jié)構(gòu)適用于實(shí)現(xiàn)LRU（最近最少使用）緩存？A.數(shù)組B.哈希表C.雙向鏈表+哈希表D.棧10.在Web開發(fā)中，以下哪個HTTP方法用于提交表單數(shù)據(jù)？A.`GET`B.`POST`C.`PUT`D.`DELETE`二、填空題（共5題，每題2分，合計10分）1.在二叉樹中，節(jié)點(diǎn)的度為0稱為______，度為2稱為______。2.快速排序的核心思想是______，其平均時間復(fù)雜度為______。3.在C++中，使用______關(guān)鍵字聲明類的構(gòu)造函數(shù)。4.Python中，用于處理文件操作的內(nèi)置函數(shù)是______。5.在數(shù)據(jù)庫中，用于確保數(shù)據(jù)一致性的完整性約束包括______、______和______。三、簡答題（共5題，每題4分，合計20分）1.簡述棧和隊列的主要區(qū)別，并分別舉例說明其應(yīng)用場景。2.解釋什么是“時間復(fù)雜度”，并說明如何計算一個算法的時間復(fù)雜度。3.什么是多線程？簡述多線程編程的主要優(yōu)勢和挑戰(zhàn)。4.什么是數(shù)據(jù)庫索引？簡述索引對查詢效率的影響。5.解釋什么是“設(shè)計模式”，并列舉三種常見的設(shè)計模式及其用途。四、編程題（共3題，合計50分）1.（15分）編寫一個函數(shù)，實(shí)現(xiàn)快速排序算法。輸入為一個整數(shù)數(shù)組，輸出為排序后的數(shù)組。要求：-不能使用現(xiàn)成的庫函數(shù)（如`std::sort`或`Arrays.sort`）。-提供測試用例并運(yùn)行驗(yàn)證。2.（20分）設(shè)計一個簡單的LRU緩存系統(tǒng)，支持以下操作：-`get(key)`:獲取鍵對應(yīng)的值，若存在則返回值，并更新其使用順序；若不存在返回-1。-`put(key,value)`:插入或更新鍵值對，若緩存已滿，則刪除最近最少使用的項。要求：-使用雙向鏈表和哈希表實(shí)現(xiàn)，時間復(fù)雜度為O(1)。-提供測試用例并運(yùn)行驗(yàn)證。3.（15分）編寫一個函數(shù)，實(shí)現(xiàn)二叉搜索樹的插入和查找操作。輸入為一系列整數(shù)，輸出為插入后的二叉搜索樹的中序遍歷結(jié)果。要求：-不使用現(xiàn)成的庫類（如`TreeNode`），需自行定義二叉樹節(jié)點(diǎn)。-提供測試用例并運(yùn)行驗(yàn)證。答案與解析一、選擇題答案與解析1.C-A錯誤，順序表插入操作的時間復(fù)雜度為O(n)（若考慮頭插法，為O(1)）。-B錯誤，哈希表查找操作最壞情況下為O(n)。-C正確，二叉搜索樹查找操作平均為O(logn)。-D錯誤，隊列的刪除操作時間復(fù)雜度為O(1)。2.D-堆排序最壞情況下時間復(fù)雜度始終為O(nlogn)。-快速排序最壞情況下為O(n2)。-冒泡排序和簡單選擇排序最壞情況下為O(n2)。3.B-析構(gòu)函數(shù)不能重載，只能有一個。-構(gòu)造函數(shù)可以帶參數(shù)，類成員可以聲明為靜態(tài)，類成員可以聲明為私有。4.C-`raise`用于拋出異常，`try`和`except`用于捕獲異常，`assert`用于斷言條件。5.B-`HashSet`不允許重復(fù)元素，`ArrayList`、`LinkedList`和`HashMap`允許。6.B-工廠方法模式屬于創(chuàng)建型模式，觀察者模式和行為型模式，策略模式和責(zé)任鏈模式屬于行為型模式。7.C-遞歸需要終止條件，否則可能導(dǎo)致棧溢出。遞歸不一定比循環(huán)高效，且適用于復(fù)雜問題。8.A-`JOIN`用于聯(lián)合兩個數(shù)據(jù)表，`WHERE`用于條件過濾，`GROUPBY`用于分組，`ORDERBY`用于排序。9.C-雙向鏈表+哈希表可以高效實(shí)現(xiàn)LRU緩存，數(shù)組查找為O(n)，哈希表+鏈表可以優(yōu)化但不如雙向鏈表直接。10.B-`POST`用于提交表單數(shù)據(jù)，`GET`用于獲取數(shù)據(jù)，`PUT`用于更新，`DELETE`用于刪除。二、填空題答案與解析1.葉子節(jié)點(diǎn)，非葉子節(jié)點(diǎn)-二叉樹中，度為0的節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)，度為2的節(jié)點(diǎn)稱為非葉子節(jié)點(diǎn)（根節(jié)點(diǎn)可能度為1或2）。2.分治思想，O(nlogn)-快速排序通過分治思想將大問題分解為小問題，平均時間復(fù)雜度為O(nlogn)。3.`explicit`-在C++中，使用`explicit`關(guān)鍵字聲明構(gòu)造函數(shù)，防止隱式類型轉(zhuǎn)換。4.`open()`-Python中，使用`open()`函數(shù)處理文件操作。5.實(shí)體完整性，參照完整性，用戶定義完整性-數(shù)據(jù)庫完整性約束包括上述三種。三、簡答題答案與解析1.棧和隊列的主要區(qū)別及應(yīng)用場景-棧：后進(jìn)先出（LIFO），適用于括號匹配、表達(dá)式求值、深度優(yōu)先搜索等。-隊列：先進(jìn)先出（FIFO），適用于任務(wù)調(diào)度、消息隊列等。2.時間復(fù)雜度及其計算方法-時間復(fù)雜度描述算法執(zhí)行時間隨輸入規(guī)模增長的趨勢。-計算方法：統(tǒng)計循環(huán)、遞歸等關(guān)鍵操作次數(shù)，取主項（如n2、nlogn）。3.多線程的優(yōu)勢與挑戰(zhàn)-優(yōu)勢：提高并發(fā)性、資源利用率。-挑戰(zhàn)：數(shù)據(jù)競爭、死鎖、調(diào)試復(fù)雜。4.數(shù)據(jù)庫索引及其影響-索引是幫助快速查找數(shù)據(jù)的結(jié)構(gòu)（如B+樹）。-影響：加速查詢，但增加寫操作開銷。5.設(shè)計模式及其用途-工廠方法模式：創(chuàng)建對象，解耦。-單例模式：確保全局唯一實(shí)例。-觀察者模式：實(shí)現(xiàn)事件監(jiān)聽。四、編程題答案與解析1.快速排序?qū)崿F(xiàn)（C++示例）cppinclude<iostream>include<vector>voidquickSort(std::vector<int>&arr,intleft,intright){if(left>=right)return;intpivot=arr[left+(right-left)/2];inti=left,j=right;while(i<=j){while(arr[i]<pivot)i++;while(arr[j]>pivot)j--;if(i<=j)std::swap(arr[i++],arr[j--]);}quickSort(arr,left,j);quickSort(arr,i,right);}intmain(){std::vector<int>arr={3,1,4,1,5,9,2,6,5,3};quickSort(arr,0,arr.size()-1);for(intnum:arr)std::cout<<num<<"";return0;}2.LRU緩存系統(tǒng)（Python示例）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.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_remove_node(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add_to_front(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_lru(self):lru=self.tail.prevself._remove_node(lru)測試用例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))#43.二叉搜索樹插入與查找（C++示例）cppinclude<iostream>include<vector>include<algorithm>structTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};voidinsert(TreeNoderoot,intval){if(!root)returnnewTreeNode(val);if(val<root->val)insert(root->left,val);elseinsert(root->right,val);}voidinorder(TreeNoderoot,std::vector<int>&res){if(!root)return;inorder(root->left,res);res.push_back(root->val);inorder(root->right,res);}TreeNodebuildBST(conststd::vector<int>&arr){TreeNoderoot=nullptr;for