賀州學院《數(shù)據(jù)結(jié)構(gòu)實驗》2022-2023學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁賀州學院《數(shù)據(jù)結(jié)構(gòu)實驗》

2022-2023學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、已知一棵二叉排序樹的中序遍歷序列為{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,252、在一個具有n個元素的數(shù)組中，進行順序查找，若查找成功，平均比較次數(shù)約為？A.n/2B.nC.lognD.13、若一個隊列的入隊序列是1、2、3、4、5，在進行出隊操作時，第一個出隊的元素是：A.1B.2C.3D.44、在一個順序存儲的隊列中，若要在隊尾插入一個元素，需要移動元素的平均次數(shù)為（）A.0B.n/2C.nD.n-15、在一個順序存儲的棧中，若棧頂指針top為-1，則表示棧（）A.已滿B.為空C.已損壞D.無法確定6、已知一個帶權(quán)無向圖的鄰接矩陣表示，若要計算圖中兩個頂點之間的最短路徑，可以使用的算法是？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法7、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)表達式樹？A.二叉樹B.鏈表C.棧D.隊列8、對于一棵二叉搜索樹，進行中序遍歷得到的序列是一個有序序列。若對其進行刪除操作，以下關(guān)于時間復雜度的描述，哪一項是正確的？A.平均時間復雜度為O(logn)，最壞情況為O(n)B.時間復雜度始終為O(logn)C.平均時間復雜度為O(n)，最壞情況為O(nlogn)D.時間復雜度始終為O(n)9、以下哪種排序算法對大規(guī)模數(shù)據(jù)排序時，通常不被優(yōu)先選擇？A.冒泡排序B.插入排序C.快速排序D.歸并排序10、若一棵二叉樹的中序遍歷序列是ABCDEFG，后序遍歷序列是BDCAFGE，則其先序遍歷序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB11、設有一個廣義表L=((a,b),c,(d,e))，其表頭和表尾分別為？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)12、在一個具有n個頂點的有向無環(huán)圖中，使用拓撲排序算法，其結(jié)果的唯一性如何？A.一定唯一B.可能不唯一C.取決于頂點的編號D.以上都不對13、棧和隊列的應用場景非常廣泛，以下關(guān)于它們的應用的說法中，錯誤的是？（）A.?？梢杂糜趯崿F(xiàn)函數(shù)調(diào)用、表達式求值和括號匹配等。B.隊列可以用于實現(xiàn)任務調(diào)度、消息隊列和廣度優(yōu)先搜索等。C.棧和隊列可以用于實現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊列只適用于計算機科學領(lǐng)域，在其他領(lǐng)域沒有實際價值。14、在一個具有n個元素的有序數(shù)組中，使用插入排序進行排序，其最壞情況下的時間復雜度為？（）A.O(n)B.O(log?n)C.O(n2)D.O(nlog?n)15、以下關(guān)于紅黑樹的性質(zhì)，錯誤的是：A.每個節(jié)點要么是紅色，要么是黑色B.根節(jié)點是黑色的C.每個葉子節(jié)點（NIL節(jié)點）是黑色的D.紅色節(jié)點的子節(jié)點一定是紅色的16、在一個具有n個節(jié)點的帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹，其時間復雜度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取決于圖的結(jié)構(gòu)17、在一個具有n個元素的最小堆中，插入一個新元素后，為了重新調(diào)整為最小堆，最壞情況下需要比較多少次？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)18、在一個具有n個元素的順序存儲的循環(huán)隊列中，隊滿的條件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front19、對于一個具有n個元素的循環(huán)隊列，隊頭指針為front，隊尾指針為rear，隊列滿的條件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front20、對于一個采用順序存儲的棧，若棧頂指針top等于-1時，表示：A.棧滿B.棧空C.棧中只有一個元素D.棧中至少有一個元素二、簡答題（本大題共4個小題，共40分)1、（本題10分）闡述如何在一個具有n個頂點的圖中，使用鄰接表存儲結(jié)構(gòu)獲取頂點的度，并分析其時間復雜度。2、（本題10分）論述在字符串操作中，如何實現(xiàn)字符串的反轉(zhuǎn)、拼接和比較等常見操作。3、（本題10分）分析在數(shù)據(jù)結(jié)構(gòu)中，如何利用棧實現(xiàn)表達式的求值和轉(zhuǎn)換。4、（本題10分）論述在最短路徑算法的并行化實現(xiàn)中，如何劃分任務和協(xié)調(diào)