2026年計(jì)算機(jī)編程與算法基礎(chǔ)考試題一、選擇題（共10題，每題2分，總計(jì)20分）說明：下列每題只有一個(gè)正確答案。1.在Python中，用于定義類的方法必須包含的關(guān)鍵字是？A.functionB.defC.methodD.class2.以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)最適合實(shí)現(xiàn)先進(jìn)先出（FIFO）的操作？A.棧（Stack）B.隊(duì)列（Queue）C.鏈表（LinkedList）D.樹（Tree）3.快速排序的平均時(shí)間復(fù)雜度是？A.O(n2)B.O(nlogn)C.O(n)D.O(logn)4.在C++中，`#include<iostream>`的作用是？A.包含標(biāo)準(zhǔn)輸入輸出庫(kù)B.定義一個(gè)類C.聲明一個(gè)函數(shù)D.包含自定義頭文件5.以下哪個(gè)不是算法的時(shí)間復(fù)雜度表示方法？A.大O表示法（BigONotation）B.大Ω表示法（BigOmegaNotation）C.大Θ表示法（BigThetaNotation）D.小p表示法（LittlepNotation）6.在JavaScript中，用于聲明常量的關(guān)鍵字是？A.varB.letC.constD.static7.以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)是遞歸算法的核心支持？A.數(shù)組（Array）B.哈希表（HashTable）C.棧（Stack）D.隊(duì)列（Queue）8.在Java中，`publicstaticvoidmain(String[]args)`的作用是？A.定義一個(gè)類B.主方法，程序入口C.聲明一個(gè)變量D.方法重載9.哈希表的主要優(yōu)點(diǎn)是？A.穩(wěn)定的排序性能B.高效的插入和刪除操作C.線性查找效率D.支持快速范圍查詢10.在HTML中，用于創(chuàng)建超鏈接的標(biāo)簽是？A.<img>B.<a>C.<span>D.<div>二、填空題（共5題，每題2分，總計(jì)10分）說明：請(qǐng)將正確答案填寫在橫線上。1.在Python中，用于表示列表（List）的關(guān)鍵字是________。（答案：`[]`）2.冒泡排序在最好情況下的時(shí)間復(fù)雜度是________。（答案：O(n)）3.在C++中，用于動(dòng)態(tài)分配內(nèi)存的運(yùn)算符是________。（答案：`new`）4.在JavaScript中，用于檢查一個(gè)變量是否為空值（undefined）的關(guān)鍵字是________。（答案：`typeof`）5.在SQL中，用于刪除表中數(shù)據(jù)的語句是________。（答案：`DELETE`）三、簡(jiǎn)答題（共5題，每題4分，總計(jì)20分）說明：請(qǐng)簡(jiǎn)要回答下列問題。1.簡(jiǎn)述棧（Stack）的基本操作及其應(yīng)用場(chǎng)景。答案：棧的基本操作包括：-push（入棧）：將元素添加到棧頂。-pop（出棧）：移除并返回棧頂元素。-peek/top（查看棧頂）：返回棧頂元素但不移除。-isEmpty（判空）：檢查棧是否為空。應(yīng)用場(chǎng)景：-函數(shù)調(diào)用棧（管理遞歸調(diào)用）。-表達(dá)式求值（中綴轉(zhuǎn)后綴）。-撤銷操作（如編輯器的Undo功能）。2.解釋什么是遞歸算法，并舉例說明其優(yōu)缺點(diǎn)。答案：遞歸算法是指函數(shù)調(diào)用自身來解決問題。優(yōu)點(diǎn)：-代碼簡(jiǎn)潔，易于理解（如樹的遍歷）。-適合解決分治問題（如快速排序）。缺點(diǎn)：-可能導(dǎo)致棧溢出（遞歸深度過大）。-效率可能低于迭代解法（有重復(fù)計(jì)算）。例子：計(jì)算階乘`factorial(n)=nfactorial(n-1)`。3.描述哈希表（HashTable）的工作原理及其常見沖突解決方法。答案：工作原理：通過哈希函數(shù)將鍵（Key）映射到數(shù)組索引，實(shí)現(xiàn)O(1)平均查找時(shí)間。沖突解決方法：-鏈地址法：同一索引的鍵存儲(chǔ)在鏈表中。-開放地址法：線性探測(cè)或二次探測(cè)尋找下一個(gè)空閑槽位。4.解釋什么是時(shí)間復(fù)雜度，并說明O(n2)和O(logn)分別適用于什么場(chǎng)景。答案：時(shí)間復(fù)雜度表示算法執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)的變化趨勢(shì)。-O(n2)：適用于小規(guī)模數(shù)據(jù)（如排序n個(gè)數(shù)字的直接插入排序）。-O(logn)：適用于大規(guī)模數(shù)據(jù)（如二分查找）。5.列舉三種常見的算法設(shè)計(jì)策略。答案：-分治法：將問題分解為子問題（如歸并排序）。-動(dòng)態(tài)規(guī)劃：存儲(chǔ)子問題解避免重復(fù)計(jì)算（如斐波那契數(shù)列）。-貪心法：每步選擇當(dāng)前最優(yōu)解（如最小生成樹）。四、編程題（共3題，每題10分，總計(jì)30分）說明：請(qǐng)根據(jù)要求完成代碼編寫。1.Python編程：編寫一個(gè)函數(shù)，接收一個(gè)列表（List）并返回其中所有偶數(shù)的平方，結(jié)果按升序排列。示例輸入：`[1,2,3,4,5,6]`示例輸出：`[4,16,36]`答案：pythondefeven_squares(nums):returnsorted([x2forxinnumsifx%2==0])測(cè)試print(even_squares([1,2,3,4,5,6]))#輸出:[4,16,36]2.C++編程：編寫一個(gè)函數(shù)，接收一個(gè)字符串并統(tǒng)計(jì)其中每個(gè)字母的出現(xiàn)次數(shù)（忽略大小寫），返回一個(gè)哈希表（`unordered_map<char,int>`）。示例輸入：`"HelloWorld"`示例輸出：`{h:1,e:1,l:3,o:2,w:1,r:1,d:1}`答案：cppinclude<unordered_map>include<cctype>std::unordered_map<char,int>count_letters(conststd::string&s){std::unordered_map<char,int>freq;for(charc:s){if(isalpha(c)){freq[tolower(c)]++;}}returnfreq;}//測(cè)試include<iostream>intmain(){autoresult=count_letters("HelloWorld");for(constauto&[k,v]:result){std::cout<<k<<":"<<v<<"";}return0;}3.Java編程：編寫一個(gè)方法，實(shí)現(xiàn)二分查找算法，輸入一個(gè)有序數(shù)組和一個(gè)目標(biāo)值，返回目標(biāo)值的索引（若不存在則返回-1）。示例輸入：`arr={1,2,4,6,8,10}`,`target=6`示例輸出：`3`答案：javapublicclassBinarySearch{publicstaticintbinarySearch(int[]arr,inttarget){intleft=0,right=arr.length-1;while(left<=right){intmid=left+(right-left)/2;if(arr[mid]==target)returnmid;elseif(arr[mid]<target)left=mid+1;elseright=mid-1;}return-1;}publicstaticvoidmain(String[]args){int[]arr={1,2,4,6,8,10};System.out.println(binarySearch(arr,6));//輸出:3}}五、算法設(shè)計(jì)題（共2題，每題15分，總計(jì)30分）說明：請(qǐng)?jiān)O(shè)計(jì)算法并說明其復(fù)雜度。1.問題描述：給定一個(gè)包含重復(fù)數(shù)字的數(shù)組，編寫算法找出所有不重復(fù)的三元組，使得三元組內(nèi)數(shù)字之和為0。示例輸入：`[-1,0,1,2,-1,-4]`示例輸出：`[[-1,-1,2],[-1,0,1]]`答案：算法步驟：1.排序數(shù)組（O(nlogn)）。2.固定一個(gè)數(shù)，使用雙指針（O(n2)）查找其他兩個(gè)數(shù)：-遍歷數(shù)組，對(duì)于每個(gè)`nums[i]`，設(shè)置`left=i+1`和`right=n-1`。-如果`nums[i]+nums[left]+nums[right]==0`，記錄三元組并移動(dòng)指針。-若和小于0，`left++`；若和大于0，`right--`。3.去重避免重復(fù)解。時(shí)間復(fù)雜度：O(n2)。2.問題描述：設(shè)計(jì)一個(gè)算法，統(tǒng)計(jì)一個(gè)字符串中所有子字符串的出現(xiàn)次數(shù)（不區(qū)分大小寫）。示例輸入：`"abba"`示例輸出：`{"a":4,"ab":2,"abb":2,"abba":1,"b":4,"bb":2,"bba":2,"ba":2,"b":4}`答案：算法步驟：1.將字符串轉(zhuǎn)為小寫（忽略大小寫）。2.使用哈希表記錄所有子字符串的出現(xiàn)次數(shù)：-外層循環(huán)固定起始位置`i`，內(nèi)層循環(huán)擴(kuò)展子字符串`s[i..j]`。-每次擴(kuò)展后更新哈希表。3.去重鍵名（如"ab"和"Ab"視為相同）。時(shí)間復(fù)雜度：O(n2)，n為字符串長(zhǎng)度。答案與解析：一、選擇題答案與解析1.B解析：Python中定義方法使用`def`，其他選項(xiàng)錯(cuò)誤。2.B解析：隊(duì)列（Queue）是先進(jìn)先出，棧是后進(jìn)先出。3.B解析：快速排序平均時(shí)間復(fù)雜度為O(nlogn)，但最壞為O(n2)。4.A解析：`#include<iostream>`包含C++標(biāo)準(zhǔn)輸入輸出流庫(kù)。5.D解析：不存在小p表示法，其他均為算法復(fù)雜度表示。6.C解析：`const`聲明不可變變量，`let`聲明可變變量。7.C解析：棧支持后進(jìn)先出，適合遞歸調(diào)用棧管理。8.B解析：`main`方法是Java程序的入口點(diǎn)。9.B解析：哈希表通過哈希函數(shù)實(shí)現(xiàn)快速插入和刪除。10.B解析：`<a>`標(biāo)簽用于創(chuàng)建超鏈接。二、填空題答案與解析1.`[]`解析：Python列表用方括號(hào)定義，如`[1,2,3]`。2.O(n)解析：冒泡排序在已排序時(shí)只需遍歷一次。3.`new`解析：C++使用`new`動(dòng)態(tài)分配內(nèi)存，如`intptr=newint(10);`。4.`typeof`解析：JavaScript用`typeofundefined`檢查空值。5.`DELETE`解析：SQL中`DELETEFROMtableWHEREcondition;`刪除數(shù)據(jù)。三、簡(jiǎn)答題答案與解析1.棧的基本操作與應(yīng)用場(chǎng)景解析：棧操作包括入棧、出棧等，應(yīng)用廣泛如函數(shù)調(diào)用、表達(dá)式求值。2.遞歸算法的定義與優(yōu)缺點(diǎn)解析：遞歸通過自調(diào)用解決問題，優(yōu)點(diǎn)是簡(jiǎn)潔，缺點(diǎn)是棧溢出風(fēng)險(xiǎn)。3.哈希表原理與沖突解決解析：哈希表通過哈希函數(shù)映射鍵到索引，沖突解決方法有鏈地址法等。4.時(shí)間復(fù)雜度及其適用場(chǎng)景解析：時(shí)間復(fù)雜度描述算法效率，O(n2)適合小數(shù)據(jù)，O(logn)適合大數(shù)據(jù)。5.算法設(shè)計(jì)策略解析：分治、動(dòng)態(tài)規(guī)劃、貪心是常見策略，適用于不同問題類型。四、編程題答案與解析1.P