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

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