學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁北京林業大學《數據可視化》

2022-2023學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個用數組實現的棧中，若要將棧的容量擴大一倍，以下哪種操作的時間復雜度最低？（）A.重新創建一個更大的數組并復制元素B.逐步將元素移動到新的更大的數組中C.直接在原數組后面追加空間D.以上操作時間復雜度相同2、在一個具有n個節點的圖中，使用深度優先搜索算法遍歷所有節點，其時間復雜度主要取決于什么？A.邊的數量B.節點的數量C.圖的存儲方式D.以上都是3、在一個具有n個頂點和e條邊的帶權有向圖中，使用弗洛伊德算法求所有頂點對之間的最短路徑，其時間復雜度為？（）A.O(n)B.O(n2)C.O(n3)D.O(e3)4、在數據結構中，鏈表的每個節點通常包含數據域和指針域。若要在一個單向鏈表中刪除一個指定節點，以下哪種操作是關鍵步驟？A.修改被刪除節點的前一個節點的指針B.修改被刪除節點的后一個節點的指針C.釋放被刪除節點的內存D.以上都是5、對于一個用數組實現的小根堆，若要將堆頂元素與最后一個元素交換，然后重新調整堆，以下關于調整的方向，哪一項是正確的？A.從堆頂向下調整B.從堆底向上調整C.先從堆頂向下調整，再從堆底向上調整D.以上都不對6、在一個具有n個元素的順序表中，若要將其逆置，以下關于操作的時間復雜度的描述，哪一項是恰當的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、在一個帶權無向圖中，使用普里姆算法構造最小生成樹時，每次選擇的邊是？（）A.權值最小的邊B.連接兩個連通分量的權值最小的邊C.任意一條邊D.以上都不對8、設有一個具有n個節點的二叉樹，采用中序遍歷將其轉換為一個有序的單鏈表。以下關于轉換過程的時間復雜度的描述，哪一項是正確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)9、在一個具有n個節點的完全二叉樹中，其葉子節點的數量大約為（）A.n/2B.n/4C.n/8D.n/2-110、在一個具有n個元素的有序數組中，若要刪除一個特定元素，并且保持數組的有序性，以下關于刪除操作的平均時間復雜度的描述，哪一項是準確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、在一個循環隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，隊列最大容量為MAXSIZE，若當前隊列長度為n，則判斷隊滿的條件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE12、對于一個具有n個元素的無序數組，使用插入排序進行排序，其最好情況下的時間復雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)13、以下哪種數據結構可以方便地實現字符串的模式匹配操作？A.二叉樹B.哈希表C.棧D.后綴樹14、在一個具有n個頂點的有向無環圖中，使用拓撲排序算法，其結果的唯一性如何？A.一定唯一B.可能不唯一C.取決于頂點的編號D.以上都不對15、在數據結構中，優先隊列可以用堆來實現，以下關于堆調整的描述，錯誤的是（）A.插入元素時，從下往上調整堆B.刪除堆頂元素時，從上往下調整堆C.調整堆的過程中，節點的值可能會交換D.調整堆的時間復雜度與堆的大小無關16、在數據結構中，線段樹的區間更新操作可以通過懶標記實現，以下關于懶標記的描述，不正確的是（）A.減少不必要的節點更新B.提高更新操作的效率C.可能會導致查詢結果不準確D.標記需要在適當的時候向下傳遞17、在一個具有n個節點的無向圖中，若要判斷圖是否連通，可以使用哪種算法？A.深度優先搜索B.廣度優先搜索C.克魯斯卡爾算法D.以上都可以18、已知一個完全二叉樹的節點總數為100，其葉子節點的個數為（）。A.49B.50C.51D.不確定19、對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則存儲空間的復雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)20、在一個哈希表中，若采用線性探測法解決哈希沖突，當發生沖突時，新元素會存儲在什么位置？A.沖突位置的下一個位置B.沖突位置C.隨機位置D.以上都不對二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述跳表在數據更新操作頻繁且數據量大的情況下的性能瓶頸及解決方案。2、（本題10分）詳細闡述在哈希表的擴容過程中，如何重新計算哈希值并遷移數據，以保證性能。3、（本題10分）比較插入排序和歸并排序在數據量較大時的性能差異。4、（本題10分）描述二叉樹的遍歷算法在二叉樹的最大路