黑河學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

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

《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個平衡二叉搜索樹中，插入一個新節(jié)點后，可能需要進(jìn)行的調(diào)整操作次數(shù)最多為（）A.1B.lognC.nD.nlogn2、對于一個具有n個元素的直接插入排序，在最好情況下，需要進(jìn)行多少次比較操作？（）A.n-1B.nC.n(n-1)/2D.03、在一個具有n個元素的無序數(shù)組中，使用冒泡排序進(jìn)行排序。以下關(guān)于冒泡排序的時間復(fù)雜度的描述，哪一項是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)4、已知一個圖的鄰接表存儲結(jié)構(gòu)，若要判斷任意兩個頂點之間是否存在邊，哪種方法最有效？（）A.遍歷鄰接表B.建立逆鄰接表C.建立鄰接矩陣D.深度優(yōu)先搜索5、已知一個棧的進(jìn)棧序列為1,2,3,4,5，下列序列中不可能是出棧序列的是（）。A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,56、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一個元素，其存儲地址為1，每個元素占一個存儲單元，則a85的地址為？（）A.33B.32C.18D.407、在一個具有n個節(jié)點的圖中，使用弗洛伊德算法求所有節(jié)點對之間的最短路徑，其時間復(fù)雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)8、若一個棧的輸入序列為1,2,3,4,5，不可能得到的輸出序列是？（）A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,59、已知一棵二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，則該二叉樹的右子樹為空的條件是？（）A.A為根節(jié)點B.B為根節(jié)點C.C為根節(jié)點D.無法確定10、在圖的最小生成樹算法中，Kruskal算法和Prim算法都能得到最小生成樹，以下關(guān)于這兩個算法的比較，錯誤的是（）A.Kruskal算法基于邊，Prim算法基于節(jié)點B.Kruskal算法需要使用并查集C.Prim算法的時間復(fù)雜度通常比Kruskal算法低D.對于稀疏圖，Kruskal算法更優(yōu)11、哈希表是一種常用的數(shù)據(jù)結(jié)構(gòu)，它通過哈希函數(shù)將鍵映射到存儲位置。以下關(guān)于哈希表的說法中，錯誤的是？（）A.哈希表的查找速度非?？欤骄鶗r間復(fù)雜度為O(1)。B.哈希函數(shù)的設(shè)計直接影響哈希表的性能。C.哈希表可能會出現(xiàn)沖突，即不同的鍵被映射到同一個存儲位置。D.哈希表只能存儲整數(shù)類型的鍵值對。12、對于一個采用順序存儲的棧，若棧頂指針top等于-1時，表示：A.棧滿B.?？誄.棧中只有一個元素D.棧中至少有一個元素13、在一個具有n個頂點的有向圖中，若存在環(huán)，則使用拓?fù)渑判蛩惴〞?？A.正常排序B.無法排序C.部分排序D.排序結(jié)果不確定14、在一個具有n個節(jié)點的二叉排序樹中，進(jìn)行查找操作的平均時間復(fù)雜度是多少？A.O(n)B.O(logn)C.O(nlogn)D.取決于樹的形態(tài)15、對于一個具有n個元素的有序鏈表，進(jìn)行二分查找的時間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.不能進(jìn)行二分查找16、對于一個具有n個頂點和e條邊的帶權(quán)無向圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)17、在一個具有n個頂點的有向完全圖中，邊的數(shù)量為：A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)18、在一個用數(shù)組實現(xiàn)的循環(huán)隊列中，若front=rear，則隊列的狀態(tài)可能為（）A.隊空B.隊滿C.既不空也不滿D.以上都有可能19、以下關(guān)于串的描述，錯誤的是：A.串是一種特殊的線性表B.串的長度是指串中字符的個數(shù)C.空串和空格串是相同的概念D.串的存儲方式有順序存儲和鏈?zhǔn)酱鎯?0、在一個具有n個頂點和m條邊的無向圖中，若采用鄰接表存儲，則存儲空間復(fù)雜度主要取決于？A.nB.mC.n+mD.n^2二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋線段樹在處理區(qū)間最大值和最小值查詢時的不同策略。2、（本題10分）論述如何在一個二叉堆中查找第k大的元素，給出算法思路和優(yōu)化方法。3、（本題10分）在哈希表中，闡述如何處理哈希沖突，給出幾種常見的處理方法的算法步驟和實現(xiàn)代碼，并分析其性能。4、（本題10分）詳細(xì)論述在一個具有n個頂點的無向圖中，如何進(jìn)行頂點的割點求