學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁湖北恩施學院

《數據結構與算法》2021-2022學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪種數據結構在查找、插入和刪除操作的綜合性能上表現較好？（）A.二叉搜索樹B.紅黑樹C.B樹D.哈希表2、以下關于圖的存儲結構的描述，哪一項是正確的？（）A.鄰接矩陣適合存儲稀疏圖B.鄰接表在存儲稠密圖時空間效率較高C.十字鏈表適合存儲有向圖D.以上都不正確3、在二叉樹中，判斷兩棵二叉樹是否完全相同，以下方法不正確的是（）A.同時進行先序遍歷，比較節點值B.同時進行中序遍歷，比較節點值C.同時進行后序遍歷，比較節點值D.比較兩棵樹的節點數量4、在圖的遍歷算法中，深度優先搜索（DFS）和廣度優先搜索（BFS）是兩種常見的方法。以下關于它們的描述，錯誤的是（）A.DFS使用棧來保存未訪問的節點B.BFS使用隊列來保存未訪問的節點C.DFS可能會陷入死循環D.BFS一定能找到最短路徑5、對于一個具有n個頂點和e條邊的帶權無向圖，使用克魯斯卡爾（Kruskal）算法構造最小生成樹，其時間復雜度主要取決于：A.邊數eB.頂點數nC.n和e的和D.n和e的乘積6、對于一棵二叉搜索樹，進行中序遍歷得到的序列是一個有序序列。若對其進行刪除操作，以下關于時間復雜度的描述，哪一項是正確的？A.平均時間復雜度為O(logn)，最壞情況為O(n)B.時間復雜度始終為O(logn)C.平均時間復雜度為O(n)，最壞情況為O(nlogn)D.時間復雜度始終為O(n)7、對于一個具有n個元素的有序單鏈表，若要在其中查找一個特定元素，其平均時間復雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)8、若一個棧的輸入序列為1,2,3,4,5，不可能得到的輸出序列是？（）A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,59、在一個具有n個元素的單鏈表中，若要在第i個位置（1<=i<=n）插入一個新元素，平均需要遍歷多少個節點？（）A.i-1B.iC.(i-1)/2D.i/210、若一棵二叉樹的中序遍歷序列是ABCDEFG，后序遍歷序列是BDCAFGE，則其先序遍歷序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB11、已知一個帶權有向圖G=(V,E)，頂點集合V={1,2,3,4,5}，邊集合E={(1,2,5),(1,3,3),(2,4,2),(3,4,6),(3,5,4),(4,5,1)}，采用迪杰斯特拉（Dijkstra）算法求從頂點1到頂點5的最短路徑，經過的中間頂點依次為？（）A.2,4B.3,4C.2,3D.3,512、對于一個用鏈表實現的棧，若要獲取棧中元素的個數，以下哪種方法效率較高？A.遍歷鏈表B.維護一個計數器C.以上效率相同D.以上都不對13、若一棵二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，則該二叉樹的后序遍歷序列為？（）A.BCAB.CBAC.ABCD.ACB14、以下關于平衡二叉樹旋轉調整的描述，正確的是：A.旋轉調整一定會改變樹的中序遍歷結果B.左旋操作是將右子樹變為根節點，原根節點變為左子節點C.右旋操作是將左子樹變為根節點，原根節點變為右子節點D.平衡二叉樹不需要進行旋轉調整15、以下哪種數據結構常用于實現LRU（最近最少使用）頁面置換算法？A.隊列B.棧C.哈希表D.雙鏈表16、在一個具有n個元素的順序表中，進行插入操作時，平均移動元素的個數為：A.n/2B.(n+1)/2C.nD.n-117、在一個具有n個頂點的有向完全圖中，邊的數量為：A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)18、在一個長度為n的順序表中，刪除第i個元素（1<=i<=n）時，需要移動的元素個數為：A.n-iB.i-1C.n-i+1D.i19、對于一個具有n個頂點的帶權有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時間復雜度為：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)20、對于一個棧，進行入棧和出棧操作時，以下哪種情況會導致棧溢出？A.入棧元素過多B.出棧元素過多C.連續進行入棧操作且存儲空間已滿D.連續進行出棧操作且棧為空二、簡答題（本大題共4個小題，共40分)1、（本題10分）對于一個具有n個元素的數組，如何使用快速排序算法處理數據元素值范圍較小的情況？2、（本題10分）對于一個用鄰接表存儲的有向圖，詳細闡述如何進行深度優先遍歷和廣度優先遍歷，給出兩種遍歷算法的步驟和實現代碼框架。3、（本題10分）論述跳表中多層結構的構建原理和對查找性能的影響。4、（本題10分）隊列是一種常見的數據結構，論述其先進先出的特性，以及如何用