大學(xué)（計(jì)算機(jī)科學(xué)與技術(shù)）算法設(shè)計(jì)2026年階段測(cè)試題及答案

（考試時(shí)間：90分鐘滿(mǎn)分100分）班級(jí)______姓名______一、選擇題（總共10題，每題3分，每題只有一個(gè)正確答案，請(qǐng)將正確答案填入括號(hào)內(nèi)）1.以下哪種算法設(shè)計(jì)策略通常用于解決具有最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題？（）A.分治法B.動(dòng)態(tài)規(guī)劃法C.貪心算法D.回溯法2.對(duì)于一個(gè)無(wú)向連通圖，其最小生成樹(shù)的邊數(shù)為（）。A.n-1B.nC.n+1D.2n-13.在深度優(yōu)先搜索中，優(yōu)先擴(kuò)展（）。A.離起始節(jié)點(diǎn)最近的節(jié)點(diǎn)B.離起始節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)C.最新產(chǎn)生的節(jié)點(diǎn)D.最早產(chǎn)生的節(jié)點(diǎn)4.以下哪個(gè)算法不是基于比較的排序算法？（）A.快速排序B.冒泡排序C.歸并排序D.基數(shù)排序5.對(duì)于一個(gè)有n個(gè)頂點(diǎn)的完全二叉樹(shù)，其葉子節(jié)點(diǎn)的個(gè)數(shù)為（）。A.?n/2?B.?n/2?C.n-?n/2?D.n-?n/2?6.動(dòng)態(tài)規(guī)劃算法的基本思想是（）。A.自頂向下，分而治之B.自底向上，逐步求解C.自頂向下，逐步求解D.自底向上，分而治之7.以下哪種數(shù)據(jù)結(jié)構(gòu)適合實(shí)現(xiàn)廣度優(yōu)先搜索？（）A.棧B.隊(duì)列C.二叉樹(shù)D.圖8.對(duì)于一個(gè)有n個(gè)頂點(diǎn)的圖，其鄰接矩陣的大小為（）。A.n×nB.(n-1)×(n-1)C.n×(n-1)D.(n-1)×n9.以下哪個(gè)算法常用于求解最短路徑問(wèn)題？（）A.迪杰斯特拉算法B.普里姆算法C.克魯斯卡爾算法D.弗洛伊德算法10.回溯法通常用于解決（）問(wèn)題。A.最優(yōu)化B.搜索C.排序D.圖的遍歷二、多項(xiàng)選擇題（總共5題，每題4分，每題有多個(gè)正確答案，請(qǐng)將正確答案填入括號(hào)內(nèi)，少選、多選均不得分）1.以下哪些算法屬于貪心算法？（）A.迪杰斯特拉算法B.普里姆算法C.克魯斯卡爾算法D.快速排序2.動(dòng)態(tài)規(guī)劃算法的優(yōu)點(diǎn)包括（）。A.避免重復(fù)計(jì)算B.時(shí)間復(fù)雜度低C.空間復(fù)雜度低D.適用于各種問(wèn)題3.以下哪些數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)圖的存儲(chǔ)？（）A.鄰接矩陣B.鄰接表C.棧D.Queue4.對(duì)于一個(gè)有n個(gè)頂點(diǎn)的圖，其深度優(yōu)先搜索的時(shí)間復(fù)雜度為（）。A.O(n)B.O(n^2)C.O(n+e)D.O(e)，其中e為邊的數(shù)量5.以下哪些算法可以用于求解背包問(wèn)題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃算法C.回溯法D.分治法三、判斷題（總共10題，每題2分，請(qǐng)判斷對(duì)錯(cuò)，在括號(hào)內(nèi)打“√”或“×”）1.分治法一定比蠻力法更高效。（）2.動(dòng)態(tài)規(guī)劃算法的空間復(fù)雜度一定比遞歸算法低。（）3.貪心算法總能找到最優(yōu)解。（）4.深度優(yōu)先搜索和廣度優(yōu)先搜索的時(shí)間復(fù)雜度相同。（）5.排序算法的時(shí)間復(fù)雜度一定是O(n^2)。（）6.回溯法可以用于求解所有問(wèn)題。（）7.對(duì)于一個(gè)無(wú)向圖，其鄰接矩陣一定是對(duì)稱(chēng)的。（）8.最小生成樹(shù)的權(quán)值是唯一的。（）9.迪杰斯特拉算法可以用于求解帶負(fù)權(quán)邊圖的最短路徑問(wèn)題。（）10.動(dòng)態(tài)規(guī)劃算法的核心是保存子問(wèn)題的解。（）四、簡(jiǎn)答題（總共3題，每題10分，請(qǐng)簡(jiǎn)要回答以下問(wèn)題）1.請(qǐng)簡(jiǎn)述動(dòng)態(tài)規(guī)劃算法的基本步驟，并舉例說(shuō)明。2.什么是貪心算法？貪心算法的基本要素有哪些？請(qǐng)舉例說(shuō)明。3.簡(jiǎn)述深度優(yōu)先搜索和廣度優(yōu)先搜索的區(qū)別，并說(shuō)明它們各自的適用場(chǎng)景。五、算法設(shè)計(jì)題（總共2題，每題15分，請(qǐng)?jiān)O(shè)計(jì)算法解決以下問(wèn)題）1.給定一個(gè)整數(shù)數(shù)組，設(shè)計(jì)一個(gè)算法找出其中的最大子數(shù)組和。例如，對(duì)于數(shù)組[-2,1,-3,4,-1,2,1,-5,4]，最大子數(shù)組和為6（子數(shù)組[4,-1,2,1]）。2.有n個(gè)物品，每個(gè)物品有重量wi和價(jià)值vi，背包容量為C。設(shè)計(jì)一個(gè)算法找出能裝入背包的最大價(jià)值物品組合。答案：選擇題答案：1.B2.A3.C4.D5.A6.B7.B8.A9.A10.B多項(xiàng)選擇題答案：1.ABC2.AB3.AB4.C5.AB判斷題答案：1.×2.×3.×4.√5.×6.×7.√8.√9.×10.√簡(jiǎn)答題答案：1.動(dòng)態(tài)規(guī)劃基本步驟：分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)；建立遞歸關(guān)系；自底向上計(jì)算最優(yōu)值；構(gòu)造最優(yōu)解。例如最長(zhǎng)公共子序列問(wèn)題。2.貪心算法是通過(guò)局部最優(yōu)解來(lái)構(gòu)造全局最優(yōu)解的算法?；疽兀鹤顑?yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)。如活動(dòng)安排問(wèn)題。3.深度優(yōu)先搜索優(yōu)先擴(kuò)展最新產(chǎn)生的節(jié)點(diǎn)，適用于深度較大的問(wèn)題；廣度優(yōu)先搜索優(yōu)先擴(kuò)展離起始節(jié)點(diǎn)最近的節(jié)點(diǎn)，適用于求最短路徑等問(wèn)題。算法設(shè)計(jì)題答案：1.可以使用動(dòng)態(tài)規(guī)劃算法，定義dp[i]表示以第i個(gè)元素結(jié)尾的最大子數(shù)組和，狀態(tài)轉(zhuǎn)移方程為dp[i]=max(dp[i-1]+nums[i],nums[i])，最終結(jié)果為dp數(shù)組中的最大值。2.可以使用動(dòng)態(tài)規(guī)劃算法