學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁阿壩師范學院

《數據結構與算法》2021-2022學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個帶頭結點的單鏈表中，若要刪除表中所有值為x的結點，最優的算法時間復雜度是？（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)2、對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表存儲，則其空間復雜度為：A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)3、在一個用鄰接矩陣存儲的圖中，若要判斷兩個節點是否相鄰，時間復雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)4、對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則存儲空間的復雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)5、在一個具有n個頂點和e條邊的無向圖中，采用鄰接表存儲，其時間復雜度為？（）A.O(n+e)B.O(n2)C.O(e2)D.O(ne)6、若要在一棵二叉搜索樹中查找一個特定的值，平均時間復雜度為？（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)7、以下哪種數據結構常用于實現LRU（最近最少使用）頁面置換算法？A.隊列B.棧C.哈希表D.雙鏈表8、以下哪種數據結構常用于實現圖的存儲？A.鄰接矩陣和鄰接表B.二叉樹和鏈表C.棧和隊列D.數組和哈希表9、棧是一種特殊的線性數據結構，它遵循后進先出（LIFO）的原則。以下關于棧的說法中，錯誤的是？（）A.棧可以用數組或鏈表實現。B.棧的插入和刪除操作只能在棧頂進行。C.棧可以用于實現函數調用、表達式求值等。D.棧的容量是無限的，可以存儲任意數量的元素。10、一棵二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為BDCAEHFG，則該二叉樹的后序遍歷序列為（）。A.DCBGFHEAB.DCBHGFEAC.BCDGFHEAD.BCDHGFEA11、在一個具有n個元素的順序存儲的線性表中，要在第i個位置插入一個新元素（1<=i<=n+1），需要移動的元素個數約為？A.n-iB.iC.n-i+1D.n-i-112、在一個具有n個元素的小根堆中，刪除堆頂元素后，將最后一個元素放到堆頂，然后進行調整，其時間復雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)13、對于一個棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則下列不可能的出棧序列是：A.54321B.45321C.12345D.3142514、對于一個采用鏈式存儲的隊列，若隊頭指針和隊尾指針相同，則隊列的狀態為：A.隊空B.隊滿C.不確定D.隊列中只有一個元素15、在一個具有n個頂點的帶權有向圖中，使用迪杰斯特拉（Dijkstra）算法求單源最短路徑。以下關于該算法的時間復雜度的描述，哪一項是準確的？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)16、在一個具有n個元素的雙向鏈表中，要在指定節點之后插入一個新節點，需要修改幾個指針？A.2B.3C.4D.517、對于一個具有n個元素的堆，進行插入操作的時間復雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)18、對于一個大根堆，若將堆中所有元素按照層次遍歷的順序存儲到一個數組中，以下關于數組元素的排列，哪一項是正確的？A.完全無序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對19、設有一個具有n個節點的二叉樹，若每個節點都有左右子樹，則該二叉樹的葉子節點數量與度為2的節點數量之間存在特定關系。以下關于這種關系的描述，哪一項是正確的？A.葉子節點數量等于度為2的節點數量B.葉子節點數量比度為2的節點數量多1C.葉子節點數量比度為2的節點數量少1D.兩者之間沒有固定關系20、設有一個具有n個節點的二叉平衡樹，若要插入一個新節點并保持平衡，以下關于插入操作的平均時間復雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）闡述并查集中如何通過數據結構的改進提高空間利用率。2、（本題10分）解釋如何對一個鏈表進行排序，選擇合適的排序算法（如歸并排序）給出算法步驟和實現代碼，并分析其時間復雜度和空間復雜度。3、（本題10分）在一個雙向鏈表中，如何刪除指定區間內的結點？4、（本題10分）說明在一個具有n個頂點和e條邊的帶權有向圖中，如何使用A*算法進行啟發式搜索，并分析算法的性能和適用場景。三