2026年程序設(shè)計(jì)競(jìng)賽經(jīng)典試題集一、單項(xiàng)選擇題（每題2分，共10題）注意：下列每題只有一個(gè)正確選項(xiàng)。1.數(shù)據(jù)結(jié)構(gòu)在有序數(shù)組中查找一個(gè)不存在的元素時(shí)，采用二分查找算法的時(shí)間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(nlogn)2.算法設(shè)計(jì)以下哪種排序算法在最壞情況下具有線性時(shí)間復(fù)雜度？A.快速排序B.歸并排序C.堆排序D.冒泡排序3.操作系統(tǒng)在多道程序系統(tǒng)中，操作系統(tǒng)通過(guò)什么機(jī)制實(shí)現(xiàn)進(jìn)程的調(diào)度？A.中斷B.分時(shí)系統(tǒng)C.虛擬內(nèi)存D.緩沖區(qū)4.計(jì)算機(jī)網(wǎng)絡(luò)以下哪種協(xié)議用于電子郵件的傳輸？A.HTTPB.FTPC.SMTPD.TCP5.數(shù)據(jù)庫(kù)SQL語(yǔ)句中，用于刪除表中數(shù)據(jù)的命令是？A.DELETEB.REMOVEC.DROPD.ERASE二、填空題（每空1分，共10空）1.在深度優(yōu)先搜索（DFS）中，用于存儲(chǔ)已訪問(wèn)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)通常是__________。2.快速排序算法的核心思想是__________。3.操作系統(tǒng)中的“死鎖”是指多個(gè)進(jìn)程因爭(zhēng)奪資源而陷入__________的狀態(tài)。4.TCP協(xié)議是一種__________連接的協(xié)議。5.SQL中，用于查詢數(shù)據(jù)的命令是__________。6.在二叉樹(shù)中，一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量稱為該節(jié)點(diǎn)的__________。7.堆排序算法的時(shí)間復(fù)雜度是__________。8.在網(wǎng)絡(luò)通信中，IP地址用于__________。9.數(shù)據(jù)庫(kù)中的“事務(wù)”是指一組可以__________執(zhí)行的數(shù)據(jù)庫(kù)操作。10.在算法分析中，大O表示法用于描述算法的__________。三、簡(jiǎn)答題（每題5分，共5題）1.簡(jiǎn)述快速排序算法的步驟。2.解釋什么是“虛擬內(nèi)存”及其作用。3.描述TCP協(xié)議的三次握手過(guò)程。4.說(shuō)明數(shù)據(jù)庫(kù)事務(wù)的ACID特性。5.解釋什么是“二叉搜索樹(shù)”及其主要性質(zhì)。四、編程題（每題15分，共2題）1.問(wèn)題描述編寫(xiě)一個(gè)函數(shù)，實(shí)現(xiàn)將一個(gè)字符串中的所有空格替換為下劃線。輸入輸出示例：輸入：`"HelloWorld"`輸出：`"Hello_World"`2.問(wèn)題描述實(shí)現(xiàn)一個(gè)簡(jiǎn)單的LRU（最近最少使用）緩存，支持以下操作：-`put(key,value)`：將鍵值對(duì)插入緩存。-`get(key)`：返回鍵對(duì)應(yīng)的值，若不存在則返回-1。緩存容量固定為3，超出時(shí)需淘汰最久未使用的元素。答案與解析一、單項(xiàng)選擇題答案1.B二分查找的時(shí)間復(fù)雜度為O(logn)，即使元素不存在，算法仍需遍歷logn次。2.D冒泡排序在最壞情況下（逆序數(shù)組）的時(shí)間復(fù)雜度為O(n2)，但其他選項(xiàng)均不是線性時(shí)間。3.A中斷是操作系統(tǒng)實(shí)現(xiàn)進(jìn)程調(diào)度的基本機(jī)制，其他選項(xiàng)與調(diào)度無(wú)關(guān)。4.CSMTP（SimpleMailTransferProtocol）是電子郵件傳輸?shù)臉?biāo)準(zhǔn)協(xié)議。5.ASQL中刪除數(shù)據(jù)的命令是`DELETE`，其他選項(xiàng)非標(biāo)準(zhǔn)命令。二、填空題答案1.隊(duì)列（或棧，取決于DFS實(shí)現(xiàn)方式）2.分治法3.死鎖4.全雙工5.`SELECT`6.度7.O(nlogn)8.定位網(wǎng)絡(luò)設(shè)備9.原子性10.時(shí)間復(fù)雜度三、簡(jiǎn)答題解析1.快速排序步驟-選擇一個(gè)基準(zhǔn)值（pivot），通常為第一個(gè)或最后一個(gè)元素。-將數(shù)組劃分為兩部分：小于基準(zhǔn)值的元素和大于基準(zhǔn)值的元素。-遞歸對(duì)兩部分進(jìn)行快速排序。-時(shí)間復(fù)雜度：平均O(nlogn)，最壞O(n2)。2.虛擬內(nèi)存虛擬內(nèi)存是操作系統(tǒng)提供的一種內(nèi)存管理技術(shù)，將物理內(nèi)存和硬盤(pán)空間結(jié)合，使程序認(rèn)為擁有連續(xù)的內(nèi)存空間。作用：-解決物理內(nèi)存不足問(wèn)題。-隔離進(jìn)程內(nèi)存，提高安全性。3.TCP三次握手-客戶端發(fā)送SYN包（seq=x）給服務(wù)器。-服務(wù)器回復(fù)SYN+ACK包（seq=y，ack=x+1）。-客戶端發(fā)送ACK包（ack=y+1）完成連接。4.數(shù)據(jù)庫(kù)事務(wù)ACID特性-原子性（Atomicity）：事務(wù)不可分割。-一致性（Consistency）：事務(wù)需保證數(shù)據(jù)庫(kù)狀態(tài)合法。-隔離性（Isolation）：并發(fā)事務(wù)互不干擾。-持久性（Durability）：事務(wù)提交后結(jié)果永久保存。5.二叉搜索樹(shù)-左子樹(shù)所有節(jié)點(diǎn)值小于根節(jié)點(diǎn)值。-右子樹(shù)所有節(jié)點(diǎn)值大于根節(jié)點(diǎn)值。-每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。-具有遞歸性質(zhì)，便于查找、插入、刪除操作。四、編程題解析1.字符串替換代碼示例（Python）pythondefreplace_spaces(s:str)->str:returns.replace("","_")2.LRU緩存實(shí)現(xiàn)（Python）pythonfromcollectionsimportOrderedDictclassLRUCache:def__init__(self,capacity:int):self.cache=OrderedDict()self.capacity=capacitydefget(self,key:int)->int:ifkeynotinself.cache:return-1self.cache.move_to_end(key)returnself.cache[key]defput(self,key:int,value:int)->None:self.cache[key]=valueself.c