自覺遵守考場紀律如考試作弊此答卷無效密自覺遵守考場紀律如考試作弊此答卷無效密封線第1頁，共3頁北京城市學院

《數據可視化技術》2022-2023學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、圖是一種復雜的數據結構。在有向圖中，頂點的入度是指指向該頂點的邊的數量。若要計算一個有向圖中所有頂點的入度，哪種算法較為合適？A.深度優先搜索B.廣度優先搜索C.拓撲排序D.以上都可以2、在二叉搜索樹的刪除操作中，如果刪除的節點是其父節點的唯一子節點，以下處理方式錯誤的是（）A.直接將該節點刪除，不做其他調整B.將該節點的值替換為其父節點的值，并刪除父節點C.將該節點的左子樹或右子樹替代該節點D.以上處理方式都不對3、在數據結構中，樹的遍歷可以采用遞歸和非遞歸方式。以下關于非遞歸中序遍歷二叉樹的說法，錯誤的是（）A.可以使用棧來輔助實現B.比遞歸方式更復雜C.時間復雜度與遞歸方式相同D.空間復雜度一定比遞歸方式低4、對于一個具有n個頂點的無向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優先搜索B.廣度優先搜索C.枚舉所有邊D.以上方法效率相同5、在一個順序存儲的棧中，若要實現共享棧，即兩個棧共用一個數組空間，以下關于棧頂指針的設置，哪一種方案較為合理？A.兩個棧的棧頂指針分別從數組的兩端向中間移動B.兩個棧的棧頂指針都從數組的同一端開始移動C.一個棧的棧頂指針從數組的開頭移動，另一個從結尾移動D.以上都可以6、對于一個具有n個元素的哈希表，負載因子（loadfactor）為0.7，當表中元素數量超過一定閾值時需要進行擴容。以下關于擴容操作的時間復雜度的描述，哪一個是恰當的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)7、對于一個用鄰接矩陣存儲的圖，若要判斷兩個頂點之間是否存在邊，時間復雜度為？（）A.O(1)B.O(n)C.O(log?n)D.O(n2)8、若要對一個具有n個元素的有序鏈表進行二分查找，是否可行？（）A.可行B.不可行C.有時可行D.取決于鏈表長度9、若要對一棵二叉樹進行層次遍歷，需要使用哪種數據結構輔助？（）A.棧B.隊列C.優先隊列D.哈希表10、對于一個大根堆，若要刪除堆頂元素并保持堆的性質，以下哪種操作是正確的？A.將堆底元素移到堆頂，然后從堆頂向下調整B.將堆頂元素直接刪除，不進行其他操作C.將堆頂元素與任意子節點交換，然后調整D.以上都不對11、在一個字符串中，要查找某個子串首次出現的位置，通常可以使用哪種算法？（）A.冒泡排序B.快速排序C.順序查找D.二分查找12、對于一個具有n個頂點和e條邊的有向圖，采用鄰接表存儲，進行深度優先遍歷。以下關于遍歷的時間復雜度的描述，哪一個是恰當的？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)13、在一個具有n個元素的隊列中，若要獲取隊頭元素的前一個元素但不刪除，以下操作不可行的是？（）A.遍歷整個隊列B.使用輔助數據結構C.直接獲取D.以上都不可行14、設有一個棧S和一個隊列Q，初始時棧為空，隊列為{1,2,3,4,5}。經過一系列入棧和出棧、入隊和出隊操作后，棧頂元素為3，此時隊列的頭元素為？（）A.1B.2C.4D.515、以下關于拓撲排序的描述，正確的是：A.拓撲排序的結果是唯一的B.一個有環的圖也可以進行拓撲排序C.拓撲排序可以用于判斷一個圖是否有環D.拓撲排序只能用于有向圖16、在一個具有n個頂點的圖中，若存在回路，則深度優先遍歷可能會出現什么情況？（）A.訪問某些頂點多次B.無法完成遍歷C.結果不正確D.以上都有可能17、在一個具有n個元素的無序鏈表中，若要對其進行快速排序，以下關于快速排序的平均時間復雜度的描述，哪一項是準確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)18、隊列也是一種常見的數據結構，遵循先進先出的原則。對于一個循環隊列，以下說法不正確的是（）A.隊頭指針和隊尾指針的移動需要考慮循環的情況B.當隊頭指針等于隊尾指針時，隊列為空C.可以通過犧牲一個存儲單元來區分隊列空和隊列滿的情況D.循環隊列可以避免假溢出的問題19、棧和隊列在計算機科學中有很多應用，以下關于它們的應用場景的說法中，錯誤的是？（）A.棧可以用于實現表達式求值、括號匹配等。B.隊列可以用于實現任務調度、消息隊列等。C.棧和隊列可以用于實現圖的深度優先搜索和廣度優先搜索。D.棧和隊列只能在編程語言的底層實現中使用，不能在實際應用中直接使用。20、在一個具有n個元素的有序鏈表中，若要查找第k個元素，以下關于查找操作的時間復雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(k)D.O(n)二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋什么是AVL樹，并說明其在保持平衡方面的調整策略。2、（本題10分）論述AVL樹的刪除操作中可能出現的四種情況及相應的調整策略。3、（本題10分）詳細闡述在拓撲排序的性能優化中，如何減少不必要的比較和操作。4、（本題10分）在數據結構中，闡述如何使用跳表進行范圍查詢，給出算法