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

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

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