濟(jì)寧學(xué)院《數(shù)據(jù)可視化》2021-2022學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁濟(jì)寧學(xué)院《數(shù)據(jù)可視化》

2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)具有n個(gè)元素的待排序序列，若采用冒泡排序算法進(jìn)行排序，在最壞情況下需要進(jìn)行的比較次數(shù)為？（）A.n(n-1)/2B.nlognC.n-1D.n2、AVL樹是一種高度平衡的二叉搜索樹，以下關(guān)于AVL樹的旋轉(zhuǎn)操作，描述不正確的是（）A.旋轉(zhuǎn)操作用于保持樹的平衡B.包括單旋轉(zhuǎn)和雙旋轉(zhuǎn)兩種類型C.旋轉(zhuǎn)操作不會(huì)改變二叉搜索樹的性質(zhì)D.每次插入或刪除節(jié)點(diǎn)都需要進(jìn)行旋轉(zhuǎn)操作3、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A.nB.n^2C.n(n-1)D.n(n+1)4、對(duì)于一個(gè)有向圖，使用鄰接矩陣存儲(chǔ)，判斷是否存在從頂點(diǎn)i到頂點(diǎn)j的邊的時(shí)間復(fù)雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)5、在一個(gè)具有n個(gè)元素的順序表中，若要在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素，需要向后移動(dòng)多少個(gè)元素？（）A.n-iB.iC.n-i+1D.n-i-16、在一個(gè)用數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列中，若front=rear，則隊(duì)列的狀態(tài)可能為（）A.隊(duì)空B.隊(duì)滿C.既不空也不滿D.以上都有可能7、對(duì)于一個(gè)采用鏈表存儲(chǔ)的隊(duì)列，若要實(shí)現(xiàn)隊(duì)列的逆置操作，以下關(guān)于時(shí)間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)8、在一個(gè)長(zhǎng)度為n的順序表中，刪除第i個(gè)元素（1<=i<=n）時(shí)，需要移動(dòng)的元素個(gè)數(shù)為：A.n-iB.i-1C.n-i+1D.i9、在圖的最短路徑算法中，Dijkstra算法適用于帶權(quán)有向圖，以下關(guān)于Dijkstra算法的描述，錯(cuò)誤的是（）A.以起始節(jié)點(diǎn)為中心向外層層擴(kuò)展B.每次選擇距離起始節(jié)點(diǎn)最近的未訪問節(jié)點(diǎn)C.可以處理負(fù)權(quán)邊D.時(shí)間復(fù)雜度為O(n^2)10、在一個(gè)具有n個(gè)元素的順序表中，若要在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素，需要移動(dòng)的元素個(gè)數(shù)為？（）A.n-iB.iC.n-i+1D.n-i-111、對(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)12、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同13、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和與出度之和的關(guān)系是：A.入度之和大于出度之和B.入度之和小于出度之和C.入度之和等于出度之和D.沒有確定的關(guān)系14、在二叉搜索樹中，左子樹的所有節(jié)點(diǎn)值都小于根節(jié)點(diǎn)值，右子樹的所有節(jié)點(diǎn)值都大于根節(jié)點(diǎn)值。若要查找一個(gè)特定值的節(jié)點(diǎn)，以下哪種方法效率最高？A.先序遍歷B.中序遍歷C.后序遍歷D.以上效率相同15、隊(duì)列是另一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，它遵循先進(jìn)先出（FIFO）的原則。以下關(guān)于隊(duì)列的說法中，錯(cuò)誤的是？（）A.隊(duì)列可以用數(shù)組或鏈表實(shí)現(xiàn)。B.隊(duì)列的插入操作在隊(duì)尾進(jìn)行，刪除操作在隊(duì)首進(jìn)行。C.隊(duì)列可以用于實(shí)現(xiàn)任務(wù)調(diào)度、消息傳遞等。D.隊(duì)列的容量是無限的，可以存儲(chǔ)任意數(shù)量的元素。16、在數(shù)據(jù)結(jié)構(gòu)中，哈希表的負(fù)載因子對(duì)性能有很大影響。以下關(guān)于負(fù)載因子的描述，不正確的是（）A.負(fù)載因子越大，哈希沖突的可能性越大B.負(fù)載因子越小，存儲(chǔ)空間利用率越高C.負(fù)載因子通常在0.5到1之間D.可以通過調(diào)整負(fù)載因子來優(yōu)化哈希表性能17、在一個(gè)具有n個(gè)元素的順序表中，若要在第i個(gè)元素之前插入一個(gè)新元素，平均需要移動(dòng)多少個(gè)元素？（）A.n/2B.nC.iD.n-i18、在一個(gè)用鄰接表存儲(chǔ)的有向圖中，若要計(jì)算某個(gè)節(jié)點(diǎn)的出度，以下哪種方法較為高效？A.遍歷該節(jié)點(diǎn)的鄰接表B.遍歷整個(gè)圖的鄰接表C.無法高效計(jì)算D.以上都不對(duì)19、設(shè)有一個(gè)廣義表L=(a,(b,c),d)，其長(zhǎng)度和深度分別為？（）A.3和2B.3和3C.4和2D.4和320、以下關(guān)于哈希沖突解決方法中二次探測(cè)法的描述，哪一項(xiàng)是不正確的？（）A.可以減少聚集現(xiàn)象B.探測(cè)的位置是連續(xù)的C.可能會(huì)出現(xiàn)找不到空閑位置的情況D.相比線性探測(cè)法，性能更優(yōu)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）論述跳表在數(shù)據(jù)動(dòng)態(tài)更新頻繁情況下的性能優(yōu)化策略。2、（本題10分）詳細(xì)闡述B樹中如何處理節(jié)點(diǎn)的刪除導(dǎo)致下溢的情況。3、（本題10分）什么是二叉搜索樹的插入操作的自平衡版本？有哪些常見的自平衡二叉搜索樹？4、（本題10分）對(duì)于一個(gè)具有n個(gè)元素的環(huán)形鏈表，如何判斷鏈表中是否存在環(huán)？請(qǐng)給出具體的算法思路和代碼示例。三、設(shè)計(jì)題（本