自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁南京傳媒學(xué)院

《數(shù)據(jù)可視化》2023-2024學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個節(jié)點的線索二叉樹，若n個節(jié)點中有m個空指針域，則線索的數(shù)量為？A.mB.m/2C.n+1D.n-12、在一個具有n個元素的順序表中，進(jìn)行插入操作時，平均移動元素的個數(shù)為：A.n/2B.(n+1)/2C.nD.n-13、以下哪種排序算法在元素數(shù)量較少時性能較好？A.歸并排序B.快速排序C.插入排序D.堆排序4、以下哪種排序算法的空間復(fù)雜度最低？A.歸并排序B.快速排序C.冒泡排序D.插入排序5、在數(shù)據(jù)結(jié)構(gòu)中，鏈表的每個節(jié)點通常包含數(shù)據(jù)域和指針域。若要在一個單向鏈表中刪除一個指定節(jié)點，以下哪種操作是關(guān)鍵步驟？A.修改被刪除節(jié)點的前一個節(jié)點的指針B.修改被刪除節(jié)點的后一個節(jié)點的指針C.釋放被刪除節(jié)點的內(nèi)存D.以上都是6、對于一個大根堆，若要刪除堆頂元素并保持堆的性質(zhì)，以下哪種操作是正確的？A.將堆底元素移到堆頂，然后從堆頂向下調(diào)整B.將堆頂元素直接刪除，不進(jìn)行其他操作C.將堆頂元素與任意子節(jié)點交換，然后調(diào)整D.以上都不對7、對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表存儲，則其空間復(fù)雜度為：A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)8、已知一個棧的進(jìn)棧序列為1,2,3,4,5，下列序列中不可能是出棧序列的是（）。A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,59、在一個具有n個節(jié)點的圖中，使用深度優(yōu)先搜索算法遍歷所有節(jié)點，其時間復(fù)雜度主要取決于什么？A.邊的數(shù)量B.節(jié)點的數(shù)量C.圖的存儲方式D.以上都是10、以下關(guān)于平衡二叉樹旋轉(zhuǎn)調(diào)整的描述，正確的是：A.旋轉(zhuǎn)調(diào)整一定會改變樹的中序遍歷結(jié)果B.左旋操作是將右子樹變?yōu)楦?jié)點，原根節(jié)點變?yōu)樽笞庸?jié)點C.右旋操作是將左子樹變?yōu)楦?jié)點，原根節(jié)點變?yōu)橛易庸?jié)點D.平衡二叉樹不需要進(jìn)行旋轉(zhuǎn)調(diào)整11、在一個具有n個節(jié)點的完全二叉樹中，若底層從左到右依次編號，節(jié)點i的左孩子節(jié)點編號是多少（假設(shè)根節(jié)點編號為1）？A.2iB.2i+1C.i*2D.以上都不對12、若要在一棵二叉搜索樹中查找一個特定的值，平均時間復(fù)雜度為？（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)13、對于一個具有n個元素的有序鏈表，進(jìn)行折半查找，其時間復(fù)雜度為？A.O(logn)B.O(nlogn)C.O(n)D.不能進(jìn)行折半查找14、對于一個具有n個節(jié)點的二叉樹，其高度的最小值和最大值分別是多少？（）A.log?n,n-1B.1,nC.log?n,nD.1,n-115、設(shè)有一個具有n個元素的最大堆，若要獲取堆中的最大元素，以下關(guān)于操作的時間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、以下關(guān)于線性表的描述，正確的是：A.線性表的元素在邏輯上和存儲上都必須是連續(xù)的B.線性表只能采用順序存儲結(jié)構(gòu)C.線性表的長度是固定不變的D.線性表可以是空表，即不含任何元素17、在一個鏈?zhǔn)酱鎯Φ年犃兄?，進(jìn)行入隊和出隊操作時，指針的移動方向分別是（）A.入隊向前，出隊向后B.入隊向后，出隊向前C.均向前D.均向后18、設(shè)有一個帶權(quán)有向圖G=(V,E)，采用拓?fù)渑判蛩惴▽ζ溥M(jìn)行排序，若得到的拓?fù)湫蛄形ㄒ?，則圖G一定是？（）A.有環(huán)圖B.無環(huán)圖C.強(qiáng)連通圖D.弱連通圖19、對于一個采用順序存儲結(jié)構(gòu)的完全二叉樹，若已知根節(jié)點在數(shù)組中的位置為1，則其第i個節(jié)點的左孩子節(jié)點在數(shù)組中的位置為？A.2iB.2i+1C.i*2D.i*2-120、在一個鏈?zhǔn)酱鎯Φ臈Ｖ?，若要在棧頂插入一個元素，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）深入分析在一個具有n個元素的順序表中，如何使用二分查找算法來查找特定元素，并說明其適用條件。2、（本題10分）詳細(xì)說明如何在一個有向圖中進(jìn)行所有頂點對之間的最短路徑計算的改進(jìn)算法，給出算法步驟和實現(xiàn)代碼，并分析其性能提升。3、（本題10分）在最短路徑問題中，解釋Dijkstra算法和Floyd算法的基本思想和實現(xiàn)步驟，比較它們在不同類型圖上的應(yīng)用和效率。4、（本題10分）詳細(xì)說明如何在一個圖中進(jìn)行歐拉回路的判斷和求解，給出算法步驟和實現(xiàn)代碼，并分析其應(yīng)用場景。三、設(shè)計題（本大題共2個小