保山學院《算法優(yōu)化設計》2021-2022學年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁保山學院《算法優(yōu)化設計》

2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在動態(tài)規(guī)劃中，狀態(tài)轉移方程描述了（）A.不同狀態(tài)之間的關系B.初始狀態(tài)的計算方法C.最優(yōu)解的計算方法D.以上都不是2、以下哪個數(shù)據(jù)結構可以用于實現(xiàn)隊列的功能？A.數(shù)組B.鏈表C.棧D.二叉樹3、在二叉樹中，中序遍歷的順序是？A.根節(jié)點、左子樹、右子樹B.左子樹、根節(jié)點、右子樹C.左子樹、右子樹、根節(jié)點D.右子樹、根節(jié)點、左子樹4、以下哪個算法常用于圖的最短路徑問題？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法5、在分治法中，合并子問題的解的時間復雜度通常為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在貪心算法中，得到的解可能是（）A.最優(yōu)解B.近似最優(yōu)解C.可行解D.以上都可能7、在算法設計中，降低時間復雜度通常比降低空間復雜度更（）A.容易B.困難C.重要D.不重要8、快速排序的遞歸終止條件是什么？A.子數(shù)組長度為0或1B.子數(shù)組長度為2C.子數(shù)組長度為3D.子數(shù)組長度為49、在回溯法中，當所有可能的選擇都嘗試過后，算法（）A.停止B.繼續(xù)C.重新開始D.以上都不是10、以下哪個數(shù)據(jù)結構常用于實現(xiàn)圖？（）A.數(shù)組B.鏈表C.鄰接矩陣和鄰接表D.棧11、歸并排序的基本思想是？A.分而治之，合并有序子序列B.選擇最小元素逐步構建有序序列C.通過交換相鄰元素進行排序D.隨機選擇元素進行排序12、以下哪個算法可以用于求解圖的所有頂點之間的最短路徑問題？A.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克魯斯卡爾算法13、以下哪種排序算法在平均情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序14、在有向圖中，進行深度優(yōu)先搜索時，需要使用什么數(shù)據(jù)結構來記錄已訪問的頂點？A.數(shù)組B.鏈表C.棧D.隊列15、快速排序的不穩(wěn)定因素主要來自于什么？A.樞軸元素的選擇B.遞歸調用的深度C.數(shù)據(jù)的規(guī)模D.排序的方向16、以下哪個數(shù)據(jù)結構可以用于實現(xiàn)圖的深度優(yōu)先搜索？A.數(shù)組B.鏈表C.棧D.隊列17、以下哪個排序算法在最壞情況下的時間復雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序18、在二叉樹中，度為0的節(jié)點稱為？A.葉子節(jié)點B.根節(jié)點C.內部節(jié)點D.分支節(jié)點19、在二叉樹中，前序遍歷的順序是？A.根節(jié)點、左子樹、右子樹B.左子樹、根節(jié)點、右子樹C.左子樹、右子樹、根節(jié)點D.右子樹、根節(jié)點、左子樹20、以下哪種算法常用于構建最小生成樹？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法二、簡答題（本大題共4個小題，共40分)1、（本題10分）簡述貪心算法的基本策略，以及它可能存在的局限性。2、（本題10分）解釋如何根據(jù)性能測試結果進行進一步優(yōu)化。3、（本題10分）分析二分搜索算法的時間復雜度和適用條件。4、（本題10分）分析最小費用流問題的解法。三、