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

2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個B樹中，每個節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量最少為多少？（）A.1B.2C.?m/2?-1D.m-12、對于一個具有n個元素的順序存儲的循環(huán)隊列，隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，若隊列非空，則隊列中元素的個數(shù)為？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+13、對于一個有向無環(huán)圖，進(jìn)行拓?fù)渑判蚩梢缘玫揭粋€線性的序列。以下關(guān)于拓?fù)渑判虻恼f法，錯誤的是？（）A.可以使用深度優(yōu)先搜索來實現(xiàn)B.結(jié)果可能不唯一C.若存在回路則無法進(jìn)行拓?fù)渑判駾.其時間復(fù)雜度為O(n2)4、在一個鏈?zhǔn)酱鎯Φ臈Ｖ?，若棧頂指針為top，要判斷棧是否為空，應(yīng)判斷？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL5、對于一個具有n個元素的堆，進(jìn)行插入操作的時間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一個有向圖中，所有頂點(diǎn)的入度之和與出度之和的關(guān)系是：A.入度之和大于出度之和B.入度之和小于出度之和C.入度之和等于出度之和D.沒有確定的關(guān)系7、對于一個具有n個節(jié)點(diǎn)的紅黑樹，插入一個新節(jié)點(diǎn)后，調(diào)整樹的結(jié)構(gòu)以保持紅黑樹性質(zhì)，其時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、在一個具有n個頂點(diǎn)的有向強(qiáng)連通圖中，至少需要多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)9、在一個具有n個元素的最小堆中，插入一個新元素后，為了重新調(diào)整為最小堆，最壞情況下需要比較多少次？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)10、在一個具有n個元素的順序表中，刪除第i個元素（1<=i<=n），平均需要移動的元素個數(shù)約為？A.n/2B.n-iC.iD.n-i+111、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，具有多種遍歷方式。對于先序遍歷、中序遍歷和后序遍歷，以下描述錯誤的是（）A.先序遍歷先訪問根節(jié)點(diǎn)，然后遞歸遍歷左子樹和右子樹B.中序遍歷先遞歸遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后遞歸遍歷右子樹C.后序遍歷先遞歸遍歷左子樹和右子樹，最后訪問根節(jié)點(diǎn)D.這三種遍歷方式的結(jié)果總是相同的12、若要對100個元素進(jìn)行排序，以下哪種排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.選擇排序C.插入排序D.歸并排序13、對于一個具有n個元素的有序單鏈表，若要在其中查找一個特定元素，其平均時間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)14、以下哪種數(shù)據(jù)結(jié)構(gòu)在處理頻繁的插入和刪除操作時，不需要移動大量元素？（）A.數(shù)組B.鏈表C.棧D.隊列15、在數(shù)據(jù)結(jié)構(gòu)中，斐波那契堆是一種可合并堆，以下關(guān)于斐波那契堆的特點(diǎn)，描述不正確的是（）A.插入操作的時間復(fù)雜度為O(1)B.查找最小元素的時間復(fù)雜度為O(1)C.刪除最小元素的時間復(fù)雜度為O(logn)D.合并操作的時間復(fù)雜度為O(n)16、在一個循環(huán)隊列中，隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，若rear>front，則隊列中的元素個數(shù)為？A.rear-frontB.rear-front+MAXSIZEC.rear-front-1D.(rear-front+MAXSIZE)%MAXSIZE17、以下哪種數(shù)據(jù)結(jié)構(gòu)可以快速查找一個有序數(shù)組中的中位數(shù)？A.二叉搜索樹B.堆C.哈希表D.鏈表18、在一個具有n個頂點(diǎn)的有向完全圖中，邊的數(shù)量為：A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)19、一個有序序列為{12,18,24,35,47,50,62,83,90,115,134}，當(dāng)用二分法查找值為90的元素時，需要比較的次數(shù)是（）。A.1B.2C.3D.420、在一個具有n個元素的雙向鏈表中，刪除一個指定節(jié)點(diǎn)，其時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述如何使用動態(tài)規(guī)劃算法解決最長公共子串問題。2、（本題10分）詳細(xì)說明選擇排序算法的基本思想和在最壞情況下的時間復(fù)雜度分析。3、（本題10分）解釋在平衡二叉搜索樹中，刪除操作可能導(dǎo)致的不平衡情況及相應(yīng)的調(diào)整方法。4、（本題10分）論述如何使用分治法解決最大子數(shù)