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

學(xué)校________________班級____________姓名____________考場____________準考證號學(xué)校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁青島大學(xué)

《算法與數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)棧？（）A.數(shù)組B.鏈表C.樹D.圖2、一個算法的時間復(fù)雜度為O(n2)，如果輸入規(guī)模擴大一倍，那么運行時間會變?yōu)樵瓉淼膸妆?？A.2倍B.4倍C.8倍D.16倍3、以下哪個算法可以用于解決0-1背包問題？A.貪心算法B.回溯法C.分治法D.動態(tài)規(guī)劃法4、在分治法中，如果子問題的規(guī)模不相等，可能會（）A.影響算法效率B.提高算法效率C.不影響算法效率D.以上都不是5、二分查找算法要求數(shù)據(jù)必須是（）A.有序的B.無序的C.平衡的D.以上都不是6、以下哪個數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)優(yōu)先隊列？（）A.堆B.棧C.隊列D.鏈表7、分治法的設(shè)計步驟不包括以下哪個？A.分解問題B.解決子問題C.合并子問題的解D.隨機選擇子問題8、在哈希表中，解決沖突的方法有哪些？A.線性探測法和二次探測法B.鏈地址法和開放定址法C.再哈希法和建立公共溢出區(qū)D.以上都是9、在動態(tài)規(guī)劃中，重疊子問題的性質(zhì)是指（）A.子問題多次出現(xiàn)B.子問題相互獨立C.子問題具有唯一性D.以上都不是10、以下哪個排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序11、在二叉樹中，度為0的節(jié)點稱為？A.葉子節(jié)點B.根節(jié)點C.內(nèi)部節(jié)點D.分支節(jié)點12、以下哪個數(shù)據(jù)結(jié)構(gòu)可以高效地進行插入和刪除操作，并且可以快速地找到最小值？A.數(shù)組B.鏈表C.棧D.堆13、在算法設(shè)計中，降低時間復(fù)雜度通常比降低空間復(fù)雜度更（）A.容易B.困難C.重要D.不重要14、快速排序的樞軸元素選擇對算法的性能有很大影響，以下哪種選擇方式通常比較好？A.第一個元素B.最后一個元素C.中間元素D.隨機元素15、以下哪個數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)隊列？（）A.數(shù)組B.鏈表C.棧D.樹16、在圖的存儲結(jié)構(gòu)中，鄰接表適合存儲什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖17、在圖的深度優(yōu)先搜索中，使用的輔助數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊列C.優(yōu)先隊列D.哈希表18、以下哪個數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)字典？（）A.哈希表B.二叉樹C.鏈表D.棧19、在算法分析中，大O記號表示的是？A.算法的精確運行時間B.算法的平均運行時間C.算法運行時間的上界D.算法運行時間的下界20、在二叉搜索樹中進行查找操作的平均時間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋插入排序在有序和無序數(shù)據(jù)混合時的表現(xiàn)。2、（本題10分）簡述貪心算法在網(wǎng)絡(luò)帶寬分配中的應(yīng)用策略及不足。3、（本題10分）闡述歸并排序在可擴展性方面的特點。4、（本題10分）簡述在能源管理中的調(diào)度算法。三、設(shè)計