湖南工商大學(xué)《算法導(dǎo)論》2022-2023學(xué)年期末試卷

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

《算法導(dǎo)論》2022-2023學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、快速排序的樞軸元素選擇對算法的性能有很大影響，以下哪種選擇方式通常比較好？A.第一個元素B.最后一個元素C.中間元素D.隨機(jī)元素2、以下哪個不是貪心算法的特點？（）A.局部最優(yōu)B.整體最優(yōu)C.高效性D.不可回溯3、在分治法中，如果子問題的規(guī)模不相等，可能會（）A.影響算法效率B.提高算法效率C.不影響算法效率D.以上都不是4、動態(tài)規(guī)劃算法通常用于解決（）問題。A.最優(yōu)解B.近似解C.隨機(jī)解D.無解5、以下哪個數(shù)據(jù)結(jié)構(gòu)可以用于實現(xiàn)圖的深度優(yōu)先搜索？A.數(shù)組B.鏈表C.棧D.隊列6、在有向圖中，進(jìn)行深度優(yōu)先搜索時，需要使用什么數(shù)據(jù)結(jié)構(gòu)來記錄已訪問的頂點？A.數(shù)組B.鏈表C.棧D.隊列7、快速排序算法在最壞情況下的時間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)8、在圖的遍歷中，廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊列C.鏈表D.樹9、在哈希表中，當(dāng)發(fā)生沖突時，可以采用哪種方法來解決？A.線性探測法B.二次探測法C.鏈地址法D.以上都是10、以下哪個不是動態(tài)規(guī)劃算法的應(yīng)用場景？A.資源分配問題B.背包問題C.圖的遍歷問題D.矩陣鏈乘法問題11、在二叉樹中，度為2的節(jié)點有10個，度為1的節(jié)點有8個，那么葉子節(jié)點有多少個？A.9B.10C.11D.1212、在圖的深度優(yōu)先搜索中，使用的輔助數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊列C.優(yōu)先隊列D.哈希表13、歸并排序的基本思想是？A.分而治之，合并有序子序列B.選擇最小元素逐步構(gòu)建有序序列C.通過交換相鄰元素進(jìn)行排序D.隨機(jī)選擇元素進(jìn)行排序14、以下哪個數(shù)據(jù)結(jié)構(gòu)可以用于實現(xiàn)棧的功能？A.數(shù)組B.鏈表C.隊列D.二叉樹15、以下哪個數(shù)據(jù)結(jié)構(gòu)可以用于實現(xiàn)隊列的功能？A.數(shù)組B.鏈表C.棧D.二叉樹16、算法的復(fù)雜度分析不包括（）A.時間復(fù)雜度B.空間復(fù)雜度C.代碼復(fù)雜度D.平均復(fù)雜度17、在動態(tài)規(guī)劃中，重疊子問題的性質(zhì)是指（）A.子問題多次出現(xiàn)B.子問題相互獨立C.子問題具有唯一性D.以上都不是18、快速排序在最好情況下的時間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)19、以下哪個不是算法的評價指標(biāo)？（）A.正確性B.可讀性C.可擴(kuò)展性D.代碼長度20、以下哪個不是動態(tài)規(guī)劃算法的關(guān)鍵步驟？A.確定狀態(tài)B.確定狀態(tài)轉(zhuǎn)移方程C.初始化狀態(tài)D.隨機(jī)選擇狀態(tài)二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋在視頻編碼中的壓縮算法。2、（本題10分）簡述活動選擇問題的算法思路和解決方法。3、（本題10分）簡述網(wǎng)絡(luò)流算法在實際中的應(yīng)用。4、（本題10分）以石子合并問題為例，分析動態(tài)規(guī)劃算法的應(yīng)用。三、設(shè)計題（