鹽城師范學(xué)院《算法實現(xiàn)訓(xùn)練》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁鹽城師范學(xué)院《算法實現(xiàn)訓(xùn)練》

2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪個不是圖的遍歷算法？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.最短路徑搜索D.拓?fù)渑判?、算法的可維護(hù)性是指（）A.易于修改和擴(kuò)展B.運行速度快C.占用資源少D.以上都是3、以下哪個算法可以用于求解圖的單源最短路徑問題？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.迪杰斯特拉算法D.克魯斯卡爾算法4、以下哪個不是動態(tài)規(guī)劃算法的應(yīng)用場景？A.資源分配問題B.背包問題C.圖的遍歷問題D.矩陣鏈乘法問題5、以下哪個排序算法在最壞情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.歸并排序D.堆排序6、在遞歸算法中，當(dāng)遞歸深度過大時可能會導(dǎo)致（）A.運行速度加快B.內(nèi)存溢出C.結(jié)果更準(zhǔn)確D.以上都不是7、以下哪個算法可以用于求解字符串的最長回文子串問題？A.貪心算法B.回溯法C.分治法D.動態(tài)規(guī)劃法8、動態(tài)規(guī)劃算法通常需要一個什么來存儲子問題的解？A.數(shù)組B.鏈表C.棧D.隊列9、在圖的遍歷中，深度優(yōu)先搜索和廣度優(yōu)先搜索的主要區(qū)別是？A.遍歷的順序不同B.時間復(fù)雜度不同C.空間復(fù)雜度不同D.適用的圖類型不同10、以下哪個算法常用于圖的最短路徑問題？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法11、在算法設(shè)計中，降低時間復(fù)雜度通常比降低空間復(fù)雜度更（）A.容易B.困難C.重要D.不重要12、在哈希表中，當(dāng)發(fā)生沖突時，可以采用哪種方法來解決？A.線性探測法B.二次探測法C.鏈地址法D.以上都是13、以下哪種算法常用于解決最大子數(shù)組問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法14、算法的正確性是指（）A.對于任意輸入都能得到正確結(jié)果B.對于大部分輸入能得到正確結(jié)果C.對于特定輸入能得到正確結(jié)果D.以上都不是15、在二叉搜索樹中進(jìn)行查找操作的平均時間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)16、以下哪個不是圖的存儲結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.順序表17、一個算法的時間復(fù)雜度為O(n2)，如果輸入規(guī)模擴(kuò)大一倍，那么運行時間會變?yōu)樵瓉淼膸妆?？A.2倍B.4倍C.8倍D.16倍18、在二叉樹中，度為0的節(jié)點稱為？A.葉子節(jié)點B.根節(jié)點C.內(nèi)部節(jié)點D.分支節(jié)點19、以下哪個不是動態(tài)規(guī)劃算法的關(guān)鍵步驟？（）A.定義狀態(tài)B.找出狀態(tài)轉(zhuǎn)移方程C.確定初始狀態(tài)D.進(jìn)行貪心選擇20、以下哪個不是動態(tài)規(guī)劃算法的優(yōu)點？A.高效性B.準(zhǔn)確性C.通用性D.簡單性二、簡答題（本大題共4個小題，共40分)1、（本題10分）說明如何用回溯法解決不等式組求解問題。2、（本題10分）分析二分搜索算法的時間復(fù)雜度和適用條件。3、（本題10分）解釋算法在操作系統(tǒng)中的應(yīng)用。4、（本題10分）簡述在出版行業(yè)中的排版和校對算法。三、設(shè)計題（本大題共2