湖南工程學(xué)院《算法與數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線第1頁(yè)，共3頁(yè)湖南工程學(xué)院

《算法與數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下哪個(gè)不是動(dòng)態(tài)規(guī)劃算法的關(guān)鍵步驟？A.確定狀態(tài)B.確定狀態(tài)轉(zhuǎn)移方程C.初始化狀態(tài)D.隨機(jī)選擇狀態(tài)2、以下哪種算法常用于解決組合優(yōu)化問(wèn)題？（）A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃3、以下哪種算法常用于解決皇后問(wèn)題？（）A.貪心算法B.回溯法C.動(dòng)態(tài)規(guī)劃D.分治法4、分治法的基本思想是？A.把大問(wèn)題分解成多個(gè)小問(wèn)題分別求解B.從一個(gè)初始解逐步優(yōu)化得到最終解C.通過(guò)隨機(jī)選擇來(lái)找到最優(yōu)解D.對(duì)問(wèn)題進(jìn)行暴力搜索5、在二叉樹中，中序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹6、在二叉樹中，后序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹7、在回溯法中，當(dāng)所有可能的選擇都嘗試過(guò)后，算法（）A.停止B.繼續(xù)C.重新開始D.以上都不是8、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖？（）A.數(shù)組B.鏈表C.鄰接矩陣和鄰接表D.棧9、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)優(yōu)先隊(duì)列？A.數(shù)組B.鏈表C.棧D.堆10、在圖的存儲(chǔ)結(jié)構(gòu)中，鄰接表適合存儲(chǔ)什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無(wú)向圖11、空間復(fù)雜度主要考慮（）A.算法執(zhí)行過(guò)程中占用的內(nèi)存空間B.算法執(zhí)行過(guò)程中占用的硬盤空間C.算法執(zhí)行過(guò)程中占用的網(wǎng)絡(luò)帶寬D.以上都是12、歸并排序的基本思想是？A.分而治之，合并有序子序列B.選擇最小元素逐步構(gòu)建有序序列C.通過(guò)交換相鄰元素進(jìn)行排序D.隨機(jī)選擇元素進(jìn)行排序13、時(shí)間復(fù)雜度和空間復(fù)雜度需要在設(shè)計(jì)算法時(shí)進(jìn)行（）A.單獨(dú)考慮B.綜合考慮C.先考慮時(shí)間復(fù)雜度D.先考慮空間復(fù)雜度14、算法的穩(wěn)定性對(duì)于（）操作較為重要。A.多次排序B.查找C.插入D.刪除15、在分治法中，將問(wèn)題分解成的子問(wèn)題通常具有（）A.不同的規(guī)模B.相同的規(guī)模C.隨機(jī)的規(guī)模D.以上都可能16、以下哪種算法常用于解決背包問(wèn)題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法17、在算法設(shè)計(jì)中，減少算法的常數(shù)因子可以（）A.提高算法效率B.降低算法效率C.不影響算法效率D.以上都不是18、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于查找操作？（）A.棧B.隊(duì)列C.二叉搜索樹D.鏈表19、在哈希表中，當(dāng)發(fā)生沖突時(shí)，可以采用哪種方法來(lái)解決？A.線性探測(cè)法B.二次探測(cè)法C.鏈地址法D.以上都是20、以下哪個(gè)算法可以用于求解圖的所有頂點(diǎn)之間的最短路徑問(wèn)題？A.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克魯斯卡爾算法二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）簡(jiǎn)述分治法的基本思想和應(yīng)用場(chǎng)景。2、（本題10分）以不同路徑問(wèn)題為例，分析動(dòng)態(tài)規(guī)劃算法的應(yīng)用。3、（本題10分）分析圖著色問(wèn)題的算法和復(fù)雜性。4、（本題10分）說(shuō)明如何用回溯法解決迷宮問(wèn)題。