江蘇海洋大學(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、在一個具有n個元素的堆中，查找最大元素的時間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)2、在一個具有n個元素的順序表中，若要在第i個元素之前插入一個新元素，平均需要移動多少個元素？（）A.n/2B.nC.iD.n-i3、對于一個具有n個元素的冒泡排序，若要交換相鄰兩個元素，平均需要移動多少次？（）A.0B.1C.2D.34、若要對一個具有n個元素的無序數(shù)組進行排序，以下哪種排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序5、在一棵平衡二叉樹中，插入一個新結(jié)點后，可能需要進行的調(diào)整操作是：A.左旋B.右旋C.左旋和右旋D.不需要調(diào)整6、對于一個具有n個元素的堆，進行刪除堆頂元素的操作，其時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)LRU（最近最少使用）頁面置換算法？A.隊列B.棧C.哈希表D.雙鏈表8、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA9、在一個帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹時，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對10、在一個具有n個元素的循環(huán)隊列中，若隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，則隊列中元素的個數(shù)為？A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+111、設(shè)有一個m階的B樹，每個非葉子節(jié)點至少有┌m/2┐個孩子，則一棵3階B樹中，根節(jié)點最少有幾個孩子？（）A.1B.2C.3D.412、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實現(xiàn)字典操作（添加、刪除、查找），且平均時間復(fù)雜度較低？A.數(shù)組B.鏈表C.二叉搜索樹D.哈希表13、在數(shù)據(jù)結(jié)構(gòu)中，使用隊列來實現(xiàn)廣度優(yōu)先遍歷圖，以下關(guān)于遍歷過程的描述，錯誤的是（）A.從起始節(jié)點開始入隊B.隊列為空時結(jié)束遍歷C.訪問節(jié)點時將其未訪問的鄰接節(jié)點入隊D.節(jié)點不會被重復(fù)訪問14、對于一個具有n個元素的順序存儲的棧，若要判斷棧是否已滿，應(yīng)判斷？（）A.top==n-1B.top==nC.top>=n-1D.top>=n15、數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型（ADT）可以用于提高代碼的可維護性和可擴展性，以下關(guān)于它們的說法中，錯誤的是？（）A.ADT使得數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)與使用分離，用戶只需要關(guān)心數(shù)據(jù)結(jié)構(gòu)的操作集合，而不需要關(guān)心其內(nèi)部實現(xiàn)。B.ADT可以用多種編程語言實現(xiàn)，不同的實現(xiàn)方式可能會有不同的性能和特點。C.ADT的操作集合應(yīng)該具有明確的語義和規(guī)范，以便用戶正確地使用數(shù)據(jù)結(jié)構(gòu)。D.ADT只適用于線性數(shù)據(jù)結(jié)構(gòu)，不適用于非線性數(shù)據(jù)結(jié)構(gòu)。16、在一個長度為n的順序表中，刪除第i個元素（1<=i<=n）時，需要移動的元素個數(shù)為：A.n-iB.i-1C.n-i+1D.i17、設(shè)有一個長度為n的順序表，要在第i個元素之前插入一個新元素，并且移動元素的平均次數(shù)為n/2，則插入算法的平均時間復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)18、設(shè)有一個具有n個節(jié)點的二叉平衡樹，若要插入一個新節(jié)點并保持平衡，以下關(guān)于插入操作的平均時間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、在一棵具有n個結(jié)點的二叉樹中，若度為2的結(jié)點數(shù)為m，則葉子結(jié)點數(shù)為：A.n-mB.m+1C.(n+1)/2D.n-2m+120、樹的遍歷方式有多種，以下關(guān)于它們的說法中，錯誤的是？（）A.前序遍歷是先訪問根節(jié)點，然后遍歷左子樹，最后遍歷右子樹。B.中序遍歷是先遍歷左子樹，然后訪問根節(jié)點，最后遍歷右子樹。C.后序遍歷是先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點。D.樹的遍歷方式只有前序遍歷、中序遍歷和后序遍歷三種。二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋如何對一個鏈表進行歸并排序，包括分割鏈表和合并鏈表的具體實現(xiàn)。2、（本題10分）解釋如何在一個具有n個元素的數(shù)組中，找出兩個數(shù)之和等于給定值的所有組合，分析所使用的算法和時間復(fù)雜度。3、（本題10分）解釋什么是塊狀數(shù)組數(shù)據(jù)結(jié)構(gòu)，說明其特點和應(yīng)用場景，并闡述如何進行訪問和修改操作。4、（本題10分）詳細論述在利用哈希表存儲結(jié)構(gòu)體數(shù)據(jù)時，如何設(shè)計哈希函數(shù)和處理沖突，