2026年程序設(shè)計(jì)基礎(chǔ)及算法應(yīng)用測(cè)試題一、選擇題（共10題，每題2分，計(jì)20分）1.以下哪個(gè)選項(xiàng)不是算法的基本特性？A.有窮性B.確定性C.可行性D.邏輯性2.在Python中，以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)最適合實(shí)現(xiàn)棧？A.列表（list）B.隊(duì)列（queue）C.集合（set）D.字典（dict）3.快速排序在最壞情況下的時(shí)間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)4.以下哪個(gè)不是遞歸算法的優(yōu)點(diǎn)？A.代碼簡(jiǎn)潔B.容易理解C.效率高D.調(diào)試方便5.在C++中，以下哪個(gè)關(guān)鍵字用于定義常量？A.staticB.constC.finalD.volatile6.以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)適合實(shí)現(xiàn)廣度優(yōu)先搜索（BFS）？A.棧（stack）B.隊(duì)列（queue）C.鏈表（linkedlist）D.樹(shù)（tree）7.在Java中，以下哪個(gè)集合類(lèi)不允許重復(fù)元素？A.ArrayListB.LinkedListC.HashSetD.HashMap8.哈希表的主要缺點(diǎn)是？A.空間復(fù)雜度高B.時(shí)間復(fù)雜度高C.容易沖突D.難以擴(kuò)展9.在Python中，以下哪個(gè)函數(shù)用于計(jì)算列表的平均值？A.mean()B.average()C.sum()/len()D.avg()10.以下哪個(gè)不是動(dòng)態(tài)規(guī)劃的應(yīng)用場(chǎng)景？A.最長(zhǎng)公共子序列B.背包問(wèn)題C.快速排序D.最短路徑問(wèn)題二、填空題（共10題，每題2分，計(jì)20分）1.算法的復(fù)雜度通常用______和______來(lái)衡量。2.在二叉樹(shù)中，一個(gè)節(jié)點(diǎn)的左子樹(shù)的根節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的______。3.冒泡排序的平均時(shí)間復(fù)雜度是______。4.在C++中，使用______關(guān)鍵字可以聲明靜態(tài)變量。5.棧的兩種基本操作是______和______。6.在圖的遍歷中，深度優(yōu)先搜索（DFS）通常使用______來(lái)實(shí)現(xiàn)。7.在Python中，使用______函數(shù)可以將字符串轉(zhuǎn)換為列表。8.哈希表的時(shí)間復(fù)雜度在理想情況下是______。9.遞歸算法的效率通常低于迭代算法，因?yàn)開(kāi)_____。10.在Java中，使用______關(guān)鍵字可以聲明抽象類(lèi)。三、簡(jiǎn)答題（共5題，每題5分，計(jì)25分）1.簡(jiǎn)述棧和隊(duì)列的主要區(qū)別。2.解釋什么是遞歸，并舉例說(shuō)明遞歸的應(yīng)用。3.描述快速排序的基本步驟。4.解釋哈希表的工作原理，并說(shuō)明哈希沖突的解決方法。5.什么是動(dòng)態(tài)規(guī)劃？請(qǐng)舉例說(shuō)明其應(yīng)用場(chǎng)景。四、編程題（共3題，每題15分，計(jì)45分）1.編寫(xiě)一個(gè)函數(shù)，實(shí)現(xiàn)冒泡排序算法。要求：輸入一個(gè)整數(shù)列表，輸出排序后的列表。示例：輸入`[64,34,25,12,22,11,90]`，輸出`[11,12,22,25,34,64,90]`。2.編寫(xiě)一個(gè)函數(shù)，實(shí)現(xiàn)二叉樹(shù)的深度優(yōu)先搜索（DFS）。要求：輸入一個(gè)二叉樹(shù)的根節(jié)點(diǎn)，輸出中序遍歷的結(jié)果。示例：輸入二叉樹(shù)`1->2->3`，輸出`[2,1,3]`。3.編寫(xiě)一個(gè)函數(shù)，實(shí)現(xiàn)最長(zhǎng)公共子序列（LCS）問(wèn)題。要求：輸入兩個(gè)字符串，輸出它們的最長(zhǎng)公共子序列。示例：輸入`str1="ABCBDAB"`,`str2="BDCAB"`，輸出`"BCAB"`。答案及解析一、選擇題答案1.D解析：算法的基本特性包括有窮性、確定性、可行性、輸入和輸出，邏輯性不是算法的基本特性。2.A解析：列表（list）在Python中可以高效實(shí)現(xiàn)棧的操作，因?yàn)槠渲С謅ppend和pop方法，符合棧的LIFO（后進(jìn)先出）特性。3.C解析：快速排序在最壞情況下（如已排序數(shù)組）的時(shí)間復(fù)雜度為O(n2)，最好和平均情況為O(nlogn)。4.C解析：遞歸算法雖然代碼簡(jiǎn)潔，但效率通常低于迭代算法，因?yàn)檫f歸需要額外的系統(tǒng)?？臻g。5.B解析：const關(guān)鍵字在C++中用于定義常量，其他選項(xiàng)不用于此目的。6.B解析：廣度優(yōu)先搜索（BFS）需要按層遍歷，隊(duì)列（queue）的FIFO（先進(jìn)先出）特性適合實(shí)現(xiàn)BFS。7.C解析：HashSet不允許重復(fù)元素，而ArrayList、LinkedList和HashMap允許。8.C解析：哈希表的主要缺點(diǎn)是沖突，即不同鍵映射到同一哈希值的情況。9.C解析：Python沒(méi)有內(nèi)置的mean()或average()函數(shù)，計(jì)算平均值通常使用`sum()/len()`。10.C解析：快速排序不屬于動(dòng)態(tài)規(guī)劃，它是基于分治策略的算法。二、填空題答案1.時(shí)間復(fù)雜度，空間復(fù)雜度解析：算法的復(fù)雜度通常用時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)衡量。2.左孩子解析：在二叉樹(shù)中，一個(gè)節(jié)點(diǎn)的左子樹(shù)的根節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的左孩子。3.O(n2)解析：冒泡排序的平均時(shí)間復(fù)雜度是O(n2)，因?yàn)樾枰啻伪闅v列表。4.static解析：static關(guān)鍵字在C++中用于聲明靜態(tài)變量，其生命周期為整個(gè)程序。5.入棧，出棧解析：棧的基本操作是入棧（push）和出棧（pop）。6.棧（stack）解析：DFS通常使用棧來(lái)實(shí)現(xiàn)，因?yàn)槠湫枰筮M(jìn)先出的特性。7.list()解析：Python中可以使用`list()`函數(shù)將字符串轉(zhuǎn)換為列表，如`list("hello")`輸出`['h','e','l','l','o']`。8.O(1)解析：哈希表在理想情況下（無(wú)沖突）的時(shí)間復(fù)雜度為O(1)。9.調(diào)用棧開(kāi)銷(xiāo)解析：遞歸算法需要多次調(diào)用系統(tǒng)棧，導(dǎo)致效率低于迭代算法。10.abstract解析：abstract關(guān)鍵字在Java中用于聲明抽象類(lèi)，抽象類(lèi)不能直接實(shí)例化。三、簡(jiǎn)答題答案1.棧和隊(duì)列的主要區(qū)別棧（Stack）是LIFO（后進(jìn)先出）結(jié)構(gòu)，只能在一端（棧頂）進(jìn)行插入和刪除操作；隊(duì)列（Queue）是FIFO（先進(jìn)先出）結(jié)構(gòu)，在一端（隊(duì)尾）插入，另一端（隊(duì)頭）刪除。2.什么是遞歸？舉例說(shuō)明遞歸的應(yīng)用遞歸是函數(shù)調(diào)用自身的過(guò)程，適用于具有自相似結(jié)構(gòu)的問(wèn)題。例如，計(jì)算階乘：`factorial(n)=nfactorial(n-1)`，基礎(chǔ)情況為`factorial(0)=1`。3.快速排序的基本步驟-選擇一個(gè)基準(zhǔn)值（pivot），通常選擇第一個(gè)或最后一個(gè)元素；-將列表分成兩部分，一部分小于基準(zhǔn)值，另一部分大于基準(zhǔn)值；-遞歸對(duì)兩部分進(jìn)行快速排序；-合并結(jié)果。4.哈希表的工作原理及沖突解決方法哈希表通過(guò)哈希函數(shù)將鍵映射到數(shù)組索引，實(shí)現(xiàn)快速查找。沖突解決方法包括：-鏈地址法：將沖突的鍵存儲(chǔ)在鏈表中；-開(kāi)放地址法：線(xiàn)性探測(cè)或二次探測(cè)尋找下一個(gè)空槽。5.什么是動(dòng)態(tài)規(guī)劃？舉例說(shuō)明應(yīng)用場(chǎng)景動(dòng)態(tài)規(guī)劃通過(guò)將問(wèn)題分解為子問(wèn)題并存儲(chǔ)結(jié)果（備忘錄）來(lái)避免重復(fù)計(jì)算。應(yīng)用場(chǎng)景包括：-最長(zhǎng)公共子序列（LCS）；-背包問(wèn)題；-最短路徑問(wèn)題（如Floyd-Warshall算法）。四、編程題答案1.冒泡排序函數(shù)（Python）pythondefbubble_sort(arr):n=len(arr)foriinrange(n):forjinrange(0,n-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]returnarr2.二叉樹(shù)DFS（中序遍歷）（Python）pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinorder_dfs(root):ifnotroot:return[]returninorder_dfs(root.left)+[root.val]+inorder_dfs(root.right)3.最長(zhǎng)公共子序列（LCS）（Python）pythondeflcs(str1,str2):m,n=len(str1),len(str2)dp=[[""](n+1)for_inrange(m+1)]foriinrange