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

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