湖北工業(yè)大學(xué)《算法分析與設(shè)計(jì)》2022-2023學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁湖北工業(yè)大學(xué)

《算法分析與設(shè)計(jì)》2022-2023學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在動(dòng)態(tài)規(guī)劃中，通過保存子問題的解來避免（）A.重復(fù)計(jì)算B.錯(cuò)誤計(jì)算C.遺漏計(jì)算D.以上都是2、時(shí)間復(fù)雜度為O(n)的算法，其執(zhí)行時(shí)間與輸入規(guī)模n的關(guān)系是（）A.線性增長B.指數(shù)增長C.對數(shù)增長D.不變3、以下哪種排序算法的平均時(shí)間復(fù)雜度為O(nlogn)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序4、歸并排序的基本思想是？A.分而治之，合并有序子序列B.選擇最小元素逐步構(gòu)建有序序列C.通過交換相鄰元素進(jìn)行排序D.隨機(jī)選擇元素進(jìn)行排序5、以下哪個(gè)排序算法的空間復(fù)雜度最低？（）A.冒泡排序B.插入排序C.選擇排序D.歸并排序6、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)隊(duì)列的功能？A.數(shù)組B.鏈表C.棧D.二叉樹7、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)常用于查找操作？（）A.棧B.隊(duì)列C.二叉搜索樹D.鏈表8、以下哪個(gè)算法可以用于判斷一個(gè)圖是否為連通圖？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.迪杰斯特拉算法D.普里姆算法9、以下哪種算法常用于解決資源分配問題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法10、以下哪個(gè)不是動(dòng)態(tài)規(guī)劃算法的優(yōu)點(diǎn)？A.高效性B.準(zhǔn)確性C.通用性D.簡單性11、快速排序的不穩(wěn)定因素主要來自于什么？A.樞軸元素的選擇B.遞歸調(diào)用的深度C.數(shù)據(jù)的規(guī)模D.排序的方向12、在算法分析中，大O記號表示的是？A.算法的精確運(yùn)行時(shí)間B.算法的平均運(yùn)行時(shí)間C.算法運(yùn)行時(shí)間的上界D.算法運(yùn)行時(shí)間的下界13、歸并排序的遞歸實(shí)現(xiàn)中，每次將數(shù)組分成兩部分，那么遞歸的深度是多少？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、以下哪種算法常用于解決背包問題？（）A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分治法15、以下哪個(gè)不是貪心算法的特點(diǎn)？（）A.局部最優(yōu)B.整體最優(yōu)C.高效性D.不可回溯16、以下哪個(gè)不是隊(duì)列的基本操作？A.入隊(duì)B.出隊(duì)C.查找D.排序17、在遞歸算法中，當(dāng)遞歸深度過大時(shí)可能會導(dǎo)致（）A.運(yùn)行速度加快B.內(nèi)存溢出C.結(jié)果更準(zhǔn)確D.以上都不是18、以下哪種排序算法對近乎有序的數(shù)組效果較好？（）A.快速排序B.插入排序C.冒泡排序D.選擇排序19、歸并排序的合并操作的時(shí)間復(fù)雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)20、在貪心算法中，每一步的選擇都是（）A.全局最優(yōu)B.局部最優(yōu)C.隨機(jī)的D.以上都不是二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）分析貪心算法在磁盤調(diào)度問題中的應(yīng)用及局限性。2、（本題10分）說明如何用回溯法解決資源分配的效益最大化問題。3、（本題10分）簡述貪心算法在任務(wù)調(diào)度問題中的應(yīng)用。4、（本題10分）舉例說明遞歸算法在求解問題中的應(yīng)用。三、設(shè)計(jì)