數(shù)據(jù)結(jié)構(gòu)樹(shù)的測(cè)試題(二)-在線瀏覽
2025-05-12 03:01本頁(yè)面
【正文】 結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。5．將下列由三棵樹(shù)組成的森林轉(zhuǎn)換為二叉樹(shù)。6．設(shè)二叉樹(shù)BT的存儲(chǔ)結(jié)構(gòu)如下: 1 2 3 4 5 6 7 8 9 10Lchild 0 0 2 3 7 5 8 0 10 1DataJ H F D B A C E G IRchild 0 0 0 9 4 0 0 0 0 0其中BT為樹(shù)根結(jié)點(diǎn)的指針，其值為6,Lchild,Rchild分別為結(jié)點(diǎn)的左、右孩子指針域,data為結(jié)點(diǎn)的數(shù)據(jù)域。（2）寫(xiě)出按前序、中序、后序遍歷該二叉樹(shù)所得到的結(jié)點(diǎn)序列。 第六章 樹(shù)和二叉樹(shù)一、單項(xiàng)選擇題3．A4．C5．B6．D7．E 8. D9．C10．B11. C12．A13．D14．B15．C16．B 17. B18. A19．C20．D21．B22. D23．C二、判斷題（在各題后填寫(xiě)“√”或“”）1. 完全二叉樹(shù)一定存在度為1的結(jié)點(diǎn)。3. 二叉樹(shù)的遍歷只是為了在應(yīng)用中找到一種線性次序。5. 用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)?！?. 二叉樹(shù)只能用二叉鏈表表示?！?0. 用鏈表(llinkrlink)存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n1個(gè)空指針。√12．將一棵樹(shù)轉(zhuǎn)成二叉樹(shù)，根結(jié)點(diǎn)沒(méi)有左子樹(shù)。14. 二叉樹(shù)中序線索化后，不存在空指針域?！?6．哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。amp。log2i9．二叉排序樹(shù)10．前序11．6912． *count++, countleaf(lrchile,count)13．(1) p=plchild // 沿左子樹(shù)向下 （2）p=prchild 14．(1)0 （2）hlhr (3)hr=hl15．(1)prchild (2)plchild (3)plchild (4)ADDQ(Q,plchild) (5)ADDQ(Q,prchild)四、應(yīng)用題1．樹(shù)和二叉樹(shù)邏輯上都是樹(shù)形結(jié)構(gòu)，樹(shù)和二叉樹(shù)的區(qū)別有三：一是二叉樹(shù)的度至多為2，樹(shù)無(wú)此限制；二是二叉樹(shù)有左右子樹(shù)之分，即使在只有一個(gè)分枝的情況下， 也必須指出是左子樹(shù)還是右子樹(shù)，樹(shù)無(wú)此限制；三是二叉樹(shù)允許為空，樹(shù)一般不允許為空（個(gè)別書(shū)上允許為空）。2．【解答】具有3個(gè)結(jié)點(diǎn)的樹(shù) 具有3個(gè)結(jié)點(diǎn)的二叉樹(shù) 3．解答：先根序列：A B C D E F G H I J。后根序列：D C B F J I H G E A。設(shè)n 為結(jié)點(diǎn)i的子女，則關(guān)系式(i1)k+2=n=ik+1成立，因i是整數(shù)，故結(jié)點(diǎn)n的雙親i的編號(hào)為235。+1。(4) 根據(jù)以上分析，結(jié)點(diǎn)n有右兄弟的條件是，它不是雙親的從右數(shù)的第一子女，即 (n1)%k!=0，其右兄弟編號(hào)是n+1。前序序列：ＡＢＣＥＤＦＨＧＩJ 中序序列： E C B H F D J I G A 后序序列： ＥＣＨＦＪＩＧＤＢＡ（3）圖略。其哈夫曼編碼如下A:1，B:000，C:01，D:0011359000111五、算法設(shè)計(jì)題1．[題目分析]二叉樹(shù)是遞歸定義的，以遞歸方式建立最簡(jiǎn)單。BiTree Creat() //建立二叉樹(shù)的二叉鏈表形式的存儲(chǔ)結(jié)構(gòu){ElemType x；BiTree bt。x)。else if(x0) {bt=(BiNode *)malloc(sizeof(BiNode))。 btlchild=creat()。 } else error(“輸入錯(cuò)誤”)；return(bt)。 BiTree p=bt, Q[]。QueueInit(Q)。 //初始化隊(duì)列，根結(jié)點(diǎn)指針入隊(duì)while (!QueueEmpty(Q)){p=QueueOut(Q)。amp。 //左子女入隊(duì) else {if (plchild) return 0。 //首次出現(xiàn)結(jié)點(diǎn)為空 if (prchild amp。 !tag) QueueIn(Q,prchild)。 else tag=1。 } //JudgeComplete[算法討論]完全二叉樹(shù)證明還有其它方法。2.[題目分析]后序遍歷最后訪問(wèn)根結(jié)點(diǎn)，即在遞歸算法中，根是壓在棧底的。本題要找p和q 的最近共同祖先結(jié)點(diǎn)r ,不失一般性，設(shè)p在q的左邊。將棧拷入另一輔助棧中。typedef struct {BiTree t。//tag=0 表示結(jié)點(diǎn)的左子女已被訪問(wèn)，tag=1表示結(jié)點(diǎn)的右子女已被訪問(wèn)}stack。//棧，容量夠大BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉樹(shù)上結(jié)點(diǎn)p和q的最近的共同祖
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1