北京工業(yè)大學(xué)《算法設(shè)計(jì)》2021-2022學(xué)年期末試卷

自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線第1頁(yè)，共3頁(yè)北京工業(yè)大學(xué)《算法設(shè)計(jì)》

2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下哪種排序算法對(duì)近乎有序的數(shù)組效果較好？（）A.快速排序B.插入排序C.冒泡排序D.選擇排序2、以下哪個(gè)不是圖的基本操作？A.插入頂點(diǎn)B.刪除頂點(diǎn)C.查找頂點(diǎn)D.排序頂點(diǎn)3、以下哪個(gè)算法可以用于求解圖的最小生成樹(shù)問(wèn)題？A.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克魯斯卡爾算法4、在有向圖中，頂點(diǎn)的入度是指？A.以該頂點(diǎn)為起點(diǎn)的邊的數(shù)量B.以該頂點(diǎn)為終點(diǎn)的邊的數(shù)量C.與該頂點(diǎn)相鄰的頂點(diǎn)數(shù)量D.該頂點(diǎn)的度數(shù)5、在哈希表中，當(dāng)發(fā)生沖突時(shí)，可以采用哪種方法來(lái)解決？A.線性探測(cè)法B.二次探測(cè)法C.鏈地址法D.以上都是6、歸并排序的合并操作的時(shí)間復(fù)雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)7、以下哪個(gè)算法可以用于求解最大子數(shù)組和問(wèn)題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法8、算法的穩(wěn)定性對(duì)于（）操作較為重要。A.多次排序B.查找C.插入D.刪除9、以下哪個(gè)排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序10、在有向無(wú)環(huán)圖中，進(jìn)行拓?fù)渑判虻臅r(shí)間復(fù)雜度是？A.O(1)B.O(n)C.O(nlogn)D.O(n2)11、算法的最優(yōu)性是指（）A.時(shí)間復(fù)雜度最低B.空間復(fù)雜度最低C.得到的解最優(yōu)D.以上都是12、在遞歸算法中，當(dāng)遞歸深度過(guò)大時(shí)可能會(huì)導(dǎo)致（）A.運(yùn)行速度加快B.內(nèi)存溢出C.結(jié)果更準(zhǔn)確D.以上都不是13、在圖的深度優(yōu)先搜索中，使用的輔助數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊(duì)列C.優(yōu)先隊(duì)列D.哈希表14、在貪心算法中，最終的解依賴于（）A.子問(wèn)題的選擇順序B.問(wèn)題的規(guī)模C.數(shù)據(jù)的分布D.以上都是15、以下哪種算法常用于解決旅行商問(wèn)題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.模擬退火算法16、快速排序的樞軸元素選擇對(duì)算法的性能有很大影響，以下哪種選擇方式通常比較好？A.第一個(gè)元素B.最后一個(gè)元素C.中間元素D.隨機(jī)元素17、以下哪個(gè)算法可以用于求解圖的單源最短路徑問(wèn)題？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.迪杰斯特拉算法D.克魯斯卡爾算法18、在哈希表中，解決沖突的方法有哪些？A.線性探測(cè)法和二次探測(cè)法B.鏈地址法和開(kāi)放定址法C.再哈希法和建立公共溢出區(qū)D.以上都是19、在貪心算法中，得到的解可能是（）A.最優(yōu)解B.近似最優(yōu)解C.可行解D.以上都可能20、以下哪種算法常用于解決活動(dòng)安排問(wèn)題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）分析在藝術(shù)創(chuàng)作中的生成算法。2、（本題10分）簡(jiǎn)述分治法的基本思想，并舉例說(shuō)明其在算法設(shè)計(jì)中的應(yīng)用。3、（本題10分）闡述堆排序在大規(guī)模數(shù)據(jù)排序中的適用性。4、（本題10分）以最長(zhǎng)回文子串問(wèn)題為例，說(shuō)明動(dòng)態(tài)規(guī)劃算法的解法。三、設(shè)計(jì)題（本大題共