懷化學院《數(shù)據(jù)結構》2021-2022學年期末試卷

站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁懷化學院

《數(shù)據(jù)結構》2021-2022學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個大根堆，若將堆中所有元素按照層次遍歷的順序存儲到一個數(shù)組中，以下關于數(shù)組元素的排列，哪一項是正確的？A.完全無序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對2、在一個用鄰接表存儲的有向圖中，若要計算某個節(jié)點的出度，以下哪種方法較為高效？A.遍歷該節(jié)點的鄰接表B.遍歷整個圖的鄰接表C.無法高效計算D.以上都不對3、深度為5的滿二叉樹的結點數(shù)為：A.16B.31C.32D.154、若一棵二叉樹的中序遍歷序列是ABCDEFG，后序遍歷序列是BDCAFGE，則其先序遍歷序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB5、在二叉搜索樹中，每個節(jié)點的值都大于其左子樹中所有節(jié)點的值，小于其右子樹中所有節(jié)點的值。以下關于二叉搜索樹的操作，不正確的是（）A.插入操作需要按照節(jié)點值的大小找到合適的位置B.查找操作的時間復雜度在最壞情況下為O(n)C.刪除節(jié)點時，如果該節(jié)點有兩個子節(jié)點，可以選擇其左子樹中的最大節(jié)點或右子樹中的最小節(jié)點進行替換D.二叉搜索樹總是平衡的，即左右子樹的高度差不超過16、已知一個哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測法處理沖突。若依次插入關鍵字31、25、19、49、37、21、13、17，則在查找關鍵字19時需要進行幾次比較？（）A.1B.2C.3D.47、在一個平衡二叉樹中，插入一個新節(jié)點后可能會導致樹的不平衡，此時需要進行調(diào)整。以下哪種調(diào)整操作可能會被執(zhí)行？（）A.左旋B.右旋C.先左旋后右旋D.以上都有可能8、在圖的存儲結構中，鄰接多重表主要用于存儲無向圖，以下關于鄰接多重表的特點，描述錯誤的是（）A.可以方便地刪除邊B.存儲空間比鄰接矩陣節(jié)省C.對于判斷兩點之間是否有邊，效率較高D.不適合用于有向圖的存儲9、在一棵AVL樹中，進行插入操作后，可能導致樹失去平衡，此時需要進行的旋轉操作最多為（）A.1次B.2次C.logn次D.n次10、在圖的最小生成樹算法中，Kruskal算法和Prim算法都能得到最小生成樹，以下關于這兩個算法的比較，錯誤的是（）A.Kruskal算法基于邊，Prim算法基于節(jié)點B.Kruskal算法需要使用并查集C.Prim算法的時間復雜度通常比Kruskal算法低D.對于稀疏圖，Kruskal算法更優(yōu)11、若對一棵二叉搜索樹進行先序遍歷，得到的節(jié)點序列是一個遞減序列，則該二叉搜索樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空12、以下哪種數(shù)據(jù)結構常用于實現(xiàn)字典操作，并且能夠快速查找、插入和刪除元素？（）A.棧B.隊列C.二叉搜索樹D.數(shù)組13、在一個具有n個節(jié)點的完全二叉樹中，若底層從左到右依次編號，節(jié)點i的左孩子節(jié)點編號是多少（假設根節(jié)點編號為1）？A.2iB.2i+1C.i*2D.以上都不對14、對于一個有向圖，使用鄰接矩陣存儲，判斷是否存在從頂點i到頂點j的邊的時間復雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)15、以下哪種數(shù)據(jù)結構可以方便地實現(xiàn)字典操作（添加、刪除、查找），且平均時間復雜度較低？A.數(shù)組B.鏈表C.二叉搜索樹D.哈希表16、設有一個具有n個頂點的帶權無向圖，使用普里姆（Prim）算法求最小生成樹。在算法執(zhí)行過程中，需要選擇一個頂點作為起始點。以下關于起始點選擇對算法時間復雜度的影響，哪一個是恰當?shù)模緼.起始點的選擇對時間復雜度沒有影響B(tài).選擇不同的起始點可能導致時間復雜度不同C.選擇頂點度最小的作為起始點可以降低時間復雜度D.選擇頂點度最大的作為起始點可以降低時間復雜度17、已知一個帶權無向圖的鄰接矩陣表示，若要計算圖中兩個頂點之間的最短路徑，可以使用的算法是？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法18、在一個用數(shù)組實現(xiàn)的堆中，若要刪除堆底的元素，需要的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、已知一棵二叉排序樹的中序遍歷序列為{10,12,15,18,20,25,30}，則其可能的前序遍歷序列為？（）A.20,18,15,12,10,25,30B.10,12,15,18,20,25,30C.30,25,20,18,15,12,10D.10,12,18,15,20,30,2520、對于一個具有n個頂點和e條邊的無向連通圖，利用Prim算法構造最小生成樹時，其時間復雜度為：A.O(n^2)B.O(elogn)C.O(nlogn)D.O(e^2)二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細說明如何在一個具有n個頂點的無向圖中找出所有頂點之間的最短路徑長度之和。2、（本題10分）解釋如何在一個具有n個元素的鏈表中，使用冒泡排序算法進行排序，并分析其時間復雜度和空間復雜度。3、（本題10分）描述二叉樹的遍歷算法在二叉樹的最大路徑和問題、樹的路徑問題變種中的應用。4、（本題10分）詳細說明如何在一個具有n個元素的鏈表中，使用插入排序算法進行排序，