成都錦城學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》2022-2023學(xué)年期末試卷

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記。…………密………………封………………線…………第1頁，共1頁成都錦城學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與算法》2022-2023學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、設(shè)有一個m階的B樹，每個非葉子節(jié)點至少有┌m/2┐個孩子，則一棵3階B樹中，根節(jié)點最少有幾個孩子？（）A.1B.2C.3D.42、對于一個具有n個頂點和e條邊的有向圖，其鄰接矩陣中非零元素的個數(shù)最多為？（）A.eB.2eC.n^2D.n(n-1)3、在一個具有n個元素的有序雙向鏈表中，刪除一個節(jié)點并保持鏈表有序，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、對于一個具有n個頂點的完全二叉樹，其葉子節(jié)點的數(shù)量為？（）A.n/2B.(n+1)/2C.n-1D.n5、對于一個滿二叉樹，若其高度為h，則其節(jié)點總數(shù)為多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-16、在一個具有n個元素的順序表中，若要在第i個元素（1<=i<=n）之前插入一個新元素，需要向后移動多少個元素？（）A.n-iB.iC.n-i+1D.n-i-17、在一個具有n個頂點的無向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n2D.2n(n-1)8、對于一個具有n個節(jié)點的二叉樹，若度為0的節(jié)點有n0個，度為1的節(jié)點有n1個，度為2的節(jié)點有n2個，則n0與n1、n2之間的關(guān)系為？A.n0=n1+n2B.n0=n2-1C.n0=n1-1D.n0=n2+19、以下關(guān)于圖的存儲結(jié)構(gòu)的描述，哪一項是正確的？（）A.鄰接矩陣適合存儲稀疏圖B.鄰接表在存儲稠密圖時空間效率較高C.十字鏈表適合存儲有向圖D.以上都不正確10、圖的存儲方式和遍歷方式對圖的操作效率有很大影響，以下關(guān)于它們的說法中，錯誤的是？（）A.鄰接矩陣適合存儲稠密圖，查找邊的時間復(fù)雜度為O(1)，但空間復(fù)雜度較高。B.鄰接表適合存儲稀疏圖，插入邊和刪除邊的時間復(fù)雜度為O(1)，但查找邊的時間復(fù)雜度較高。C.深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的兩種基本遍歷方式，它們的時間復(fù)雜度都為O(n+m)，其中n是頂點數(shù)，m是邊數(shù)。D.圖的存儲方式和遍歷方式一旦確定，就不能再改變，否則會影響圖的操作效率。11、在二叉樹的序列化和反序列化過程中，以下方法不能保證唯一性的是（）A.先序遍歷序列化B.中序遍歷序列化C.后序遍歷序列化D.層序遍歷序列化12、對于一棵二叉搜索樹，進(jìn)行中序遍歷得到的序列是一個有序序列。若對其進(jìn)行刪除操作，以下關(guān)于時間復(fù)雜度的描述，哪一項是正確的？A.平均時間復(fù)雜度為O(logn)，最壞情況為O(n)B.時間復(fù)雜度始終為O(logn)C.平均時間復(fù)雜度為O(n)，最壞情況為O(nlogn)D.時間復(fù)雜度始終為O(n)13、對于一個用數(shù)組實現(xiàn)的小根堆，若要將堆頂元素與最后一個元素交換，然后重新調(diào)整堆，以下關(guān)于調(diào)整的方向，哪一項是正確的？A.從堆頂向下調(diào)整B.從堆底向上調(diào)整C.先從堆頂向下調(diào)整，再從堆底向上調(diào)整D.以上都不對14、在一個具有n個頂點的有向圖中，若存在環(huán)，則使用拓?fù)渑判蛩惴〞?？A.正常排序B.無法排序C.部分排序D.排序結(jié)果不確定15、在一個m行n列的二維數(shù)組中，按列優(yōu)先存儲時，元素aij的存儲地址為？（）A.LOC(a11)+[(j-1)*m+(i-1)]*dB.LOC(a11)+[(i-1)*m+(j-1)]*dC.LOC(a11)+[(j-1)*n+(i-1)]*dD.LOC(a11)+[(i-1)*n+(j-1)]*d16、在一個具有n個元素的堆中，進(jìn)行插入操作的時間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)17、在一個具有n個節(jié)點的無向圖中，若要判斷兩個節(jié)點之間是否存在路徑，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.普里姆算法D.克魯斯卡爾算法18、在一個有向無環(huán)圖中，進(jìn)行拓?fù)渑判虻慕Y(jié)果是唯一的嗎？A.一定唯一B.一定不唯一C.可能唯一，也可能不唯一D.以上都不對19、以下關(guān)于線性表的描述，正確的是：A.線性表的元素在邏輯上和存儲上都必須是連續(xù)的B.線性表只能采用順序存儲結(jié)構(gòu)C.線性表的長度是固定不變的D.線性表可以是空表，即不含任何元素20、在一個鏈?zhǔn)酱鎯Φ木€性表中，若要刪除第i個元素（1<=i<=n），需要找到其前驅(qū)節(jié)點的時間復(fù)雜度為？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）闡述如何在一個具有n個元素的無序數(shù)組中，使用冒泡排序算法進(jìn)行排序，并分析其時間復(fù)雜度和空間復(fù)雜度。2、（本題10分）解釋什么是哈希表沖突，以及常見的解決哈希表沖突的方法有哪些？3、（本題10分）解釋什么是樹狀數(shù)組，并說明其在計算前綴和方面的應(yīng)用。4、（本題10分）詳細(xì)闡述在一個具有n個元素的堆中，如何刪除任意