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

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

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