裝訂線裝訂線PAGE2第1頁，共3頁湖北理工學院《算法設計與分析》

2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪種排序算法是穩定的？（）A.快速排序B.冒泡排序C.選擇排序D.希爾排序2、以下哪個不是貪心算法的應用場景？A.哈夫曼編碼B.最小生成樹C.背包問題D.矩陣乘法3、在貪心算法中，得到的解可能是（）A.最優解B.近似最優解C.可行解D.以上都可能4、以下哪個數據結構可以用于實現優先隊列？A.數組B.鏈表C.棧D.堆5、在回溯法中，當所有可能的選擇都嘗試過后，算法（）A.停止B.繼續C.重新開始D.以上都不是6、在動態規劃中，狀態轉移方程描述了（）A.不同狀態之間的關系B.初始狀態的計算方法C.最優解的計算方法D.以上都不是7、以下哪個算法可以用于求解最大子數組和問題？A.貪心算法B.回溯法C.分治法D.動態規劃法8、在二叉搜索樹中，查找一個元素的時間復雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)9、以下哪種算法常用于解決旅行商問題？（）A.貪心算法B.動態規劃C.回溯法D.模擬退火算法10、二分查找算法要求數據必須是（）A.有序的B.無序的C.平衡的D.以上都不是11、在圖的遍歷中，廣度優先搜索使用的數據結構是（）A.棧B.隊列C.鏈表D.樹12、歸并排序的合并操作的時間復雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)13、以下關于算法復雜度的說法中，錯誤的是？A.時間復雜度是指算法執行所需的時間B.空間復雜度是指算法執行所需的存儲空間C.算法的時間復雜度和空間復雜度可以相互獨立D.算法的時間復雜度總是小于空間復雜度14、以下哪個不是動態規劃算法的應用場景？A.資源分配問題B.背包問題C.圖的遍歷問題D.矩陣鏈乘法問題15、快速排序的遞歸終止條件是什么？A.子數組長度為0或1B.子數組長度為2C.子數組長度為3D.子數組長度為416、以下哪種算法常用于構建最小生成樹？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法17、一個算法的時間復雜度為O(n2)，如果輸入規模擴大一倍，那么運行時間會變為原來的幾倍？A.2倍B.4倍C.8倍D.16倍18、以下哪個算法可以用于求解字符串的最長回文子串問題？A.貪心算法B.回溯法C.分治法D.動態規劃法19、以下哪個數據結構可以用于實現圖的深度優先搜索？A.數組B.鏈表C.棧D.隊列20、分治法的設計步驟不包括以下哪個？A.分解問題B.解決子問題C.合并子問題的解D.隨機選擇子問題二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋倍增算法的原理和適用問題。2、（本題10分）簡述競爭分析在在線算法中的應用。3、（本題10分）解釋貪心算法在背包問題中的應用和局限性。4、（本題10分）簡述單調棧和單調隊列的用途。三、設計題（本大題共2個小題，共20分)1、