數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫(kù)含答案解析2023

數(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、高