阜陽師范大學(xué)《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》2022-2023學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁阜陽師范大學(xué)

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》2022-2023學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA2、對于一個采用鏈表存儲的棧，若要獲取棧的大?。ㄔ財?shù)量），以下關(guān)于操作的時間復(fù)雜度的描述，哪一個是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、在一個具有n個元素的小頂堆中，若將堆頂元素與最后一個元素交換，然后對堆進(jìn)行調(diào)整，其時間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)4、若哈希函數(shù)H(key)=key%7，要將關(guān)鍵字38插入到長度為7的哈希表中，其存儲位置是：A.3B.5C.6D.05、以下哪種排序算法是穩(wěn)定的排序算法？A.快速排序B.選擇排序C.冒泡排序D.希爾排序6、在數(shù)據(jù)結(jié)構(gòu)中，字典樹在處理大量字符串時，可能會出現(xiàn)內(nèi)存占用過高的問題，以下解決方法錯誤的是（）A.壓縮節(jié)點B.限制字典樹的深度C.使用哈希表替代字典樹D.減少字符串的存儲7、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為（）。A.CEABDB.CEDBAC.CABDED.CEDAB8、在數(shù)據(jù)結(jié)構(gòu)中，使用并查集解決集合合并問題時，以下關(guān)于路徑壓縮的描述，錯誤的是（）A.可以提高查找效率B.不改變集合的關(guān)系C.增加了合并操作的復(fù)雜度D.使樹的高度降低9、在一個具有n個元素的鏈表中，若要在表頭插入一個新元素，平均需要修改幾個指針？（）A.1B.2C.nD.n+110、在一個具有n個節(jié)點的無向圖中，若要判斷圖是否連通，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.克魯斯卡爾算法D.以上都可以11、對于一個采用鏈表存儲的隊列，若要刪除隊尾元素，以下關(guān)于操作的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)12、在一個用數(shù)組實現(xiàn)的堆中，若要刪除堆底的元素，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、在一個具有n個頂點和m條邊的無向圖中，若采用鄰接表存儲，則存儲空間復(fù)雜度主要取決于？A.nB.mC.n+mD.n^214、在一棵二叉樹中，若每個節(jié)點的左子樹和右子樹的高度最多相差1，則該二叉樹被稱為平衡二叉樹。對于一個平衡二叉樹，進(jìn)行插入操作后，為了保持平衡，可能需要進(jìn)行多少次旋轉(zhuǎn)調(diào)整？A.0次B.1次C.最多2次D.不確定15、對于一個具有n個元素的希爾排序，其時間復(fù)雜度取決于？（）A.初始序列B.增量序列C.元素值D.以上都是16、在一個有序表（12,24,36,48,60,72,84）中，使用二分查找法查找48，需要比較的次數(shù)是：A.1B.2C.3D.417、一棵完全二叉樹的第5層（根為第1層）有16個葉子節(jié)點，則該完全二叉樹的節(jié)點總數(shù)最少為（）。A.47B.55C.63D.6418、在一個具有n個節(jié)點的有向圖中，若存在環(huán)，則使用拓?fù)渑判蛩惴〞霈F(xiàn)什么情況？A.正常完成排序B.無法完成排序C.排序結(jié)果不準(zhǔn)確D.以上都不對19、已知一個圖的鄰接矩陣如下所示：ABCDA0110B1011C1100D0100則該圖中頂點A的度為：A.1B.2C.3D.420、設(shè)有一個帶權(quán)有向圖G=(V,E)，采用拓?fù)渑判蛩惴▽ζ溥M(jìn)行排序，若得到的拓?fù)湫蛄形ㄒ唬瑒t圖G一定是？（）A.有環(huán)圖B.無環(huán)圖C.強連通圖D.弱連通圖二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述伸展樹在元素插入后的調(diào)整過程和時間復(fù)雜度分析。2、（本題10分）解釋什么是伸展樹數(shù)據(jù)結(jié)構(gòu)，說明其自調(diào)整的原理和優(yōu)勢，并闡述如何進(jìn)行插入和查找操作。3、（本題10分）深入分析在具有n個元素的鏈表中，如何刪除指定位置的節(jié)點，并給出具體的算法步驟和代碼實現(xiàn)。4、（本題10分）簡述哈希表的哈希函數(shù)設(shè)計原則，包括均勻性、高效性等方面。三、設(shè)計題（本大題共2個小題，共20