河北地質(zhì)大學(xué)《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁河北地質(zhì)大學(xué)《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫》

2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下關(guān)于線索二叉樹的描述，錯(cuò)誤的是：A.線索二叉樹便于在中序遍歷中查找前驅(qū)和后繼節(jié)點(diǎn)B.線索二叉樹中的線索是指向空指針的指針C.線索二叉樹的存儲(chǔ)空間利用率比普通二叉樹高D.線索二叉樹的構(gòu)建過程非常簡單，不需要復(fù)雜的算法2、在二叉搜索樹中，每個(gè)節(jié)點(diǎn)的值都大于其左子樹中所有節(jié)點(diǎn)的值，小于其右子樹中所有節(jié)點(diǎn)的值。以下關(guān)于二叉搜索樹的操作，不正確的是（）A.插入操作需要按照節(jié)點(diǎn)值的大小找到合適的位置B.查找操作的時(shí)間復(fù)雜度在最壞情況下為O(n)C.刪除節(jié)點(diǎn)時(shí)，如果該節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，可以選擇其左子樹中的最大節(jié)點(diǎn)或右子樹中的最小節(jié)點(diǎn)進(jìn)行替換D.二叉搜索樹總是平衡的，即左右子樹的高度差不超過13、在一棵度為4的樹中，若有20個(gè)度為4的節(jié)點(diǎn)，10個(gè)度為3的節(jié)點(diǎn)，1個(gè)度為2的節(jié)點(diǎn)，10個(gè)葉子節(jié)點(diǎn)，那么這棵樹的總節(jié)點(diǎn)數(shù)是多少？A.82B.81C.79D.784、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同5、對(duì)于一個(gè)大根堆，若將堆中所有元素按照層次遍歷的順序存儲(chǔ)到一個(gè)數(shù)組中，以下關(guān)于數(shù)組元素的排列，哪一項(xiàng)是正確的？A.完全無序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對(duì)6、以下關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的描述，哪一項(xiàng)是正確的？（）A.鄰接矩陣適合存儲(chǔ)稀疏圖B.鄰接表在存儲(chǔ)稠密圖時(shí)空間效率較高C.十字鏈表適合存儲(chǔ)有向圖D.以上都不正確7、在一個(gè)具有n個(gè)元素的順序表中，若要在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素，需要向后移動(dòng)多少個(gè)元素？（）A.n-iB.iC.n-i+1D.n-i-18、在一個(gè)用鄰接矩陣存儲(chǔ)的無向圖中，若要?jiǎng)h除一條邊，需要修改矩陣中的幾個(gè)元素？A.1個(gè)B.2個(gè)C.3個(gè)D.4個(gè)9、對(duì)于一個(gè)具有n個(gè)元素的歸并排序，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)10、在一個(gè)具有n個(gè)元素的雙向鏈表中，刪除一個(gè)指定節(jié)點(diǎn)，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、在一個(gè)具有n個(gè)元素的無序數(shù)組中，使用順序查找算法查找一個(gè)特定元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.nlogn12、對(duì)于一個(gè)棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.5B.14C.21D.無數(shù)種13、排序算法的穩(wěn)定性和時(shí)間復(fù)雜度可以用于選擇合適的排序算法，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.穩(wěn)定性對(duì)于某些應(yīng)用場(chǎng)景非常重要，如對(duì)具有多個(gè)關(guān)鍵字的記錄進(jìn)行排序時(shí)。B.時(shí)間復(fù)雜度是衡量排序算法效率的重要指標(biāo)，不同的排序算法具有不同的時(shí)間復(fù)雜度。C.可以根據(jù)實(shí)際情況選擇穩(wěn)定的或不穩(wěn)定的排序算法，以及時(shí)間復(fù)雜度較低的排序算法。D.排序算法的穩(wěn)定性和時(shí)間復(fù)雜度只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價(jià)值。14、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時(shí)間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(e^2)15、若一棵二叉樹的先序遍歷序列和后序遍歷序列分別為ABC和CBA，則其中序遍歷序列為：A.BCAB.CABC.ABCD.無法確定16、在一個(gè)具有n個(gè)元素的有序數(shù)組中，使用二分查找查找一個(gè)不存在的元素，最多比較次數(shù)約為？A.lognB.nC.n/2D.nlogn17、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)元素的隨機(jī)訪問？（）A.鏈表B.隊(duì)列C.棧D.數(shù)組18、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時(shí)間復(fù)雜度為：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)19、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的無向完全圖，其邊的數(shù)量為多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/220、設(shè)有一個(gè)廣義表L=((a,b),c,(d,e))，其表頭和表尾分別為？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)闡述如何在一個(gè)具有n個(gè)元素的無序數(shù)組中，使用快速選擇算法查找第k小的元素，分析其時(shí)間復(fù)雜度。2、（本題10分）論述在貪心算法的局限性分析中，舉例說明在哪些情況下貪心算法不能得到最優(yōu)解。3、（本題10分）闡述后綴樹在自然語言處理中的應(yīng)用場(chǎng)景和技術(shù)挑戰(zhàn)。4、（本題10分）闡述后綴樹在網(wǎng)絡(luò)流量分析中的潛在用