裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)南京信息工程大學(xué)《算法》

2023-2024學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在二叉搜索樹中，插入一個(gè)新節(jié)點(diǎn)的時(shí)間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)2、在貪心算法中，一旦做出選擇就（）A.可以更改B.不能更改C.視情況更改D.以上都不是3、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先隊(duì)列？（）A.堆B.棧C.隊(duì)列D.鏈表4、在二叉搜索樹中刪除一個(gè)節(jié)點(diǎn)時(shí)，需要考慮幾種情況？A.1種B.2種C.3種D.4種5、算法分析的主要目的是（）A.評(píng)估算法的性能B.設(shè)計(jì)新算法C.比較不同算法D.以上都是6、空間復(fù)雜度主要考慮（）A.算法執(zhí)行過(guò)程中占用的內(nèi)存空間B.算法執(zhí)行過(guò)程中占用的硬盤空間C.算法執(zhí)行過(guò)程中占用的網(wǎng)絡(luò)帶寬D.以上都是7、以下哪個(gè)算法可以用于求解最大子數(shù)組和問(wèn)題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法8、以下哪種算法常用于解決組合優(yōu)化問(wèn)題？（）A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃9、在哈希表中，當(dāng)發(fā)生沖突時(shí)，可以采用哪種方法來(lái)解決？A.線性探測(cè)法B.二次探測(cè)法C.鏈地址法D.以上都是10、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)隊(duì)列的功能？A.數(shù)組B.鏈表C.棧D.二叉樹11、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)集合的交集、并集和差集等操作？A.數(shù)組B.鏈表C.棧D.哈希表12、以下哪個(gè)排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序13、以下哪個(gè)不是貪心算法的應(yīng)用場(chǎng)景？A.哈夫曼編碼B.最小生成樹C.背包問(wèn)題D.矩陣乘法14、算法的空間復(fù)雜度是指（）A.算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間B.算法執(zhí)行過(guò)程中所需的平均存儲(chǔ)空間C.算法執(zhí)行過(guò)程中所需的最小存儲(chǔ)空間D.算法執(zhí)行過(guò)程中所需的存儲(chǔ)空間的變化情況15、動(dòng)態(tài)規(guī)劃算法的核心是？A.遞歸B.貪心選擇C.記憶化搜索D.分治16、快速排序的樞軸元素選擇對(duì)算法的性能有很大影響，以下哪種選擇方式通常比較好？A.第一個(gè)元素B.最后一個(gè)元素C.中間元素D.隨機(jī)元素17、算法的通用性是指（）A.適用于多種問(wèn)題B.代碼可復(fù)用C.易于理解D.以上都是18、以下哪種算法常用于解決裝箱問(wèn)題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法19、以下哪個(gè)算法可以用于求解旅行商問(wèn)題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法20、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于查找操作？（）A.棧B.隊(duì)列C.二叉搜索樹D.鏈表二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）簡(jiǎn)述快速排序的優(yōu)化技巧（如選取樞軸的方法）。2、（本題10分）闡述堆排序在大規(guī)模數(shù)據(jù)排序中的適用性。3、（本題10分）分析在工業(yè)控制中的優(yōu)化算法。4、（本題10分）解釋在視頻編碼中的壓縮算法。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20分)1