成都大學《算法設計》2022-2023學年期末試卷

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

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