自覺遵守考場紀律如考試作弊此答卷無效密自覺遵守考場紀律如考試作弊此答卷無效密封線第1頁，共3頁賀州學院

《算法分析與設計基礎語言》2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪個不是貪心算法的局限性？A.不一定能得到全局最優(yōu)解B.算法的時間復雜度較高C.對問題的性質(zhì)有一定要求D.難以證明算法的正確性2、時間復雜度和空間復雜度之間通常存在（）A.正相關關系B.負相關關系C.沒有關系D.不確定的關系3、以下哪種算法常用于解決最大子數(shù)組問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法4、在圖的遍歷中，深度優(yōu)先搜索和廣度優(yōu)先搜索的主要區(qū)別是？A.遍歷的順序不同B.時間復雜度不同C.空間復雜度不同D.適用的圖類型不同5、以下哪個排序算法的空間復雜度最低？（）A.冒泡排序B.插入排序C.選擇排序D.歸并排序6、算法分析的主要目的是（）A.評估算法的性能B.設計新算法C.比較不同算法D.以上都是7、以下哪個算法常用于圖的最短路徑問題？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法8、在動態(tài)規(guī)劃中，重疊子問題的性質(zhì)是指（）A.子問題多次出現(xiàn)B.子問題相互獨立C.子問題具有唯一性D.以上都不是9、時間復雜度為O(n)的算法，其執(zhí)行時間與輸入規(guī)模n的關系是（）A.線性增長B.指數(shù)增長C.對數(shù)增長D.不變10、二分查找算法要求數(shù)據(jù)必須是（）A.有序的B.無序的C.平衡的D.以上都不是11、時間復雜度和空間復雜度需要在設計算法時進行（）A.單獨考慮B.綜合考慮C.先考慮時間復雜度D.先考慮空間復雜度12、以下哪個不是動態(tài)規(guī)劃算法的關鍵步驟？A.確定狀態(tài)B.確定狀態(tài)轉(zhuǎn)移方程C.初始化狀態(tài)D.隨機選擇狀態(tài)13、以下哪種算法常用于解決資源分配問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法14、在貪心算法中，每一步的選擇都是（）A.全局最優(yōu)B.局部最優(yōu)C.隨機的D.以上都不是15、快速排序的不穩(wěn)定因素主要來自于什么？A.樞軸元素的選擇B.遞歸調(diào)用的深度C.數(shù)據(jù)的規(guī)模D.排序的方向16、以下哪個算法可以用于解決0-1背包問題？A.貪心算法B.回溯法C.分治法D.動態(tài)規(guī)劃法17、以下哪種算法常用于解決組合優(yōu)化問題？（）A.貪心算法B.回溯法C.分治法D.動態(tài)規(guī)劃18、以下哪種排序算法在平均情況下時間復雜度最低？A.冒泡排序B.插入排序C.選擇排序D.快速排序19、在貪心算法中，最終的解依賴于（）A.子問題的選擇順序B.問題的規(guī)模C.數(shù)據(jù)的分布D.以上都是20、以下哪種排序算法對近乎有序的數(shù)組效果較好？（）A.快速排序B.插入排序C.冒泡排序D.選擇排序二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋在信號處理中的頻譜分析算法。2、（本題10分）解釋在金融工程中使用的風險評估算法。3、（本題10分）簡述堆排序在優(yōu)先隊列中的應用。4、（本題10分）簡述KMP算法中next數(shù)組的計算方法。三、設