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

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

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