南京信息工程大學(xué)《算法設(shè)計(jì)與分析II》2022-2023學(xué)年期末試卷

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁南京信息工程大學(xué)《算法設(shè)計(jì)與分析II》

2022-2023學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、時(shí)間復(fù)雜度為O(n)的算法，其執(zhí)行時(shí)間與輸入規(guī)模n的關(guān)系是（）A.線性增長B.指數(shù)增長C.對(duì)數(shù)增長D.不變2、在貪心算法中，每一步的選擇都是（）A.全局最優(yōu)B.局部最優(yōu)C.隨機(jī)的D.以上都不是3、動(dòng)態(tài)規(guī)劃算法的核心是？A.遞歸B.貪心選擇C.記憶化搜索D.分治4、以下哪個(gè)算法可以用于求解圖的單源最短路徑問題？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.迪杰斯特拉算法D.克魯斯卡爾算法5、在貪心算法中，得到的解可能是（）A.最優(yōu)解B.近似最優(yōu)解C.可行解D.以上都可能6、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)圖的深度優(yōu)先搜索？A.數(shù)組B.鏈表C.棧D.隊(duì)列7、算法的最優(yōu)性是指（）A.時(shí)間復(fù)雜度最低B.空間復(fù)雜度最低C.得到的解最優(yōu)D.以上都是8、以下哪個(gè)不是隊(duì)列的基本操作？A.入隊(duì)B.出隊(duì)C.查找D.排序9、以下哪種算法常用于解決旅行商問題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.模擬退火算法10、歸并排序的基本思想是？A.分而治之，合并有序子序列B.選擇最小元素逐步構(gòu)建有序序列C.通過交換相鄰元素進(jìn)行排序D.隨機(jī)選擇元素進(jìn)行排序11、快速排序的樞軸元素選擇對(duì)算法的性能有很大影響，以下哪種選擇方式通常比較好？A.第一個(gè)元素B.最后一個(gè)元素C.中間元素D.隨機(jī)元素12、在二叉搜索樹中，查找一個(gè)元素的時(shí)間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)13、歸并排序的空間復(fù)雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)14、在二叉搜索樹中刪除一個(gè)節(jié)點(diǎn)時(shí)，需要考慮幾種情況？A.1種B.2種C.3種D.4種15、以下哪種算法常用于解決背包問題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法16、在二叉搜索樹中進(jìn)行查找操作的平均時(shí)間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)17、以下哪個(gè)不是圖的基本操作？A.插入頂點(diǎn)B.刪除頂點(diǎn)C.查找頂點(diǎn)D.排序頂點(diǎn)18、在分治法中，合并子問題的解的時(shí)間復(fù)雜度通常為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、在哈希表中，解決沖突的方法有哪些？A.線性探測法和二次探測法B.鏈地址法和開放定址法C.再哈希法和建立公共溢出區(qū)D.以上都是20、以下哪種算法常用于解決凸包問題？（）A.Graham掃描法B.Dijkstra算法C.Prim算法D.Kruskal算法二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）說明如何用回溯法解決資源分配的效益最大化問題。2、（本題10分）解釋最大流問題的算法和優(yōu)化。3、（本題10分）說明如何用回溯法解決數(shù)的全排列問題。4、（本題10分）解釋選擇排序在特定數(shù)據(jù)分布下的性能優(yōu)勢。三、設(shè)計(jì)題（