黑河學(xué)院《算法設(shè)計(jì)及應(yīng)用》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ì)及應(yīng)用》

2022-2023學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在二叉搜索樹(shù)中，查找一個(gè)元素的時(shí)間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)2、以下哪個(gè)不是圖的遍歷算法？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.最短路徑搜索D.拓?fù)渑判?、算法的穩(wěn)定性對(duì)于（）操作較為重要。A.多次排序B.查找C.插入D.刪除4、在動(dòng)態(tài)規(guī)劃中，重疊子問(wèn)題的性質(zhì)是指（）A.子問(wèn)題多次出現(xiàn)B.子問(wèn)題相互獨(dú)立C.子問(wèn)題具有唯一性D.以上都不是5、以下哪個(gè)排序算法是穩(wěn)定的？A.快速排序B.堆排序C.希爾排序D.冒泡排序6、歸并排序的遞歸實(shí)現(xiàn)中，每次將數(shù)組分成兩部分，那么遞歸的深度是多少？A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、以下哪個(gè)算法可以用于求解圖的最小生成樹(shù)問(wèn)題？A.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克魯斯卡爾算法8、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)圖的深度優(yōu)先搜索？A.數(shù)組B.鏈表C.棧D.隊(duì)列9、以下哪個(gè)算法可以用于求解最大子數(shù)組和問(wèn)題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法10、空間復(fù)雜度為O(1)的算法意味著（）A.不使用額外空間B.使用固定大小的額外空間C.使用少量的額外空間D.以上都不是11、快速排序在最好情況下的時(shí)間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)12、算法的正確性是指（）A.對(duì)于任意輸入都能得到正確結(jié)果B.對(duì)于大部分輸入能得到正確結(jié)果C.對(duì)于特定輸入能得到正確結(jié)果D.以上都不是13、算法的空間復(fù)雜度是指（）A.算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間B.算法執(zhí)行過(guò)程中所需的平均存儲(chǔ)空間C.算法執(zhí)行過(guò)程中所需的最小存儲(chǔ)空間D.算法執(zhí)行過(guò)程中所需的存儲(chǔ)空間的變化情況14、動(dòng)態(tài)規(guī)劃算法通常需要一個(gè)什么來(lái)存儲(chǔ)子問(wèn)題的解？A.數(shù)組B.鏈表C.棧D.隊(duì)列15、以下哪種算法常用于解決裝箱問(wèn)題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法16、在二叉搜索樹(shù)中進(jìn)行查找操作的平均時(shí)間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)17、在二叉樹(shù)中，度為0的節(jié)點(diǎn)稱為？A.葉子節(jié)點(diǎn)B.根節(jié)點(diǎn)C.內(nèi)部節(jié)點(diǎn)D.分支節(jié)點(diǎn)18、以下哪個(gè)排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序19、空間復(fù)雜度主要考慮（）A.算法執(zhí)行過(guò)程中占用的內(nèi)存空間B.算法執(zhí)行過(guò)程中占用的硬盤(pán)空間C.算法執(zhí)行過(guò)程中占用的網(wǎng)絡(luò)帶寬D.以上都是20、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先隊(duì)列？（）A.堆B.棧C.隊(duì)列D.鏈表二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）分析希爾排序的時(shí)間復(fù)雜度分析方法。2、（本題10分）以最大子數(shù)組乘積問(wèn)題為例，分析動(dòng)態(tài)規(guī)劃算法的解法。3、（本題10分）分析算法文檔的重要性和應(yīng)包含的內(nèi)容。4、（本題10分）簡(jiǎn)述在數(shù)據(jù)庫(kù)管理中用到的算法