自覺遵守考場(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、算法的通用性是指（）A.適用于多種問題B.代碼可復(fù)用C.易于理解D.以上都是2、空間復(fù)雜度主要考慮（）A.算法執(zhí)行過程中占用的內(nèi)存空間B.算法執(zhí)行過程中占用的硬盤空間C.算法執(zhí)行過程中占用的網(wǎng)絡(luò)帶寬D.以上都是3、在動(dòng)態(tài)規(guī)劃中，重疊子問題的性質(zhì)是指（）A.子問題多次出現(xiàn)B.子問題相互獨(dú)立C.子問題具有唯一性D.以上都不是4、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字典？（）A.哈希表B.二叉樹C.鏈表D.棧5、以下哪個(gè)算法可以用于求解圖的最小生成樹問題？A.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克魯斯卡爾算法6、在哈希表中，解決沖突的方法有哪些？A.線性探測(cè)法和二次探測(cè)法B.鏈地址法和開放定址法C.再哈希法和建立公共溢出區(qū)D.以上都是7、以下哪種算法常用于解決背包問題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法8、以下哪個(gè)不是貪心算法的應(yīng)用場(chǎng)景？A.哈夫曼編碼B.最小生成樹C.背包問題D.矩陣乘法9、歸并排序的遞歸實(shí)現(xiàn)中，每次將數(shù)組分成兩部分，那么遞歸的深度是多少？A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、時(shí)間復(fù)雜度為O(logn)的算法通常比時(shí)間復(fù)雜度為O(n)的算法（）A.更慢B.更快C.一樣快D.無法比較11、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于查找操作？（）A.棧B.隊(duì)列C.二叉搜索樹D.鏈表12、以下哪種排序算法的平均時(shí)間復(fù)雜度為O(nlogn)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序13、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)集合？（）A.數(shù)組B.鏈表C.哈希表D.樹14、在回溯法中，當(dāng)所有可能的選擇都嘗試過后，算法（）A.停止B.繼續(xù)C.重新開始D.以上都不是15、快速排序的遞歸終止條件是什么？A.子數(shù)組長(zhǎng)度為0或1B.子數(shù)組長(zhǎng)度為2C.子數(shù)組長(zhǎng)度為3D.子數(shù)組長(zhǎng)度為416、以下哪個(gè)算法可以用于求解旅行商問題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法17、在遞歸算法中，當(dāng)遞歸深度過大時(shí)可能會(huì)導(dǎo)致（）A.運(yùn)行速度加快B.內(nèi)存溢出C.結(jié)果更準(zhǔn)確D.以上都不是18、在二叉樹中，前序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹19、遞歸算法的基本思想是（）A.自頂向下分解B.自底向上計(jì)算C.不斷重復(fù)相同操作D.調(diào)用自身函數(shù)20、以下哪個(gè)算法可以用于求解圖的單源最短路徑問題？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.迪杰斯特拉算法D.克魯斯卡爾算法二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋0-1背包問題為何不能用貪心算法得到最優(yōu)解。2、（本題10分）解釋選擇排序在隨機(jī)數(shù)據(jù)下的性能特點(diǎn)。3、（本題10分）簡(jiǎn)述近似算法的設(shè)計(jì)目標(biāo)和評(píng)估方法。4、（本題10分）解釋如何在推薦系統(tǒng)中運(yùn)用算法。三、設(shè)計(jì)題（