賀州學(xué)院《算法分析與設(shè)計(jì)基礎(chǔ)實(shí)驗(yàn)語言》2021-2022學(xué)年期末試卷

自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁賀州學(xué)院《算法分析與設(shè)計(jì)基礎(chǔ)實(shí)驗(yàn)語言》

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