學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁成都大學《算法設計》

2022-2023學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、快速排序的遞歸終止條件是什么？A.子數組長度為0或1B.子數組長度為2C.子數組長度為3D.子數組長度為42、以下哪種算法常用于解決資源分配問題？（）A.貪心算法B.動態規劃C.回溯法D.分治法3、以下哪個不是隊列的基本操作？A.入隊B.出隊C.查找D.排序4、在圖的存儲結構中，鄰接表適合存儲什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖5、以下哪種算法常用于構建最小生成樹？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法6、以下哪個不是算法的評價指標？（）A.正確性B.可讀性C.可擴展性D.代碼長度7、在分治法中，如果子問題的規模不相等，可能會（）A.影響算法效率B.提高算法效率C.不影響算法效率D.以上都不是8、以下關于算法復雜度的說法中，錯誤的是？A.時間復雜度是指算法執行所需的時間B.空間復雜度是指算法執行所需的存儲空間C.算法的時間復雜度和空間復雜度可以相互獨立D.算法的時間復雜度總是小于空間復雜度9、在貪心算法中，如果局部最優解不能導致全局最優解，該算法（）A.仍然有效B.無效C.可能有效D.以上都不是10、在回溯法中，當所有可能的選擇都嘗試過后，算法（）A.停止B.繼續C.重新開始D.以上都不是11、快速排序的不穩定因素主要來自于什么？A.樞軸元素的選擇B.遞歸調用的深度C.數據的規模D.排序的方向12、在哈希表中，當發生沖突時，可以采用哪種方法來解決？A.線性探測法B.二次探測法C.鏈地址法D.以上都是13、在有向圖中，進行深度優先搜索時，需要使用什么數據結構來記錄已訪問的頂點？A.數組B.鏈表C.棧D.隊列14、在圖的存儲結構中，十字鏈表適合存儲什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖15、動態規劃算法通常用于解決（）問題。A.最優解B.近似解C.隨機解D.無解16、動態規劃算法的核心是？A.遞歸B.貪心選擇C.記憶化搜索D.分治17、以下哪個排序算法在最壞情況下的時間復雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序18、在二叉搜索樹中進行查找操作的平均時間復雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)19、在動態規劃中，通過保存子問題的解來避免（）A.重復計算B.錯誤計算C.遺漏計算D.以上都是20、在動態規劃中，狀態轉移方程描述了（）A.不同狀態之間的關系B.初始狀態的計算方法C.最優解的計算方法D.以上都不是二、簡答題（本大題共4個小題，共40分)1、（本題10分）分析模擬退火算法的基本思想和應用。2、（本題10分）解釋在軍事領域中的作戰模擬和決策支持算法。3、（本題10分）分析編輯距離問題的算法實現和應用場景。4、（本題10分）簡述分塊算法的思想和應用