北方民族大學《數(shù)據(jù)可視化》2021-2022學年期末試卷

站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁北方民族大學《數(shù)據(jù)可視化》

2021-2022學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的順序表中，進行插入操作時，平均移動元素的個數(shù)為：A.n/2B.(n+1)/2C.nD.n-12、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)。對于一個滿二叉樹，若其高度為h，則節(jié)點總數(shù)為多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-13、對于一個具有n個元素的無序數(shù)組，使用冒泡排序進行排序，最壞情況下的比較次數(shù)為？A.n(n-1)/2B.nlognC.n^2D.2^n4、對于一個具有n個頂點的無向連通圖，若要判斷其是否存在環(huán)，以下哪種算法的時間復雜度最低？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓撲排序D.以上算法時間復雜度相同5、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)表達式求值？A.二叉樹B.棧C.隊列D.哈希表6、已知一個有序表為{11,22,33,44,55,66,77,88,99}，使用折半查找法查找值為77的元素，需要比較的次數(shù)是（）。A.1B.2C.3D.47、已知一個哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測法處理沖突。若依次插入關(guān)鍵字31、25、19、49、37、21、13、17，則在查找關(guān)鍵字19時需要進行幾次比較？（）A.1B.2C.3D.48、在圖的存儲結(jié)構(gòu)中，鄰接多重表主要用于存儲無向圖，以下關(guān)于鄰接多重表的特點，描述錯誤的是（）A.可以方便地刪除邊B.存儲空間比鄰接矩陣節(jié)省C.對于判斷兩點之間是否有邊，效率較高D.不適合用于有向圖的存儲9、在數(shù)據(jù)結(jié)構(gòu)中，跳表的索引層數(shù)是根據(jù)數(shù)據(jù)量動態(tài)調(diào)整的，以下關(guān)于索引層數(shù)調(diào)整的描述，錯誤的是（）A.當數(shù)據(jù)量增加時，可能增加索引層數(shù)B.索引層數(shù)越多，查找效率越高C.調(diào)整索引層數(shù)的過程比較復雜D.索引層數(shù)的調(diào)整不會影響數(shù)據(jù)的存儲結(jié)構(gòu)10、對于一個具有n個頂點的連通圖，其生成樹中邊的數(shù)量為：A.n-1B.nC.n+1D.不確定11、在一個哈希表中，解決沖突的方法不包括：A.開放定址法B.再哈希法C.建立索引表D.鏈地址法12、在一個帶頭結(jié)點的雙向鏈表中，若要在p所指結(jié)點之后插入一個新結(jié)點q，需要修改幾個指針？（）A.2B.4C.6D.813、對于一個具有n個元素的小根堆，若要刪除堆頂元素并重新調(diào)整堆，以下關(guān)于操作的平均時間復雜度的描述，哪一項是準確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、對于一個具有n個節(jié)點的二叉排序樹，刪除一個節(jié)點后，重新調(diào)整為二叉排序樹，其時間復雜度最壞情況下為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、在一棵二叉搜索樹中，刪除一個有兩個子節(jié)點的節(jié)點時，通常采用的方法是：A.用左子樹的最大值替代該節(jié)點B.用右子樹的最小值替代該節(jié)點C.隨機選擇左子樹或右子樹的節(jié)點替代D.不進行替代，直接刪除16、在數(shù)據(jù)結(jié)構(gòu)中，對于一個具有n個元素的有序數(shù)組，使用二分查找算法查找一個特定元素，其平均時間復雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)17、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，若一個二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，那么它的后序遍歷序列是什么？（）A.BCAB.CBAC.CABD.ACB18、對于一個具有n個元素的有序雙向鏈表，查找中間元素的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、若一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBDAEGF，則其后序遍歷序列為？（）A.CDBGFEAB.CDBFGEAC.CDBAGFED.CDBEAGF20、對于一個具有n個元素的快速排序，在最好情況下，其時間復雜度為？（）A.O(nlogn)B.O(n^2)C.O(n)D.O(logn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細解釋什么是平衡二叉樹，以及如何通過旋轉(zhuǎn)操作來保持平衡二叉樹的平衡性質(zhì)，給出常見的旋轉(zhuǎn)類型和示例。2、（本題10分）詳細說明如何在一個圖中判斷兩個頂點是否在同一個連通分量中。3、（本題10分）解釋什么是可持久化線段樹，并說明其應用場景。4、（本題10分）詳細說明如何反轉(zhuǎn)一個鏈表，分析所使用的算法和時間復雜度。