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

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

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