湖南中醫(yī)藥大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

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

《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行刪除堆頂元素的操作，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)2、二叉樹(shù)是一種重要的數(shù)據(jù)結(jié)構(gòu)，若一個(gè)二叉樹(shù)的先序遍歷序列為ABC，中序遍歷序列為BAC，那么它的后序遍歷序列是什么？（）A.BCAB.CBAC.CABD.ACB3、在一個(gè)具有n個(gè)元素的無(wú)序數(shù)組中，使用選擇排序進(jìn)行排序，其空間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)4、在一個(gè)具有n個(gè)元素的雙向鏈表中，刪除一個(gè)指定節(jié)點(diǎn)，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、二叉樹(shù)的性質(zhì)和遍歷方式可以用于解決很多實(shí)際問(wèn)題，以下關(guān)于它們的應(yīng)用的說(shuō)法中，錯(cuò)誤的是？（）A.二叉搜索樹(shù)可以用于實(shí)現(xiàn)高效的查找、插入和刪除操作。B.平衡二叉樹(shù)可以用于解決二叉搜索樹(shù)的不平衡問(wèn)題，提高查找效率。C.二叉樹(shù)的遍歷方式可以用于實(shí)現(xiàn)二叉樹(shù)的復(fù)制、遍歷和序列化等操作。D.二叉樹(shù)的性質(zhì)和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒(méi)有實(shí)際價(jià)值。6、設(shè)有一個(gè)m階的B+樹(shù)，每個(gè)節(jié)點(diǎn)最多有m個(gè)孩子，除根節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)至少有┌m/2┐個(gè)孩子。若要插入一個(gè)新關(guān)鍵字，需要進(jìn)行節(jié)點(diǎn)分裂的條件是？（）A.節(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)等于mB.節(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)大于mC.節(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)等于┌m/2┐D.節(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)小于┌m/2┐7、對(duì)于一個(gè)大根堆，若將堆中所有元素按照層次遍歷的順序存儲(chǔ)到一個(gè)數(shù)組中，以下關(guān)于數(shù)組元素的排列，哪一項(xiàng)是正確的？A.完全無(wú)序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對(duì)8、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)中，若每個(gè)節(jié)點(diǎn)的值都不相同，并且中序遍歷和后序遍歷的結(jié)果分別為[4,2,5,1,3]和[4,5,2,3,1]，則先序遍歷的結(jié)果為（）A.[1,2,4,3,5]B.[1,2,3,4,5]C.[1,2,4,5,3]D.[1,3,2,5,4]9、若要對(duì)100個(gè)元素進(jìn)行排序，以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.選擇排序C.插入排序D.歸并排序10、在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n11、以下關(guān)于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的描述，哪一項(xiàng)是正確的？（）A.深度優(yōu)先搜索使用隊(duì)列實(shí)現(xiàn)B.廣度優(yōu)先搜索使用棧實(shí)現(xiàn)C.兩種搜索算法都可以用于判斷圖是否連通D.深度優(yōu)先搜索一定能找到最短路徑12、在一個(gè)具有n個(gè)元素的堆中，進(jìn)行插入操作的時(shí)間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)13、以下關(guān)于紅黑樹(shù)的性質(zhì)，錯(cuò)誤的是：A.每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色B.根節(jié)點(diǎn)是黑色的C.每個(gè)葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)）是黑色的D.紅色節(jié)點(diǎn)的子節(jié)點(diǎn)一定是紅色的14、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無(wú)向圖中，若邊的數(shù)量遠(yuǎn)遠(yuǎn)小于n(n-1)/2，則適合使用哪種存儲(chǔ)方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以15、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無(wú)向圖中，使用Prim算法生成最小生成樹(shù)。若采用鄰接矩陣存儲(chǔ)圖，以下關(guān)于算法的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)16、在一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通圖中，至少有多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)17、在一個(gè)具有n個(gè)元素的雙向鏈表中，要在指定節(jié)點(diǎn)之后插入一個(gè)新節(jié)點(diǎn)，需要修改幾個(gè)指針？A.2B.3C.4D.518、在一個(gè)具有n個(gè)元素的有序數(shù)組中，使用二分查找查找一個(gè)不存在的元素，其時(shí)間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)19、在一個(gè)大根堆中，刪除堆頂元素后，為了重新調(diào)整為大根堆，需要進(jìn)行的操作是？（）A.將最后一個(gè)元素移到堆頂，然后從堆頂向下調(diào)整B.將堆中所有元素重新排序C.將堆頂元素與最后一個(gè)元素交換，然后從堆頂向下調(diào)整D.無(wú)需調(diào)整20、若要在一棵二叉搜索樹(shù)中查找一個(gè)特定的值，平均時(shí)間復(fù)雜度為？（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）比較希爾排序和快速排序在穩(wěn)定性方面的表現(xiàn)。2、（本題10分）對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的有向圖，如何判斷是否存在環(huán)并且找出環(huán)？3、（本題10分）鏈表的插入排序有哪些步驟？請(qǐng)?jiān)敿?xì)描述其實(shí)現(xiàn)過(guò)程。4、（本題10分）詳細(xì)闡述在具有n個(gè)元素的雙向循環(huán)鏈表中，如何在指定位置插入節(jié)點(diǎn)，并給出具體的算