湖南財(cái)政經(jīng)濟(jì)學(xué)院《算法設(shè)計(jì)與分析》2022-2023學(xué)年期末試卷

自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁湖南財(cái)政經(jīng)濟(jì)學(xué)院

《算法設(shè)計(jì)與分析》2022-2023學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在二叉搜索樹中刪除一個(gè)節(jié)點(diǎn)時(shí)，需要考慮幾種情況？A.1種B.2種C.3種D.4種2、以下哪個(gè)算法常用于字符串匹配？（）A.KMP算法B.冒泡排序C.快速排序D.插入排序3、以下哪個(gè)不是圖的遍歷算法？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.最短路徑搜索D.拓?fù)渑判?、以下哪個(gè)不是算法的設(shè)計(jì)方法？A.分治法B.動(dòng)態(tài)規(guī)劃法C.貪心算法D.隨機(jī)猜測(cè)法5、在算法分析中，大O記號(hào)表示的是？A.算法的精確運(yùn)行時(shí)間B.算法的平均運(yùn)行時(shí)間C.算法運(yùn)行時(shí)間的上界D.算法運(yùn)行時(shí)間的下界6、在有向圖中，進(jìn)行深度優(yōu)先搜索時(shí)，需要使用什么數(shù)據(jù)結(jié)構(gòu)來記錄已訪問的頂點(diǎn)？A.數(shù)組B.鏈表C.棧D.隊(duì)列7、以下哪個(gè)不是算法的性能指標(biāo)？A.正確性B.可讀性C.可擴(kuò)展性D.美觀性8、以下哪個(gè)算法可以用于求解旅行商問題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法9、在二叉樹中，后序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹10、以下哪種排序算法在平均情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序11、以下哪個(gè)排序算法在最壞情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.歸并排序D.堆排序12、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)隊(duì)列？（）A.數(shù)組B.鏈表C.棧D.樹13、空間復(fù)雜度為O(1)的算法意味著（）A.不使用額外空間B.使用固定大小的額外空間C.使用少量的額外空間D.以上都不是14、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)集合的交集、并集和差集等操作？A.數(shù)組B.鏈表C.棧D.哈希表15、分治法的基本思想是？A.把大問題分解成多個(gè)小問題分別求解B.從一個(gè)初始解逐步優(yōu)化得到最終解C.通過隨機(jī)選擇來找到最優(yōu)解D.對(duì)問題進(jìn)行暴力搜索16、在圖的存儲(chǔ)結(jié)構(gòu)中，鄰接表適合存儲(chǔ)什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖17、以下哪個(gè)算法可以用于求解最長(zhǎng)遞增子序列問題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法18、動(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ì)19、以下哪種算法的時(shí)間復(fù)雜度最低？（）A.O(n^2)B.O(nlogn)C.O(logn)D.O(n)20、在二叉樹中，度為0的節(jié)點(diǎn)稱為？A.葉子節(jié)點(diǎn)B.根節(jié)點(diǎn)C.內(nèi)部節(jié)點(diǎn)D.分支節(jié)點(diǎn)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）闡述堆排序在有序數(shù)據(jù)插入時(shí)的性能特點(diǎn)。2、（本題10分）分析字符串匹配算法，如BF算法和KMP算法。3、（本題10分）以快速排序算法為例，說明算法的時(shí)間復(fù)雜度分析過程。4、（本題10分）簡(jiǎn)述動(dòng)態(tài)規(guī)劃算法解決矩陣鏈乘法問題的步驟。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20分)1、（本題