學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁長春大學(xué)《算法分析與設(shè)計》

2022-2023學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)棧？（）A.數(shù)組B.鏈表C.樹D.圖2、以下哪種算法常用于解決凸包問題？（）A.Graham掃描法B.Dijkstra算法C.Prim算法D.Kruskal算法3、在回溯法中，通過（）來避免無效搜索。A.剪枝B.貪心選擇C.動態(tài)規(guī)劃D.分治4、在二叉樹中，度為2的節(jié)點有10個，度為1的節(jié)點有8個，那么葉子節(jié)點有多少個？A.9B.10C.11D.125、以下哪種算法常用于解決活動安排問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法6、在有向圖中，頂點的入度是指？A.以該頂點為起點的邊的數(shù)量B.以該頂點為終點的邊的數(shù)量C.與該頂點相鄰的頂點數(shù)量D.該頂點的度數(shù)7、以下哪個數(shù)據(jù)結(jié)構(gòu)常用于查找操作？（）A.棧B.隊列C.二叉搜索樹D.鏈表8、歸并排序的遞歸實現(xiàn)中，每次將數(shù)組分成兩部分，那么遞歸的深度是多少？A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、以下哪個不是圖的基本操作？A.插入頂點B.刪除頂點C.查找頂點D.排序頂點10、在圖的遍歷中，深度優(yōu)先搜索和廣度優(yōu)先搜索的主要區(qū)別是？A.遍歷的順序不同B.時間復(fù)雜度不同C.空間復(fù)雜度不同D.適用的圖類型不同11、算法的最優(yōu)性是指（）A.時間復(fù)雜度最低B.空間復(fù)雜度最低C.得到的解最優(yōu)D.以上都是12、以下哪個排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序13、算法的正確性是指（）A.對于任意輸入都能得到正確結(jié)果B.對于大部分輸入能得到正確結(jié)果C.對于特定輸入能得到正確結(jié)果D.以上都不是14、在圖的存儲結(jié)構(gòu)中，鄰接矩陣適合存儲什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖15、在哈希表中，裝填因子的取值范圍是？A.0到1B.0到正無窮C.負(fù)無窮到正無窮D.1到正無窮16、以下哪個數(shù)據(jù)結(jié)構(gòu)可以用于實現(xiàn)集合的交集、并集和差集等操作？A.數(shù)組B.鏈表C.棧D.哈希表17、以下哪種排序算法在數(shù)據(jù)量較大時性能較好？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序18、在二叉樹中，后序遍歷的順序是？A.根節(jié)點、左子樹、右子樹B.左子樹、根節(jié)點、右子樹C.左子樹、右子樹、根節(jié)點D.右子樹、根節(jié)點、左子樹19、空間復(fù)雜度為O(1)的算法意味著（）A.不使用額外空間B.使用固定大小的額外空間C.使用少量的額外空間D.以上都不是20、動態(tài)規(guī)劃算法的核心是？A.遞歸B.貪心選擇C.記憶化搜索D.分治二、簡答題（本大題共4個小題，共40分)1、（本題10分）以字符串匹配問題為例，說明動態(tài)規(guī)劃算法的應(yīng)用。2、（本題10分）簡述在移動計算中的節(jié)能算法。3、（本題10分）解釋插入排序算法的工作原理，并比較它與選擇排序的差異。4、（本題10分）解釋插入排序在實時數(shù)據(jù)插入時的特點。三、設(shè)計題