數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫(kù)含答案解析2023_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫(kù)含答案解析2023_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫(kù)含答案解析2023_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫(kù)含答案解析2023_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫(kù)含答案解析2023_第5頁(yè)
已閱讀5頁(yè),還剩14頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫(kù)含答案解析(全考點(diǎn))1、含有n個(gè)非葉結(jié)點(diǎn)的m階B樹(shù)中至少包含()個(gè)關(guān)鍵字。?A:n(m+1)?B:n?C:n()?D:(n-1)()+1解析除根結(jié)點(diǎn)外,m階B樹(shù)中的每個(gè)非葉結(jié)點(diǎn)至少有個(gè)關(guān)鍵字,根結(jié)點(diǎn)至少有一個(gè)關(guān)鍵字,所以總共包含的關(guān)鍵字最少個(gè)數(shù)=(n-1)()+1。答案:D2、已知一棵5階B樹(shù)中共有53個(gè)關(guān)鍵字,則樹(shù)的最大高度為(),最小高度為()。?A:2?B:3?C:4?D:5解析5階B樹(shù)中共有53個(gè)關(guān)鍵字,由最大高度公式H得最大高度=4,即最大高度為4;由最小高度公式得最小高度=2.5,從而最小高度為3。答案:C。B3、已知一棵3階B樹(shù)中有2047個(gè)關(guān)鍵字,則此B樹(shù)的最大高度為(),最小高度為()。?A:11?B:10?C:8?D:7解析利用最小高度和最大高度的公式??梢运愠鲎畲蟾叨?,最小高度,從而最小高度取7。答案:A。D4、下列關(guān)于B樹(shù)和B+樹(shù)的敘述中,不正確的是()。?A:B樹(shù)和B+樹(shù)都能有效地支持順序查找?B:B樹(shù)和B+樹(shù)都能有效地支持隨機(jī)查找?C:B樹(shù)和B+樹(shù)都是平衡的多叉樹(shù)?D:B樹(shù)和B+樹(shù)都可以用于文件索引結(jié)構(gòu)解析B樹(shù)和B+樹(shù)的差異主要體現(xiàn)在:1.結(jié)點(diǎn)關(guān)鍵字和子樹(shù)的個(gè)數(shù);2.B+樹(shù)非葉結(jié)點(diǎn)僅起索引作用;3.B樹(shù)葉結(jié)點(diǎn)關(guān)鍵字和其他結(jié)點(diǎn)包含的關(guān)鍵字是不重復(fù)的;4.B+樹(shù)支持順序查找和隨機(jī)查找。而B(niǎo)樹(shù)僅支持隨機(jī)查找。由于B+樹(shù)的所有葉結(jié)點(diǎn)中包含了全部的關(guān)鍵字信息,且葉結(jié)點(diǎn)本身依關(guān)鍵字從小到大順序鏈接,因此可以進(jìn)行順序查找,而B(niǎo)樹(shù)不支持順序查找。答案:A5、在一棵高度為2的5階B樹(shù)中,所含關(guān)鍵字的個(gè)數(shù)至少是()。?A:5?B:7?C:8?D:14解析答案:A6、在一棵有15個(gè)關(guān)鍵字的4階B樹(shù)中,含關(guān)鍵字的結(jié)點(diǎn)的個(gè)數(shù)最多是()。?A:5?B:6?C:10?D:15解析關(guān)鍵字?jǐn)?shù)量不變,要求結(jié)點(diǎn)數(shù)量最多,即要求每個(gè)結(jié)點(diǎn)中含關(guān)鍵字的數(shù)量最少。根據(jù)4階B樹(shù)的定義,根結(jié)點(diǎn)最少含1個(gè)關(guān)鍵字,非根結(jié)點(diǎn)中最少含個(gè)關(guān)鍵字,所以每個(gè)結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)量最少都為1個(gè),即每個(gè)結(jié)點(diǎn)都有2個(gè)分支,類(lèi)似于排序二叉樹(shù),而15個(gè)結(jié)點(diǎn)正好可以構(gòu)造一個(gè)4層的4階B樹(shù),使得終端結(jié)點(diǎn)全在第四層,符合B樹(shù)的定義,因此選D。答案:D7、B+樹(shù)不同于B樹(shù)的特點(diǎn)之一是()。?A:能支持順序查找?B:節(jié)點(diǎn)中含有關(guān)鍵字?C:根結(jié)點(diǎn)至少有兩個(gè)分支?D:所有葉結(jié)點(diǎn)都在同一層上解析由于B+樹(shù)的所有葉結(jié)點(diǎn)中包含了全部的關(guān)鍵字信息,且葉結(jié)點(diǎn)本身依關(guān)鍵字從小到大順序鏈接,因此可以進(jìn)行順序查找,而B(niǎo)樹(shù)不支持順序查找(只支持多路查找)。答案:A8、高度為5的3階B樹(shù)含有的關(guān)鍵字個(gè)數(shù)至少是()。?A:15?B:31?C:62?D:242解析m階B樹(shù)的基本性質(zhì):根結(jié)點(diǎn)以外的非葉結(jié)點(diǎn)最少含有個(gè)關(guān)鍵字,代入m=3得到每個(gè)非葉結(jié)點(diǎn)中最少包含1個(gè)關(guān)鍵字,而根結(jié)點(diǎn)含有1個(gè)關(guān)鍵字,因此所有非葉結(jié)點(diǎn)都有兩個(gè)孩子。此時(shí)其樹(shù)形與h=5的滿二叉樹(shù)相同,可求得關(guān)鍵字最少為31個(gè)。答案:B9、依次將關(guān)鍵字5,6,9,13,8,2,12,15插入初始為空的4階B樹(shù)后,根結(jié)點(diǎn)包含的關(guān)鍵字是()。?A:8?B:6,9?C:8,13?D:9,12解析一個(gè)4階B樹(shù)的任意非葉結(jié)點(diǎn)至多含有m-1=3個(gè)關(guān)鍵字,在關(guān)鍵字依次插入的過(guò)程中,會(huì)導(dǎo)致結(jié)點(diǎn)的不斷分裂,插入過(guò)程如下所示。請(qǐng)?zhí)砑訄D片描述得到根結(jié)點(diǎn)包含的關(guān)鍵字為6,9。答案:B10、下列關(guān)于散列表的說(shuō)法中,正確的是()。Ⅰ、若散列表的填裝因子,則可避免碰撞的產(chǎn)生Ⅱ、散列查找中不需要任何關(guān)鍵字的比較Ⅲ、散列表在查找成功時(shí)平均查找長(zhǎng)度與表長(zhǎng)有關(guān)Ⅳ、若在散列表中刪除一個(gè)元素,不能簡(jiǎn)單地將該元素刪除?A:Ⅰ和Ⅳ?B:Ⅱ和Ⅲ?C:Ⅲ?D:Ⅳ解析?沖突(碰撞)是不可避免的,與裝填因子無(wú)關(guān),因此需要設(shè)計(jì)處理沖突的方法,Ⅰ錯(cuò)誤。?散列查找的思想是計(jì)算出散列地址來(lái)進(jìn)行查找,然后比較關(guān)鍵字以確定是否查找成功,Ⅱ錯(cuò)誤。?散列查找成功的平均查找長(zhǎng)度與裝填因子有關(guān),與表長(zhǎng)無(wú)關(guān),Ⅲ錯(cuò)誤。?在開(kāi)放地址的情形下,不能隨便刪除散列表中的某個(gè)元素,否則可能會(huì)導(dǎo)致搜索路徑被中斷(因此通常的做法是在要?jiǎng)h除的地方做刪除標(biāo)記,而不是直接刪除),Ⅳ正確。答案:D1、在下圖所示的平衡二叉樹(shù)中插入關(guān)鍵字48后得到一棵新平衡二叉樹(shù),在新平衡二叉樹(shù)中,關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是()。?A:13,48?B:24,48?C:24,53?D:24,90解析插入48后,該二叉樹(shù)根結(jié)點(diǎn)的平衡因子由-1變?yōu)?2,失去平衡,需要進(jìn)行兩次旋轉(zhuǎn)(先右旋后左旋)操作。答案:C2、若平衡二叉樹(shù)的高度為6,且所有非葉子結(jié)點(diǎn)的平衡因子均為1,則該平衡二叉樹(shù)的結(jié)點(diǎn)總數(shù)為()。?A:12?B:20?C:32?D:33解析所有非葉結(jié)點(diǎn)的平衡因子均為1,即平衡二叉樹(shù)滿足平衡的最少結(jié)點(diǎn)情況,如下圖所示。對(duì)于高度為n、左右子樹(shù)的高度分別為n-1和n-2、所有非葉結(jié)點(diǎn)的平衡因子均為1的平衡二叉樹(shù),計(jì)算總結(jié)點(diǎn)數(shù)的公式為=++1,=1,=2,=2+1+1=4,可推出=20。畫(huà)圖法:先畫(huà)出和;然后新建一個(gè)根結(jié)點(diǎn),連接、構(gòu)成;新建一個(gè)根結(jié)點(diǎn),連接、構(gòu)成......直到畫(huà)出,可知的結(jié)點(diǎn)數(shù)為20。答案:B3、若將關(guān)鍵字1,2,3,4,5,6,7依次插入初始為空的平衡二叉樹(shù)T,則T中平衡因子為0的分支結(jié)點(diǎn)的個(gè)數(shù)是()。?A:0?B:1?C:2?D:3解析利用7個(gè)關(guān)鍵字構(gòu)建平衡二叉樹(shù)T,平衡因子為0的分支結(jié)點(diǎn)個(gè)數(shù)為3,構(gòu)建的平衡二叉樹(shù)及構(gòu)造與調(diào)整過(guò)程如下圖所示。請(qǐng)?zhí)砑訄D片描述答案:D4、現(xiàn)有一棵無(wú)重復(fù)關(guān)鍵字的平衡二叉樹(shù)(AVL),對(duì)其進(jìn)行中序遍歷可得到一個(gè)降序序列。下列關(guān)于該平衡二叉樹(shù)的敘述中,正確的是()。?A:根結(jié)點(diǎn)的度一定為2?B:樹(shù)中最小元素一定是葉結(jié)點(diǎn)?C:最后插入的元素一定是葉結(jié)點(diǎn)?D:樹(shù)中最大元素一定是無(wú)左子樹(shù)解析只有兩個(gè)結(jié)點(diǎn)的平衡二叉樹(shù)的根結(jié)點(diǎn)的度為1,A錯(cuò)誤。中序遍歷后可以得到一個(gè)降序序列,樹(shù)中最小元素一定無(wú)左子樹(shù)(可能有右子樹(shù)),因此不一定是葉結(jié)點(diǎn),B錯(cuò)誤。最后插入的結(jié)點(diǎn)可能會(huì)導(dǎo)致平衡調(diào)整,而不一定是葉結(jié)點(diǎn),C錯(cuò)誤。答案:D5、在任意一棵非空平衡二叉樹(shù)(AVL樹(shù))中,刪除某結(jié)點(diǎn)v之后形成平衡二叉樹(shù),再將v插入形成平衡二叉樹(shù)。下列關(guān)于與的敘述中,正確的是()。Ⅰ、若v是的葉結(jié)點(diǎn),則與可能不相同Ⅱ、若v不是的葉結(jié)點(diǎn),則與一定不相同Ⅲ、若v不是的葉結(jié)點(diǎn),則與一定相同?A:僅Ⅰ?B:僅Ⅱ?C:僅Ⅰ、Ⅱ?D:僅Ⅰ、Ⅲ解析在非空平衡二叉樹(shù)中插入結(jié)點(diǎn),在失去平衡調(diào)整前,一定插入在葉結(jié)點(diǎn)的位置。若刪除的是的葉結(jié)點(diǎn),則刪除后平衡二叉樹(shù)可能不會(huì)失去平衡,即不會(huì)發(fā)生調(diào)整,再插入此結(jié)點(diǎn)得到的二叉平衡樹(shù)與相同;若刪除后平衡二叉樹(shù)失去平衡而發(fā)生調(diào)整,再插入結(jié)點(diǎn)得到的二叉平衡樹(shù)與可能不同。Ⅰ正確。對(duì)于比較絕對(duì)的說(shuō)法Ⅱ和Ⅲ,通常只需舉出反例即可。例如,如下圖所示,刪除結(jié)點(diǎn)0,平衡二叉樹(shù)失衡調(diào)整,再插入結(jié)點(diǎn)0后,平衡二叉樹(shù)和以前不同。若刪除的是的非葉結(jié)點(diǎn),且刪除和插入操作均沒(méi)有導(dǎo)致平衡二叉樹(shù)的調(diào)整,則該結(jié)點(diǎn)從非葉結(jié)點(diǎn)變成了葉結(jié)點(diǎn),與顯然不同。例如,如下圖所示,刪除結(jié)點(diǎn)2,用有孩子結(jié)點(diǎn)3填補(bǔ),再插入結(jié)點(diǎn)2,平衡二叉樹(shù)和以前不同。若刪除的是的非葉結(jié)點(diǎn),且刪除和插入操作后導(dǎo)致了平衡二叉樹(shù)的調(diào)整,則該結(jié)點(diǎn)有可能通過(guò)旋轉(zhuǎn)后繼續(xù)變成非葉結(jié)點(diǎn),與相同。例如,如下圖所示,刪除結(jié)點(diǎn)2,用右孩子結(jié)點(diǎn)3填補(bǔ),再插入結(jié)點(diǎn)2,平衡二叉樹(shù)失衡調(diào)整,調(diào)整后的平衡二叉樹(shù)和以前相同。答案:A6、下圖所示是一棵()。?A:4階B樹(shù)?B:4階B+樹(shù)?C:3階B樹(shù)?D:3階B+樹(shù)解析關(guān)鍵字?jǐn)?shù)量比子樹(shù)數(shù)量少1,所以不是B+樹(shù),而是B樹(shù)。又因?yàn)閙階B樹(shù)結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)最多為m-1,有一個(gè)結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)為3,所以不可能為3階。答案:A7、下列關(guān)于m階B樹(shù)的說(shuō)法中,錯(cuò)誤的是()。?A:根結(jié)點(diǎn)至多有m棵子樹(shù)?B:所有葉結(jié)點(diǎn)都在同一層次上?C:非葉結(jié)點(diǎn)至少有m/2(m為偶數(shù))或(m+1)/2(m為奇數(shù))棵子樹(shù)?D:根結(jié)點(diǎn)中的數(shù)據(jù)是有序的解析除根結(jié)點(diǎn)外的所有非終端結(jié)點(diǎn)至少有棵子樹(shù)。對(duì)于根結(jié)點(diǎn),最多有m棵子樹(shù),若其不是葉結(jié)點(diǎn),則至少有2棵子樹(shù)。答案:C8、以下關(guān)于m階B樹(shù)的說(shuō)法中,正確的是()。Ⅰ、每個(gè)結(jié)點(diǎn)至少有兩棵非空子樹(shù)Ⅱ、樹(shù)中每個(gè)結(jié)點(diǎn)至多有m-1個(gè)關(guān)鍵字Ⅲ、所有葉結(jié)點(diǎn)在同一層Ⅳ、插入一個(gè)元素引起B(yǎng)樹(shù)結(jié)點(diǎn)分裂后,樹(shù)長(zhǎng)高一層?A:Ⅰ、Ⅱ?B:Ⅱ、Ⅲ?C:Ⅲ、Ⅳ?D:Ⅰ、Ⅱ、Ⅳ解析每個(gè)非根的內(nèi)部結(jié)點(diǎn)必須至少有棵子樹(shù),而根結(jié)點(diǎn)至少要有兩棵子樹(shù),所以Ⅰ不正確。Ⅱ、Ⅲ顯然正確。對(duì)于Ⅳ,插入一個(gè)元素引起B(yǎng)樹(shù)結(jié)點(diǎn)分裂后,只要從根結(jié)點(diǎn)到該元素插入位置的路徑上至少有一個(gè)結(jié)點(diǎn)未滿,B樹(shù)就不會(huì)長(zhǎng)高,如圖1所示;只有當(dāng)結(jié)點(diǎn)的分裂傳到根結(jié)點(diǎn),并使根結(jié)點(diǎn)也分裂時(shí),才會(huì)導(dǎo)致樹(shù)高增1,如圖2所示,因此Ⅳ錯(cuò)誤。答案:B9、具有n個(gè)關(guān)鍵字的m階B樹(shù),應(yīng)有()個(gè)葉結(jié)點(diǎn)。?A:n+1?B:n-1?C:mn?D:nm/2解析B樹(shù)的葉結(jié)點(diǎn)對(duì)應(yīng)查找失敗的情況,對(duì)有n個(gè)關(guān)鍵字的查找集合進(jìn)行查找,失敗可能性有n+1種。答案:A10、高

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(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)論