湖南工程學院《算法設計與分析A》2021-2022學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁湖南工程學院

《算法設計與分析A》2021-2022學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪個不是動態(tài)規(guī)劃算法的優(yōu)點？A.高效性B.準確性C.通用性D.簡單性2、以下哪種算法的時間復雜度最低？（）A.O(n^2)B.O(nlogn)C.O(logn)D.O(n)3、在貪心算法中，一旦做出選擇就（）A.可以更改B.不能更改C.視情況更改D.以上都不是4、在哈希表中，解決沖突的方法有哪些？A.線性探測法和二次探測法B.鏈地址法和開放定址法C.再哈希法和建立公共溢出區(qū)D.以上都是5、算法的穩(wěn)定性對于（）操作較為重要。A.多次排序B.查找C.插入D.刪除6、以下哪個算法可以用于解決0-1背包問題？A.貪心算法B.回溯法C.分治法D.動態(tài)規(guī)劃法7、在二叉樹中，中序遍歷的順序是？A.根節(jié)點、左子樹、右子樹B.左子樹、根節(jié)點、右子樹C.左子樹、右子樹、根節(jié)點D.右子樹、根節(jié)點、左子樹8、動態(tài)規(guī)劃算法通常用于解決具有什么性質的問題？A.最優(yōu)子結構性質和貪心選擇性質B.最優(yōu)子結構性質和重疊子問題性質C.貪心選擇性質和重疊子問題性質D.隨機性質和重疊子問題性質9、以下哪個排序算法是穩(wěn)定的？A.快速排序B.堆排序C.希爾排序D.冒泡排序10、快速排序的平均時間復雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)11、時間復雜度和空間復雜度之間通常存在（）A.正相關關系B.負相關關系C.沒有關系D.不確定的關系12、以下哪個算法可以用于求解最長遞增子序列問題？A.貪心算法B.回溯法C.分治法D.動態(tài)規(guī)劃法13、在哈希表中，哈希函數的作用是？A.確定元素在表中的存儲位置B.解決沖突C.提高查找效率D.減少存儲空間14、以下哪個數據結構常用于查找操作？（）A.棧B.隊列C.二叉搜索樹D.鏈表15、以下哪個不是貪心算法的基本要素？A.貪心選擇性質B.最優(yōu)子結構性質C.重疊子問題性質D.無后效性16、在二叉樹中，后序遍歷的順序是？A.根節(jié)點、左子樹、右子樹B.左子樹、根節(jié)點、右子樹C.左子樹、右子樹、根節(jié)點D.右子樹、根節(jié)點、左子樹17、在貪心算法中，如果局部最優(yōu)解不能導致全局最優(yōu)解，該算法（）A.仍然有效B.無效C.可能有效D.以上都不是18、在二叉樹中，度為0的節(jié)點稱為？A.葉子節(jié)點B.根節(jié)點C.內部節(jié)點D.分支節(jié)點19、在有向無環(huán)圖中，進行拓撲排序的時間復雜度是？A.O(1)B.O(n)C.O(nlogn)D.O(n2)20、以下哪個數據結構可以用于實現隊列的功能？A.數組B.鏈表C.棧D.二叉樹二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋后綴樹和后綴數組的概念和應用。2、（本題10分）解釋粒子群優(yōu)化算法的概念和特點。3、（本題10分）闡述堆排序在大規(guī)模數據排序中的適用性。4、（本題10分）解釋在電子商務中的推薦和定價算法。三、