衡陽師范學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷_第1頁
衡陽師范學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷_第2頁
衡陽師范學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷_第3頁
全文預(yù)覽已結(jié)束

下載本文檔

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

文檔簡介

站名:站名:年級(jí)專業(yè):姓名:學(xué)號(hào):凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者,成績按零分記?!堋狻€…………第1頁,共1頁衡陽師范學(xué)院《數(shù)據(jù)結(jié)構(gòu)》

2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題(本大題共20個(gè)小題,每小題2分,共40分.在每小題給出的四個(gè)選項(xiàng)中,只有一項(xiàng)是符合題目要求的.)1、在一個(gè)B樹中,每個(gè)節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量最少為多少?()A.1B.2C.?m/2?-1D.m-12、對(duì)于一個(gè)具有n個(gè)元素的順序存儲(chǔ)的循環(huán)隊(duì)列,隊(duì)尾指針rear指向隊(duì)尾元素的下一個(gè)位置,隊(duì)頭指針front指向隊(duì)頭元素,若隊(duì)列非空,則隊(duì)列中元素的個(gè)數(shù)為?()A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+13、對(duì)于一個(gè)有向無環(huán)圖,進(jìn)行拓?fù)渑判蚩梢缘玫揭粋€(gè)線性的序列。以下關(guān)于拓?fù)渑判虻恼f法,錯(cuò)誤的是?()A.可以使用深度優(yōu)先搜索來實(shí)現(xiàn)B.結(jié)果可能不唯一C.若存在回路則無法進(jìn)行拓?fù)渑判駾.其時(shí)間復(fù)雜度為O(n2)4、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的棧中,若棧頂指針為top,要判斷棧是否為空,應(yīng)判斷?()A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL5、對(duì)于一個(gè)具有n個(gè)元素的堆,進(jìn)行插入操作的時(shí)間復(fù)雜度為?()A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一個(gè)有向圖中,所有頂點(diǎn)的入度之和與出度之和的關(guān)系是:A.入度之和大于出度之和B.入度之和小于出度之和C.入度之和等于出度之和D.沒有確定的關(guān)系7、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的紅黑樹,插入一個(gè)新節(jié)點(diǎn)后,調(diào)整樹的結(jié)構(gòu)以保持紅黑樹性質(zhì),其時(shí)間復(fù)雜度為?A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、在一個(gè)具有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖中,至少需要多少條邊?()A.n-1B.nC.n(n-1)/2D.n(n-1)9、在一個(gè)具有n個(gè)元素的最小堆中,插入一個(gè)新元素后,為了重新調(diào)整為最小堆,最壞情況下需要比較多少次?()A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)10、在一個(gè)具有n個(gè)元素的順序表中,刪除第i個(gè)元素(1<=i<=n),平均需要移動(dòng)的元素個(gè)數(shù)約為?A.n/2B.n-iC.iD.n-i+111、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu),具有多種遍歷方式。對(duì)于先序遍歷、中序遍歷和后序遍歷,以下描述錯(cuò)誤的是()A.先序遍歷先訪問根節(jié)點(diǎn),然后遞歸遍歷左子樹和右子樹B.中序遍歷先遞歸遍歷左子樹,然后訪問根節(jié)點(diǎn),最后遞歸遍歷右子樹C.后序遍歷先遞歸遍歷左子樹和右子樹,最后訪問根節(jié)點(diǎn)D.這三種遍歷方式的結(jié)果總是相同的12、若要對(duì)100個(gè)元素進(jìn)行排序,以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低?A.冒泡排序B.選擇排序C.插入排序D.歸并排序13、對(duì)于一個(gè)具有n個(gè)元素的有序單鏈表,若要在其中查找一個(gè)特定元素,其平均時(shí)間復(fù)雜度為:A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)14、以下哪種數(shù)據(jù)結(jié)構(gòu)在處理頻繁的插入和刪除操作時(shí),不需要移動(dòng)大量元素?()A.數(shù)組B.鏈表C.棧D.隊(duì)列15、在數(shù)據(jù)結(jié)構(gòu)中,斐波那契堆是一種可合并堆,以下關(guān)于斐波那契堆的特點(diǎn),描述不正確的是()A.插入操作的時(shí)間復(fù)雜度為O(1)B.查找最小元素的時(shí)間復(fù)雜度為O(1)C.刪除最小元素的時(shí)間復(fù)雜度為O(logn)D.合并操作的時(shí)間復(fù)雜度為O(n)16、在一個(gè)循環(huán)隊(duì)列中,隊(duì)頭指針為front,隊(duì)尾指針為rear,隊(duì)列最大容量為MAXSIZE,若rear>front,則隊(duì)列中的元素個(gè)數(shù)為?A.rear-frontB.rear-front+MAXSIZEC.rear-front-1D.(rear-front+MAXSIZE)%MAXSIZE17、以下哪種數(shù)據(jù)結(jié)構(gòu)可以快速查找一個(gè)有序數(shù)組中的中位數(shù)?A.二叉搜索樹B.堆C.哈希表D.鏈表18、在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中,邊的數(shù)量為:A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)19、一個(gè)有序序列為{12,18,24,35,47,50,62,83,90,115,134},當(dāng)用二分法查找值為90的元素時(shí),需要比較的次數(shù)是()。A.1B.2C.3D.420、在一個(gè)具有n個(gè)元素的雙向鏈表中,刪除一個(gè)指定節(jié)點(diǎn),其時(shí)間復(fù)雜度為?A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題(本大題共4個(gè)小題,共40分)1、(本題10分)論述如何使用動(dòng)態(tài)規(guī)劃算法解決最長公共子串問題。2、(本題10分)詳細(xì)說明選擇排序算法的基本思想和在最壞情況下的時(shí)間復(fù)雜度分析。3、(本題10分)解釋在平衡二叉搜索樹中,刪除操作可能導(dǎo)致的不平衡情況及相應(yīng)的調(diào)整方法。4、(本題10分)論述如何使用分治法解決最大子數(shù)

溫馨提示

  • 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)論