荊楚理工學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁荊楚理工學(xué)院《數(shù)據(jù)結(jié)構(gòu)》

2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在數(shù)據(jù)結(jié)構(gòu)中，使用并查集解決集合合并問題時，以下關(guān)于路徑壓縮的描述，錯誤的是（）A.可以提高查找效率B.不改變集合的關(guān)系C.增加了合并操作的復(fù)雜度D.使樹的高度降低2、在一個具有n個元素的順序表中，若要在第i個元素（1<=i<=n）之前插入一個新元素，需要向后移動多少個元素？（）A.n-iB.iC.n-i+1D.n-i-13、若對一棵二叉搜索樹進(jìn)行先序遍歷，得到的節(jié)點(diǎn)序列是一個遞減序列，則該二叉搜索樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空4、在圖的存儲結(jié)構(gòu)中，十字鏈表主要用于存儲有向圖，以下關(guān)于十字鏈表的特點(diǎn)，描述不正確的是（）A.既能方便地訪問出邊，也能方便地訪問入邊B.存儲空間比鄰接表節(jié)省C.對于刪除邊的操作比較復(fù)雜D.不適合用于稀疏有向圖5、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEABC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EACDB6、在一個具有n個元素的無序鏈表中，若要對其進(jìn)行快速排序，以下關(guān)于快速排序的平均時間復(fù)雜度的描述，哪一項是準(zhǔn)確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)7、哈希表是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)。在處理哈希沖突時，常用的方法有開放地址法和鏈地址法。以下關(guān)于這兩種方法的描述，哪一項是不準(zhǔn)確的？A.開放地址法會增加查找時間B.鏈地址法需要額外的指針空間C.開放地址法容易產(chǎn)生聚集現(xiàn)象D.鏈地址法的沖突解決更復(fù)雜8、已知一個圖的鄰接表如下所示，則從頂點(diǎn)V1出發(fā)進(jìn)行廣度優(yōu)先遍歷，可能得到的頂點(diǎn)訪問序列是（）。V1:->V2->V3V2:->V4V3:->V4->V5V4:->V5V5:A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V4,V3,V5D.V1,V4,V2,V3,V59、在一個具有n個元素的有序單鏈表中，要查找一個特定元素，平均時間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)10、在一個具有n個頂點(diǎn)和e條邊的無向圖中，采用鄰接表存儲，其時間復(fù)雜度為？（）A.O(n+e)B.O(n2)C.O(e2)D.O(ne)11、對于一個棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則下列不可能的出棧序列是：A.54321B.45321C.12345D.3142512、在二叉搜索樹中，左子樹的所有節(jié)點(diǎn)值都小于根節(jié)點(diǎn)值，右子樹的所有節(jié)點(diǎn)值都大于根節(jié)點(diǎn)值。若要查找一個特定值的節(jié)點(diǎn)，以下哪種方法效率最高？A.先序遍歷B.中序遍歷C.后序遍歷D.以上效率相同13、在一個用十字鏈表存儲的有向圖中，查找一個頂點(diǎn)的所有出邊和入邊的時間復(fù)雜度是？（）A.O(1)B.O(n)C.O(e)D.O(n+e)14、在一個具有n個元素的循環(huán)鏈表中，查找第i個元素（1<=i<=n），平均需要比較的次數(shù)為（）。A.nB.n/2C.(n+1)/2D.(n-1)/215、對于一個棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.5B.14C.21D.無數(shù)種16、若要對一個具有n個元素的有序鏈表進(jìn)行二分查找，是否可行？（）A.可行B.不可行C.有時可行D.取決于鏈表長度17、對于一個有向無環(huán)圖（DAG），進(jìn)行拓?fù)渑判虻姆椒ú恢挂环N。以下關(guān)于拓?fù)渑判虻拿枋?，錯誤的是（）A.可以使用深度優(yōu)先搜索實現(xiàn)B.結(jié)果不唯一C.可以用于判斷圖中是否存在環(huán)D.所有節(jié)點(diǎn)的入度在排序過程中不會改變18、以下哪種數(shù)據(jù)結(jié)構(gòu)可以快速判斷一個元素是否在集合中？A.鏈表B.二叉搜索樹C.哈希表D.棧19、對于一個具有n個節(jié)點(diǎn)的二叉樹，若每個節(jié)點(diǎn)都有左子樹和右子樹，則其葉子節(jié)點(diǎn)的個數(shù)至少為？A.n/2B.(n+1)/2C.n-1D.logn20、以下關(guān)于堆的描述，正確的是：A.大頂堆中每個父節(jié)點(diǎn)的值都大于其子節(jié)點(diǎn)的值B.小頂堆中每個父節(jié)點(diǎn)的值都小于其子節(jié)點(diǎn)的值C.堆可以用順序存儲也可以用鏈?zhǔn)酱鎯.堆是完全二叉樹二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細(xì)闡述在一個具有n個頂點(diǎn)的無向圖中，如何進(jìn)行邊的雙連通分量的求解。2、（本題10分）解釋如何判斷一個二叉樹是否為完全二叉樹，給出算法步驟和代碼實現(xiàn)。3、（本題10分）詳細(xì)說明棧的基本操作（入棧、出棧）的實現(xiàn)原理，以及棧在函數(shù)調(diào)用和表達(dá)式求值中的應(yīng)用。4、（本題10分）詳細(xì)論述在利用堆進(jìn)行多路歸并排序時，如何構(gòu)建初始堆和進(jìn)行歸并過程，并給出具體的算法步驟和代碼