長(zhǎng)春工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)長(zhǎng)春工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)》

2021-2022學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共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ì)頭開(kāi)始，依次訪問(wèn)每個(gè)節(jié)點(diǎn)B.從隊(duì)尾開(kāi)始，依次向前訪問(wèn)每個(gè)節(jié)點(diǎn)C.隨機(jī)訪問(wèn)鏈表中的節(jié)點(diǎn)D.以上都不對(duì)3、對(duì)于一個(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.并查集通常采用樹(shù)形結(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、對(duì)于一個(gè)具有n個(gè)元素的快速排序，每次劃分選取的基準(zhǔn)元素不同，對(duì)排序的時(shí)間復(fù)雜度有何影響？（）A.沒(méi)有影響B(tài).可能會(huì)提高C.可能會(huì)降低D.以上都不對(duì)8、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉排序樹(shù)中，刪除一個(gè)節(jié)點(diǎn)后，為了保持二叉排序樹(shù)的性質(zhì)，可能需要進(jìn)行哪些操作？A.僅調(diào)整刪除節(jié)點(diǎn)的子樹(shù)B.從根節(jié)點(diǎn)開(kāi)始重新調(diào)整C.調(diào)整整個(gè)樹(shù)的結(jié)構(gòu)D.以上都有可能9、已知一棵二叉樹(shù)的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA10、一棵二叉樹(shù)的先序遍歷序列為ABDECFGH，中序遍歷序列為DBEAFCGH，則該二叉樹(shù)的后序遍歷序列為（）。A.DEBFGCHAB.DEBFHGCAC.DEBHGFCAD.DEBHFCGA11、哈希表的性能取決于哈希函數(shù)的設(shè)計(jì)和沖突解決方法的選擇，以下關(guān)于它們的說(shuō)法中，錯(cuò)誤的是？（）A.好的哈希函數(shù)應(yīng)該具有均勻分布性、隨機(jī)性和高效性等特點(diǎn)。B.沖突解決方法的選擇應(yīng)該根據(jù)哈希表的大小、數(shù)據(jù)的特點(diǎn)和操作的頻率等因素來(lái)決定。C.哈希表的性能可以通過(guò)調(diào)整哈希函數(shù)和沖突解決方法來(lái)優(yōu)化。D.哈希表的性能只取決于哈希函數(shù)的設(shè)計(jì)，與沖突解決方法無(wú)關(guān)。12、對(duì)于一個(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.跳表通過(guò)增加索引層次來(lái)提高查找效率C.跳表的空間復(fù)雜度比普通鏈表高D.跳表的性能不如二叉搜索樹(shù)15、在數(shù)據(jù)結(jié)構(gòu)中，塊狀鏈表結(jié)合了鏈表和數(shù)組的優(yōu)點(diǎn)，以下關(guān)于塊狀鏈表的特點(diǎn)，描述不正確的是（）A.適合頻繁的插入和刪除操作B.可以提高隨機(jī)訪問(wèn)的效率C.每個(gè)塊內(nèi)部是有序的D.空間復(fù)雜度比普通鏈表低16、對(duì)于一棵二叉樹(shù)，先序遍歷序列為ABC，中序遍歷序列為BAC，則其后序遍歷序列為？A.BCAB.CBAC.ACBD.ABC17、已知一棵二叉排序樹(shù)的中序遍歷序列為{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.堆二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）深入解釋在具有n個(gè)元素的鏈表中，如何實(shí)現(xiàn)鏈表的分割，將鏈表分為小于、等于和大于指定值的三個(gè)部分。2、（本題10分）說(shuō)明二叉樹(shù)的遍歷在實(shí)際問(wèn)題中的應(yīng)用，如查找特定節(jié)點(diǎn)、判斷二叉樹(shù)的性質(zhì)等。3、（本題10分）闡述隊(duì)列在數(shù)據(jù)庫(kù)系統(tǒng)中的應(yīng)用，如事務(wù)隊(duì)列、查詢結(jié)果緩存等，并解釋其作用。4、（本題10分）比較歸并排序和快速排序在最壞情況下