自覺遵守考場紀律如考試作弊此答卷無效密自覺遵守考場紀律如考試作弊此答卷無效密封線第1頁，共3頁北京郵電大學

《數據結構與算法導論》2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個循環隊列中，若隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，則判斷隊滿的條件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front2、在一棵完全二叉樹中，若節點個數為n，那么其葉子節點的個數大約為多少？（）A.n/2B.n/4C.(n+1)/2D.n/33、已知一個有序表為{5,10,15,20,25,30,35,40,45,50}，使用折半查找法查找值為35的元素，需要比較的次數是（）。A.1B.2C.3D.44、在一個具有n個元素的順序表中，若要將其逆置，以下關于操作的時間復雜度的描述，哪一項是恰當的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、在一個具有n個頂點的無向圖中，若存在從頂點i到頂點j的路徑，同時也存在從頂點j到頂點i的路徑，則該圖被稱為？（）A.強連通圖B.弱連通圖C.連通圖D.非連通圖6、在一個具有n個頂點的圖中，若存在回路，則深度優先遍歷可能會出現什么情況？（）A.訪問某些頂點多次B.無法完成遍歷C.結果不正確D.以上都有可能7、對于一個有向圖，使用鄰接矩陣存儲，判斷是否存在從頂點i到頂點j的邊的時間復雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)8、以下關于字符串匹配算法的描述，哪一項是不正確的？（）A.BF算法的時間復雜度在最壞情況下較高B.KMP算法通過利用已匹配的部分信息來提高效率C.BM算法在一般情況下比KMP算法效率更高D.所有字符串匹配算法的時間復雜度都與模式串的長度成正比9、以下哪種數據結構常用于實現字符串的反轉操作？A.棧B.隊列C.鏈表D.樹10、在一個大根堆中，刪除堆頂元素后，為了重新調整為大根堆，需要進行的操作是？（）A.將最后一個元素移到堆頂，然后從堆頂向下調整B.將堆中所有元素重新排序C.將堆頂元素與最后一個元素交換，然后從堆頂向下調整D.無需調整11、哈希表是一種用于快速查找的數據結構，通過哈希函數將關鍵字映射到存儲位置。關于哈希沖突的解決方法，錯誤的是（）A.開放定址法通過尋找空閑位置來解決沖突B.鏈地址法將沖突的元素存儲在鏈表中C.再哈希法通過更換哈希函數來解決沖突D.哈希沖突無法避免，且對查找效率沒有影響12、若對一棵二叉搜索樹進行先序遍歷，得到的節點序列是一個遞減序列，則該二叉搜索樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空13、一棵完全二叉樹的第6層（根為第1層）有8個葉子節點，則該完全二叉樹的節點總數最多為（）。A.39B.56C.111D.11914、對于一個具有n個頂點和m條邊的有向圖，使用鄰接表存儲，其入度和出度的計算時間復雜度分別為（）A.O(n)和O(m)B.O(m)和O(n)C.O(n+m)和O(n+m)D.O(n^2)和O(n^2)15、設有一個具有n個節點的二叉樹，采用中序遍歷將其轉換為一個有序的單鏈表。以下關于轉換過程的時間復雜度的描述，哪一項是正確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)16、對于一個具有n個元素的直接插入排序，在最好情況下，需要進行多少次比較操作？（）A.n-1B.nC.n(n-1)/2D.017、設有一個棧S和一個隊列Q，初始時棧為空，隊列為{1,2,3,4,5}。經過一系列入棧和出棧、入隊和出隊操作后，棧頂元素為3，此時隊列的頭元素為？（）A.1B.2C.4D.518、在一棵二叉搜索樹中，刪除一個有兩個子節點的節點時，通常采用的方法是：A.用左子樹的最大值替代該節點B.用右子樹的最小值替代該節點C.隨機選擇左子樹或右子樹的節點替代D.不進行替代，直接刪除19、已知一個帶權無向圖的鄰接矩陣表示，若要計算圖中兩個頂點之間的最短路徑，可以使用的算法是？（）A.深度優先搜索B.廣度優先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法20、在一個帶權的有向圖中，使用迪杰斯特拉算法求從源點到其他頂點的最短路徑，每次選擇的頂點是？（）A.距離源點最近的頂點B.距離源點最遠的頂點C.未確定最短路徑的頂點中權值最小的頂點D.未確定最短路徑的頂點中權值最大的頂點二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細闡述如何使用A*算法在圖中進行尋路，解釋其啟發函數的作用和設計原則，并分析其性能優勢。2、（本題10分）描述二叉樹的中序遍歷在二叉搜索樹中的特殊意義。3、（本題10分）深入分析在具有n個元素的數組中，如何實現快速選擇算法，用于查找第k小的元素，并給出時間復雜度的分析。4、（本題10分）詳細說明在樹的應用中，如何使用二叉樹實現表達式求值或存儲文件系統