學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第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.根節點、左子樹、右子樹B.左子樹、根節點、右子樹C.左子樹、右子樹、根節點D.右子樹、根節點、左子樹9、歸并排序的基本思想是？A.分而治之，合并有序子序列B.選擇最小元素逐步構建有序序列C.通過交換相鄰元素進行排序D.隨機選擇元素進行排序10、算法的正確性是指（）A.對于任意輸入都能得到正確結果B.對于大部分輸入能得到正確結果C.對于特定輸入能得到正確結果D.以上都不是11、歸并排序的合并操作的時間復雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)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.影響算法效率B.提高算法效率C.不影響算法效率D.以上都不是19、以下哪個算法可以用于判斷一個圖是否為連通圖？A.深度優先搜索B.廣度優先搜索C.迪杰斯特拉算法D.普里姆算法20、以下哪個數據結構可以用于實現圖的深度優先搜索？A.數組B.鏈表C.棧D.隊列二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋動態規劃在資源分配問題中的解法。2、（本題10分）解釋選擇排序對不同數據類型的通用性。3、（本題10分）解釋矩陣乘法的常見算法和優化策略。4、（本題10分）解釋插入排序對近乎逆序數組的處理性能。三、設