蘇州大學(xué)《算法設(shè)計(jì)與分析》2023-2024學(xué)年期末試卷

自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁蘇州大學(xué)

《算法設(shè)計(jì)與分析》2023-2024學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在算法分析中，大O記號(hào)表示的是？A.算法的精確運(yùn)行時(shí)間B.算法的平均運(yùn)行時(shí)間C.算法運(yùn)行時(shí)間的上界D.算法運(yùn)行時(shí)間的下界2、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)棧的功能？A.數(shù)組B.鏈表C.隊(duì)列D.二叉樹3、以下哪種算法常用于解決資源分配問題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法4、在二叉樹中，中序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹5、在分治法中，如果子問題的規(guī)模不相等，可能會(huì)（）A.影響算法效率B.提高算法效率C.不影響算法效率D.以上都不是6、以下哪種算法常用于解決裝箱問題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法7、在算法設(shè)計(jì)中，減少算法的常數(shù)因子可以（）A.提高算法效率B.降低算法效率C.不影響算法效率D.以上都不是8、在貪心算法中，得到的解可能是（）A.最優(yōu)解B.近似最優(yōu)解C.可行解D.以上都可能9、在二叉樹中，度為2的節(jié)點(diǎn)有10個(gè)，度為1的節(jié)點(diǎn)有8個(gè)，那么葉子節(jié)點(diǎn)有多少個(gè)？A.9B.10C.11D.1210、以下哪個(gè)排序算法是穩(wěn)定的？A.快速排序B.堆排序C.希爾排序D.冒泡排序11、在二叉樹中，后序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹12、以下哪種排序算法在數(shù)據(jù)量較大時(shí)性能較好？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序13、以下哪種算法常用于解決凸包問題？（）A.Graham掃描法B.Dijkstra算法C.Prim算法D.Kruskal算法14、在動(dòng)態(tài)規(guī)劃中，優(yōu)化子問題的解存儲(chǔ)方式可以（）A.降低時(shí)間復(fù)雜度B.降低空間復(fù)雜度C.提高可讀性D.以上都是15、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)隊(duì)列？（）A.數(shù)組B.鏈表C.棧D.樹16、動(dòng)態(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ì)17、在貪心算法中，如果局部最優(yōu)解不能導(dǎo)致全局最優(yōu)解，該算法（）A.仍然有效B.無效C.可能有效D.以上都不是18、在有向圖中，進(jìn)行深度優(yōu)先搜索時(shí)，需要使用什么數(shù)據(jù)結(jié)構(gòu)來記錄已訪問的頂點(diǎn)？A.數(shù)組B.鏈表C.棧D.隊(duì)列19、在圖的遍歷中，廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊(duì)列C.鏈表D.樹20、在哈希表中，解決沖突的方法有哪些？A.線性探測(cè)法和二次探測(cè)法B.鏈地址法和開放定址法C.再哈希法和建立公共溢出區(qū)D.以上都是二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）說明如何用回溯法解決密碼破解問題。2、（本題10分）以字符串匹配問題為例，說明動(dòng)態(tài)規(guī)劃算法的應(yīng)用。3、（本題10分）分析分布式系統(tǒng)中的一致性問題和解決方法。4、（本題10分）解釋歸并排序的合并操作的實(shí)現(xiàn)細(xì)節(jié)。三、設(shè)計(jì)