湖北理工學(xué)院《算法設(shè)計與分析》2021-2022學(xué)年期末試卷

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

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