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

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

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