下載本文檔
版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年版江西省企業(yè)與員工勞動(dòng)合同范本
- 2024-2030年中國大黃提取物市場(chǎng)規(guī)模分析及發(fā)展建議研究報(bào)告
- 2024年煤礦礦井水循環(huán)利用水池施工合同
- 眉山藥科職業(yè)學(xué)院《計(jì)算數(shù)論》2023-2024學(xué)年第一學(xué)期期末試卷
- 2024年物業(yè)管理保安勞務(wù)服務(wù)協(xié)議范本版B版
- 知識(shí)拓展 打破場(chǎng)景束縛:掌握景別組接藝術(shù)讓你的視頻更具沖擊力
- 2024全新二手車買賣合同帶車輛電子檔案及保養(yǎng)記錄下載3篇
- 2024年水利水電工程施工合同范本
- 2024年標(biāo)準(zhǔn)方便面長期供應(yīng)合作協(xié)議版B版
- 2024年度危險(xiǎn)品應(yīng)急預(yù)案編制合同3篇
- 2024年四川省普通高中學(xué)業(yè)水平考試(思想政治樣題)
- 中儲(chǔ)糧西安公司社會(huì)招聘試題
- 《犬貓牙科學(xué)》課件
- 《ehr系統(tǒng)培訓(xùn)》課件
- 品質(zhì)部年終總結(jié)報(bào)告2022
- 庫爾勒香梨行業(yè)分析
- 易燃液體罐車裝卸作業(yè)操作規(guī)程模版
- 六年級(jí)上冊(cè)必讀書目《童年》閱讀測(cè)試題(附答案)
- 頭痛的鑒別診斷
- 機(jī)械工程測(cè)試技術(shù)課后習(xí)題
- 人工智能輔助命題
評(píng)論
0/150
提交評(píng)論