數(shù)據(jù)結(jié)構(gòu)書(shū)面作業(yè)練習(xí)題69-文庫(kù)吧
2025-03-10 03:01 本頁(yè)面
【正文】 點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序_A___。A. 不發(fā)生改變 B. 發(fā)生改變 C. 不能確定 D. 以上都不對(duì)21. 實(shí)現(xiàn)任意二叉樹(shù)的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳方案是二叉樹(shù)采用__C__存儲(chǔ)結(jié)構(gòu)。A. 二叉鏈表 B. 廣義表存儲(chǔ)結(jié)構(gòu) C. 三叉鏈表 D. 順序存儲(chǔ)結(jié)構(gòu)22. 對(duì)一個(gè)滿(mǎn)二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h，則__D__ 。A. n=h+m B. h+m=2n C. m=h1 D. n=2 h123. 如果某二叉樹(shù)的前序?yàn)閟tuwv，中序?yàn)閡wtvs，那么該二叉樹(shù)的后序?yàn)開(kāi)C___。A. uwvts B. vwuts C. wuvts D. wutsv。F(n)=F(n1)+F(n2)+1, 1是根節(jié)點(diǎn)，F(xiàn)(n1)是左子樹(shù)的節(jié)點(diǎn)數(shù)量，F(xiàn)(n2)是右子樹(shù)的節(jié)點(diǎn)數(shù)量A. 10 B. 12 C. 15 D. 1725. 設(shè)n，m為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是__C__。A. n在m右方 B. n是m祖先 C. n在m左方 D. n是m子孫 填空題（將正確的答案填在相應(yīng)的空中）1. ，回答下面的問(wèn)題：⑴ 這棵樹(shù)的根結(jié)點(diǎn)是___K1_；⑵ 這棵樹(shù)的葉子結(jié)點(diǎn)是___K2,K5,K7,K4_；⑶ 結(jié)點(diǎn)k3的度是_2___；⑷ 這棵樹(shù)的度是___3_；⑸ 這棵樹(shù)的深度是_4___；⑹ 結(jié)點(diǎn)k3的子女是__K5,K6__；⑺ 結(jié)點(diǎn)k3的父結(jié)點(diǎn)是__K1__；2. 指出樹(shù)和二叉樹(shù)的三個(gè)主要差別_樹(shù)的結(jié)點(diǎn)個(gè)數(shù)至少為1，而二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)可以為0； 樹(shù)中結(jié)點(diǎn)的最大度數(shù)沒(méi)有限制，而二叉樹(shù)結(jié)點(diǎn)的最大度數(shù)為2； 樹(shù)的結(jié)點(diǎn)無(wú)左、右之分，而二叉樹(shù)的結(jié)點(diǎn)有左、右之分。3. 從概念上講，樹(shù)與二叉樹(shù)是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹(shù)轉(zhuǎn)化為二叉樹(shù)的基本目的是_利用二叉樹(shù)的已有算法解決樹(shù)的有關(guān)問(wèn)題___。4. 一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組t中，則該二叉樹(shù)的鏈接表示形式為_(kāi)___。123456789101112131415161718192021eafdgcjlhb 一棵二叉樹(shù)的順序存儲(chǔ)數(shù)組t5. 深度為k的完全二叉樹(shù)至少有__2k1__個(gè)結(jié)點(diǎn)。至多有__2k1__個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從1開(kāi)始），則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是_2k2+1___。6. 在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n 0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為 n 2，則有n0=_n2+1___。7. 一棵二叉樹(shù)的第i（i≥1）層最多有_2i1___個(gè)結(jié)點(diǎn)；一棵有n（n0）個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)共有__ 2[log2n+1]1__個(gè)葉子和___2[log2n+1]1_個(gè)非終端結(jié)點(diǎn)。8. 結(jié)點(diǎn)最少的樹(shù)為_(kāi)_只有一個(gè)結(jié)點(diǎn)的樹(shù)__，結(jié)點(diǎn)最少的二叉樹(shù)為_(kāi)空二叉樹(shù)___。9. 現(xiàn)有按中序遍歷二叉樹(shù)的結(jié)果為abc，問(wèn)有__5__種不同形態(tài)的二叉樹(shù)可以得到這一遍歷結(jié)果，這些二叉樹(shù)分別是____。10. 根據(jù)二叉樹(shù)的定義，具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)有___5_種不同的形態(tài)，它們分別是__參照樓上__。11. ，回答以下問(wèn)題：⑴ 其中序遍歷序列為_(kāi)dgbaechif__；⑵ 其前序遍歷序列為_(kāi)__ abdgcefhi_；⑶ 其后序遍歷序列為_(kāi)gdbeihfca___；⑷ 該二叉樹(shù)的中序線索二叉樹(shù)為_(kāi)__ _；⑸ 該二叉樹(shù)的后序線索二叉樹(shù)為_(kāi)___；⑹ 該二叉樹(shù)對(duì)應(yīng)的森林是____。12. ，轉(zhuǎn)化為一棵二叉樹(shù)，表示為_(kāi)___。13. 以數(shù)據(jù)集{4，5，6，7，10，12，18}為結(jié)點(diǎn)權(quán)值所構(gòu)造的Huffman樹(shù)為_(kāi)___，其帶權(quán)路徑長(zhǎng)度為_(kāi)_165__。 算法設(shè)計(jì)題:1．試編寫(xiě)算法，對(duì)一棵以孩子兄弟鏈表表示的樹(shù)統(tǒng)計(jì)葉子的個(gè)數(shù)。2. 一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別?3. 一棵含有N個(gè)結(jié)點(diǎn)的k叉樹(shù),可能達(dá)到的最大深度和最小深度各為多少?4. 證明:一棵滿(mǎn)k叉樹(shù)上的葉子結(jié)點(diǎn)數(shù)n和非葉子結(jié)點(diǎn)數(shù)n之間滿(mǎn)足以下關(guān)系: n=(k1)n+15. 請(qǐng)對(duì)下圖所示二叉樹(shù)進(jìn)行后序線索化，為每個(gè)空指針建立相應(yīng)的前驅(qū)或后繼線索。DHFECGGBA 6. 畫(huà)出和下列已知序列對(duì)應(yīng)的樹(shù)T： 樹(shù)的先根次序訪問(wèn)序列為GFKDAIEBCHJ； 樹(shù)的后根次序訪問(wèn)序列為DIAEKFCJHBFG。7. 假設(shè)用于通訊的電文僅有八個(gè)字母組成，,,。試為這八個(gè)字母設(shè)計(jì)哈夫曼編碼。使用07的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1