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

2022-2023學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為：A.CBEFDGAB.CEBFDGAC.CBEFAGDD.CEBFAGD2、對于一個m行n列的二維數組，按行優先存儲時，元素a[i][j]（0<=i<m,0<=j<n）的地址計算公式為：A.LOC(a[i][j])=LOC(a[0][0])+i*n+jB.LOC(a[i][j])=LOC(a[0][0])+j*m+iC.LOC(a[i][j])=LOC(a[0][0])+i*m+jD.LOC(a[i][j])=LOC(a[0][0])+j*n+i3、在一個具有n個元素的最小堆中，插入一個新元素并調整為最小堆，其時間復雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、在圖的最小生成樹算法中，Kruskal算法和Prim算法都能得到最小生成樹，以下關于這兩個算法的比較，錯誤的是（）A.Kruskal算法基于邊，Prim算法基于節點B.Kruskal算法需要使用并查集C.Prim算法的時間復雜度通常比Kruskal算法低D.對于稀疏圖，Kruskal算法更優5、對于一個具有n個節點的二叉樹，進行先序遍歷和中序遍歷，得到的序列相同，則該二叉樹的形狀為？A.只有一個根節點B.所有節點只有左子樹C.所有節點只有右子樹D.是一棵滿二叉樹6、對于一個棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.5B.14C.21D.無數種7、在一個具有n個元素的順序表中，若要在第i個元素（1<=i<=n）之前插入一個新元素，需要移動的元素個數為？（）A.n-iB.iC.n-i+1D.n-i-18、在一個具有n個元素的二叉排序樹中，查找一個不存在的元素，其時間復雜度最壞情況下為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)9、設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲其下三角部分，第一個元素A[1,1]存儲在數組B[0]中，若A[8,5]在數組B中的存儲位置為k，則A[7,5]在數組B中的存儲位置為（）。A.k-13B.k-12C.k-11D.k-1010、在數據結構中，使用并查集解決集合合并問題時，以下關于路徑壓縮的描述，錯誤的是（）A.可以提高查找效率B.不改變集合的關系C.增加了合并操作的復雜度D.使樹的高度降低11、對于一個具有n個節點的帶權有向圖，使用迪杰斯特拉算法求最短路徑，其時間復雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)12、對于一個具有n個元素的無序數組，使用快速排序算法進行排序，在平均情況下的空間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、隊列也是一種線性表，遵循先進先出原則。在一個循環隊列中，隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，那么判斷隊列為空的條件是什么？A.front==rearB.(rear+1)%MAXSIZE==frontC.front==(rear+1)%MAXSIZED.以上都不對14、若一個圖的鄰接矩陣對角線以下（不包括對角線）的元素全為0，則該圖一定是：A.無向圖B.有向圖C.強連通圖D.弱連通圖15、在一個具有n個頂點的有向完全圖中，邊的數量為？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n16、在一個用順序存儲結構實現的棧中，若棧頂指針top指向棧頂元素的上一個位置，當棧為空時，top的值為？A.-1B.0C.1D.n-1（其中n為棧的最大容量）17、圖的存儲方式和遍歷方式對圖的操作效率有很大影響，以下關于它們的說法中，錯誤的是？（）A.鄰接矩陣適合存儲稠密圖，查找邊的時間復雜度為O(1)，但空間復雜度較高。B.鄰接表適合存儲稀疏圖，插入邊和刪除邊的時間復雜度為O(1)，但查找邊的時間復雜度較高。C.深度優先搜索和廣度優先搜索是圖的兩種基本遍歷方式，它們的時間復雜度都為O(n+m)，其中n是頂點數，m是邊數。D.圖的存儲方式和遍歷方式一旦確定，就不能再改變，否則會影響圖的操作效率。18、在一個用數組實現的小根堆中，若要插入一個元素，應該將其插入到數組的哪個位置？A.數組末尾B.堆頂C.任意位置D.以上都不對19、在一個帶權的有向圖中，使用迪杰斯特拉算法求從源點到其他頂點的最短路徑，每次選擇的頂點是？（）A.距離源點最近的頂點B.距離源點最遠的頂點C.未確定最短路徑的頂點中權值最小的頂點D.未確定最短路徑的頂點中權值最大的頂點20、在一個循環鏈表中，若要刪除鏈表中的最后一個節點，需要的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細說明如何在一個具有n個元素的順序表中，進行刪除操作，并分析其時間復雜度和空間復雜度。2、（本題10分）解釋什么是哈希表沖突，以及常見的解決哈希表沖突的方法有哪些？3、（本題10分）解釋如何使用跳表實現有序集合的插入、刪除和查找操作，分析其時間復雜度和空間復雜度。4、（本題10分）解釋線段