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

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

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