青島大學《數(shù)據(jù)結(jié)構(gòu)與算法基礎》2021-2022學年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁青島大學《數(shù)據(jù)結(jié)構(gòu)與算法基礎》

2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、鏈表是另一種常見的數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點組成，每個節(jié)點包含數(shù)據(jù)和指向下一個節(jié)點的指針。以下關于鏈表的說法中，錯誤的是？（）A.鏈表的插入和刪除操作比較方便，只需要修改指針即可。B.鏈表可以動態(tài)地增長和縮小，不像數(shù)組那樣受固定長度的限制。C.鏈表的訪問速度比數(shù)組慢，因為需要遍歷鏈表才能找到特定的元素。D.鏈表只能存儲整數(shù)類型的數(shù)據(jù)元素。2、設有一個具有n個節(jié)點的二叉樹，采用中序遍歷將其轉(zhuǎn)換為一個有序的單鏈表。以下關于轉(zhuǎn)換過程的時間復雜度的描述，哪一項是正確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)3、對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A.nB.n^2C.n(n-1)D.n(n+1)4、在一個用鄰接矩陣存儲的無向圖中，若要刪除一條邊，需要修改矩陣中的幾個元素？A.1個B.2個C.3個D.4個5、已知一個棧的進棧序列為1,2,3,4,5，下列序列中不可能是出棧序列的是（）。A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,56、對于一個具有n個頂點和m條邊的有向圖，使用鄰接表存儲，其入度和出度的計算時間復雜度分別為（）A.O(n)和O(m)B.O(m)和O(n)C.O(n+m)和O(n+m)D.O(n^2)和O(n^2)7、已知一個圖的鄰接表存儲結(jié)構(gòu)，若要判斷任意兩個頂點之間是否存在邊，哪種方法最有效？（）A.遍歷鄰接表B.建立逆鄰接表C.建立鄰接矩陣D.深度優(yōu)先搜索8、在一棵紅黑樹中，插入一個新節(jié)點后，調(diào)整樹的結(jié)構(gòu)以保持紅黑性質(zhì)的操作次數(shù)最多為（）A.1B.2C.lognD.n9、在一個用十字鏈表存儲的有向圖中，查找一個頂點的所有出邊和入邊的時間復雜度是？（）A.O(1)B.O(n)C.O(e)D.O(n+e)10、哈希表的性能取決于哈希函數(shù)的設計和沖突解決方法的選擇，以下關于它們的說法中，錯誤的是？（）A.好的哈希函數(shù)應該具有均勻分布性、隨機性和高效性等特點。B.沖突解決方法的選擇應該根據(jù)哈希表的大小、數(shù)據(jù)的特點和操作的頻率等因素來決定。C.哈希表的性能可以通過調(diào)整哈希函數(shù)和沖突解決方法來優(yōu)化。D.哈希表的性能只取決于哈希函數(shù)的設計，與沖突解決方法無關。11、在數(shù)據(jù)結(jié)構(gòu)中，使用隊列來實現(xiàn)廣度優(yōu)先遍歷圖，以下關于遍歷過程的描述，錯誤的是（）A.從起始節(jié)點開始入隊B.隊列為空時結(jié)束遍歷C.訪問節(jié)點時將其未訪問的鄰接節(jié)點入隊D.節(jié)點不會被重復訪問12、在一個具有n個節(jié)點的二叉樹中，若采用后序遍歷得到的節(jié)點序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定13、對于一個具有n個頂點的無向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同14、設有一個長度為n的順序表，要在第i個元素之前插入一個新元素，并且移動元素的平均次數(shù)為n/2，則插入算法的平均時間復雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)15、若要從一個具有n個元素的有序單鏈表中刪除所有值重復的元素，使得鏈表中每個元素的值都不同，最優(yōu)的算法時間復雜度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)16、對于一個用鄰接矩陣存儲的圖，若要判斷兩個頂點之間是否存在邊，時間復雜度為？（）A.O(1)B.O(n)C.O(log?n)D.O(n2)17、已知一個哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測法處理沖突。若依次插入關鍵字31、25、19、49、37、21、13、17，則在查找關鍵字19時需要進行幾次比較？（）A.1B.2C.3D.418、在一棵平衡二叉樹中，插入一個新節(jié)點后可能導致失衡，需要進行調(diào)整。以下哪種調(diào)整操作可能涉及到旋轉(zhuǎn)次數(shù)最多？（）A.LL型調(diào)整B.RR型調(diào)整C.LR型調(diào)整D.RL型調(diào)整19、數(shù)組通常具有的兩種基本操作是：A.插入和刪除B.查找和修改C.遍歷和排序D.索引和賦值20、在數(shù)據(jù)結(jié)構(gòu)中，使用并查集解決集合合并問題時，以下關于路徑壓縮的描述，錯誤的是（）A.可以提高查找效率B.不改變集合的關系C.增加了合并操作的復雜度D.使樹的高度降低二、簡答題（本大題共4個小題，共40分)1、（本題10分）比較快速排序和歸并排序在空間利用上的不同，并舉例說明。2、（本題10分）解釋如何在一個二叉搜索樹中進行層次遍歷的迭代實現(xiàn)，給出算法步驟和實現(xiàn)代碼，并分析其時間復雜度。3、（本題10分）解釋如何在一個字符串中查找第一個只出現(xiàn)一次的字符。4、（本題10分）闡述在一個帶權(quán)有向圖中，如何使用迪杰斯特拉算法求解單源最短路徑問題，分析算法的正確性和時