經(jīng)典算法題目及答案

單項(xiàng)選擇題（每題2分，共10題）1.以下哪種排序算法平均時(shí)間復(fù)雜度為O(nlogn)？A.冒泡排序B.選擇排序C.歸并排序D.插入排序2.深度優(yōu)先搜索算法常借助什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)？A.隊(duì)列B.棧C.數(shù)組D.鏈表3.計(jì)算斐波那契數(shù)列第n項(xiàng)的遞歸算法時(shí)間復(fù)雜度約為？A.O(n)B.O(2^n)C.O(n^2)D.O(logn)4.二分查找適用于？A.無序數(shù)組B.有序數(shù)組C.鏈表D.哈希表5.以下哪個(gè)不是貪心算法的特點(diǎn)？A.局部最優(yōu)B.全局最優(yōu)C.不回溯D.快速求解6.廣度優(yōu)先搜索算法借助的數(shù)據(jù)結(jié)構(gòu)是？A.棧B.隊(duì)列C.堆D.樹7.快速排序的平均時(shí)間復(fù)雜度是？A.O(n^2)B.O(nlogn)C.O(logn)D.O(n)8.哈希表查找的平均時(shí)間復(fù)雜度接近？A.O(n)B.O(n^2)C.O(1)D.O(logn)9.堆排序基于什么數(shù)據(jù)結(jié)構(gòu)？A.二叉堆B.二叉樹C.圖D.鏈表10.動(dòng)態(tài)規(guī)劃算法的核心思想是？A.分治B.貪心C.最優(yōu)子結(jié)構(gòu)D.遞歸多項(xiàng)選擇題（每題2分，共10題）1.以下屬于排序算法的有？A.冒泡排序B.快速排序C.拓?fù)渑判駾.堆排序2.常用于圖算法的有？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.迪杰斯特拉算法D.弗洛伊德算法3.動(dòng)態(tài)規(guī)劃算法適用的問題特征有？A.最優(yōu)子結(jié)構(gòu)B.重疊子問題C.貪心選擇性質(zhì)D.無后效性4.以下哪些算法時(shí)間復(fù)雜度為多項(xiàng)式時(shí)間？A.冒泡排序B.快速排序C.指數(shù)搜索算法D.哈希表查找5.貪心算法可解決的問題有？A.活動(dòng)安排問題B.背包問題C.哈夫曼編碼D.旅行商問題6.關(guān)于搜索算法，正確的是？A.深度優(yōu)先搜索適合找深度解B.廣度優(yōu)先搜索適合找廣度解C.深度優(yōu)先搜索用棧實(shí)現(xiàn)D.廣度優(yōu)先搜索用隊(duì)列實(shí)現(xiàn)7.排序算法穩(wěn)定性的描述正確的是？A.冒泡排序是穩(wěn)定的B.選擇排序是穩(wěn)定的C.歸并排序是穩(wěn)定的D.快速排序是穩(wěn)定的8.屬于圖的遍歷算法有？A.深度優(yōu)先遍歷B.廣度優(yōu)先遍歷C.拓?fù)渑判虮闅vD.關(guān)鍵路徑遍歷9.哈希表的沖突解決方法有？A.開放定址法B.鏈地址法C.再哈希法D.建立公共溢出區(qū)10.以下哪些屬于分治算法？A.歸并排序B.快速排序C.二分查找D.動(dòng)態(tài)規(guī)劃判斷題（每題2分，共10題）1.冒泡排序是穩(wěn)定的排序算法。（）2.深度優(yōu)先搜索和廣度優(yōu)先搜索可以用于樹的遍歷。（）3.貪心算法一定能得到全局最優(yōu)解。（）4.動(dòng)態(tài)規(guī)劃算法通常用遞歸方式實(shí)現(xiàn)效率更高。（）5.快速排序的最壞時(shí)間復(fù)雜度是O(n^2)。（）6.哈希表查找效率一定比順序查找高。（）7.拓?fù)渑判蜻m用于有向無環(huán)圖。（）8.堆排序是不穩(wěn)定的排序算法。（）9.計(jì)算斐波那契數(shù)列使用迭代法比遞歸法效率高。（）10.迪杰斯特拉算法用于求解無向圖的最短路徑。（）簡答題（每題5分，共4題）1.簡述歸并排序的基本思想。答案：將一個(gè)數(shù)組分成兩個(gè)子數(shù)組，對(duì)兩個(gè)子數(shù)組分別進(jìn)行排序，然后將排序好的子數(shù)組合并成一個(gè)有序的數(shù)組，不斷遞歸此過程直至整個(gè)數(shù)組有序。2.簡述二分查找的條件及基本步驟。答案：條件是數(shù)組有序?；静襟E：取數(shù)組中間元素與目標(biāo)值比較，若相等則找到；若目標(biāo)值小于中間元素，在左半部分繼續(xù)查找；若大于，則在右半部分繼續(xù)查找，不斷縮小查找范圍。3.簡述貪心算法的基本要素。答案：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心選擇性質(zhì)是指通過局部最優(yōu)選擇能產(chǎn)生全局最優(yōu)解；最優(yōu)子結(jié)構(gòu)性質(zhì)指問題的最優(yōu)解包含子問題的最優(yōu)解。4.簡述哈希表的基本原理。答案：通過哈希函數(shù)將關(guān)鍵字映射到一個(gè)有限的地址空間中，形成哈希表。當(dāng)需要查找時(shí)，再通過哈希函數(shù)計(jì)算關(guān)鍵字對(duì)應(yīng)的地址來快速定位數(shù)據(jù)，若發(fā)生沖突則采用特定方法解決。討論題（每題5分，共4題）1.比較快速排序和歸并排序的優(yōu)缺點(diǎn)。答案：快速排序優(yōu)點(diǎn)是平均效率高，不需要額外太多空間；缺點(diǎn)是最壞情況時(shí)間復(fù)雜度高，且不穩(wěn)定。歸并排序優(yōu)點(diǎn)是穩(wěn)定，時(shí)間復(fù)雜度穩(wěn)定為O(nlogn)；缺點(diǎn)是需要額外空間輔助合并操作。2.在實(shí)際應(yīng)用中，如何選擇合適的排序算法？答案：若數(shù)據(jù)量小且對(duì)穩(wěn)定性有要求，可選擇冒泡排序等；數(shù)據(jù)量較大且要求平均性能好，快速排序合適；若要穩(wěn)定排序且數(shù)據(jù)量大，歸并排序較好；若對(duì)空間要求高，堆排序可考慮。3.談?wù)剟?dòng)態(tài)規(guī)劃算法和分治算法的異同。答案：相同點(diǎn)是都將問題分解為子問題求解。不同點(diǎn)在于動(dòng)態(tài)規(guī)劃解決有重疊子問題的情況，會(huì)保存子問題解避免重復(fù)計(jì)算；分治算法分解的子問題相互獨(dú)立，直接遞歸求解子問題。4.舉例說明貪心算法在生活中的應(yīng)用。答案：如活動(dòng)安排問題，在一天內(nèi)有多個(gè)活動(dòng)，每個(gè)活動(dòng)有開始和結(jié)束時(shí)間，貪心算法可按結(jié)束時(shí)間早的優(yōu)先選擇，能安排盡可能多的活動(dòng)。又如找零時(shí)，優(yōu)先選擇面額大的貨幣，以減少貨幣數(shù)量。答案單項(xiàng)選擇題1.C2.B3.B4.B5.B6.B7.B8.C9.A10.C多項(xiàng)選擇題1.ABD2.ABCD3.ABD