學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁衡陽師范學(xué)院《算法設(shè)計與分析》

2022-2023學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、算法分析的主要目的是（）A.評估算法的性能B.設(shè)計新算法C.比較不同算法D.以上都是2、以下哪個不是貪心算法的特點？（）A.局部最優(yōu)B.整體最優(yōu)C.高效性D.不可回溯3、在圖的存儲結(jié)構(gòu)中，十字鏈表適合存儲什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖4、以下哪個不是貪心算法的應(yīng)用場景？A.哈夫曼編碼B.最小生成樹C.背包問題D.矩陣乘法5、以下哪個不是動態(tài)規(guī)劃算法的關(guān)鍵步驟？A.確定狀態(tài)B.確定狀態(tài)轉(zhuǎn)移方程C.初始化狀態(tài)D.隨機選擇狀態(tài)6、快速排序的不穩(wěn)定因素主要來自于什么？A.樞軸元素的選擇B.遞歸調(diào)用的深度C.數(shù)據(jù)的規(guī)模D.排序的方向7、以下哪個排序算法是穩(wěn)定的？A.快速排序B.堆排序C.希爾排序D.冒泡排序8、以下哪種算法常用于解決旅行商問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.模擬退火算法9、在動態(tài)規(guī)劃中，重疊子問題的性質(zhì)是指（）A.子問題多次出現(xiàn)B.子問題相互獨立C.子問題具有唯一性D.以上都不是10、在算法設(shè)計中，降低時間復(fù)雜度通常比降低空間復(fù)雜度更（）A.容易B.困難C.重要D.不重要11、以下哪個數(shù)據(jù)結(jié)構(gòu)可以用于實現(xiàn)集合的交集、并集和差集等操作？A.數(shù)組B.鏈表C.棧D.哈希表12、以下哪個不是算法的設(shè)計方法？A.分治法B.動態(tài)規(guī)劃法C.貪心算法D.隨機猜測法13、以下哪種算法常用于解決裝箱問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法14、時間復(fù)雜度和空間復(fù)雜度需要在設(shè)計算法時進(jìn)行（）A.單獨考慮B.綜合考慮C.先考慮時間復(fù)雜度D.先考慮空間復(fù)雜度15、算法的復(fù)雜度分析不包括（）A.時間復(fù)雜度B.空間復(fù)雜度C.代碼復(fù)雜度D.平均復(fù)雜度16、在哈希表中，解決沖突的方法有哪些？A.線性探測法和二次探測法B.鏈地址法和開放定址法C.再哈希法和建立公共溢出區(qū)D.以上都是17、以下哪種算法常用于解決背包問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法18、在有向圖中，頂點的入度是指？A.以該頂點為起點的邊的數(shù)量B.以該頂點為終點的邊的數(shù)量C.與該頂點相鄰的頂點數(shù)量D.該頂點的度數(shù)19、以下哪種算法常用于解決最大子數(shù)組問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法20、以下哪種算法常用于解決數(shù)獨問題？（）A.貪心算法B.回溯法C.動態(tài)規(guī)劃D.分治法二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋選擇排序的改進(jìn)方向和潛在可能性。2、（本題10分）解釋插入排序在大規(guī)模數(shù)據(jù)處理中的局限性。3、（本題10分）以最長回文子串問題為例，說明動態(tài)規(guī)劃算法的解法。4、（本題10分）解釋紅黑樹的性質(zhì)和插入、刪除操作。三、設(shè)計題（本大題共2