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

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁湖北中醫(yī)藥大學(xué)《數(shù)據(jù)結(jié)構(gòu)》

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