賀州學院《算法分析與設計基礎實驗語言》2021-2022學年期末試卷

自覺遵守考場紀律如考試作弊此答卷無效密自覺遵守考場紀律如考試作弊此答卷無效密封線第1頁，共3頁賀州學院《算法分析與設計基礎實驗語言》

2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在哈希表中，裝填因子的取值范圍是？A.0到1B.0到正無窮C.負無窮到正無窮D.1到正無窮2、以下哪個不是圖的遍歷算法？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.最短路徑搜索D.拓撲排序3、以下哪個算法可以用于求解字符串的最長回文子串問題？A.貪心算法B.回溯法C.分治法D.動態(tài)規(guī)劃法4、以下哪個不是查找算法？（）A.順序查找B.二分查找C.冒泡排序D.哈希查找5、以下哪個算法可以用于解決0-1背包問題？A.貪心算法B.回溯法C.分治法D.動態(tài)規(guī)劃法6、快速排序的樞軸元素選擇對算法的性能有很大影響，以下哪種選擇方式通常比較好？A.第一個元素B.最后一個元素C.中間元素D.隨機元素7、算法的正確性是指（）A.對于任意輸入都能得到正確結果B.對于大部分輸入能得到正確結果C.對于特定輸入能得到正確結果D.以上都不是8、在分治法中，如果子問題的規(guī)模不相等，可能會（）A.影響算法效率B.提高算法效率C.不影響算法效率D.以上都不是9、分治法的設計步驟不包括以下哪個？A.分解問題B.解決子問題C.合并子問題的解D.隨機選擇子問題10、以下哪個算法常用于字符串匹配？（）A.KMP算法B.冒泡排序C.快速排序D.插入排序11、歸并排序是一種穩(wěn)定的排序算法，它的穩(wěn)定性體現(xiàn)在？A.對于相等的元素，排序前后的相對位置不變B.排序的時間復雜度穩(wěn)定C.排序的空間復雜度穩(wěn)定D.對于不同的輸入，排序結果一致12、分治法的基本思想是？A.把大問題分解成多個小問題分別求解B.從一個初始解逐步優(yōu)化得到最終解C.通過隨機選擇來找到最優(yōu)解D.對問題進行暴力搜索13、動態(tài)規(guī)劃算法通常用于解決具有什么性質的問題？A.最優(yōu)子結構性質和貪心選擇性質B.最優(yōu)子結構性質和重疊子問題性質C.貪心選擇性質和重疊子問題性質D.隨機性質和重疊子問題性質14、以下哪個算法可以用于求解最大子數(shù)組和問題？A.貪心算法B.回溯法C.分治法D.動態(tài)規(guī)劃法15、在算法設計中，降低時間復雜度通常比降低空間復雜度更（）A.容易B.困難C.重要D.不重要16、快速排序的空間復雜度主要取決于？A.遞歸調用的深度B.數(shù)據(jù)的規(guī)模C.樞軸元素的選擇D.排序的穩(wěn)定性17、以下哪種數(shù)據(jù)結構常用于實現(xiàn)棧？（）A.數(shù)組B.鏈表C.樹D.圖18、在算法設計中，如何提高算法的可讀性？A.使用復雜的數(shù)據(jù)結構B.減少注釋和文檔C.采用簡潔明了的代碼風格D.增加算法的時間復雜度19、以下哪個不是動態(tài)規(guī)劃算法的關鍵步驟？（）A.定義狀態(tài)B.找出狀態(tài)轉移方程C.確定初始狀態(tài)D.進行貪心選擇20、快速排序的不穩(wěn)定因素主要來自于什么？A.樞軸元素的選擇B.遞歸調用的深度C.數(shù)據(jù)的規(guī)模D.排序的方向二、簡答題（本大題共4個小題，共40分)1、（本題10分）以圖的最短路徑問題為例，說明動態(tài)規(guī)劃算法的求解思路。2、（本題10分）說明如何用回溯法解決資源分配的公平性問題。3、（本題10分）解釋在電子商務中的推薦和定價算法。4、（本題10分）說明如何用回溯法解決組合問題