青島科技大學(xué)《算法設(shè)計與分析》2023-2024學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁青島科技大學(xué)

《算法設(shè)計與分析》2023-2024學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、動態(tài)規(guī)劃算法通常用于解決（）問題。A.最優(yōu)解B.近似解C.隨機解D.無解2、動態(tài)規(guī)劃算法通常需要一個什么來存儲子問題的解？A.數(shù)組B.鏈表C.棧D.隊列3、在圖的存儲結(jié)構(gòu)中，十字鏈表適合存儲什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖4、算法的通用性是指（）A.適用于多種問題B.代碼可復(fù)用C.易于理解D.以上都是5、在有向圖中，進行深度優(yōu)先搜索時，需要使用什么數(shù)據(jù)結(jié)構(gòu)來記錄已訪問的頂點？A.數(shù)組B.鏈表C.棧D.隊列6、在有向圖中，頂點的入度是指？A.以該頂點為起點的邊的數(shù)量B.以該頂點為終點的邊的數(shù)量C.與該頂點相鄰的頂點數(shù)量D.該頂點的度數(shù)7、以下哪個數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)隊列？（）A.數(shù)組B.鏈表C.棧D.樹8、歸并排序的空間復(fù)雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)9、以下哪個數(shù)據(jù)結(jié)構(gòu)可以用于實現(xiàn)集合的交集、并集和差集等操作？A.數(shù)組B.鏈表C.棧D.哈希表10、動態(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ì)11、以下哪個數(shù)據(jù)結(jié)構(gòu)可以用于實現(xiàn)圖的深度優(yōu)先搜索？A.數(shù)組B.鏈表C.棧D.隊列12、以下哪種算法常用于解決裝箱問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法13、在動態(tài)規(guī)劃中，狀態(tài)轉(zhuǎn)移方程描述了（）A.不同狀態(tài)之間的關(guān)系B.初始狀態(tài)的計算方法C.最優(yōu)解的計算方法D.以上都不是14、算法的最優(yōu)性是指（）A.時間復(fù)雜度最低B.空間復(fù)雜度最低C.得到的解最優(yōu)D.以上都是15、以下哪個不是貪心算法的局限性？A.不一定能得到全局最優(yōu)解B.算法的時間復(fù)雜度較高C.對問題的性質(zhì)有一定要求D.難以證明算法的正確性16、在動態(tài)規(guī)劃中，重疊子問題的性質(zhì)是指（）A.子問題多次出現(xiàn)B.子問題相互獨立C.子問題具有唯一性D.以上都不是17、在算法分析中，大O記號表示的是？A.算法的精確運行時間B.算法的平均運行時間C.算法運行時間的上界D.算法運行時間的下界18、以下哪個不是動態(tài)規(guī)劃算法的應(yīng)用場景？A.資源分配問題B.背包問題C.圖的遍歷問題D.矩陣鏈乘法問題19、快速排序的平均時間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)20、以下哪種算法常用于解決最大子數(shù)組問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋在視頻編碼中的壓縮算法。2、（本題10分）簡述貪心算法在數(shù)據(jù)庫查詢優(yōu)化中的應(yīng)用思路。3、（本題10分）分析冒泡排序在數(shù)據(jù)基本有序時的效率提升。4、（本題10分）分析如何通過預(yù)處理提高算法效率。三、設(shè)計題（本大題共2個小題，共20分)1、（