浙江工業(yè)大學之江學院《算法分析與設計》2022-2023學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁浙江工業(yè)大學之江學院《算法分析與設計》

2022-2023學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在圖的存儲結構中，鄰接表適合存儲什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖2、算法的穩(wěn)定性對于（）操作較為重要。A.多次排序B.查找C.插入D.刪除3、在回溯法中，當所有可能的選擇都嘗試過后，算法（）A.停止B.繼續(xù)C.重新開始D.以上都不是4、分治法的設計步驟不包括以下哪個？A.分解問題B.解決子問題C.合并子問題的解D.隨機選擇子問題5、以下哪種算法常用于構建最小生成樹？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法6、以下哪個不是算法的評價指標？（）A.正確性B.可讀性C.可擴展性D.代碼長度7、在二叉樹中，度為2的節(jié)點有10個，度為1的節(jié)點有8個，那么葉子節(jié)點有多少個？A.9B.10C.11D.128、歸并排序的基本思想是？A.分而治之，合并有序子序列B.選擇最小元素逐步構建有序序列C.通過交換相鄰元素進行排序D.隨機選擇元素進行排序9、在貪心算法中，最終的解依賴于（）A.子問題的選擇順序B.問題的規(guī)模C.數(shù)據(jù)的分布D.以上都是10、以下哪個數(shù)據(jù)結構常用于實現(xiàn)優(yōu)先隊列？（）A.堆B.棧C.隊列D.鏈表11、在算法設計中，減少算法的常數(shù)因子可以（）A.提高算法效率B.降低算法效率C.不影響算法效率D.以上都不是12、在動態(tài)規(guī)劃中，重疊子問題的性質是指（）A.子問題多次出現(xiàn)B.子問題相互獨立C.子問題具有唯一性D.以上都不是13、以下哪種算法常用于解決皇后問題？（）A.貪心算法B.回溯法C.動態(tài)規(guī)劃D.分治法14、動態(tài)規(guī)劃算法的核心是？A.遞歸B.貪心選擇C.記憶化搜索D.分治15、在圖的遍歷中，廣度優(yōu)先搜索使用的數(shù)據(jù)結構是（）A.棧B.隊列C.鏈表D.樹16、以下哪個不是算法的性能指標？A.正確性B.可讀性C.可擴展性D.美觀性17、以下哪種算法常用于解決裝箱問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法18、以下哪個不是貪心算法的應用場景？A.哈夫曼編碼B.最小生成樹C.背包問題D.矩陣乘法19、在算法設計中，如何提高算法的可讀性？A.使用復雜的數(shù)據(jù)結構B.減少注釋和文檔C.采用簡潔明了的代碼風格D.增加算法的時間復雜度20、在貪心算法中，每一步的選擇都是（）A.全局最優(yōu)B.局部最優(yōu)C.隨機的D.以上都不是二、簡答題（本大題共4個小題，共40分)1、（本題10分）簡述字符串壓縮算法的設計思路。2、（本題10分）解釋插入排序在近乎有序數(shù)組中的性能優(yōu)勢。3、（本題10分）簡述貪心算法在路由表更新中的應用及潛在問題。4、（本題10分）分析算法在智能交通系統(tǒng)中的作用。三、設計題（本大題共2個小題，共20分)1