北方民族大學《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學年期末試卷

站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁北方民族大學

《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個節(jié)點的圖中，使用弗洛伊德算法求所有節(jié)點對之間的最短路徑，其時間復雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)2、在一個具有n個節(jié)點的完全二叉樹中，其葉子節(jié)點的數(shù)量大約為（）A.n/2B.n/4C.n/8D.n/2-13、已知一個有序表為{11,22,33,44,55,66,77,88,99}，使用折半查找法查找值為77的元素，需要比較的次數(shù)是（）。A.1B.2C.3D.44、在一個具有n個元素的無序鏈表中，若要對其進行快速排序，以下關(guān)于快速排序的平均時間復雜度的描述，哪一項是準確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)5、在數(shù)據(jù)結(jié)構(gòu)中，紅黑樹的插入操作可能會導致樹的不平衡，需要進行調(diào)整。以下關(guān)于調(diào)整過程的描述，不正確的是（）A.可能需要進行顏色修改和旋轉(zhuǎn)操作B.調(diào)整后的紅黑樹仍然滿足紅黑樹的性質(zhì)C.調(diào)整的目的是使樹的高度盡量降低D.每次插入操作都需要進行多次調(diào)整6、在一個具有n個頂點和m條邊的有向圖中，使用弗洛伊德算法求所有頂點對之間的最短路徑，其時間復雜度為？A.O(n^2)B.O(n^3)C.O(mn)D.O(m^2)7、在一個具有n個節(jié)點的無向圖中，若邊的數(shù)量遠遠小于n(n-1)/2，則適合使用哪種存儲方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以8、對于一個具有n個元素的有序單鏈表，若要在其中查找一個特定元素，其平均時間復雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)9、AVL樹是一種高度平衡的二叉搜索樹，以下關(guān)于AVL樹的旋轉(zhuǎn)操作，描述不正確的是（）A.旋轉(zhuǎn)操作用于保持樹的平衡B.包括單旋轉(zhuǎn)和雙旋轉(zhuǎn)兩種類型C.旋轉(zhuǎn)操作不會改變二叉搜索樹的性質(zhì)D.每次插入或刪除節(jié)點都需要進行旋轉(zhuǎn)操作10、在二叉樹的序列化和反序列化過程中，以下方法不能保證唯一性的是（）A.先序遍歷序列化B.中序遍歷序列化C.后序遍歷序列化D.層序遍歷序列化11、對于一個具有n個頂點的無向連通圖，若要判斷其是否存在環(huán)，以下哪種算法的時間復雜度最低？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓撲排序D.以上算法時間復雜度相同12、在一棵二叉樹中，若度為2的節(jié)點有10個，度為1的節(jié)點有20個，那么葉子節(jié)點的數(shù)量是多少？A.11B.21C.30D.無法確定13、圖的存儲方式和遍歷方式對圖的操作效率有很大影響，以下關(guān)于它們的說法中，錯誤的是？（）A.鄰接矩陣適合存儲稠密圖，查找邊的時間復雜度為O(1)，但空間復雜度較高。B.鄰接表適合存儲稀疏圖，插入邊和刪除邊的時間復雜度為O(1)，但查找邊的時間復雜度較高。C.深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的兩種基本遍歷方式，它們的時間復雜度都為O(n+m)，其中n是頂點數(shù)，m是邊數(shù)。D.圖的存儲方式和遍歷方式一旦確定，就不能再改變，否則會影響圖的操作效率。14、在一個采用哈希表存儲的數(shù)據(jù)結(jié)構(gòu)中，哈希函數(shù)將關(guān)鍵字映射到存儲位置。若發(fā)生哈希沖突，通常采用開放定址法解決。以下關(guān)于開放定址法的時間復雜度的描述，哪一個是恰當?shù)?？A.查找操作的時間復雜度在平均情況下為O(1)，最壞情況為O(n)B.查找操作的時間復雜度始終為O(1)C.查找操作的時間復雜度在平均情況下為O(logn)，最壞情況為O(nlogn)D.查找操作的時間復雜度始終為O(n)15、在一個長度為n的有序線性表中進行二分查找，在最壞情況下，需要比較的次數(shù)為（）。A.O(n)B.O(n^2)C.O(log?n)D.O(nlog?n)16、在一個具有n個元素的循環(huán)隊列中，若隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，則隊列中元素的個數(shù)為？A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+117、在一個具有n個頂點和e條邊的無向圖中，使用克魯斯卡爾（Kruskal）算法生成最小生成樹。以下關(guān)于該算法的時間復雜度的描述，哪一項是正確的？A.O(nlogn)B.O(eloge)C.O(elogn)D.O(n^2)18、在一個長度為n的有序數(shù)組中進行二分查找，其時間復雜度為？（）A.O(n)B.O(nlogn)C.O(logn)D.O(n2)19、在一個具有n個元素的無序數(shù)組中，使用順序查找算法查找一個特定元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.nlogn20、對于一個具有n個元素的大頂堆，若要獲取堆中的第k大元素（1<=k<=n），以下哪種方法效率較高？A.先排序再獲取B.每次刪除堆頂元素k-1次C.構(gòu)建一個大小為k的小頂堆，然后逐步替換D.以上方法效率相同二、簡答題（本大題共4個小題，共40分)1、（本題10分）在一個具有n個節(jié)點的二叉搜索樹中，如何查找第k小的元素，給出算法思路和時間復雜度分析。2、（本題10分）深入分析在具有n個頂點和e條邊的有向圖中，如何計算圖的傳遞閉包，并給出一種有效的算法和代碼示例。3、（本題10分）解釋在一個有向圖中如何判斷是否存在回路，以及如何使用拓撲排序?qū)D進行排序。4、（本題10分）解釋并舉例說明在