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

裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)北京工業(yè)大學(xué)《算法設(shè)計(jì)》

2022-2023學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、時(shí)間復(fù)雜度和空間復(fù)雜度需要在設(shè)計(jì)算法時(shí)進(jìn)行（）A.單獨(dú)考慮B.綜合考慮C.先考慮時(shí)間復(fù)雜度D.先考慮空間復(fù)雜度2、在貪心算法中，一旦做出選擇就（）A.可以更改B.不能更改C.視情況更改D.以上都不是3、以下哪個(gè)算法可以用于求解旅行商問(wèn)題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法4、以下哪個(gè)不是圖的遍歷算法？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.最短路徑搜索D.拓?fù)渑判?、分治法的設(shè)計(jì)步驟不包括以下哪個(gè)？A.分解問(wèn)題B.解決子問(wèn)題C.合并子問(wèn)題的解D.隨機(jī)選擇子問(wèn)題6、在算法設(shè)計(jì)中，如何提高算法的可讀性？A.使用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)B.減少注釋和文檔C.采用簡(jiǎn)潔明了的代碼風(fēng)格D.增加算法的時(shí)間復(fù)雜度7、動(dòng)態(tài)規(guī)劃算法通常需要一個(gè)什么來(lái)存儲(chǔ)子問(wèn)題的解？A.數(shù)組B.鏈表C.棧D.隊(duì)列8、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)隊(duì)列的功能？A.數(shù)組B.鏈表C.棧D.二叉樹(shù)9、算法的空間復(fù)雜度是指（）A.算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間B.算法執(zhí)行過(guò)程中所需的平均存儲(chǔ)空間C.算法執(zhí)行過(guò)程中所需的最小存儲(chǔ)空間D.算法執(zhí)行過(guò)程中所需的存儲(chǔ)空間的變化情況10、以下哪個(gè)算法可以用于求解圖的最小生成樹(shù)問(wèn)題？A.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克魯斯卡爾算法11、在圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表適合存儲(chǔ)什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無(wú)向圖12、在分治法中，將問(wèn)題分解成的子問(wèn)題通常具有（）A.不同的規(guī)模B.相同的規(guī)模C.隨機(jī)的規(guī)模D.以上都可能13、以下哪個(gè)算法可以用于判斷一個(gè)圖是否為連通圖？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.迪杰斯特拉算法D.普里姆算法14、動(dòng)態(tài)規(guī)劃算法通常用于解決具有什么性質(zhì)的問(wèn)題？A.最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)B.最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問(wèn)題性質(zhì)C.貪心選擇性質(zhì)和重疊子問(wèn)題性質(zhì)D.隨機(jī)性質(zhì)和重疊子問(wèn)題性質(zhì)15、以下哪個(gè)排序算法是穩(wěn)定的？A.快速排序B.堆排序C.希爾排序D.冒泡排序16、在遞歸算法中，當(dāng)遞歸深度過(guò)大時(shí)可能會(huì)導(dǎo)致（）A.運(yùn)行速度加快B.內(nèi)存溢出C.結(jié)果更準(zhǔn)確D.以上都不是17、以下哪個(gè)算法可以用于解決0-1背包問(wèn)題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法18、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)棧的功能？A.數(shù)組B.鏈表C.隊(duì)列D.二叉樹(shù)19、二分查找算法要求數(shù)據(jù)必須是（）A.有序的B.無(wú)序的C.平衡的D.以上都不是20、以下哪個(gè)不是算法的評(píng)價(jià)指標(biāo)？（）A.正確性B.可讀性C.可擴(kuò)展性D.代碼長(zhǎng)度二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）分析冒泡排序在不同數(shù)據(jù)分布下的性能差異。2、（本題10分）解釋什么是分支限界法，以及它與回溯法的異同。3、（本題10分）比較Dijkstra算法和Floyd算法的適用情況。4、（本題10分）簡(jiǎn)述在數(shù)據(jù)庫(kù)管理中用到的算法。三、設(shè)計(jì)題（本大題共2個(gè)小題，共2