裝訂線裝訂線PAGE2第1頁，共3頁北京聯合大學

《數據結構與算法》2022-2023學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、設棧的初始狀態為空，元素1、2、3、4、5依次入棧，出棧序列不可能是？（）A.54321B.21543C.21345D.154322、在一個具有n個節點的二叉排序樹中，進行查找操作的平均時間復雜度是多少？A.O(n)B.O(logn)C.O(nlogn)D.取決于樹的形態3、在數據結構中，雙向循環鏈表相較于單向鏈表，以下優勢描述錯誤的是（）A.可以方便地反向遍歷B.插入和刪除節點的操作更簡單C.查找前一個節點的時間復雜度更低D.空間復雜度更低4、若要在一個已排序的數組中使用二分查找算法查找一個特定元素，以下關于時間復雜度的描述，哪一項是正確的？A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)5、在一個具有n個節點的完全二叉樹中，若底層從左到右第x個節點為葉子節點，則x的取值范圍是（）A.[2^(h-1),2^h-1]B.[2^(h-2),2^(h-1)-1]C.[2^(h-1)-1,2^h-2]D.[2^(h-2)-1,2^(h-1)-1]6、已知一個哈希表的長度為11，哈希函數為H(key)=key%11，采用二次探測法處理沖突。若依次插入關鍵字15、38、61、84，則在查找關鍵字61時需要進行幾次探測？（）A.1B.2C.3D.47、以下哪種數據結構常用于實現操作系統中的進程調度？A.隊列B.棧C.樹D.圖8、對于一個具有n個節點的無向連通圖，其生成樹的邊數為（）A.n-1B.nC.n+1D.2n9、設有一個棧，元素進棧的次序為A、B、C、D、E，下列不可能的出棧序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE10、在一個容量為10的順序存儲的循環隊列中，若front=4，rear=8，則此時隊列中元素的個數為：A.4B.5C.6D.711、在一個具有n個元素的隊列中，若要獲取隊頭元素的前一個元素但不刪除，以下操作不可行的是？（）A.遍歷整個隊列B.使用輔助數據結構C.直接獲取D.以上都不可行12、在圖的存儲結構中，十字鏈表主要用于存儲有向圖，以下關于十字鏈表的特點，描述不正確的是（）A.既能方便地訪問出邊，也能方便地訪問入邊B.存儲空間比鄰接表節省C.對于刪除邊的操作比較復雜D.不適合用于稀疏有向圖13、對于一個具有n個元素的順序存儲的循環隊列，隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，若隊列非空，則隊列中元素的個數為？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+114、在一個具有n個元素的順序表中，要在中間位置插入一個新元素，平均移動元素的個數約為？A.n/2B.nC.lognD.115、在一棵平衡二叉樹中，插入一個新結點后，可能需要進行的調整操作是：A.左旋B.右旋C.左旋和右旋D.不需要調整16、對于一個具有n個元素的無序數組，使用選擇排序進行排序，其交換次數最多為？A.n-1B.nC.n(n-1)/2D.n^217、在一個具有n個頂點和e條邊的有向圖中，采用鄰接表存儲，求頂點的入度的時間復雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)18、若一棵二叉樹的層次遍歷序列為ABCDEFGHI，則其可能的中序遍歷序列有多少種？（）A.1B.n!C.2^nD.不確定19、圖的最短路徑算法有多種，以下關于它們的說法中，錯誤的是？（）A.迪杰斯特拉算法用于求解單源最短路徑問題，即從一個源點到其他所有頂點的最短路徑。B.弗洛伊德算法用于求解任意兩點之間的最短路徑問題。C.貝爾曼-福特算法也可以用于求解單源最短路徑問題，但它的時間復雜度比迪杰斯特拉算法高。D.圖的最短路徑算法只有迪杰斯特拉算法和弗洛伊德算法兩種。20、對于一個具有n個頂點和e條邊的帶權無向圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時間復雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋如何在一個二叉搜索樹中進行刪除操作的多線程實現，給出算法步驟和實現代碼，并分析其同步和競爭問題。2、（本題10分）對于一個用鄰接表存儲的有向圖，詳細闡述如何進行深度優先遍歷和廣度優先遍歷，給出兩種遍歷算法的步驟和實現代碼框架。3、（本題10分）詳細說明如何使用并查集解決動態連通性問題，并分析其時間復雜度和空間復雜度。4、（本題10分）闡述如何在一個二叉樹中進行先序遍歷的非遞歸實現，給出算法步驟