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

裝訂線裝訂線PAGE2第1頁，共3頁北方民族大學(xué)《數(shù)據(jù)可視化》

2022-2023學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無向圖中，若邊的數(shù)量遠(yuǎn)遠(yuǎn)小于n(n-1)/2，則適合使用哪種存儲(chǔ)方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以2、在一個(gè)用數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列中，若隊(duì)頭指針front=5，隊(duì)尾指針rear=2，隊(duì)列容量為10，則隊(duì)列中的元素個(gè)數(shù)是多少？A.7B.6C.5D.43、對(duì)于一個(gè)具有n個(gè)元素的快速排序，每次劃分選取的基準(zhǔn)元素不同，對(duì)排序的時(shí)間復(fù)雜度有何影響？（）A.沒有影響B(tài).可能會(huì)提高C.可能會(huì)降低D.以上都不對(duì)4、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)操作系統(tǒng)中的進(jìn)程調(diào)度？A.隊(duì)列B.棧C.樹D.圖5、哈希表的沖突解決方法有多種，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.開放定址法是一種常用的沖突解決方法，它通過在哈希表中尋找下一個(gè)空閑位置來解決沖突。B.鏈地址法是另一種常用的沖突解決方法，它將沖突的元素存儲(chǔ)在鏈表中。C.再哈希法是通過使用不同的哈希函數(shù)來解決沖突。D.哈希表的沖突解決方法只有開放定址法和鏈地址法兩種。6、若一棵二叉樹的葉子節(jié)點(diǎn)數(shù)為n0，度為2的節(jié)點(diǎn)數(shù)為n2，則n0和n2之間的關(guān)系是？（）A.n0=n2-1B.n0=n2+1C.n0=2n2-1D.n0=2n2+17、對(duì)于一個(gè)具有n個(gè)元素的哈希表，負(fù)載因子（loadfactor）為0.7，當(dāng)表中元素?cái)?shù)量超過一定閾值時(shí)需要進(jìn)行擴(kuò)容。以下關(guān)于擴(kuò)容操作的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.O(1)B.O(n)C.O(logn)D.O(nlogn)8、紅黑樹是一種自平衡的二叉搜索樹，具有嚴(yán)格的性質(zhì)。以下關(guān)于紅黑樹的描述，不正確的是（）A.節(jié)點(diǎn)要么是紅色，要么是黑色B.根節(jié)點(diǎn)一定是黑色C.從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑上，黑色節(jié)點(diǎn)的數(shù)量相同D.紅黑樹的插入和刪除操作比平衡二叉樹簡單9、在一個(gè)有向無環(huán)圖中，進(jìn)行拓?fù)渑判虻慕Y(jié)果是唯一的嗎？A.一定唯一B.一定不唯一C.可能唯一，也可能不唯一D.以上都不對(duì)10、在數(shù)據(jù)結(jié)構(gòu)中，樹的遍歷可以采用遞歸和非遞歸方式。以下關(guān)于非遞歸中序遍歷二叉樹的說法，錯(cuò)誤的是（）A.可以使用棧來輔助實(shí)現(xiàn)B.比遞歸方式更復(fù)雜C.時(shí)間復(fù)雜度與遞歸方式相同D.空間復(fù)雜度一定比遞歸方式低11、一棵哈夫曼樹中，葉子節(jié)點(diǎn)的編碼長度一定（）非葉子節(jié)點(diǎn)的編碼長度。A.大于B.等于C.小于D.不小于12、在數(shù)據(jù)結(jié)構(gòu)的應(yīng)用中，優(yōu)先隊(duì)列常用于實(shí)現(xiàn)任務(wù)調(diào)度，以下關(guān)于優(yōu)先隊(duì)列的描述，錯(cuò)誤的是（）A.可以使用堆來實(shí)現(xiàn)B.元素的出隊(duì)順序按照優(yōu)先級(jí)確定C.插入元素的時(shí)間復(fù)雜度為O(logn)D.不支持修改元素的優(yōu)先級(jí)13、在一個(gè)具有n個(gè)節(jié)點(diǎn)的有向圖中，若存在環(huán)，則使用拓?fù)渑判蛩惴〞?huì)出現(xiàn)什么情況？A.正常完成排序B.無法完成排序C.排序結(jié)果不準(zhǔn)確D.以上都不對(duì)14、隊(duì)列也是一種常見的數(shù)據(jù)結(jié)構(gòu)，遵循先進(jìn)先出的原則。對(duì)于一個(gè)循環(huán)隊(duì)列，以下說法不正確的是（）A.隊(duì)頭指針和隊(duì)尾指針的移動(dòng)需要考慮循環(huán)的情況B.當(dāng)隊(duì)頭指針等于隊(duì)尾指針時(shí)，隊(duì)列為空C.可以通過犧牲一個(gè)存儲(chǔ)單元來區(qū)分隊(duì)列空和隊(duì)列滿的情況D.循環(huán)隊(duì)列可以避免假溢出的問題15、在一個(gè)具有n個(gè)元素的有序數(shù)組中，若要?jiǎng)h除一個(gè)特定元素，并且保持?jǐn)?shù)組的有序性，以下關(guān)于刪除操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、哈希表的沖突解決方法和性能優(yōu)化可以用于提高哈希表的效率，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.開放定址法和鏈地址法是哈希表的兩種主要沖突解決方法，它們各有優(yōu)缺點(diǎn)。B.可以通過調(diào)整哈希函數(shù)、增加哈希表的大小和采用二次探測等方法來優(yōu)化哈希表的性能。C.哈希表的性能優(yōu)化需要根據(jù)實(shí)際情況進(jìn)行選擇，不同的應(yīng)用場景可能需要不同的優(yōu)化方法。D.哈希表的沖突解決方法和性能優(yōu)化只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價(jià)值。17、在一個(gè)用鏈表實(shí)現(xiàn)的隊(duì)列中，若要?jiǎng)h除隊(duì)頭元素并返回其值，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)18、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖，采用鄰接表存儲(chǔ)，進(jìn)行深度優(yōu)先遍歷。以下關(guān)于遍歷的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)19、以下哪種數(shù)據(jù)結(jié)構(gòu)可以高效地支持集合的并、交、差等操作？A.二叉搜索樹B.哈希表C.并查集D.平衡二叉樹20、對(duì)于一個(gè)具有n個(gè)元素的有序鏈表，進(jìn)行折半查找，其時(shí)間復(fù)雜度為？A.O(logn)B.O(nlogn)C.O(n)D.不能進(jìn)行折半查找二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）簡述哈希表的哈希沖突解決方法中雙哈希法的原理及優(yōu)缺點(diǎn)。2、（本題10分）論述在鏈表中如何實(shí)現(xiàn)查找、插入和刪除操作，與順序表相比，它們在時(shí)間復(fù)雜度上有何不同？3、（本題10分）詳細(xì)說明在二叉樹的平衡調(diào)整中，除了旋轉(zhuǎn)操作，還有哪些方法可以保持平衡。4、（本題10分）解釋什么是線段樹數(shù)據(jù)結(jié)構(gòu)，說明其應(yīng)用場景和構(gòu)建過程