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

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