黑龍江工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫》2022-2023學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁黑龍江工程學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫》2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對于一個具有n個元素的有序鏈表，進(jìn)行折半查找，其時間復(fù)雜度為？A.O(logn)B.O(nlogn)C.O(n)D.不能進(jìn)行折半查找2、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，若要表示一個有向圖，通?？梢允褂媚姆N存儲結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.以上均可3、在一個具有n個元素的堆中，查找最大元素的時間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)4、在數(shù)據(jù)結(jié)構(gòu)中，伸展樹（SplayTree）通過自調(diào)整保持較好的性能，以下關(guān)于伸展樹的操作，不正確的是（）A.查找操作會將被查找的節(jié)點(diǎn)旋轉(zhuǎn)到根節(jié)點(diǎn)B.插入操作可能會引起多次旋轉(zhuǎn)C.伸展樹的平均性能較好D.伸展樹的空間復(fù)雜度較高5、棧是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，它遵循后進(jìn)先出（LIFO）的原則。以下關(guān)于棧的說法中，錯誤的是？（）A.?？梢杂脭?shù)組或鏈表實(shí)現(xiàn)。B.棧的插入和刪除操作只能在棧頂進(jìn)行。C.棧可以用于實(shí)現(xiàn)函數(shù)調(diào)用、表達(dá)式求值等。D.棧的容量是無限的，可以存儲任意數(shù)量的元素。6、紅黑樹是一種自平衡的二叉搜索樹，具有嚴(yán)格的性質(zhì)。以下關(guān)于紅黑樹的描述，不正確的是（）A.節(jié)點(diǎn)要么是紅色，要么是黑色B.根節(jié)點(diǎn)一定是黑色C.從根節(jié)點(diǎn)到每個葉子節(jié)點(diǎn)的路徑上，黑色節(jié)點(diǎn)的數(shù)量相同D.紅黑樹的插入和刪除操作比平衡二叉樹簡單7、對于一個具有n個節(jié)點(diǎn)的紅黑樹，插入一個新節(jié)點(diǎn)后，調(diào)整樹的結(jié)構(gòu)以保持紅黑樹性質(zhì)，其時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、對于單鏈表，若要訪問鏈表中的第i個元素，必須從鏈表的頭指針開始依次遍歷，平均時間復(fù)雜度為O(n)。那么如果要在鏈表的末尾添加一個新元素，時間復(fù)雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)9、在一個具有n個元素的無序數(shù)組中，使用順序查找算法查找一個特定元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.nlogn10、對于一個具有n個元素的無序數(shù)組，使用插入排序進(jìn)行排序，其最好情況下的時間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)11、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)LRU（最近最少使用）頁面置換算法？A.隊(duì)列B.棧C.哈希表D.雙鏈表12、在一個字符串匹配算法中，BM算法相對于樸素的字符串匹配算法，其優(yōu)勢在于？（）A.平均性能更好B.代碼更簡潔C.空間復(fù)雜度更低D.適用于短字符串匹配13、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)文件系統(tǒng)中的目錄結(jié)構(gòu)？（）A.棧B.隊(duì)列C.樹D.哈希表14、在一個用鄰接表存儲的有向圖中，若要計(jì)算某個節(jié)點(diǎn)的出度，以下哪種方法較為高效？A.遍歷該節(jié)點(diǎn)的鄰接表B.遍歷整個圖的鄰接表C.無法高效計(jì)算D.以上都不對15、若一個圖的鄰接矩陣對角線以下（不包括對角線）的元素全為0，則該圖一定是：A.無向圖B.有向圖C.強(qiáng)連通圖D.弱連通圖16、在一個具有n個節(jié)點(diǎn)的有向圖中，若存在環(huán)，則使用拓?fù)渑判蛩惴〞霈F(xiàn)什么情況？A.正常完成排序B.無法完成排序C.排序結(jié)果不準(zhǔn)確D.以上都不對17、在一個循環(huán)隊(duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAXSIZE，則判斷隊(duì)滿的條件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front18、已知一個帶權(quán)無向圖的鄰接矩陣表示，若要計(jì)算圖中兩個頂點(diǎn)之間的最短路徑，可以使用的算法是？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法19、對于一個具有n個元素的堆，若要將其所有元素從小到大排序，最好的方法是？A.每次刪除堆頂元素并調(diào)整B.直接使用快速排序C.先構(gòu)建大頂堆再調(diào)整D.以上方法效率相同20、在一個有序的單鏈表中，若要刪除一個重復(fù)出現(xiàn)的元素，使得鏈表中不再有重復(fù)元素，應(yīng)如何操作？（）A.從頭遍歷，遇到重復(fù)元素就刪除B.從尾遍歷，遇到重復(fù)元素就刪除C.先排序，再刪除重復(fù)元素D.建立一個新鏈表，將不重復(fù)元素插入二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述在拓?fù)渑判虻牟⑿谢瘜?shí)現(xiàn)中，如何提高處理效率。2、（本題10分）詳細(xì)闡述在哈希表的擴(kuò)容過程中，如何重新計(jì)算哈希值并遷移數(shù)據(jù)，以保證性能。3、（本題10分）詳細(xì)說明在字符串操作中，如何實(shí)現(xiàn)字符串的加密和解密。4、（本題10分）數(shù)組的排序算法中，計(jì)數(shù)排序的實(shí)現(xiàn)過程是怎樣的？時間復(fù)雜度和空間復(fù)雜度分別是多少？適用于