學(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ù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、遞歸算法的基本思想是（）A.自頂向下分解B.自底向上計(jì)算C.不斷重復(fù)相同操作D.調(diào)用自身函數(shù)2、在貪心算法中，如果局部最優(yōu)解不能導(dǎo)致全局最優(yōu)解，該算法（）A.仍然有效B.無(wú)效C.可能有效D.以上都不是3、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以高效地進(jìn)行插入和刪除操作，并且可以快速地找到最小值？A.數(shù)組B.鏈表C.棧D.堆4、以下哪個(gè)不是貪心算法的應(yīng)用場(chǎng)景？A.哈夫曼編碼B.最小生成樹(shù)C.背包問(wèn)題D.矩陣乘法5、以下哪個(gè)不是動(dòng)態(tài)規(guī)劃算法的關(guān)鍵步驟？（）A.定義狀態(tài)B.找出狀態(tài)轉(zhuǎn)移方程C.確定初始狀態(tài)D.進(jìn)行貪心選擇6、以下哪個(gè)不是查找算法？（）A.順序查找B.二分查找C.冒泡排序D.哈希查找7、以下哪種算法常用于解決組合優(yōu)化問(wèn)題？（）A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃8、以下哪種算法常用于解決旅行商問(wèn)題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.模擬退火算法9、在動(dòng)態(tài)規(guī)劃中，通過(guò)保存子問(wèn)題的解來(lái)避免（）A.重復(fù)計(jì)算B.錯(cuò)誤計(jì)算C.遺漏計(jì)算D.以上都是10、在圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表適合存儲(chǔ)什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無(wú)向圖11、算法的通用性是指（）A.適用于多種問(wèn)題B.代碼可復(fù)用C.易于理解D.以上都是12、二分查找算法要求數(shù)據(jù)必須是（）A.有序的B.無(wú)序的C.平衡的D.以上都不是13、以下哪種算法常用于解決皇后問(wèn)題？（）A.貪心算法B.回溯法C.動(dòng)態(tài)規(guī)劃D.分治法14、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)圖的深度優(yōu)先搜索？A.數(shù)組B.鏈表C.棧D.隊(duì)列15、以下哪種算法常用于解決最大子數(shù)組問(wèn)題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法16、以下哪個(gè)算法可以用于求解字符串的最長(zhǎng)回文子串問(wèn)題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法17、以下哪個(gè)不是動(dòng)態(tài)規(guī)劃算法的優(yōu)點(diǎn)？A.高效性B.準(zhǔn)確性C.通用性D.簡(jiǎn)單性18、以下哪個(gè)算法可以用于求解圖的單源最短路徑問(wèn)題？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.迪杰斯特拉算法D.克魯斯卡爾算法19、以下哪個(gè)不是圖的基本操作？A.插入頂點(diǎn)B.刪除頂點(diǎn)C.查找頂點(diǎn)D.排序頂點(diǎn)20、在分治法中，合并子問(wèn)題的解的時(shí)間復(fù)雜度通常為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）以最長(zhǎng)不下降子序列問(wèn)題為例，分析動(dòng)態(tài)規(guī)劃算法的解法。2、（本題10分）簡(jiǎn)述在計(jì)算機(jī)網(wǎng)絡(luò)中使用的路由算法。3、（本題10分）簡(jiǎn)述在智能電網(wǎng)中的優(yōu)化算法。4、（本題10分）解釋如何根據(jù)性能測(cè)試結(jié)果進(jìn)行進(jìn)一步優(yōu)