仲愷農(nóng)業(yè)工程學(xué)院《算法分析與設(shè)計(jì)》2022-2023學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁仲愷農(nóng)業(yè)工程學(xué)院《算法分析與設(shè)計(jì)》2022-2023學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在回溯法中，當(dāng)所有可能的選擇都嘗試過后，算法（）A.停止B.繼續(xù)C.重新開始D.以上都不是2、在二叉搜索樹中進(jìn)行查找操作的平均時間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)3、算法的空間復(fù)雜度是指（）A.算法執(zhí)行過程中所需的最大存儲空間B.算法執(zhí)行過程中所需的平均存儲空間C.算法執(zhí)行過程中所需的最小存儲空間D.算法執(zhí)行過程中所需的存儲空間的變化情況4、以下哪種算法的時間復(fù)雜度最低？（）A.O(n^2)B.O(nlogn)C.O(logn)D.O(n)5、以下哪種排序算法的平均時間復(fù)雜度為O(nlogn)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序6、以下哪個不是貪心算法的應(yīng)用場景？A.哈夫曼編碼B.最小生成樹C.背包問題D.矩陣乘法7、在分治法中，如果子問題的規(guī)模不相等，可能會（）A.影響算法效率B.提高算法效率C.不影響算法效率D.以上都不是8、以下哪種算法常用于解決皇后問題？（）A.貪心算法B.回溯法C.動態(tài)規(guī)劃D.分治法9、動態(tài)規(guī)劃算法的核心是？A.遞歸B.貪心選擇C.記憶化搜索D.分治10、以下哪個算法常用于圖的最短路徑問題？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法11、快速排序的空間復(fù)雜度主要取決于？A.遞歸調(diào)用的深度B.數(shù)據(jù)的規(guī)模C.樞軸元素的選擇D.排序的穩(wěn)定性12、以下哪種排序算法是穩(wěn)定的？（）A.快速排序B.冒泡排序C.選擇排序D.希爾排序13、分治法的基本思想是？A.把大問題分解成多個小問題分別求解B.從一個初始解逐步優(yōu)化得到最終解C.通過隨機(jī)選擇來找到最優(yōu)解D.對問題進(jìn)行暴力搜索14、二分查找算法要求數(shù)據(jù)必須是（）A.有序的B.無序的C.平衡的D.以上都不是15、以下哪個算法可以用于求解圖的單源最短路徑問題？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.迪杰斯特拉算法D.克魯斯卡爾算法16、以下哪個不是隊(duì)列的基本操作？A.入隊(duì)B.出隊(duì)C.查找D.排序17、以下哪種算法常用于解決凸包問題？（）A.Graham掃描法B.Dijkstra算法C.Prim算法D.Kruskal算法18、以下哪種排序算法在平均情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序19、在二叉搜索樹中，插入一個新節(jié)點(diǎn)的時間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)20、以下哪種算法常用于構(gòu)建最小生成樹？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋選擇排序在元素重復(fù)較多時的表現(xiàn)。2、（本題10分）用動態(tài)規(guī)劃算法解決0-1背包問題。3、（本題10分）簡述在寵物服務(wù)行業(yè)中的健康監(jiān)測和行為分析算法。4、（本題10分）簡述貪心算法在哈夫曼編碼中的應(yīng)用。三、設(shè)計(jì)