西安電子科技大學《數(shù)據(jù)結構與數(shù)據(jù)庫技術》2021-2022學年期末試卷

自覺遵守考場紀律如考試作弊此答卷無效密自覺遵守考場紀律如考試作弊此答卷無效密封線第1頁，共3頁西安電子科技大學

《數(shù)據(jù)結構與數(shù)據(jù)庫技術》2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個節(jié)點的完全二叉樹，若底層從左到右填充，則第i個節(jié)點的左孩子節(jié)點的編號為？A.2iB.2i+1C.i*2D.i*2+12、二叉樹是一種重要的數(shù)據(jù)結構，具有多種遍歷方式。對于先序遍歷、中序遍歷和后序遍歷，以下描述錯誤的是（）A.先序遍歷先訪問根節(jié)點，然后遞歸遍歷左子樹和右子樹B.中序遍歷先遞歸遍歷左子樹，然后訪問根節(jié)點，最后遞歸遍歷右子樹C.后序遍歷先遞歸遍歷左子樹和右子樹，最后訪問根節(jié)點D.這三種遍歷方式的結果總是相同的3、在一棵二叉搜索樹中，刪除一個有兩個子節(jié)點的節(jié)點時，通常采用的方法是：A.用左子樹的最大值替代該節(jié)點B.用右子樹的最小值替代該節(jié)點C.隨機選擇左子樹或右子樹的節(jié)點替代D.不進行替代，直接刪除4、在一個具有n個元素的順序存儲的線性表中，刪除第i個元素（1<=i<=n），平均需要移動多少個元素？（）A.n-iB.iC.(n-i)/2D.n/25、在一個具有n個頂點的無向圖中，若采用鄰接矩陣存儲，則存儲空間復雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)6、在一個帶權有向圖中，若以頂點v為源點，利用迪杰斯特拉算法求從v到其他頂點的最短路徑，在算法執(zhí)行過程中，每個頂點的最短路徑值是如何確定的？（）A.初始時都設為無窮大，逐步更新B.初始時都設為0，逐步更新C.隨機設定，逐步更新D.根據(jù)頂點的權值設定，逐步更新7、在一個長度為n的有序線性表中進行二分查找，在最壞情況下，需要比較的次數(shù)為（）。A.O(n)B.O(n^2)C.O(log?n)D.O(nlog?n)8、對于一個具有n個頂點的無向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同9、在一個有向圖中，所有頂點的入度之和與出度之和的關系是：A.入度之和大于出度之和B.入度之和小于出度之和C.入度之和等于出度之和D.沒有確定的關系10、對于一個用鏈表實現(xiàn)的棧，若要獲取棧中元素的個數(shù)，以下哪種方法效率較高？A.遍歷鏈表B.維護一個計數(shù)器C.以上效率相同D.以上都不對11、若對線性表的操作只有兩種，即插入和刪除，且以鏈表作為存儲結構，則插入和刪除操作的時間復雜度分別為：A.O(n)和O(n)B.O(1)和O(1)C.O(n)和O(1)D.O(1)和O(n)12、一棵完全二叉樹的第6層（根為第1層）有8個葉子節(jié)點，則該完全二叉樹的節(jié)點總數(shù)最多為（）。A.39B.56C.111D.11913、在一個具有n個節(jié)點的帶權無向圖中，使用普里姆算法構造最小生成樹，其時間復雜度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取決于圖的結構14、一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲，其空間復雜度為？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)15、在二叉樹中，判斷兩棵二叉樹是否完全相同，以下方法不正確的是（）A.同時進行先序遍歷，比較節(jié)點值B.同時進行中序遍歷，比較節(jié)點值C.同時進行后序遍歷，比較節(jié)點值D.比較兩棵樹的節(jié)點數(shù)量16、在數(shù)據(jù)結構中，字典樹（Trie樹）常用于字符串的存儲和查找，以下關于字典樹的特點，不正確的是（）A.對于前綴相同的字符串可以節(jié)省存儲空間B.查找操作的時間復雜度與字符串長度有關C.適合用于詞頻統(tǒng)計D.插入和刪除操作比較復雜17、若一棵二叉樹的層次遍歷序列為ABCDEFGHI，則其可能的中序遍歷序列有多少種？（）A.1B.n!C.2^nD.不確定18、對于一個具有n個元素的無序數(shù)組，若要對其進行排序，以下哪種算法在最壞情況下時間復雜度最高？（）A.冒泡排序B.快速排序C.插入排序D.選擇排序19、在一個具有n個元素的堆中，進行插入操作的時間復雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)20、在數(shù)據(jù)結構中，桶排序是一種外部排序算法，以下關于桶排序的描述，錯誤的是（）A.要求輸入數(shù)據(jù)具有特定的分布B.時間復雜度為O(n)C.空間復雜度較高D.適用于大規(guī)模數(shù)據(jù)排序二、簡答題（本大題共4個小題，共40分)1、（本題10分）鏈表的反轉操作在雙向鏈表中的實現(xiàn)方法與單向鏈表有何不同？2、（本題10分）解釋如何在一個具有n個元素的最小堆中，找出第k小的元素，并分析其時間復雜度。3、（本題10分）論述如何使用動態(tài)規(guī)劃算法解決最長公共子串問題。4、（本題10分）解釋如何將一個二叉樹轉換為雙向鏈表，給出算法步驟和實現(xiàn)代碼，并