北京林業(yè)大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線第1頁(yè)，共3頁(yè)北京林業(yè)大學(xué)

《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則矩陣中非零元素的個(gè)數(shù)至少為：A.n-1B.nC.2(n-1)D.2n2、以下哪種排序算法在元素基本有序的情況下性能最佳？A.快速排序B.冒泡排序C.插入排序D.堆排序3、在一個(gè)具有n個(gè)元素的大根堆中，刪除堆頂元素后，將最后一個(gè)元素放到堆頂，然后進(jìn)行調(diào)整，其時(shí)間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)4、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的棧中，若棧頂指針為top，要判斷棧是否為空，應(yīng)判斷？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL5、在一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)有向圖中，使用迪杰斯特拉（Dijkstra）算法求單源最短路徑。以下關(guān)于該算法的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)6、在數(shù)據(jù)結(jié)構(gòu)中，AVL樹(shù)的刪除操作比插入操作更復(fù)雜，以下關(guān)于刪除操作的描述，錯(cuò)誤的是（）A.可能需要進(jìn)行多次旋轉(zhuǎn)來(lái)保持平衡B.首先找到要?jiǎng)h除的節(jié)點(diǎn)C.刪除后不需要調(diào)整樹(shù)的結(jié)構(gòu)D.要考慮刪除節(jié)點(diǎn)的子樹(shù)情況7、在一個(gè)具有n個(gè)元素的有序雙向鏈表中，若要在指定位置插入一個(gè)新元素，以下關(guān)于插入操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行插入操作的時(shí)間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖中，使用弗洛伊德算法求所有頂點(diǎn)對(duì)之間的最短路徑，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(n2)C.O(n3)D.O(e3)10、二叉樹(shù)是一種重要的數(shù)據(jù)結(jié)構(gòu)。對(duì)于一個(gè)滿(mǎn)二叉樹(shù)，若其高度為h，則節(jié)點(diǎn)總數(shù)為多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-111、在一個(gè)具有n個(gè)頂點(diǎn)和m條邊的無(wú)向圖中，若采用鄰接表存儲(chǔ)，則存儲(chǔ)空間復(fù)雜度主要取決于？A.nB.mC.n+mD.n^212、對(duì)于一個(gè)具有n個(gè)元素的順序存儲(chǔ)的棧，若要判斷棧是否已滿(mǎn)，應(yīng)判斷？（）A.top==n-1B.top==nC.top>=n-1D.top>=n13、在一棵度為4的樹(shù)中，若有20個(gè)度為4的節(jié)點(diǎn)，10個(gè)度為3的節(jié)點(diǎn)，1個(gè)度為2的節(jié)點(diǎn)，10個(gè)葉子節(jié)點(diǎn)，那么這棵樹(shù)的總節(jié)點(diǎn)數(shù)是多少？A.82B.81C.79D.7814、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行刪除操作并調(diào)整堆的時(shí)間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、棧和隊(duì)列的實(shí)現(xiàn)可以使用數(shù)組或鏈表，以下關(guān)于它們的實(shí)現(xiàn)方式的說(shuō)法中，錯(cuò)誤的是？（）A.用數(shù)組實(shí)現(xiàn)棧和隊(duì)列時(shí)，需要考慮數(shù)組的大小和溢出問(wèn)題。B.用鏈表實(shí)現(xiàn)棧和隊(duì)列時(shí)，插入和刪除操作的時(shí)間復(fù)雜度為O(1)。C.棧和隊(duì)列的實(shí)現(xiàn)方式只影響它們的性能，不影響它們的功能。D.棧和隊(duì)列可以同時(shí)使用數(shù)組和鏈表實(shí)現(xiàn)，以提高性能和靈活性。16、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，進(jìn)行先序遍歷和中序遍歷，得到的序列相同，則該二叉樹(shù)的形狀為？A.只有一個(gè)根節(jié)點(diǎn)B.所有節(jié)點(diǎn)只有左子樹(shù)C.所有節(jié)點(diǎn)只有右子樹(shù)D.是一棵滿(mǎn)二叉樹(shù)17、在一個(gè)具有n個(gè)元素的小頂堆中，若將堆頂元素與最后一個(gè)元素交換，然后對(duì)堆進(jìn)行調(diào)整，其時(shí)間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)18、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖中，使用克魯斯卡爾（Kruskal）算法生成最小生成樹(shù)。以下關(guān)于該算法的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(nlogn)B.O(eloge)C.O(elogn)D.O(n^2)19、若要對(duì)一個(gè)具有n個(gè)元素的無(wú)序數(shù)組進(jìn)行排序，以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序20、對(duì)于一個(gè)用數(shù)組實(shí)現(xiàn)的最小堆，若要?jiǎng)h除堆頂元素并調(diào)整堆，以下操作正確的是？（）A.將堆尾元素移到堆頂，然后從堆頂向下調(diào)整B.將堆頂元素與堆尾元素交換，然后從堆頂向下調(diào)整C.將堆頂元素刪除，然后重新構(gòu)建堆D.以上都不對(duì)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)說(shuō)明如何在二叉搜索樹(shù)中查找第k小的元素，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度。2、（本題10分）在一個(gè)二叉樹(shù)中，如何實(shí)現(xiàn)層次遍歷？3、（本題10分）比較計(jì)數(shù)排序和歸并排序在適用數(shù)據(jù)規(guī)模上的差異。4、（本題10分）論述如何優(yōu)化哈希表的性能以應(yīng)對(duì)高并發(fā)訪問(wèn)。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20分)1、（本題10分）設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)