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

站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁北京林業(yè)大學《數(shù)據(jù)結(jié)構(gòu)A》

2021-2022學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，它由節(jié)點和邊組成。以下關(guān)于樹的說法中，錯誤的是？（）A.樹中的每個節(jié)點都有一個父節(jié)點（除了根節(jié)點）和零個或多個子節(jié)點。B.二叉樹是一種特殊的樹，每個節(jié)點最多有兩個子節(jié)點。C.樹可以用于實現(xiàn)文件系統(tǒng)、數(shù)據(jù)庫索引等。D.樹的遍歷方式只有前序遍歷、中序遍歷和后序遍歷三種。2、對于一個具有n個頂點和e條邊的帶權(quán)無向圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時間復雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)3、一棵完全二叉樹的第6層（根為第1層）有8個葉子節(jié)點，則該完全二叉樹的節(jié)點總數(shù)最多為（）。A.39B.56C.111D.1194、在一個有向圖中，所有頂點的入度之和與出度之和的關(guān)系是：A.入度之和大于出度之和B.入度之和小于出度之和C.入度之和等于出度之和D.沒有確定的關(guān)系5、若一個鏈表的每個節(jié)點只包含數(shù)據(jù)域和指針域，且指針域只指向其后繼節(jié)點，這種鏈表稱為：A.單向鏈表B.雙向鏈表C.循環(huán)鏈表D.靜態(tài)鏈表6、在一個用數(shù)組實現(xiàn)的棧中，若要將棧的容量擴大一倍，以下哪種操作的時間復雜度最低？（）A.重新創(chuàng)建一個更大的數(shù)組并復制元素B.逐步將元素移動到新的更大的數(shù)組中C.直接在原數(shù)組后面追加空間D.以上操作時間復雜度相同7、在一個具有n個元素的有序數(shù)組中，使用二分查找查找一個不存在的元素，其時間復雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)8、對于一個具有n個元素的棧，若要實現(xiàn)將棧中元素逆置，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)為？（）A.隊列B.棧C.鏈表D.數(shù)組9、在一個具有n個頂點的無向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n2D.2n(n-1)10、在一個用鏈表實現(xiàn)的隊列中，若要實現(xiàn)隊列的遍歷操作，以下哪種方式較為合適？A.從隊頭開始，依次訪問每個節(jié)點B.從隊尾開始，依次向前訪問每個節(jié)點C.隨機訪問鏈表中的節(jié)點D.以上都不對11、以下關(guān)于圖的存儲結(jié)構(gòu)的描述，哪一項是正確的？（）A.鄰接矩陣適合存儲稀疏圖B.鄰接表在存儲稠密圖時空間效率較高C.十字鏈表適合存儲有向圖D.以上都不正確12、已知一個哈希表的長度為11，哈希函數(shù)為H(key)=key%11，采用二次探測法處理沖突。若依次插入關(guān)鍵字15、38、61、84，則在查找關(guān)鍵字61時需要進行幾次探測？（）A.1B.2C.3D.413、二叉樹的性質(zhì)和遍歷方式可以用于解決很多實際問題，以下關(guān)于它們的應用的說法中，錯誤的是？（）A.二叉搜索樹可以用于實現(xiàn)高效的查找、插入和刪除操作。B.平衡二叉樹可以用于解決二叉搜索樹的不平衡問題，提高查找效率。C.二叉樹的遍歷方式可以用于實現(xiàn)二叉樹的復制、遍歷和序列化等操作。D.二叉樹的性質(zhì)和遍歷方式只適用于理論研究，在實際應用中沒有實際價值。14、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一個元素，其存儲地址為1，每個元素占一個存儲單元，則a85的地址為？（）A.33B.32C.18D.4015、在圖的最小生成樹算法中，Kruskal算法和Prim算法都能得到最小生成樹，以下關(guān)于這兩個算法的比較，錯誤的是（）A.Kruskal算法基于邊，Prim算法基于節(jié)點B.Kruskal算法需要使用并查集C.Prim算法的時間復雜度通常比Kruskal算法低D.對于稀疏圖，Kruskal算法更優(yōu)16、在一棵紅黑樹中，插入一個新節(jié)點后，調(diào)整樹的結(jié)構(gòu)以保持紅黑性質(zhì)的操作次數(shù)最多為（）A.1B.2C.lognD.n17、在數(shù)據(jù)結(jié)構(gòu)中，字典樹（Trie樹）常用于字符串的存儲和查找，以下關(guān)于字典樹的特點，不正確的是（）A.對于前綴相同的字符串可以節(jié)省存儲空間B.查找操作的時間復雜度與字符串長度有關(guān)C.適合用于詞頻統(tǒng)計D.插入和刪除操作比較復雜18、棧和隊列在計算機科學中有很多應用，以下關(guān)于它們的應用場景的說法中，錯誤的是？（）A.?？梢杂糜趯崿F(xiàn)表達式求值、括號匹配等。B.隊列可以用于實現(xiàn)任務調(diào)度、消息隊列等。C.棧和隊列可以用于實現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊列只能在編程語言的底層實現(xiàn)中使用，不能在實際應用中直接使用。19、對于一個具有n個元素的希爾排序，其時間復雜度取決于？（）A.初始序列B.增量序列C.元素值D.以上都是20、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)。對于一個滿二叉樹，若其高度為h，則節(jié)點總數(shù)為多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-1二、簡答題（本大題共4個小題，共40分)1、（本題10分）在一個鏈表中，如何實現(xiàn)鏈表的復制操作？2、（本題10分）詳細闡述在一個具有n個元素的二叉樹中，如何進行層次遍歷的非遞歸實現(xiàn)。3、（本題10分）論述AVL樹的旋轉(zhuǎn)操作對樹的高度和平衡的影響。4、（本題10分）論述拓撲排序在有向無環(huán)圖中的作用和實現(xiàn)步驟，以及如何判斷一個