河北地質(zhì)大學(xué)《算法設(shè)計(jì)與分析實(shí)驗(yàn)》2021-2022學(xué)年期末試卷

自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線第1頁(yè)，共3頁(yè)河北地質(zhì)大學(xué)《算法設(shè)計(jì)與分析實(shí)驗(yàn)》

2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在圖的遍歷中，深度優(yōu)先搜索和廣度優(yōu)先搜索的主要區(qū)別是？A.遍歷的順序不同B.時(shí)間復(fù)雜度不同C.空間復(fù)雜度不同D.適用的圖類(lèi)型不同2、快速排序在最好情況下的時(shí)間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)3、以下哪種算法常用于構(gòu)建最小生成樹(shù)？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法4、在貪心算法中，一旦做出選擇就（）A.可以更改B.不能更改C.視情況更改D.以上都不是5、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)集合的交集、并集和差集等操作？A.數(shù)組B.鏈表C.棧D.哈希表6、在算法分析中，大O記號(hào)表示的是？A.算法的精確運(yùn)行時(shí)間B.算法的平均運(yùn)行時(shí)間C.算法運(yùn)行時(shí)間的上界D.算法運(yùn)行時(shí)間的下界7、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)棧的功能？A.數(shù)組B.鏈表C.隊(duì)列D.二叉樹(shù)8、空間復(fù)雜度主要考慮（）A.算法執(zhí)行過(guò)程中占用的內(nèi)存空間B.算法執(zhí)行過(guò)程中占用的硬盤(pán)空間C.算法執(zhí)行過(guò)程中占用的網(wǎng)絡(luò)帶寬D.以上都是9、以下哪個(gè)不是動(dòng)態(tài)規(guī)劃算法的優(yōu)點(diǎn)？A.高效性B.準(zhǔn)確性C.通用性D.簡(jiǎn)單性10、空間復(fù)雜度為O(1)的算法意味著（）A.不使用額外空間B.使用固定大小的額外空間C.使用少量的額外空間D.以上都不是11、在回溯法中，通過(guò)（）來(lái)避免無(wú)效搜索。A.剪枝B.貪心選擇C.動(dòng)態(tài)規(guī)劃D.分治12、以下哪個(gè)不是圖的存儲(chǔ)結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.順序表13、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)隊(duì)列的功能？A.數(shù)組B.鏈表C.棧D.二叉樹(shù)14、以下哪個(gè)不是算法的性能指標(biāo)？A.正確性B.可讀性C.可擴(kuò)展性D.美觀性15、時(shí)間復(fù)雜度和空間復(fù)雜度需要在設(shè)計(jì)算法時(shí)進(jìn)行（）A.單獨(dú)考慮B.綜合考慮C.先考慮時(shí)間復(fù)雜度D.先考慮空間復(fù)雜度16、以下哪種算法常用于解決背包問(wèn)題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法17、以下哪個(gè)算法常用于字符串匹配？（）A.KMP算法B.冒泡排序C.快速排序D.插入排序18、在貪心算法中，每一步的選擇都是（）A.全局最優(yōu)B.局部最優(yōu)C.隨機(jī)的D.以上都不是19、快速排序算法在最壞情況下的時(shí)間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)20、以下哪個(gè)不是貪心算法的特點(diǎn)？（）A.局部最優(yōu)B.整體最優(yōu)C.高效性D.不可回溯二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）以圖像壓縮問(wèn)題為例，說(shuō)明動(dòng)態(tài)規(guī)劃算法的應(yīng)用。2、（本題10分）闡述堆排序在數(shù)據(jù)排序穩(wěn)定性方面的特點(diǎn)。3、（本題10分）闡述堆排序在數(shù)據(jù)緩存中的應(yīng)用優(yōu)勢(shì)。4、（本題10分）解釋在金融工程中使用的風(fēng)險(xiǎn)評(píng)估算法。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20分)