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