湖南工商大學《算法設計與分析》2022-2023學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁湖南工商大學《算法設計與分析》

2022-2023學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在二叉搜索樹中刪除一個節(jié)點時，需要考慮幾種情況？A.1種B.2種C.3種D.4種2、時間復雜度為O(n)的算法，其執(zhí)行時間與輸入規(guī)模n的關系是（）A.線性增長B.指數(shù)增長C.對數(shù)增長D.不變3、在貪心算法中，如果局部最優(yōu)解不能導致全局最優(yōu)解，該算法（）A.仍然有效B.無效C.可能有效D.以上都不是4、以下哪個不是動態(tài)規(guī)劃算法的優(yōu)點？A.高效性B.準確性C.通用性D.簡單性5、遞歸算法的基本思想是（）A.自頂向下分解B.自底向上計算C.不斷重復相同操作D.調用自身函數(shù)6、以下哪個不是貪心算法的應用場景？A.哈夫曼編碼B.最小生成樹C.背包問題D.矩陣乘法7、在二叉樹中，度為0的節(jié)點稱為？A.葉子節(jié)點B.根節(jié)點C.內部節(jié)點D.分支節(jié)點8、在回溯法中，通過（）來避免無效搜索。A.剪枝B.貪心選擇C.動態(tài)規(guī)劃D.分治9、在動態(tài)規(guī)劃中，優(yōu)化子問題的解存儲方式可以（）A.降低時間復雜度B.降低空間復雜度C.提高可讀性D.以上都是10、以下哪種算法常用于解決資源分配問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法11、以下哪種數(shù)據(jù)結構常用于實現(xiàn)棧？（）A.數(shù)組B.鏈表C.樹D.圖12、在二叉樹中，后序遍歷的順序是？A.根節(jié)點、左子樹、右子樹B.左子樹、根節(jié)點、右子樹C.左子樹、右子樹、根節(jié)點D.右子樹、根節(jié)點、左子樹13、算法的空間復雜度是指（）A.算法執(zhí)行過程中所需的最大存儲空間B.算法執(zhí)行過程中所需的平均存儲空間C.算法執(zhí)行過程中所需的最小存儲空間D.算法執(zhí)行過程中所需的存儲空間的變化情況14、歸并排序的遞歸實現(xiàn)中，每次將數(shù)組分成兩部分，那么遞歸的深度是多少？A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、快速排序的平均時間復雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)16、以下哪個不是動態(tài)規(guī)劃算法的關鍵步驟？A.確定狀態(tài)B.確定狀態(tài)轉移方程C.初始化狀態(tài)D.隨機選擇狀態(tài)17、空間復雜度為O(1)的算法意味著（）A.不使用額外空間B.使用固定大小的額外空間C.使用少量的額外空間D.以上都不是18、以下哪個不是圖的存儲結構？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.順序表19、動態(tài)規(guī)劃算法通常用于解決（）問題。A.最優(yōu)解B.近似解C.隨機解D.無解20、在算法分析中，大O記號表示的是？A.算法的精確運行時間B.算法的平均運行時間C.算法運行時間的上界D.算法運行時間的下界二、簡答題（本大題共4個小題，共40分)1、（本題10分）以最大子段和問題為例，說明動態(tài)規(guī)劃算法的求解思路。2、（本題10分）解釋在虛擬現(xiàn)實中的渲染算法。3、（本題10分）分析遞歸算法的優(yōu)缺點，并說明在什么情況下適合使用遞歸。4、（本題10分）簡述快速排序的優(yōu)化技巧（如選取樞軸的方法）。三、設