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

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁成都錦城學(xué)院

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