蘇州大學(xué)《算法設(shè)計(jì)與分析》2021-2022學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁蘇州大學(xué)

《算法設(shè)計(jì)與分析》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、歸并排序的遞歸實(shí)現(xiàn)中，每次將數(shù)組分成兩部分，那么遞歸的深度是多少？A.O(1)B.O(logn)C.O(n)D.O(nlogn)2、算法分析的主要目的是（）A.評(píng)估算法的性能B.設(shè)計(jì)新算法C.比較不同算法D.以上都是3、以下哪種算法的時(shí)間復(fù)雜度最低？（）A.O(n^2)B.O(nlogn)C.O(logn)D.O(n)4、在圖的存儲(chǔ)結(jié)構(gòu)中，鄰接表適合存儲(chǔ)什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖5、以下哪個(gè)排序算法是穩(wěn)定的？A.快速排序B.堆排序C.希爾排序D.冒泡排序6、以下哪個(gè)算法可以用于求解最長遞增子序列問題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法7、以下哪個(gè)不是圖的存儲(chǔ)結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.順序表8、以下哪種排序算法的平均時(shí)間復(fù)雜度為O(nlogn)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序9、以下哪種排序算法是穩(wěn)定的？（）A.快速排序B.冒泡排序C.選擇排序D.希爾排序10、在二叉搜索樹中，查找一個(gè)元素的時(shí)間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)11、在哈希表中，裝填因子的取值范圍是？A.0到1B.0到正無窮C.負(fù)無窮到正無窮D.1到正無窮12、歸并排序的空間復(fù)雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)13、在圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表適合存儲(chǔ)什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖14、在分治法中，合并子問題的解的時(shí)間復(fù)雜度通常為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、歸并排序的基本思想是？A.分而治之，合并有序子序列B.選擇最小元素逐步構(gòu)建有序序列C.通過交換相鄰元素進(jìn)行排序D.隨機(jī)選擇元素進(jìn)行排序16、二分查找算法要求數(shù)據(jù)必須是（）A.有序的B.無序的C.平衡的D.以上都不是17、動(dòng)態(tài)規(guī)劃算法的核心是？A.遞歸B.貪心選擇C.記憶化搜索D.分治18、以下哪種排序算法在數(shù)據(jù)量較大時(shí)性能較好？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序19、在算法設(shè)計(jì)中，減少算法的常數(shù)因子可以（）A.提高算法效率B.降低算法效率C.不影響算法效率D.以上都不是20、以下哪個(gè)不是動(dòng)態(tài)規(guī)劃算法的關(guān)鍵步驟？（）A.定義狀態(tài)B.找出狀態(tài)轉(zhuǎn)移方程C.確定初始狀態(tài)D.進(jìn)行貪心選擇二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）說明如何用回溯法解決組合問題。2、（本題10分）分析在線算法和離線算法的區(qū)別。3、（本題10分）簡述貪心算法在網(wǎng)絡(luò)拓?fù)鋬?yōu)化中的應(yīng)用策略。4、（本題10分）分析快速排序的最壞情況如何避免。三、設(shè)計(jì)題（本大題共2個(gè)小題，共