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

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁湖南工程學(xué)院

《算法設(shè)計與分析A》2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪個不是動態(tài)規(guī)劃算法的優(yōu)點(diǎn)？A.高效性B.準(zhǔn)確性C.通用性D.簡單性2、以下哪種算法的時間復(fù)雜度最低？（）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é)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹8、動態(tài)規(guī)劃算法通常用于解決具有什么性質(zhì)的問題？A.最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)B.最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題性質(zhì)C.貪心選擇性質(zhì)和重疊子問題性質(zhì)D.隨機(jī)性質(zhì)和重疊子問題性質(zhì)9、以下哪個排序算法是穩(wěn)定的？A.快速排序B.堆排序C.希爾排序D.冒泡排序10、快速排序的平均時間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)11、時間復(fù)雜度和空間復(fù)雜度之間通常存在（）A.正相關(guān)關(guān)系B.負(fù)相關(guān)關(guān)系C.沒有關(guān)系D.不確定的關(guān)系12、以下哪個算法可以用于求解最長遞增子序列問題？A.貪心算法B.回溯法C.分治法D.動態(tài)規(guī)劃法13、在哈希表中，哈希函數(shù)的作用是？A.確定元素在表中的存儲位置B.解決沖突C.提高查找效率D.減少存儲空間14、以下哪個數(shù)據(jù)結(jié)構(gòu)常用于查找操作？（）A.棧B.隊列C.二叉搜索樹D.鏈表15、以下哪個不是貪心算法的基本要素？A.貪心選擇性質(zhì)B.最優(yōu)子結(jié)構(gòu)性質(zhì)C.重疊子問題性質(zhì)D.無后效性16、在二叉樹中，后序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹17、在貪心算法中，如果局部最優(yōu)解不能導(dǎo)致全局最優(yōu)解，該算法（）A.仍然有效B.無效C.可能有效D.以上都不是18、在二叉樹中，度為0的節(jié)點(diǎn)稱為？A.葉子節(jié)點(diǎn)B.根節(jié)點(diǎn)C.內(nèi)部節(jié)點(diǎn)D.分支節(jié)點(diǎn)19、在有向無環(huán)圖中，進(jìn)行拓?fù)渑判虻臅r間復(fù)雜度是？A.O(1)B.O(n)C.O(nlogn)D.O(n2)20、以下哪個數(shù)據(jù)結(jié)構(gòu)可以用于實現(xiàn)隊列的功能？A.數(shù)組B.鏈表C.棧D.二叉樹二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋后綴樹和后綴數(shù)組的概念和應(yīng)用。2、（本題10分）解釋粒子群優(yōu)化算法的概念和特點(diǎn)。3、（本題10分）闡述堆排序在大規(guī)模數(shù)據(jù)排序中的適用性。4、（本題10分）解釋在電子商務(wù)中的推薦和定價算法。三、