長春工程學(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、若一個棧的輸入序列為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,52、在一個用鏈表實現(xiàn)的隊列中，若要實現(xiàn)隊列的遍歷操作，以下哪種方式較為合適？A.從隊頭開始，依次訪問每個節(jié)點B.從隊尾開始，依次向前訪問每個節(jié)點C.隨機訪問鏈表中的節(jié)點D.以上都不對3、對于一個具有n個元素的小根堆，若要刪除堆頂元素并重新調(diào)整堆，以下關(guān)于操作的平均時間復(fù)雜度的描述，哪一項是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、以下關(guān)于并查集的描述，錯誤的是：A.并查集可以用于判斷兩個元素是否在同一個集合中B.并查集的查找操作時間復(fù)雜度較低C.并查集的合并操作時間復(fù)雜度較高D.并查集通常采用樹形結(jié)構(gòu)存儲5、在一個具有n個元素的循環(huán)雙鏈表中，若要在表頭插入一個新元素，以下關(guān)于插入操作的時間復(fù)雜度的描述，哪一項是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一個具有n個元素的順序存儲的線性表中，要在第i個位置插入一個新元素（1<=i<=n+1），需要移動的元素個數(shù)約為？A.n-iB.iC.n-i+1D.n-i-17、對于一個具有n個元素的快速排序，每次劃分選取的基準(zhǔn)元素不同，對排序的時間復(fù)雜度有何影響？（）A.沒有影響B(tài).可能會提高C.可能會降低D.以上都不對8、在一個具有n個節(jié)點的二叉排序樹中，刪除一個節(jié)點后，為了保持二叉排序樹的性質(zhì)，可能需要進行哪些操作？A.僅調(diào)整刪除節(jié)點的子樹B.從根節(jié)點開始重新調(diào)整C.調(diào)整整個樹的結(jié)構(gòu)D.以上都有可能9、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA10、一棵二叉樹的先序遍歷序列為ABDECFGH，中序遍歷序列為DBEAFCGH，則該二叉樹的后序遍歷序列為（）。A.DEBFGCHAB.DEBFHGCAC.DEBHGFCAD.DEBHFCGA11、哈希表的性能取決于哈希函數(shù)的設(shè)計和沖突解決方法的選擇，以下關(guān)于它們的說法中，錯誤的是？（）A.好的哈希函數(shù)應(yīng)該具有均勻分布性、隨機性和高效性等特點。B.沖突解決方法的選擇應(yīng)該根據(jù)哈希表的大小、數(shù)據(jù)的特點和操作的頻率等因素來決定。C.哈希表的性能可以通過調(diào)整哈希函數(shù)和沖突解決方法來優(yōu)化。D.哈希表的性能只取決于哈希函數(shù)的設(shè)計，與沖突解決方法無關(guān)。12、對于一個用鄰接矩陣存儲的圖，若要判斷兩個頂點之間是否存在邊，時間復(fù)雜度為？（）A.O(1)B.O(n)C.O(log?n)D.O(n2)13、在一個具有n個元素的雙向循環(huán)鏈表中，刪除一個節(jié)點后，需要修改幾個指針？A.2B.3C.4D.514、跳表是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)，用于實現(xiàn)有序集合的快速查找。關(guān)于跳表的特點，以下描述錯誤的是（）A.跳表的查找、插入和刪除操作的平均時間復(fù)雜度為O(logn)B.跳表通過增加索引層次來提高查找效率C.跳表的空間復(fù)雜度比普通鏈表高D.跳表的性能不如二叉搜索樹15、在數(shù)據(jù)結(jié)構(gòu)中，塊狀鏈表結(jié)合了鏈表和數(shù)組的優(yōu)點，以下關(guān)于塊狀鏈表的特點，描述不正確的是（）A.適合頻繁的插入和刪除操作B.可以提高隨機訪問的效率C.每個塊內(nèi)部是有序的D.空間復(fù)雜度比普通鏈表低16、對于一棵二叉樹，先序遍歷序列為ABC，中序遍歷序列為BAC，則其后序遍歷序列為？A.BCAB.CBAC.ACBD.ABC17、已知一棵二叉排序樹的中序遍歷序列為{10,12,15,18,20,25,30}，則其可能的前序遍歷序列為？（）A.20,18,15,12,10,25,30B.10,12,15,18,20,25,30C.30,25,20,18,15,12,10D.10,12,18,15,20,30,2518、在一個具有n個元素的有序雙向鏈表中，若要在指定位置插入一個新元素，以下關(guān)于插入操作的時間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、在一個具有n個頂點的有向圖中，若所有頂點的出度之和為m，入度之和為k，則m和k的關(guān)系是？（）A.m=kB.m>kC.m<kD.不確定20、以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實現(xiàn)一個可以快速查找最大值和最小值的數(shù)據(jù)集合？A.鏈表B.棧C.隊列D.堆二、簡答題（本大題共4個小題，共40分)1、（本題10分）深入解釋在具有n個元素的鏈表中，如何實現(xiàn)鏈表的分割，將鏈表分為小于、等于和大于指定值的三個部分。2、（本題10分）說明二叉樹的遍歷在實際問題中的應(yīng)用，如查找特定節(jié)點、判斷二叉樹的性質(zhì)等。3、（本題10分）闡述隊列在數(shù)據(jù)庫系統(tǒng)中的應(yīng)用，如事務(wù)隊列、查詢結(jié)果緩存等，并解釋其作用。4、（本題10分）比較歸并排序和快速排序在最壞情況下