湖北中醫(yī)藥大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷

自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線第1頁(yè)，共3頁(yè)湖北中醫(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、在一個(gè)具有n個(gè)頂點(diǎn)和m條邊的無(wú)向圖中，若采用鄰接表存儲(chǔ)，則存儲(chǔ)空間復(fù)雜度主要取決于？A.nB.mC.n+mD.n^22、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時(shí)間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(n^3)3、一棵完全二叉樹(shù)的第5層（根為第1層）有16個(gè)葉子節(jié)點(diǎn)，則該完全二叉樹(shù)的節(jié)點(diǎn)總數(shù)最少為（）。A.47B.55C.63D.644、哈希表的性能取決于哈希函數(shù)的設(shè)計(jì)和沖突解決方法的選擇，以下關(guān)于它們的說(shuō)法中，錯(cuò)誤的是？（）A.好的哈希函數(shù)應(yīng)該具有均勻分布性、隨機(jī)性和高效性等特點(diǎn)。B.沖突解決方法的選擇應(yīng)該根據(jù)哈希表的大小、數(shù)據(jù)的特點(diǎn)和操作的頻率等因素來(lái)決定。C.哈希表的性能可以通過(guò)調(diào)整哈希函數(shù)和沖突解決方法來(lái)優(yōu)化。D.哈希表的性能只取決于哈希函數(shù)的設(shè)計(jì)，與沖突解決方法無(wú)關(guān)。5、對(duì)于一個(gè)具有n個(gè)元素的有序單鏈表，若要在其中查找一個(gè)特定元素，平均需要比較的次數(shù)為？（）A.n/2B.nC.lognD.nlogn6、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，若每個(gè)頂點(diǎn)的度均為k，則該圖的邊數(shù)為（）。A.nkB.nk/2C.(n-1)k/2D.(n+1)k/27、對(duì)于一個(gè)具有n個(gè)元素的快速排序，在最好情況下，其時(shí)間復(fù)雜度為？（）A.O(nlogn)B.O(n^2)C.O(n)D.O(logn)8、設(shè)有一個(gè)m階的B樹(shù)，每個(gè)非葉子節(jié)點(diǎn)至少有┌m/2┐個(gè)孩子，則一棵3階B樹(shù)中，根節(jié)點(diǎn)最少有幾個(gè)孩子？（）A.1B.2C.3D.49、對(duì)于一個(gè)具有n個(gè)元素的堆排序，其空間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行插入操作的時(shí)間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠方便地實(shí)現(xiàn)集合的交、并、差等運(yùn)算？（）A.二叉樹(shù)B.鏈表C.哈希表D.樹(shù)狀數(shù)組12、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)中，若每個(gè)節(jié)點(diǎn)的值都不相同，并且中序遍歷和后序遍歷的結(jié)果分別為[4,2,5,1,3]和[4,5,2,3,1]，則先序遍歷的結(jié)果為（）A.[1,2,4,3,5]B.[1,2,3,4,5]C.[1,2,4,5,3]D.[1,3,2,5,4]13、對(duì)于一個(gè)具有n個(gè)元素的冒泡排序，在最壞情況下，需要進(jìn)行多少次比較操作？（）A.n(n-1)/2B.nC.n+1D.n-114、對(duì)于一棵二叉搜索樹(shù)，進(jìn)行中序遍歷得到的序列是一個(gè)有序序列。若對(duì)其進(jìn)行刪除操作，以下關(guān)于時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.平均時(shí)間復(fù)雜度為O(logn)，最壞情況為O(n)B.時(shí)間復(fù)雜度始終為O(logn)C.平均時(shí)間復(fù)雜度為O(n)，最壞情況為O(nlogn)D.時(shí)間復(fù)雜度始終為O(n)15、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無(wú)向圖中，若要判斷圖是否連通，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.克魯斯卡爾算法D.以上都可以16、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖，其鄰接矩陣中非零元素的個(gè)數(shù)最多為？（）A.eB.2eC.n^2D.n(n-1)17、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，若采用鄰接矩陣存儲(chǔ)，則矩陣中非零元素的個(gè)數(shù)至少為？（）A.nB.n-1C.2(n-1)D.n(n-1)/218、一棵二叉樹(shù)的先序遍歷序列為ABCDEFGH，中序遍歷序列為BDCAEHFG，則該二叉樹(shù)的后序遍歷序列為（）。A.DCBGFHEAB.DCBHGFEAC.BCDGFHEAD.BCDHGFEA19、對(duì)于一個(gè)具有n個(gè)元素的歸并排序，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)20、在一個(gè)有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖中，采用鄰接矩陣存儲(chǔ)，其空間復(fù)雜度為多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）論述如何利用圖的深度優(yōu)先搜索算法生成圖的生成樹(shù)。2、（本題10分）對(duì)于一個(gè)具有n個(gè)元素的數(shù)組，如何使用希爾排序算法處理逆序?qū)^多的數(shù)據(jù)？3、（本題10分）論述跳表在內(nèi)存受限環(huán)境下的優(yōu)化方法和策略。4、（本題10分）詳細(xì)說(shuō)明如何在一個(gè)具有n個(gè)元素的隊(duì)列中，實(shí)現(xiàn)元素的循環(huán)移位，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。三