河北地質(zhì)大學(xué)《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫》2021-2022學(xué)年期末試卷_第1頁
河北地質(zhì)大學(xué)《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫》2021-2022學(xué)年期末試卷_第2頁
河北地質(zhì)大學(xué)《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫》2021-2022學(xué)年期末試卷_第3頁
河北地質(zhì)大學(xué)《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫》2021-2022學(xué)年期末試卷_第4頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

裝訂線裝訂線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)用場景非常重要,如對(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)用場景和技術(shù)挑戰(zhàn)。4、(本題10分)闡述后綴樹在網(wǎng)絡(luò)流量分析中的潛在用

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論