渤海大學(xué)《算法與數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁渤海大學(xué)

《算法與數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、動(dòng)態(tài)規(guī)劃算法的核心是？A.遞歸B.貪心選擇C.記憶化搜索D.分治2、空間復(fù)雜度主要考慮（）A.算法執(zhí)行過程中占用的內(nèi)存空間B.算法執(zhí)行過程中占用的硬盤空間C.算法執(zhí)行過程中占用的網(wǎng)絡(luò)帶寬D.以上都是3、以下哪個(gè)算法常用于圖的最短路徑問題？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法4、以下哪種排序算法在平均情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序5、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)隊(duì)列？（）A.數(shù)組B.鏈表C.棧D.樹6、在哈希表中，裝填因子的取值范圍是？A.0到1B.0到正無窮C.負(fù)無窮到正無窮D.1到正無窮7、以下哪個(gè)不是隊(duì)列的基本操作？A.入隊(duì)B.出隊(duì)C.查找D.排序8、算法的可維護(hù)性是指（）A.易于修改和擴(kuò)展B.運(yùn)行速度快C.占用資源少D.以上都是9、在動(dòng)態(tài)規(guī)劃中，優(yōu)化子問題的解存儲(chǔ)方式可以（）A.降低時(shí)間復(fù)雜度B.降低空間復(fù)雜度C.提高可讀性D.以上都是10、在二叉樹中，中序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹11、時(shí)間復(fù)雜度為O(logn)的算法通常比時(shí)間復(fù)雜度為O(n)的算法（）A.更慢B.更快C.一樣快D.無法比較12、以下哪個(gè)不是動(dòng)態(tài)規(guī)劃算法的應(yīng)用場(chǎng)景？A.資源分配問題B.背包問題C.圖的遍歷問題D.矩陣鏈乘法問題13、動(dòng)態(tài)規(guī)劃算法通常用于解決具有什么性質(zhì)的問題？A.最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)B.最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題性質(zhì)C.貪心選擇性質(zhì)和重疊子問題性質(zhì)D.隨機(jī)性質(zhì)和重疊子問題性質(zhì)14、快速排序算法在最壞情況下的時(shí)間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)15、在算法設(shè)計(jì)中，如何提高算法的可讀性？A.使用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)B.減少注釋和文檔C.采用簡(jiǎn)潔明了的代碼風(fēng)格D.增加算法的時(shí)間復(fù)雜度16、在算法分析中，大O記號(hào)表示的是？A.算法的精確運(yùn)行時(shí)間B.算法的平均運(yùn)行時(shí)間C.算法運(yùn)行時(shí)間的上界D.算法運(yùn)行時(shí)間的下界17、在哈希表中，哈希函數(shù)的作用是？A.確定元素在表中的存儲(chǔ)位置B.解決沖突C.提高查找效率D.減少存儲(chǔ)空間18、以下哪個(gè)算法可以用于求解旅行商問題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法19、快速排序的樞軸元素選擇對(duì)算法的性能有很大影響，以下哪種選擇方式通常比較好？A.第一個(gè)元素B.最后一個(gè)元素C.中間元素D.隨機(jī)元素20、二分查找算法要求數(shù)據(jù)必須是（）A.有序的B.無序的C.平衡的D.以上都不是二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）說明如何用回溯法解決排課問題。2、（本題10分）說明如何用分支限界法解決資源分配的成本最小化問題。3、（本題10分）闡述歸并排序在分布式系統(tǒng)中的應(yīng)用。4、（本題10分）分析快速排序的最壞情況如何避免。三、設(shè)計(jì)題（本大題