淮北師范大學(xué)《算法設(shè)計(jì)與分析課程設(shè)計(jì)》2021-2022學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)淮北師范大學(xué)

《算法設(shè)計(jì)與分析課程設(shè)計(jì)》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、歸并排序的空間復(fù)雜度主要取決于什么？A.數(shù)據(jù)的規(guī)模B.遞歸調(diào)用的深度C.合并操作的次數(shù)D.數(shù)據(jù)的類型2、空間復(fù)雜度主要考慮（）A.算法執(zhí)行過(guò)程中占用的內(nèi)存空間B.算法執(zhí)行過(guò)程中占用的硬盤空間C.算法執(zhí)行過(guò)程中占用的網(wǎng)絡(luò)帶寬D.以上都是3、時(shí)間復(fù)雜度為O(logn)的算法通常比時(shí)間復(fù)雜度為O(n)的算法（）A.更慢B.更快C.一樣快D.無(wú)法比較4、以下哪個(gè)不是圖的存儲(chǔ)結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.順序表5、在算法設(shè)計(jì)中，減少算法的常數(shù)因子可以（）A.提高算法效率B.降低算法效率C.不影響算法效率D.以上都不是6、空間復(fù)雜度為O(1)的算法意味著（）A.不使用額外空間B.使用固定大小的額外空間C.使用少量的額外空間D.以上都不是7、在貪心算法中，得到的解可能是（）A.最優(yōu)解B.近似最優(yōu)解C.可行解D.以上都可能8、以下哪種排序算法在平均情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序9、在圖的遍歷中，廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊(duì)列C.鏈表D.樹(shù)10、在回溯法中，當(dāng)所有可能的選擇都嘗試過(guò)后，算法（）A.停止B.繼續(xù)C.重新開(kāi)始D.以上都不是11、在二叉搜索樹(shù)中，查找一個(gè)元素的時(shí)間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)12、在哈希表中，裝填因子的取值范圍是？A.0到1B.0到正無(wú)窮C.負(fù)無(wú)窮到正無(wú)窮D.1到正無(wú)窮13、在圖的深度優(yōu)先搜索中，使用的輔助數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊(duì)列C.優(yōu)先隊(duì)列D.哈希表14、以下哪個(gè)算法常用于圖的最短路徑問(wèn)題？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法15、以下哪個(gè)不是貪心算法的基本要素？A.貪心選擇性質(zhì)B.最優(yōu)子結(jié)構(gòu)性質(zhì)C.重疊子問(wèn)題性質(zhì)D.無(wú)后效性16、以下哪個(gè)不是查找算法？（）A.順序查找B.二分查找C.冒泡排序D.哈希查找17、以下哪個(gè)排序算法的空間復(fù)雜度最低？（）A.冒泡排序B.插入排序C.選擇排序D.歸并排序18、以下哪個(gè)不是貪心算法的應(yīng)用場(chǎng)景？A.哈夫曼編碼B.最小生成樹(shù)C.背包問(wèn)題D.矩陣乘法19、以下哪個(gè)算法可以用于求解最長(zhǎng)遞增子序列問(wèn)題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法20、以下哪個(gè)算法可以用于求解字符串的最長(zhǎng)回文子串問(wèn)題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）闡述堆排序在實(shí)時(shí)數(shù)據(jù)處理中的優(yōu)勢(shì)。2、（本題10分）闡述歸并排序在外部排序中的應(yīng)用。3、（本題10分）解釋選擇排序在元素重復(fù)較多時(shí)的表現(xiàn)。4、（本題10分）說(shuō)明如何用分支限界法解決資源均衡分配問(wèn)題。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20分)1、（本題10