學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁賀州學院《數據結構與算法》

2022-2023學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪種數據結構常用于實現圖的廣度優先遍歷的輔助隊列？A.循環隊列B.鏈隊列C.優先隊列D.雙端隊列2、對于一個具有n個頂點和e條邊的有向圖，采用鄰接表存儲，進行深度優先遍歷。以下關于遍歷的時間復雜度的描述，哪一個是恰當的？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)3、在一棵度為4的樹中，度為4的節點個數為1，度為3的節點個數為2，度為2的節點個數為3，度為1的節點個數為4，葉子節點個數為（）。A.15B.16C.17D.184、在一個具有n個頂點的無向圖中，若要判斷兩個頂點之間是否存在路徑，使用哪種算法較為合適？A.迪杰斯特拉算法B.弗洛伊德算法C.深度優先遍歷或廣度優先遍歷D.拓撲排序5、在數據結構中，使用棧來實現表達式求值，以下關于表達式求值的過程，描述錯誤的是（）A.遇到操作數入棧B.遇到運算符時，彈出棧頂的兩個操作數進行計算C.括號不影響求值的順序D.最終棧頂元素即為表達式的結果6、對于一個具有n個元素的堆，進行刪除操作并調整堆的時間復雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為：A.CBEFDGAB.CEBFDGAC.CBEFAGDD.CEBFAGD8、在一棵二叉搜索樹中，刪除一個有兩個子節點的節點時，通常采用的方法是：A.用左子樹的最大值替代該節點B.用右子樹的最小值替代該節點C.隨機選擇左子樹或右子樹的節點替代D.不進行替代，直接刪除9、在一個具有n個元素的鏈表中，若要在表頭插入一個新元素，平均需要修改幾個指針？（）A.1B.2C.nD.n+110、對于一個具有n個節點的平衡二叉樹，插入一個新節點并調整平衡，其平均時間復雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、在一個具有n個頂點的有向圖中，若存在頂點的入度為0，則該圖可能是：A.強連通圖B.弱連通圖C.非連通圖D.以上都不對12、設有一個棧S和一個隊列Q，初始時棧為空，隊列為{1,2,3,4,5}。經過一系列入棧和出棧、入隊和出隊操作后，棧頂元素為3，此時隊列的頭元素為？（）A.1B.2C.4D.513、對于一個具有n個頂點和e條邊的無向圖，使用深度優先搜索算法進行遍歷。以下關于算法中使用的標記數組的空間復雜度的描述，哪一項是正確的？A.O(1)B.O(n)C.O(e)D.O(n^2)14、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEABC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EACDB15、在一個棧中，若入棧序列為1,2,3,4，且在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.1716、若要對一棵二叉排序樹進行中序遍歷，得到的序列是一個有序序列，這是因為二叉排序樹的定義具有什么特性？（）A.左子樹的值小于根節點，右子樹的值大于根節點B.左子樹和右子樹的深度相同C.每個節點的值都不同D.以上都不是17、圖的存儲方式和遍歷方式對圖的操作效率有很大影響，以下關于它們的說法中，錯誤的是？（）A.鄰接矩陣適合存儲稠密圖，查找邊的時間復雜度為O(1)，但空間復雜度較高。B.鄰接表適合存儲稀疏圖，插入邊和刪除邊的時間復雜度為O(1)，但查找邊的時間復雜度較高。C.深度優先搜索和廣度優先搜索是圖的兩種基本遍歷方式，它們的時間復雜度都為O(n+m)，其中n是頂點數，m是邊數。D.圖的存儲方式和遍歷方式一旦確定，就不能再改變，否則會影響圖的操作效率。18、設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲其下三角部分，第一個元素A[1,1]存儲在數組B[0]中，若A[8,5]在數組B中的存儲位置為k，則A[7,5]在數組B中的存儲位置為（）。A.k-13B.k-12C.k-11D.k-1019、對于一個具有n個節點的無向完全圖，其邊的數量為多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/220、以下關于圖的遍歷算法的描述，哪一項是正確的？（）A.深度優先遍歷和廣度優先遍歷都能訪問到圖中的所有節點B.深度優先遍歷適合用于求解最短路徑問題C.廣度優先遍歷的空間復雜度低于深度優先遍歷D.兩種遍歷算法的時間復雜度都與圖的邊數成正比二、簡答題（本大題共4個小題，共40分)1、（本題10分）比較歸并排序和快速排序在對隨機數據的排序效果。2、（本題10分）詳細闡述基數排序算法的基本思想和適用場景，并說明其時間復雜度。3、（本題10分）詳細論述在利用二叉樹存儲數據時，如何進行前序遍歷、中序遍歷和后序遍歷，并給出相應的遞歸和非遞歸實現代碼。4、（本題10分）詳細闡述B樹在文件系統中的應用和優化