南京信息工程大學(xué)《隨機(jī)算法》2023-2024學(xué)年期末試卷

站名：站名：年級(jí)專(zhuān)業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專(zhuān)業(yè)、姓名、學(xué)號(hào)錯(cuò)寫(xiě)、漏寫(xiě)或字跡不清者，成績(jī)按零分記?！堋狻€(xiàn)…………第1頁(yè)，共1頁(yè)南京信息工程大學(xué)

《隨機(jī)算法》2023-2024學(xué)年期末試卷題號(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ìn)行貪心選擇2、動(dòng)態(tài)規(guī)劃算法通常用于解決具有什么性質(zhì)的問(wèn)題？A.最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)B.最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問(wèn)題性質(zhì)C.貪心選擇性質(zhì)和重疊子問(wèn)題性質(zhì)D.隨機(jī)性質(zhì)和重疊子問(wèn)題性質(zhì)3、在圖的遍歷中，廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊(duì)列C.鏈表D.樹(shù)4、在圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表適合存儲(chǔ)什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無(wú)向圖5、以下哪種排序算法在平均情況下時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.快速排序6、以下哪個(gè)排序算法在最壞情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.歸并排序D.堆排序7、在算法設(shè)計(jì)中，降低時(shí)間復(fù)雜度通常比降低空間復(fù)雜度更（）A.容易B.困難C.重要D.不重要8、在二叉樹(shù)中，前序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹(shù)、右子樹(shù)B.左子樹(shù)、根節(jié)點(diǎn)、右子樹(shù)C.左子樹(shù)、右子樹(shù)、根節(jié)點(diǎn)D.右子樹(shù)、根節(jié)點(diǎn)、左子樹(shù)9、算法的正確性是指（）A.對(duì)于任意輸入都能得到正確結(jié)果B.對(duì)于大部分輸入能得到正確結(jié)果C.對(duì)于特定輸入能得到正確結(jié)果D.以上都不是10、算法的穩(wěn)定性對(duì)于（）操作較為重要。A.多次排序B.查找C.插入D.刪除11、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖？（）A.數(shù)組B.鏈表C.鄰接矩陣和鄰接表D.棧12、歸并排序的空間復(fù)雜度主要取決于什么？A.數(shù)據(jù)的規(guī)模B.遞歸調(diào)用的深度C.合并操作的次數(shù)D.數(shù)據(jù)的類(lèi)型13、在二叉樹(shù)中，度為2的節(jié)點(diǎn)有10個(gè)，度為1的節(jié)點(diǎn)有8個(gè)，那么葉子節(jié)點(diǎn)有多少個(gè)？A.9B.10C.11D.1214、以下哪種排序算法對(duì)近乎有序的數(shù)組效果較好？（）A.快速排序B.插入排序C.冒泡排序D.選擇排序15、以下哪個(gè)不是圖的存儲(chǔ)結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.順序表16、以下哪個(gè)算法常用于圖的最短路徑問(wèn)題？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法17、快速排序的樞軸元素選擇對(duì)算法的性能有很大影響，以下哪種選擇方式通常比較好？A.第一個(gè)元素B.最后一個(gè)元素C.中間元素D.隨機(jī)元素18、分治法的基本思想是？A.把大問(wèn)題分解成多個(gè)小問(wèn)題分別求解B.從一個(gè)初始解逐步優(yōu)化得到最終解C.通過(guò)隨機(jī)選擇來(lái)找到最優(yōu)解D.對(duì)問(wèn)題進(jìn)行暴力搜索19、以下哪個(gè)算法可以用于判斷一個(gè)圖是否為連通圖？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.迪杰斯特拉算法D.普里姆算法20、在貪心算法中，一旦做出選擇就（）A.可以更改B.不能更改C.視情況更改D.以上都不是二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）舉例說(shuō)明貪心算法在實(shí)際問(wèn)題中的應(yīng)用。2、（本題10分）闡述堆排序在數(shù)據(jù)頻繁更新場(chǎng)景下的局限性。3、（本題10分）簡(jiǎn)述單調(diào)棧和單調(diào)隊(duì)列的用途。4、（本題10分）分析冒泡排序在不同編程語(yǔ)言中的實(shí)現(xiàn)差異。三、