江蘇海洋大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁江蘇海洋大學(xué)

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