北方民族大學(xué)《算法設(shè)計(jì)》2022-2023學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁北方民族大學(xué)

《算法設(shè)計(jì)》2022-2023學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在動(dòng)態(tài)規(guī)劃中，重疊子問題的性質(zhì)是指（）A.子問題多次出現(xiàn)B.子問題相互獨(dú)立C.子問題具有唯一性D.以上都不是2、分治法的設(shè)計(jì)步驟不包括以下哪個(gè)？A.分解問題B.解決子問題C.合并子問題的解D.隨機(jī)選擇子問題3、在有向無環(huán)圖中，進(jìn)行拓?fù)渑判虻臅r(shí)間復(fù)雜度是？A.O(1)B.O(n)C.O(nlogn)D.O(n2)4、在貪心算法中，一旦做出選擇就（）A.可以更改B.不能更改C.視情況更改D.以上都不是5、動(dòng)態(tài)規(guī)劃算法通常用于解決（）問題。A.最優(yōu)解B.近似解C.隨機(jī)解D.無解6、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)隊(duì)列的功能？A.數(shù)組B.鏈表C.棧D.二叉樹7、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)圖的深度優(yōu)先搜索？A.數(shù)組B.鏈表C.棧D.隊(duì)列8、歸并排序的遞歸實(shí)現(xiàn)中，每次將數(shù)組分成兩部分，那么遞歸的深度是多少？A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、歸并排序的空間復(fù)雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)10、以下哪個(gè)排序算法在最壞情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.歸并排序D.堆排序11、時(shí)間復(fù)雜度和空間復(fù)雜度之間通常存在（）A.正相關(guān)關(guān)系B.負(fù)相關(guān)關(guān)系C.沒有關(guān)系D.不確定的關(guān)系12、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字典？（）A.哈希表B.二叉樹C.鏈表D.棧13、在圖的遍歷中，廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊(duì)列C.鏈表D.樹14、在哈希表中，哈希函數(shù)的作用是？A.確定元素在表中的存儲(chǔ)位置B.解決沖突C.提高查找效率D.減少存儲(chǔ)空間15、算法的通用性是指（）A.適用于多種問題B.代碼可復(fù)用C.易于理解D.以上都是16、在二叉樹中，度為2的節(jié)點(diǎn)有10個(gè)，度為1的節(jié)點(diǎn)有8個(gè)，那么葉子節(jié)點(diǎn)有多少個(gè)？A.9B.10C.11D.1217、快速排序的遞歸終止條件是什么？A.子數(shù)組長(zhǎng)度為0或1B.子數(shù)組長(zhǎng)度為2C.子數(shù)組長(zhǎng)度為3D.子數(shù)組長(zhǎng)度為418、以下哪個(gè)不是圖的存儲(chǔ)結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.順序表19、以下哪種算法常用于解決最大子數(shù)組問題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法20、時(shí)間復(fù)雜度為O(n)的算法，其執(zhí)行時(shí)間與輸入規(guī)模n的關(guān)系是（）A.線性增長(zhǎng)B.指數(shù)增長(zhǎng)C.對(duì)數(shù)增長(zhǎng)D.不變二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）簡(jiǎn)述貪心算法在任務(wù)調(diào)度問題中的應(yīng)用。2、（本題10分）說明如何用回溯法解決組合優(yōu)化的約束滿足問題。3、（本題10分）簡(jiǎn)述如何在機(jī)器學(xué)習(xí)中選擇合適的算法。4、（本題10分）簡(jiǎn)述貪心算法在任務(wù)優(yōu)先級(jí)排序中的應(yīng)用及可能的偏差。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20分)1、（本題1