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

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