編程算法筆試題庫及答案

單項(xiàng)選擇題（每題2分，共10題）1.以下哪種算法常用于排序？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.快速排序D.回溯算法答案：C2.關(guān)于遞歸算法，以下說法正確的是？A.不會出現(xiàn)棧溢出B.效率很高C.代碼簡潔D.必須有終止條件答案：D3.以下哪個是動態(tài)規(guī)劃的特點(diǎn)？A.自頂向下B.重復(fù)子問題C.貪心選擇D.無后效性答案：B4.哪種算法適合解決最短路徑問題？A.迪杰斯特拉算法B.克魯斯卡爾算法C.哈夫曼算法D.拓?fù)渑判蛩惴ù鸢福篈5.以下算法中時間復(fù)雜度為O(n^2)的是？A.冒泡排序B.快速排序C.歸并排序D.堆排序答案：A6.深度優(yōu)先搜索優(yōu)先訪問？A.離起始點(diǎn)近的節(jié)點(diǎn)B.離起始點(diǎn)遠(yuǎn)的節(jié)點(diǎn)C.新發(fā)現(xiàn)的節(jié)點(diǎn)D.已訪問過的節(jié)點(diǎn)答案：C7.以下哪個算法可用于求最大公約數(shù)？A.歐幾里得算法B.輾轉(zhuǎn)相除法C.以上都是D.以上都不是答案：C8.哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)隊(duì)列？A.數(shù)組B.鏈表C.棧D.哈希表答案：B9.以下算法中屬于貪心算法的是？A.背包問題B.0-1背包問題C.活動安排問題D.最長公共子序列問題答案：C10.廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)通常是？A.棧B.隊(duì)列C.優(yōu)先隊(duì)列D.哈希表答案：B多項(xiàng)選擇題（每題2分，共10題）1.以下屬于分治算法的有？A.快速排序B.歸并排序C.二分查找D.拓?fù)渑判虼鸢福篈BC2.動態(tài)規(guī)劃可解決的問題有？A.最長公共子序列B.背包問題C.矩陣鏈乘法D.最短路徑答案：ABC3.以下哪些算法涉及圖的操作？A.迪杰斯特拉算法B.克魯斯卡爾算法C.拓?fù)渑判蛩惴―.深度優(yōu)先搜索答案：ABCD4.貪心算法適用于？A.活動安排問題B.部分背包問題C.哈夫曼編碼D.最長遞增子序列答案：ABC5.以下數(shù)據(jù)結(jié)構(gòu)可用于實(shí)現(xiàn)棧的有？A.數(shù)組B.鏈表C.哈希表D.隊(duì)列答案：AB6.遞歸算法的優(yōu)點(diǎn)有？A.代碼簡潔B.易于理解C.效率高D.適合復(fù)雜問題答案：AB7.以下算法時間復(fù)雜度為O(n)的有？A.線性查找B.冒泡排序C.快速排序平均情況D.歸并排序答案：A8.可用于字符串匹配的算法有？A.暴力匹配B.KMP算法C.哈希表匹配D.深度優(yōu)先搜索答案：ABC9.以下屬于貪心選擇性質(zhì)的是？A.局部最優(yōu)解B.全局最優(yōu)解C.子問題獨(dú)立性D.重復(fù)子問題答案：AB10.深度優(yōu)先搜索和廣度優(yōu)先搜索的區(qū)別在于？A.訪問節(jié)點(diǎn)順序B.使用數(shù)據(jù)結(jié)構(gòu)C.時間復(fù)雜度D.空間復(fù)雜度答案：AB判斷題（每題皮2分，共10題）1.快速排序平均時間復(fù)雜度為O(n^2)。（×）2.動態(tài)規(guī)劃一定比貪心算法效率高。（×）3.遞歸算法一定會導(dǎo)致棧溢出。（×）4.迪杰斯特拉算法可用于有負(fù)權(quán)邊的圖。（×）5.廣度優(yōu)先搜索總能找到最短路徑。（×）6.貪心算法總能得到全局最優(yōu)解。（×）7.棧是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。（×）8.深度優(yōu)先搜索是一種盲目搜索。（√）9.分治算法將問題分解為子問題求解。（√）10.拓?fù)渑判蛩惴捎糜谟邢驘o環(huán)圖。（√）簡答題（總4題，每題5分）1.簡述快速排序基本思想。答案：選擇一個基準(zhǔn)值，將數(shù)組分為兩部分，小于基準(zhǔn)值的放左邊，大于的放右邊，遞歸對兩部分排序。2.動態(tài)規(guī)劃和貪心算法的區(qū)別。答案：動態(tài)規(guī)劃考慮所有子問題，貪心算法只考慮局部最優(yōu)。動態(tài)規(guī)劃有重疊子問題，貪心算法有貪心選擇性質(zhì)。3.簡述迪杰斯特拉算法步驟。答案：初始化距離數(shù)組，每次選擇距離最小節(jié)點(diǎn)更新其鄰接節(jié)點(diǎn)距離，重復(fù)直到所有節(jié)點(diǎn)距離確定。4.簡述深度優(yōu)先搜索過程。答案：從起始節(jié)點(diǎn)開始，優(yōu)先訪問新發(fā)現(xiàn)節(jié)點(diǎn)，若訪問完相鄰節(jié)點(diǎn)還有未訪問節(jié)點(diǎn)則繼續(xù)，直到所有節(jié)點(diǎn)訪問或無法訪問。討論題（總4題，每題5分）1.比較遞歸和迭代算法優(yōu)缺點(diǎn)。答案：遞歸代碼簡潔易理解，但可能棧溢出；迭代效率高，無棧溢出問題，但代碼稍復(fù)雜。2.貪心算法在什么情況下不適用。答案：當(dāng)問題不滿足貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)時不適用，如0-1背包問題。3.如何