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

裝訂線裝訂線PAGE2第1頁，共3頁青島科技大學(xué)《算法與數(shù)據(jù)結(jié)構(gòu)》

2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪種算法常用于解決凸包問題？（）A.Graham掃描法B.Dijkstra算法C.Prim算法D.Kruskal算法2、以下哪個數(shù)據(jù)結(jié)構(gòu)可以用于實現(xiàn)圖的深度優(yōu)先搜索？A.數(shù)組B.鏈表C.棧D.隊列3、在貪心算法中，每一步的選擇都是（）A.全局最優(yōu)B.局部最優(yōu)C.隨機的D.以上都不是4、快速排序的平均時間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)5、在哈希表中，解決沖突的方法有哪些？A.線性探測法和二次探測法B.鏈地址法和開放定址法C.再哈希法和建立公共溢出區(qū)D.以上都是6、歸并排序的基本思想是？A.分而治之，合并有序子序列B.選擇最小元素逐步構(gòu)建有序序列C.通過交換相鄰元素進行排序D.隨機選擇元素進行排序7、在分治法中，合并子問題的解的時間復(fù)雜度通常為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、以下哪個排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序9、以下哪個不是動態(tài)規(guī)劃算法的關(guān)鍵步驟？A.確定狀態(tài)B.確定狀態(tài)轉(zhuǎn)移方程C.初始化狀態(tài)D.隨機選擇狀態(tài)10、以下哪個算法可以用于求解圖的最小生成樹問題？A.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克魯斯卡爾算法11、以下哪個數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)字典？（）A.哈希表B.二叉樹C.鏈表D.棧12、以下哪個不是貪心算法的特點？（）A.局部最優(yōu)B.整體最優(yōu)C.高效性D.不可回溯13、在圖的存儲結(jié)構(gòu)中，十字鏈表適合存儲什么樣的圖？A.稀疏圖B.稠密圖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、一個算法的時間復(fù)雜度為O(n2)，如果輸入規(guī)模擴大一倍，那么運行時間會變?yōu)樵瓉淼膸妆?？A.2倍B.4倍C.8倍D.16倍16、動態(tài)規(guī)劃算法通常用于解決（）問題。A.最優(yōu)解B.近似解C.隨機解D.無解17、在二叉搜索樹中，查找一個元素的時間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)18、以下哪個算法可以用于求解最大子數(shù)組和問題？A.貪心算法B.回溯法C.分治法D.動態(tài)規(guī)劃法19、時間復(fù)雜度為O(logn)的算法通常比時間復(fù)雜度為O(n)的算法（）A.更慢B.更快C.一樣快D.無法比較20、算法的穩(wěn)定性對于（）操作較為重要。A.多次排序B.查找C.插入D.刪除二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋分布式算法的特點和應(yīng)用領(lǐng)域。2、（本題10分）簡述插入排序在鏈表上的實現(xiàn)方法。3、（本題10分）分析在控制系統(tǒng)中的PID算法。4、（本題10分）簡述搜索算法中的順序搜索和二分搜索的區(qū)別。三、設(shè)計題（本大