裝訂線裝訂線PAGE2第1頁，共3頁北京工業大學《算法設計》

2022-2023學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共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.稀疏圖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、以下哪個算法可以用于解決0-1背包問題？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分）比較Dijkstra算法和Floyd算法的適用情況。4、（本題10分）簡述在數據庫管理中用到的算法。三、設計題（本大題共2個小題，共2