黑龍江工程學院《算法分析與設(shè)計》2021-2022學年期末試卷

自覺遵守考場紀律如考試作弊此答卷無效密自覺遵守考場紀律如考試作弊此答卷無效密封線第1頁，共3頁黑龍江工程學院《算法分析與設(shè)計》

2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪個不是算法的設(shè)計方法？A.分治法B.動態(tài)規(guī)劃法C.貪心算法D.隨機猜測法2、在貪心算法中，如果局部最優(yōu)解不能導致全局最優(yōu)解，該算法（）A.仍然有效B.無效C.可能有效D.以上都不是3、在圖的存儲結(jié)構(gòu)中，鄰接矩陣適合存儲什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖4、在圖的存儲結(jié)構(gòu)中，十字鏈表適合存儲什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖5、動態(tài)規(guī)劃算法通常用于解決（）問題。A.最優(yōu)解B.近似解C.隨機解D.無解6、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)棧？（）A.數(shù)組B.鏈表C.樹D.圖7、在算法設(shè)計中，減少算法的常數(shù)因子可以（）A.提高算法效率B.降低算法效率C.不影響算法效率D.以上都不是8、在圖的存儲結(jié)構(gòu)中，鄰接表適合存儲什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖9、以下哪個不是圖的遍歷算法？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.最短路徑搜索D.拓撲排序10、以下哪個不是算法的評價指標？（）A.正確性B.可讀性C.可擴展性D.代碼長度11、在動態(tài)規(guī)劃中，通過保存子問題的解來避免（）A.重復計算B.錯誤計算C.遺漏計算D.以上都是12、以下哪個數(shù)據(jù)結(jié)構(gòu)可以高效地進行插入和刪除操作，并且可以快速地找到最小值？A.數(shù)組B.鏈表C.棧D.堆13、以下哪種算法常用于解決凸包問題？（）A.Graham掃描法B.Dijkstra算法C.Prim算法D.Kruskal算法14、在有向圖中，進行深度優(yōu)先搜索時，需要使用什么數(shù)據(jù)結(jié)構(gòu)來記錄已訪問的頂點？A.數(shù)組B.鏈表C.棧D.隊列15、以下哪個算法可以用于求解圖的最小生成樹問題？A.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克魯斯卡爾算法16、快速排序在最好情況下的時間復雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)17、以下哪個算法可以用于求解最長遞增子序列問題？A.貪心算法B.回溯法C.分治法D.動態(tài)規(guī)劃法18、以下哪個排序算法的空間復雜度最低？（）A.冒泡排序B.插入排序C.選擇排序D.歸并排序19、在哈希表中，哈希函數(shù)的作用是？A.確定元素在表中的存儲位置B.解決沖突C.提高查找效率D.減少存儲空間20、以下哪個數(shù)據(jù)結(jié)構(gòu)常用于查找操作？（）A.棧B.隊列C.二叉搜索樹D.鏈表二、簡答題（本大題共4個小題，共40分)1、（本題10分）簡述如何利用并行計算加速算法。2、（本題10分）簡述如何考慮算法的可擴展性。3、（本題10分）分析在編譯原理中涉及的算法。4、（本題10分）解釋選擇排序在數(shù)據(jù)規(guī)模較大時的效率問題。三、設(shè)計題