裝訂線裝訂線PAGE2第1頁，共3頁湖北工業(yè)大學(xué)

《算法分析與設(shè)計(jì)》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、以下哪個(gè)排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序3、以下哪個(gè)不是算法的評(píng)價(jià)指標(biāo)？（）A.正確性B.可讀性C.可擴(kuò)展性D.代碼長(zhǎng)度4、以下哪種排序算法在平均情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序5、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)棧的功能？A.數(shù)組B.鏈表C.隊(duì)列D.二叉樹6、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖？（）A.數(shù)組B.鏈表C.鄰接矩陣和鄰接表D.棧7、以下關(guān)于算法復(fù)雜度的說法中，錯(cuò)誤的是？A.時(shí)間復(fù)雜度是指算法執(zhí)行所需的時(shí)間B.空間復(fù)雜度是指算法執(zhí)行所需的存儲(chǔ)空間C.算法的時(shí)間復(fù)雜度和空間復(fù)雜度可以相互獨(dú)立D.算法的時(shí)間復(fù)雜度總是小于空間復(fù)雜度8、在圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表適合存儲(chǔ)什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖9、分治法的基本思想是？A.把大問題分解成多個(gè)小問題分別求解B.從一個(gè)初始解逐步優(yōu)化得到最終解C.通過隨機(jī)選擇來找到最優(yōu)解D.對(duì)問題進(jìn)行暴力搜索10、以下哪個(gè)不是貪心算法的局限性？A.不一定能得到全局最優(yōu)解B.算法的時(shí)間復(fù)雜度較高C.對(duì)問題的性質(zhì)有一定要求D.難以證明算法的正確性11、快速排序在最好情況下的時(shí)間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)12、以下哪種排序算法對(duì)近乎有序的數(shù)組效果較好？（）A.快速排序B.插入排序C.冒泡排序D.選擇排序13、在動(dòng)態(tài)規(guī)劃中，優(yōu)化子問題的解存儲(chǔ)方式可以（）A.降低時(shí)間復(fù)雜度B.降低空間復(fù)雜度C.提高可讀性D.以上都是14、在圖的遍歷中，廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊(duì)列C.鏈表D.樹15、快速排序的樞軸元素選擇對(duì)算法的性能有很大影響，以下哪種選擇方式通常比較好？A.第一個(gè)元素B.最后一個(gè)元素C.中間元素D.隨機(jī)元素16、以下哪個(gè)不是貪心算法的基本要素？A.貪心選擇性質(zhì)B.最優(yōu)子結(jié)構(gòu)性質(zhì)C.重疊子問題性質(zhì)D.無后效性17、以下哪個(gè)排序算法在最壞情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.歸并排序D.堆排序18、以下哪種算法常用于解決數(shù)獨(dú)問題？（）A.貪心算法B.回溯法C.動(dòng)態(tài)規(guī)劃D.分治法19、算法的空間復(fù)雜度是指（）A.算法執(zhí)行過程中所需的最大存儲(chǔ)空間B.算法執(zhí)行過程中所需的平均存儲(chǔ)空間C.算法執(zhí)行過程中所需的最小存儲(chǔ)空間D.算法執(zhí)行過程中所需的存儲(chǔ)空間的變化情況20、在哈希表中，解決沖突的方法有哪些？A.線性探測(cè)法和二次探測(cè)法B.鏈地址法和開放定址法C.再哈希法和建立公共溢出區(qū)D.以上都是二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）簡(jiǎn)述B樹和B+樹的結(jié)構(gòu)和應(yīng)用場(chǎng)景。2、（本題10分）解釋如何處理邊界情況和特殊輸入。3、（本題10分）闡述如何用分支限界法解決裝箱問題。4、（本題10分）解釋插入排序在不同操作系統(tǒng)中的性能差異原因。三、設(shè)計(jì)題（本大題共2個(gè)小題，共2