學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁吉林大學(xué)

《算法與數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在圖的遍歷中，廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊(duì)列C.鏈表D.樹2、歸并排序的合并操作的時間復(fù)雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)3、以下哪個排序算法在最壞情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.歸并排序D.堆排序4、在二叉搜索樹中，查找一個元素的時間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)5、以下哪個不是動態(tài)規(guī)劃算法的關(guān)鍵步驟？A.確定狀態(tài)B.確定狀態(tài)轉(zhuǎn)移方程C.初始化狀態(tài)D.隨機(jī)選擇狀態(tài)6、算法的復(fù)雜度分析不包括（）A.時間復(fù)雜度B.空間復(fù)雜度C.代碼復(fù)雜度D.平均復(fù)雜度7、在二叉搜索樹中刪除一個節(jié)點(diǎn)時，需要考慮幾種情況？A.1種B.2種C.3種D.4種8、在動態(tài)規(guī)劃中，通過保存子問題的解來避免（）A.重復(fù)計算B.錯誤計算C.遺漏計算D.以上都是9、以下哪個不是圖的遍歷算法？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.最短路徑搜索D.拓?fù)渑判?0、算法的穩(wěn)定性對于（）操作較為重要。A.多次排序B.查找C.插入D.刪除11、以下哪種算法常用于解決資源分配問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法12、以下哪種排序算法在平均情況下時間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.快速排序13、時間復(fù)雜度和空間復(fù)雜度需要在設(shè)計算法時進(jìn)行（）A.單獨(dú)考慮B.綜合考慮C.先考慮時間復(fù)雜度D.先考慮空間復(fù)雜度14、以下哪種算法常用于解決活動安排問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法15、在動態(tài)規(guī)劃中，狀態(tài)轉(zhuǎn)移方程描述了（）A.不同狀態(tài)之間的關(guān)系B.初始狀態(tài)的計算方法C.最優(yōu)解的計算方法D.以上都不是16、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)棧？（）A.數(shù)組B.鏈表C.樹D.圖17、以下哪種算法常用于構(gòu)建最小生成樹？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法18、二分查找算法要求數(shù)據(jù)必須是（）A.有序的B.無序的C.平衡的D.以上都不是19、以下哪個不是查找算法？（）A.順序查找B.二分查找C.冒泡排序D.哈希查找20、在二叉搜索樹中，插入一個新節(jié)點(diǎn)的時間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)二、簡答題（本大題共4個小題，共40分)1、（本題10分）如何分析一個算法的時間復(fù)雜度？2、（本題10分）比較深度優(yōu)先搜索和廣度優(yōu)先搜索的適用場景。3、（本題10分）闡述基數(shù)排序算法的基本原理和適用場景。4、（本題10分）簡述在交通運(yùn)輸中的流量預(yù)測和路線規(guī)劃算法。三、設(shè)計題（本