南京信息工程大學(xué)《算法設(shè)計(jì)與分析》2022-2023學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁南京信息工程大學(xué)

《算法設(shè)計(jì)與分析》2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在哈希表中，哈希函數(shù)的作用是？A.確定元素在表中的存儲位置B.解決沖突C.提高查找效率D.減少存儲空間2、以下哪個不是算法的性能指標(biāo)？A.正確性B.可讀性C.可擴(kuò)展性D.美觀性3、在圖的遍歷中，廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊(duì)列C.鏈表D.樹4、歸并排序的合并操作的時間復(fù)雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)5、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)棧？（）A.數(shù)組B.鏈表C.樹D.圖6、以下哪個不是算法的評價(jià)指標(biāo)？（）A.正確性B.可讀性C.可擴(kuò)展性D.代碼長度7、以下哪種排序算法在平均情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序8、以下關(guān)于算法復(fù)雜度的說法中，錯誤的是？A.時間復(fù)雜度是指算法執(zhí)行所需的時間B.空間復(fù)雜度是指算法執(zhí)行所需的存儲空間C.算法的時間復(fù)雜度和空間復(fù)雜度可以相互獨(dú)立D.算法的時間復(fù)雜度總是小于空間復(fù)雜度9、在動態(tài)規(guī)劃中，優(yōu)化子問題的解存儲方式可以（）A.降低時間復(fù)雜度B.降低空間復(fù)雜度C.提高可讀性D.以上都是10、以下哪個不是動態(tài)規(guī)劃算法的關(guān)鍵步驟？（）A.定義狀態(tài)B.找出狀態(tài)轉(zhuǎn)移方程C.確定初始狀態(tài)D.進(jìn)行貪心選擇11、以下哪個數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)棧的功能？A.數(shù)組B.鏈表C.隊(duì)列D.二叉樹12、以下哪個排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序13、以下哪個數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)圖的深度優(yōu)先搜索？A.數(shù)組B.鏈表C.棧D.隊(duì)列14、算法分析的主要目的是（）A.評估算法的性能B.設(shè)計(jì)新算法C.比較不同算法D.以上都是15、以下哪種算法常用于解決最大子數(shù)組問題？（）A.貪心算法B.動態(tài)規(guī)劃C.回溯法D.分治法16、在算法分析中，大O記號表示的是？A.算法的精確運(yùn)行時間B.算法的平均運(yùn)行時間C.算法運(yùn)行時間的上界D.算法運(yùn)行時間的下界17、以下哪個不是貪心算法的局限性？A.不一定能得到全局最優(yōu)解B.算法的時間復(fù)雜度較高C.對問題的性質(zhì)有一定要求D.難以證明算法的正確性18、在有向圖中，進(jìn)行深度優(yōu)先搜索時，需要使用什么數(shù)據(jù)結(jié)構(gòu)來記錄已訪問的頂點(diǎn)？A.數(shù)組B.鏈表C.棧D.隊(duì)列19、在二叉樹中，前序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹20、快速排序的不穩(wěn)定因素主要來自于什么？A.樞軸元素的選擇B.遞歸調(diào)用的深度C.數(shù)據(jù)的規(guī)模D.排序的方向二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋在視頻編碼中的壓縮算法。2、（本題10分）舉例說明遞歸算法在求解問題中的應(yīng)用。3、（本題10分）解釋遞歸算法的概念和優(yōu)點(diǎn)。4、（本題10分）簡述單調(diào)棧和單調(diào)隊(duì)列的用途。三、設(shè)計(jì)題（本大題共2個小題，共2