湖南工商大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁湖南工商大學(xué)《數(shù)據(jù)結(jié)構(gòu)》

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