青島大學(xué)《算法與數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁青島大學(xué)

《算法與數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)棧？（）A.數(shù)組B.鏈表C.樹D.圖2、在有向圖中，進(jìn)行深度優(yōu)先搜索時(shí)，需要使用什么數(shù)據(jù)結(jié)構(gòu)來記錄已訪問的頂點(diǎn)？A.數(shù)組B.鏈表C.棧D.隊(duì)列3、在二叉樹中，度為2的節(jié)點(diǎn)有10個(gè)，度為1的節(jié)點(diǎn)有8個(gè)，那么葉子節(jié)點(diǎn)有多少個(gè)？A.9B.10C.11D.124、以下哪個(gè)不是動(dòng)態(tài)規(guī)劃算法的關(guān)鍵步驟？A.確定狀態(tài)B.確定狀態(tài)轉(zhuǎn)移方程C.初始化狀態(tài)D.隨機(jī)選擇狀態(tài)5、在回溯法中，當(dāng)所有可能的選擇都嘗試過后，算法（）A.停止B.繼續(xù)C.重新開始D.以上都不是6、在二叉樹中，中序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹7、以下哪個(gè)算法常用于字符串匹配？（）A.KMP算法B.冒泡排序C.快速排序D.插入排序8、以下哪個(gè)不是隊(duì)列的基本操作？A.入隊(duì)B.出隊(duì)C.查找D.排序9、時(shí)間復(fù)雜度為O(logn)的算法通常比時(shí)間復(fù)雜度為O(n)的算法（）A.更慢B.更快C.一樣快D.無法比較10、以下哪個(gè)不是動(dòng)態(tài)規(guī)劃算法的優(yōu)點(diǎn)？A.高效性B.準(zhǔn)確性C.通用性D.簡單性11、以下哪種排序算法是穩(wěn)定的？（）A.快速排序B.冒泡排序C.選擇排序D.希爾排序12、空間復(fù)雜度主要考慮（）A.算法執(zhí)行過程中占用的內(nèi)存空間B.算法執(zhí)行過程中占用的硬盤空間C.算法執(zhí)行過程中占用的網(wǎng)絡(luò)帶寬D.以上都是13、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)棧的功能？A.數(shù)組B.鏈表C.隊(duì)列D.二叉樹14、以下哪種算法常用于解決背包問題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法15、以下哪個(gè)不是算法的評價(jià)指標(biāo)？（）A.正確性B.可讀性C.可擴(kuò)展性D.代碼長度16、以下哪個(gè)算法可以用于求解最長遞增子序列問題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法17、在算法設(shè)計(jì)中，減少算法的常數(shù)因子可以（）A.提高算法效率B.降低算法效率C.不影響算法效率D.以上都不是18、在動(dòng)態(tài)規(guī)劃中，優(yōu)化子問題的解存儲(chǔ)方式可以（）A.降低時(shí)間復(fù)雜度B.降低空間復(fù)雜度C.提高可讀性D.以上都是19、以下哪個(gè)不是貪心算法的應(yīng)用場景？A.哈夫曼編碼B.最小生成樹C.背包問題D.矩陣乘法20、以下哪種算法常用于解決資源分配問題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）簡述算法的定義和其重要特征。2、（本題10分）解釋選擇排序在隨機(jī)數(shù)據(jù)下的性能特點(diǎn)。3、（本題10分）說明如何用回溯法解決數(shù)獨(dú)的變體問題。4、（本題10分）分析在數(shù)字營銷中的精準(zhǔn)投放算法。三、設(shè)計(jì)題（本