成都大學(xué)《算法設(shè)計(jì)》2022-2023學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)成都大學(xué)《算法設(shè)計(jì)》

2022-2023學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、快速排序的遞歸終止條件是什么？A.子數(shù)組長(zhǎng)度為0或1B.子數(shù)組長(zhǎng)度為2C.子數(shù)組長(zhǎng)度為3D.子數(shù)組長(zhǎng)度為42、以下哪種算法常用于解決資源分配問(wèn)題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法3、以下哪個(gè)不是隊(duì)列的基本操作？A.入隊(duì)B.出隊(duì)C.查找D.排序4、在圖的存儲(chǔ)結(jié)構(gòu)中，鄰接表適合存儲(chǔ)什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無(wú)向圖5、以下哪種算法常用于構(gòu)建最小生成樹(shù)？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法6、以下哪個(gè)不是算法的評(píng)價(jià)指標(biāo)？（）A.正確性B.可讀性C.可擴(kuò)展性D.代碼長(zhǎng)度7、在分治法中，如果子問(wèn)題的規(guī)模不相等，可能會(huì)（）A.影響算法效率B.提高算法效率C.不影響算法效率D.以上都不是8、以下關(guān)于算法復(fù)雜度的說(shuō)法中，錯(cuò)誤的是？A.時(shí)間復(fù)雜度是指算法執(zhí)行所需的時(shí)間B.空間復(fù)雜度是指算法執(zhí)行所需的存儲(chǔ)空間C.算法的時(shí)間復(fù)雜度和空間復(fù)雜度可以相互獨(dú)立D.算法的時(shí)間復(fù)雜度總是小于空間復(fù)雜度9、在貪心算法中，如果局部最優(yōu)解不能導(dǎo)致全局最優(yōu)解，該算法（）A.仍然有效B.無(wú)效C.可能有效D.以上都不是10、在回溯法中，當(dāng)所有可能的選擇都嘗試過(guò)后，算法（）A.停止B.繼續(xù)C.重新開(kāi)始D.以上都不是11、快速排序的不穩(wěn)定因素主要來(lái)自于什么？A.樞軸元素的選擇B.遞歸調(diào)用的深度C.數(shù)據(jù)的規(guī)模D.排序的方向12、在哈希表中，當(dāng)發(fā)生沖突時(shí)，可以采用哪種方法來(lái)解決？A.線性探測(cè)法B.二次探測(cè)法C.鏈地址法D.以上都是13、在有向圖中，進(jìn)行深度優(yōu)先搜索時(shí)，需要使用什么數(shù)據(jù)結(jié)構(gòu)來(lái)記錄已訪問(wèn)的頂點(diǎn)？A.數(shù)組B.鏈表C.棧D.隊(duì)列14、在圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表適合存儲(chǔ)什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無(wú)向圖15、動(dòng)態(tài)規(guī)劃算法通常用于解決（）問(wèn)題。A.最優(yōu)解B.近似解C.隨機(jī)解D.無(wú)解16、動(dòng)態(tài)規(guī)劃算法的核心是？A.遞歸B.貪心選擇C.記憶化搜索D.分治17、以下哪個(gè)排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序18、在二叉搜索樹(shù)中進(jìn)行查找操作的平均時(shí)間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)19、在動(dòng)態(tài)規(guī)劃中，通過(guò)保存子問(wèn)題的解來(lái)避免（）A.重復(fù)計(jì)算B.錯(cuò)誤計(jì)算C.遺漏計(jì)算D.以上都是20、在動(dòng)態(tài)規(guī)劃中，狀態(tài)轉(zhuǎn)移方程描述了（）A.不同狀態(tài)之間的關(guān)系B.初始狀態(tài)的計(jì)算方法C.最優(yōu)解的計(jì)算方法D.以上都不是二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）分析模擬退火算法的基本思想和應(yīng)用。2、（本題10分）解釋在軍事領(lǐng)域中的作戰(zhàn)模擬和決策支持算法。3、（本題10分）分析編輯距離問(wèn)題的算法實(shí)現(xiàn)和應(yīng)用場(chǎng)景。4、（本題10分）簡(jiǎn)述分塊算法的思想和應(yīng)用