下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁,共3頁遼寧石油化工大學(xué)《數(shù)據(jù)科學(xué)與智能技術(shù)概論》
2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題(本大題共20個(gè)小題,每小題2分,共40分.在每小題給出的四個(gè)選項(xiàng)中,只有一項(xiàng)是符合題目要求的.)1、在一個(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)%MAXSIZE2、在數(shù)據(jù)結(jié)構(gòu)中,AVL樹的刪除操作比插入操作更復(fù)雜,以下關(guān)于刪除操作的描述,錯(cuò)誤的是()A.可能需要進(jìn)行多次旋轉(zhuǎn)來保持平衡B.首先找到要?jiǎng)h除的節(jié)點(diǎn)C.刪除后不需要調(diào)整樹的結(jié)構(gòu)D.要考慮刪除節(jié)點(diǎn)的子樹情況3、在一個(gè)具有n個(gè)元素的有序單鏈表中,進(jìn)行插入操作時(shí),平均需要移動(dòng)的元素個(gè)數(shù)約為?A.n/2B.nC.lognD.14、在二叉搜索樹中,每個(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.二叉搜索樹總是平衡的,即左右子樹的高度差不超過15、在數(shù)據(jù)結(jié)構(gòu)中,基數(shù)排序是一種非比較排序算法,以下關(guān)于基數(shù)排序的描述,不正確的是()A.按照位數(shù)依次進(jìn)行排序B.可以用于整數(shù)和字符串的排序C.時(shí)間復(fù)雜度為O(d(n+r)),其中d是位數(shù),r是基數(shù)D.對數(shù)據(jù)的分布敏感6、已知一個(gè)棧的進(jìn)棧序列為1,2,3,4,出棧序列為3,2,4,1,則棧的容量至少為()。A.2B.3C.4D.57、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉排序樹中,進(jìn)行查找操作的平均時(shí)間復(fù)雜度是多少?A.O(n)B.O(logn)C.O(nlogn)D.取決于樹的形態(tài)8、在一棵二叉樹中,若每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度最多相差1,則該二叉樹被稱為平衡二叉樹。對于一個(gè)平衡二叉樹,進(jìn)行插入操作后,為了保持平衡,可能需要進(jìn)行多少次旋轉(zhuǎn)調(diào)整?A.0次B.1次C.最多2次D.不確定9、在數(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)10、對于一個(gè)棧,進(jìn)行入棧和出棧操作時(shí),若棧頂指針top初始值為-1,當(dāng)進(jìn)行5次入棧和3次出棧操作后,top的值為多少?()A.1B.2C.3D.411、平衡二叉樹是一種特殊的二叉搜索樹,其目的是為了保證查找效率。以下哪種操作可能會導(dǎo)致平衡二叉樹失去平衡?A.插入節(jié)點(diǎn)B.刪除節(jié)點(diǎn)C.查找節(jié)點(diǎn)D.以上都可能12、在一棵二叉樹中,若度為2的節(jié)點(diǎn)有10個(gè),度為1的節(jié)點(diǎn)有20個(gè),那么葉子節(jié)點(diǎn)的數(shù)量是多少?A.11B.21C.30D.無法確定13、以下關(guān)于堆的描述,正確的是:A.大頂堆中每個(gè)父節(jié)點(diǎn)的值都大于其子節(jié)點(diǎn)的值B.小頂堆中每個(gè)父節(jié)點(diǎn)的值都小于其子節(jié)點(diǎn)的值C.堆可以用順序存儲也可以用鏈?zhǔn)酱鎯.堆是完全二叉樹14、在二叉樹中,判斷兩棵二叉樹是否完全相同,以下方法不正確的是()A.同時(shí)進(jìn)行先序遍歷,比較節(jié)點(diǎn)值B.同時(shí)進(jìn)行中序遍歷,比較節(jié)點(diǎn)值C.同時(shí)進(jìn)行后序遍歷,比較節(jié)點(diǎn)值D.比較兩棵樹的節(jié)點(diǎn)數(shù)量15、對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖,若采用鄰接矩陣表示,則該矩陣的大小為()。A.nB.n^2C.n(n-1)D.n(n+1)16、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹中,若先序遍歷序列為ABC,中序遍歷序列為BAC,則后序遍歷序列是什么?A.BCAB.CBAC.ACBD.無法確定17、已知一棵二叉樹的先序遍歷序列為ABCDEFG,中序遍歷序列為CBAEDFG,則其后序遍歷序列為?()A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA18、對于一個(gè)具有n個(gè)元素的有序單鏈表,若要在其中查找一個(gè)特定元素,其平均時(shí)間復(fù)雜度為:A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)19、在圖的存儲結(jié)構(gòu)中,十字鏈表主要用于存儲有向圖,以下關(guān)于十字鏈表的特點(diǎn),描述不正確的是()A.既能方便地訪問出邊,也能方便地訪問入邊B.存儲空間比鄰接表節(jié)省C.對于刪除邊的操作比較復(fù)雜D.不適合用于稀疏有向圖20、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向連通圖,其生成樹中邊的條數(shù)為()。A.nB.n-1C.eD.e-1二、簡答題(本大題共4個(gè)小題,共40分)1、(本題10分)簡述哈希表的哈希沖突解決方法中二次探測法的原理及優(yōu)缺點(diǎn)。2、(本題10分)論述在二叉樹的層次遍歷中,如何使用隊(duì)列來實(shí)現(xiàn),并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。3、(本題10分)深入探討在一個(gè)具有n個(gè)元素的二叉搜索樹中,如何求第k小的元素。4、(本題10分)分析在字符串匹配中,如何結(jié)合多種算法提高匹配效率。三、設(shè)計(jì)題(
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 農(nóng)村物流合同范本
- 二手車維修轉(zhuǎn)讓合同范例
- 供熱煤炭出售合同范本
- 醫(yī)院藥房人員聘用合同范本
- 買賣公雞廣告合同范本
- 勞務(wù)合同機(jī)械租賃合同范本
- 代理銷售補(bǔ)充合同范本
- 醫(yī)院與攝影合作合同范例
- 產(chǎn)品用量贈送合同范本
- 2024年千島醬項(xiàng)目策劃方案報(bào)告
- 《鉆井液用磺甲基酚醛樹脂技術(shù)要求》
- 數(shù)學(xué)-九宮數(shù)獨(dú)100題(附答案)
- 中國農(nóng)業(yè)發(fā)展銀行XX支行 關(guān)于綜合評價(jià)自評情況的報(bào)告
- 2010年宣武區(qū)第六屆中小學(xué)生地理知識競賽題庫
- 人教三年級數(shù)學(xué)下冊表格式全冊
- QC課題提高檢查井周邊壓實(shí)
- 應(yīng)征公民體格檢查表(征兵)
- ACL磁致伸縮液位計(jì)說明書
- 優(yōu)秀教研組評比制度及實(shí)施細(xì)則
- 慈善祖師—太乙救苦天尊經(jīng)文選集拼音版
- 3建筑工程規(guī)劃放線、驗(yàn)線多測合一成果報(bào)告書
評論
0/150
提交評論