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

《數據結構》2021-2022學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一棵二叉搜索樹，進行中序遍歷得到的序列是一個有序序列。若對其進行刪除操作，以下關于時間復雜度的描述，哪一項是正確的？A.平均時間復雜度為O(logn)，最壞情況為O(n)B.時間復雜度始終為O(logn)C.平均時間復雜度為O(n)，最壞情況為O(nlogn)D.時間復雜度始終為O(n)2、在一個用順序存儲結構實現的棧中，若棧頂指針top指向棧頂元素的上一個位置，當棧為空時，top的值為？A.-1B.0C.1D.n-1（其中n為棧的最大容量）3、以下關于紅黑樹的性質，錯誤的是：A.每個節點要么是紅色，要么是黑色B.根節點是黑色的C.每個葉子節點（NIL節點）是黑色的D.紅色節點的子節點一定是紅色的4、對于一個用鏈表表示的線性表，在表頭插入一個新元素和在表尾插入一個新元素，哪個操作更復雜？A.表頭插入B.表尾插入C.復雜度相同D.取決于鏈表長度5、在一個鏈式存儲的線性表中，若要刪除第i個元素（1<=i<=n），需要找到其前驅節點的時間復雜度為？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)6、若要對一棵二叉排序樹進行中序遍歷，得到的序列是一個有序序列，這是因為二叉排序樹的定義具有什么特性？（）A.左子樹的值小于根節點，右子樹的值大于根節點B.左子樹和右子樹的深度相同C.每個節點的值都不同D.以上都不是7、在一個鏈式存儲的棧中，若棧頂指針為top，要判斷棧是否為空，應判斷？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL8、在一個具有n個頂點和e條邊的帶權無向圖中，使用Prim算法生成最小生成樹。若采用鄰接矩陣存儲圖，以下關于算法的空間復雜度的描述，哪一項是正確的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)9、在一個用鏈表實現的隊列中，若要刪除隊頭元素并返回其值，需要的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、在一個字符串匹配算法中，BM算法相對于樸素的字符串匹配算法，其優勢在于？（）A.平均性能更好B.代碼更簡潔C.空間復雜度更低D.適用于短字符串匹配11、在一棵平衡二叉樹中，插入一個新結點后，可能需要進行的調整操作是：A.左旋B.右旋C.左旋和右旋D.不需要調整12、以下哪種數據結構常用于實現字符串的最長公共子序列問題？A.二維數組B.棧C.隊列D.樹13、以下哪種數據結構在處理頻繁的插入和刪除操作時，不需要移動大量元素？（）A.數組B.鏈表C.棧D.隊列14、在一個具有n個節點的完全二叉樹中，若底層從左到右第x個節點為葉子節點，則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]15、在一個具有n個節點的完全二叉樹中，若節點編號從1開始，對于編號為i的節點，其雙親節點的編號是多少？A.i/2B.(i-1)/2C.(i+1)/2D.以上都不對16、對于一個具有n個節點的線索二叉樹，若n個節點中有m個空指針域，則線索的數量為？A.mB.m/2C.n+1D.n-117、對于單鏈表，若要訪問鏈表中的第i個元素，必須從鏈表的頭指針開始依次遍歷，平均時間復雜度為O(n)。那么如果要在鏈表的末尾添加一個新元素，時間復雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)18、在一個順序存儲的棧中，若棧頂指針top為-1，則表示棧（）A.已滿B.為空C.已損壞D.無法確定19、對于一個具有n個頂點和e條邊的帶權無向圖，使用克魯斯卡爾算法構造最小生成樹時，每次選擇的邊是？（）A.權值最小的邊B.連接兩個連通分量的權值最小的邊C.任意一條邊D.以上都不對20、在一棵二叉搜索樹中，刪除一個只有左子樹的節點，其右子樹的節點需要（）A.替換被刪除節點B.保持不動C.全部刪除D.移動到左子樹二、簡答題（本大題共4個小題，共40分)1、（本題10分）比較計數排序和冒泡排序在處理大量重復數據時的效率。2、（本題10分）詳細說明如何使用基數排序對整數或字符串進行排序，分析其原理和時間復雜度。3、（本題10分）論述如何使用堆優化迪杰斯特拉算法求解單源最短路徑問題的性能。4、（本題10分）詳細說明如何在一個無向圖中判斷是否為二部圖，給出算法步驟和實現代碼，并分析其時間復雜度。三、設