湖南工商大學《數(shù)據(jù)結構與算法分析》2022-2023學年期末試卷

站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁湖南工商大學

《數(shù)據(jù)結構與算法分析》2022-2023學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個元素的哈希表，負載因子越大，發(fā)生沖突的可能性如何變化？（）A.越大B.越小C.不變D.不確定2、在一個字符串匹配算法中，BM算法相對于樸素的字符串匹配算法，其優(yōu)勢在于？（）A.平均性能更好B.代碼更簡潔C.空間復雜度更低D.適用于短字符串匹配3、在一個用鄰接矩陣存儲的圖中，若要判斷兩個節(jié)點是否相鄰，時間復雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)4、對于一個具有n個元素的雙向循環(huán)鏈表，若要刪除第i個節(jié)點（1<=i<=n），平均需要修改多少個指針？（）A.2B.3C.4D.55、圖的存儲方式和遍歷方式可以用于解決很多實際問題，以下關于它們的應用的說法中，錯誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡中的連接關系，如社交網(wǎng)絡、交通網(wǎng)絡等。B.圖的鄰接表可以用于表示稀疏圖，如地圖、電路圖等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡流問題和最小生成樹問題等。D.圖的存儲方式和遍歷方式只適用于理論研究，在實際應用中沒有實際價值。6、深度為5的滿二叉樹的結點數(shù)為：A.16B.31C.32D.157、在一個帶頭結點的雙向鏈表中，若要在p所指結點之后插入一個新結點q，需要修改幾個指針？（）A.2B.4C.6D.88、以下關于紅黑樹的性質，錯誤的是：A.每個節(jié)點要么是紅色，要么是黑色B.根節(jié)點是黑色的C.每個葉子節(jié)點（NIL節(jié)點）是黑色的D.紅色節(jié)點的子節(jié)點一定是紅色的9、設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲其下三角部分，第一個元素A[1,1]存儲在數(shù)組B[0]中，若A[8,5]在數(shù)組B中的存儲位置為k，則A[7,5]在數(shù)組B中的存儲位置為（）。A.k-13B.k-12C.k-11D.k-1010、以下哪種排序算法在元素基本有序的情況下性能最佳？A.快速排序B.冒泡排序C.插入排序D.堆排序11、若一個鏈表的每個節(jié)點只包含數(shù)據(jù)域和指針域，且指針域只指向其后繼節(jié)點，這種鏈表稱為：A.單向鏈表B.雙向鏈表C.循環(huán)鏈表D.靜態(tài)鏈表12、在一個順序存儲的隊列中，若要在隊尾插入一個元素，需要移動元素的平均次數(shù)為（）A.0B.n/2C.nD.n-113、以下關于字符串壓縮算法的描述，哪一項是不正確的？（）A.哈夫曼編碼可以根據(jù)字符出現(xiàn)頻率進行壓縮B.LZW壓縮算法基于字典進行壓縮C.壓縮算法一定能減小字符串的存儲空間D.不同的壓縮算法適用于不同類型的字符串14、在一個具有n個元素的最大堆中，插入一個新元素后，為了恢復堆的性質，需要進行的調(diào)整操作的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、在一個具有n個元素的堆中，查找最大元素的時間復雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)16、在圖的遍歷算法中，深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）是兩種常見的方法。以下關于它們的描述，錯誤的是（）A.DFS使用棧來保存未訪問的節(jié)點B.BFS使用隊列來保存未訪問的節(jié)點C.DFS可能會陷入死循環(huán)D.BFS一定能找到最短路徑17、對于一個具有n個元素的循環(huán)隊列，隊頭指針為front，隊尾指針為rear，隊列滿的條件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front18、在一個具有n個節(jié)點的無向圖中，若邊的數(shù)量遠遠小于n(n-1)/2，則適合使用哪種存儲方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以19、對于一個大根堆，若將堆中所有元素按照層次遍歷的順序存儲到一個數(shù)組中，以下關于數(shù)組元素的排列，哪一項是正確的？A.完全無序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對20、在一個具有n個節(jié)點的圖中，使用弗洛伊德算法求所有節(jié)點對之間的最短路徑，其時間復雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)二、簡答題（本大題共4個小題，共40分)1、（本題10分）比較快速排序和插入排序在對重復元素較多的數(shù)據(jù)處理情況。2、（本題10分）詳細闡述在圖的廣度優(yōu)先遍歷算法中，如何使用隊列來實現(xiàn)，并說明其應用場景。3、（本題10分）詳細闡述在具有n個頂點的無向圖中，如何使用廣度優(yōu)先搜索算法判斷兩個頂點是否連通，并給出具體的算法步驟和代碼實現(xiàn)。4、（本題10分）詳細闡述如何在一個字符串中查找所有由相同字符組成的子串。三、設計題（本大題共2個小題，共20分)1、（本題10分）設計一個程