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

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

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