湖南工商大學《數據結構》2022-2023學年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁湖南工商大學《數據結構》

2022-2023學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下關于圖的遍歷算法的描述，哪一項是正確的？（）A.深度優(yōu)先遍歷和廣度優(yōu)先遍歷都能訪問到圖中的所有節(jié)點B.深度優(yōu)先遍歷適合用于求解最短路徑問題C.廣度優(yōu)先遍歷的空間復雜度低于深度優(yōu)先遍歷D.兩種遍歷算法的時間復雜度都與圖的邊數成正比2、在一個具有n個頂點的圖中，若存在回路，則深度優(yōu)先遍歷可能會出現什么情況？（）A.訪問某些頂點多次B.無法完成遍歷C.結果不正確D.以上都有可能3、對于一個具有n個頂點的帶權連通圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時間復雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(e^2)4、在一個具有n個元素的順序表中，刪除第i個元素（1<=i<=n），需要移動的元素個數最多為（）。A.i-1B.n-iC.n-i+1D.n-15、對于一個具有n個元素的哈希表，若采用鏈地址法處理沖突，以下關于查找操作的平均時間復雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則該二叉樹的后序遍歷序列為（）。A.CBEFDGAB.CEBFDGAC.CBEFGDAD.CEBFGDA7、以下關于快速排序的描述，錯誤的是：A.快速排序在平均情況下的時間復雜度為O(nlogn)B.快速排序是一種不穩(wěn)定的排序算法C.快速排序在最壞情況下的時間復雜度為O(n^2)D.快速排序不需要額外的存儲空間8、對于一個具有n個元素的待排序序列，若采用冒泡排序算法進行排序，在最壞情況下需要進行的比較次數為？（）A.n(n-1)/2B.nlognC.n-1D.n9、在一個哈希表中，解決沖突的方法不包括：A.開放定址法B.再哈希法C.建立索引表D.鏈地址法10、對于一個具有n個頂點和e條邊的無向連通圖，利用Prim算法構造最小生成樹時，其時間復雜度為：A.O(n^2)B.O(elogn)C.O(nlogn)D.O(e^2)11、對于一個用鏈表實現的棧，若要獲取棧中元素的個數，以下哪種方法效率較高？A.遍歷鏈表B.維護一個計數器C.以上效率相同D.以上都不對12、若要在一棵二叉搜索樹中查找一個特定的值，平均時間復雜度為？（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)13、以下哪種數據結構常用于實現操作系統(tǒng)中的進程調度？A.隊列B.棧C.樹D.圖14、對于一個具有n個節(jié)點的完全二叉樹，若按層序編號，則編號為i的節(jié)點，其雙親節(jié)點的編號為？A.i/2B.(i-1)/2C.2iD.2i+115、以下哪種數據結構能夠高效地支持動態(tài)集合的操作，如合并、查找等？（）A.鏈表B.二叉樹C.并查集D.哈希表16、以下關于串的描述，錯誤的是：A.串是一種特殊的線性表B.串的長度是指串中字符的個數C.空串和空格串是相同的概念D.串的存儲方式有順序存儲和鏈式存儲17、對于一個具有n個節(jié)點的二叉樹，其先序遍歷、中序遍歷和后序遍歷的結果都是唯一確定的，這個二叉樹一定是（）A.滿二叉樹B.完全二叉樹C.單支樹D.以上都不是18、在一個順序存儲的棧中，若要實現共享棧，即兩個棧共用一個數組空間，以下關于棧頂指針的設置，哪一種方案較為合理？A.兩個棧的棧頂指針分別從數組的兩端向中間移動B.兩個棧的棧頂指針都從數組的同一端開始移動C.一個棧的棧頂指針從數組的開頭移動，另一個從結尾移動D.以上都可以19、若要在一個已排序的數組中使用二分查找算法查找一個特定元素，以下關于時間復雜度的描述，哪一項是正確的？A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)20、在一個具有n個節(jié)點的無向圖中，若邊的數量遠遠小于n(n-1)/2，則適合使用哪種存儲方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以二、簡答題（本大題共4個小題，共40分)1、（本題10分）深入探討在一個具有n個元素的二叉搜索樹中，如何進行范圍查詢。2、（本題10分）深入分析在具有n個頂點的圖中，如何進行拓撲排序以確定任務的執(zhí)行順序，并說明其應用場景。3、（本題10分）詳細說明最短路徑問題的定義，以及Dijkstra算法和Floyd算法在解決不同類型最短路徑問題中的應用。4、（本題10分）解釋如何在一個二叉搜索樹中進行刪除操作的多線程實現，給出算法步驟和實現代碼，并