保定學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》2022-2023學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁保定學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》

2022-2023學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹中，其葉子節(jié)點(diǎn)的數(shù)量大約為（）A.n/2B.n/4C.n/8D.n/2-12、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的AVL樹，插入一個(gè)新節(jié)點(diǎn)后，調(diào)整樹的平衡，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的完全二叉樹，其葉子節(jié)點(diǎn)的數(shù)量為？（）A.n/2B.(n+1)/2C.n-1D.n4、已知一個(gè)棧的進(jìn)棧序列為1,2,3,4，出棧序列為3,2,4,1，則棧的容量至少為（）。A.2B.3C.4D.55、在數(shù)據(jù)結(jié)構(gòu)中，樹的遍歷可以采用遞歸和非遞歸方式。以下關(guān)于非遞歸中序遍歷二叉樹的說法，錯(cuò)誤的是（）A.可以使用棧來輔助實(shí)現(xiàn)B.比遞歸方式更復(fù)雜C.時(shí)間復(fù)雜度與遞歸方式相同D.空間復(fù)雜度一定比遞歸方式低6、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)有向圖中，使用迪杰斯特拉算法求最短路徑，其時(shí)間復(fù)雜度是多少？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)7、在一個(gè)具有n個(gè)節(jié)點(diǎn)的有向圖中，若存在環(huán)，則使用拓?fù)渑判蛩惴〞?huì)出現(xiàn)什么情況？A.正常完成排序B.無法完成排序C.排序結(jié)果不準(zhǔn)確D.以上都不對(duì)8、對(duì)于一個(gè)具有n個(gè)元素的循環(huán)隊(duì)列，隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列滿的條件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front9、在一個(gè)具有n個(gè)元素的無序數(shù)組中，采用冒泡排序進(jìn)行排序，在最壞情況下，需要比較的次數(shù)為（）。A.n-1B.n(n-1)/2C.n(n+1)/2D.n^210、在一個(gè)用數(shù)組實(shí)現(xiàn)的小根堆中，若要插入一個(gè)元素，應(yīng)該將其插入到數(shù)組的哪個(gè)位置？A.數(shù)組末尾B.堆頂C.任意位置D.以上都不對(duì)11、以下關(guān)于平衡二叉樹旋轉(zhuǎn)調(diào)整的描述，正確的是：A.旋轉(zhuǎn)調(diào)整一定會(huì)改變樹的中序遍歷結(jié)果B.左旋操作是將右子樹變?yōu)楦?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)樽笞庸?jié)點(diǎn)C.右旋操作是將左子樹變?yōu)楦?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)橛易庸?jié)點(diǎn)D.平衡二叉樹不需要進(jìn)行旋轉(zhuǎn)調(diào)整12、在一個(gè)帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹時(shí)，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個(gè)連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對(duì)13、對(duì)于一個(gè)用鏈表實(shí)現(xiàn)的棧，若要獲取棧中元素的個(gè)數(shù)，以下哪種方法效率較高？A.遍歷鏈表B.維護(hù)一個(gè)計(jì)數(shù)器C.以上效率相同D.以上都不對(duì)14、平衡二叉樹是一種特殊的二叉搜索樹，通過自動(dòng)調(diào)整保持樹的平衡。以下關(guān)于平衡二叉樹的操作，不正確的是（）A.插入節(jié)點(diǎn)可能會(huì)導(dǎo)致樹的不平衡，需要進(jìn)行旋轉(zhuǎn)調(diào)整B.平衡二叉樹的查找效率在最壞情況下為O(logn)C.平衡因子用于判斷節(jié)點(diǎn)是否平衡D.平衡二叉樹的節(jié)點(diǎn)刪除操作比插入操作更復(fù)雜15、圖的存儲(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ì)影響圖的操作效率。16、跳表是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)，用于實(shí)現(xiàn)有序集合的快速查找。關(guān)于跳表的特點(diǎn)，以下描述錯(cuò)誤的是（）A.跳表的查找、插入和刪除操作的平均時(shí)間復(fù)雜度為O(logn)B.跳表通過增加索引層次來提高查找效率C.跳表的空間復(fù)雜度比普通鏈表高D.跳表的性能不如二叉搜索樹17、在一個(gè)具有n個(gè)元素的有序數(shù)組中進(jìn)行二分查找，其時(shí)間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(logn)D.O(n^2)18、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖中，采用鄰接表存儲(chǔ)，求頂點(diǎn)的入度的時(shí)間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)19、在一個(gè)帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接已選頂點(diǎn)和未選頂點(diǎn)的權(quán)值最小的邊C.任意一條邊D.以上都不對(duì)20、設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前插入一個(gè)新元素，并且移動(dòng)元素的平均次數(shù)為n/2，則插入算法的平均時(shí)間復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋什么是哈夫曼編碼，并說明其在數(shù)據(jù)壓縮中的作用和優(yōu)勢(shì)。2、（本題10分）詳細(xì)說明字符串匹配的BF算法和KMP算法的基本思想，比較它們?cè)诓煌闆r下的性能優(yōu)劣。3、（本題10分）分析在數(shù)據(jù)結(jié)構(gòu)中，如何利用堆進(jìn)行Top-K問題的求解。4、（本題10分）解釋什么是樹狀數(shù)組數(shù)據(jù)結(jié)構(gòu)，說明其特點(diǎn)和應(yīng)用場(chǎng)景，并闡述如何進(jìn)行區(qū)間求和和單點(diǎn)