北京聯(lián)合大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2022-2023學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁北京聯(lián)合大學(xué)

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