最全數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案(耿國(guó)華版[1]-資料下載頁(yè)
2025-06-20 12:53本頁(yè)面
【正文】 AD[((a,b),(c,d))]]。 (b)（4） HEAD[TAIL[HEAD[((a,b),(c,d))]]]。 b（5） TAIL[HEAD[TAIL[((a,b),(c,d))]]]。 (d)第六章第六章答案6． 1分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)?！窘獯稹烤哂?個(gè)結(jié)點(diǎn)的樹 具有3個(gè)結(jié)點(diǎn)的二叉樹 ，n2個(gè)度為2的結(jié)點(diǎn)，……，nk個(gè)度為k的結(jié)點(diǎn)，則該樹中有多少個(gè)葉子結(jié)點(diǎn)？【解答】設(shè)樹中結(jié)點(diǎn)總數(shù)為n,則n=n0 + n1 + …… + nk樹中分支數(shù)目為B,則B=n1 + 2n2 + 3n3 + …… + knk因?yàn)槌Y(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支，所以有n= B + 1即n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1由上式可得葉子結(jié)點(diǎn)數(shù)為：n0 = n2 + 2n3 + …… + (k1)nk + 1，則該二叉樹的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個(gè)？【解答】n0表示葉子結(jié)點(diǎn)數(shù)，n2表示度為2的結(jié)點(diǎn)數(shù)，則n0 = n2+1 所以n2= n0 –1=49，當(dāng)二叉樹中沒有度為1的結(jié)點(diǎn)時(shí)，總結(jié)點(diǎn)數(shù)n=n0+n2=99 試分別找出滿足以下條件的所有二叉樹:(1) 前序序列與中序序列相同。(2) 中序序列與后序序列相同。(3) 前序序列與后序序列相同。【解答】 (1) 前序與中序相同：空樹或缺左子樹的單支樹； (2) 中序與后序相同：空樹或缺右子樹的單支樹； (3) 前序與后序相同：空樹或只有根結(jié)點(diǎn)的二叉樹。 假設(shè)通訊的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為：，，，，請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼?！窘獯稹? 構(gòu)造哈夫曼樹如下：哈夫曼編碼為：I1：11111 I5：1100 I2：11110 I6： 10I3：1110 I7： 01 I4：1101 I8： 00。【解答】，實(shí)現(xiàn)在中序線索二叉樹T中查找給定結(jié)點(diǎn)*p在中序序列中的前驅(qū)與后繼。在先序線索二叉樹T中，查找給定結(jié)點(diǎn)*p在先序序列中的后繼。在后序線索二叉樹T中，查找給定結(jié)點(diǎn)*p在后序序列中的前驅(qū)。（1）找結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)BiTNode *InPre (BiTNode *p)/*在中序線索二叉樹中查找p的中序前驅(qū)結(jié)點(diǎn)，并用pre指針返回結(jié)果*/{ if (pLtag= =1) pre = pLChild。 /*直接利用線索*/ else {/*在p的左子樹中查找“最右下端”結(jié)點(diǎn)*/ for ( q=pLChild。 qRtag= =0。 q=qRChild)。 pre = q。 } return (pre)。 }（2）找結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)BiTNode *InSucc (BiTNode *p)/*在中序線索二叉樹中查找p的中序后繼結(jié)點(diǎn)，并用succ指針返回結(jié)果*/{ if (pRtag= =1) succ = pRChild。 /*直接利用線索*/ else {/*在p的右子樹中查找“最左下端”結(jié)點(diǎn)*/ for ( q=pRChild。 qLtag= =0。 q=qLChild)。 succ= q。 } return (succ)。 }(3) 找結(jié)點(diǎn)的先序后繼結(jié)點(diǎn)BiTNode *PreSucc (BiTNode *p)/*在先序線索二叉樹中查找p的先序后繼結(jié)點(diǎn)，并用succ指針返回結(jié)果*/{ if (pLtag= =0) succ = pLChild。 else succ= pRChild。 return (succ)。 }(4) 找結(jié)點(diǎn)的后序前驅(qū)結(jié)點(diǎn)BiTNode *SuccPre (BiTNode *p)/*在后序線索二叉樹中查找p的后序前驅(qū)結(jié)點(diǎn)，并用pre指針返回結(jié)果*/{ if (pLtag= =1) pre = pLChild。 else pre= pRChild。 return (pre)。 }，利用棧的基本操作寫出先序遍歷非遞歸形式的算法。【解答】Void PreOrder(BiTree root) /*先序遍歷二叉樹的非遞歸算法*/{ InitStack(amp。S)。 p=root。 while(p!=NULL || !IsEmpty(S) ) { if(p!=NULL) {Visit(pdata)。push(amp。S,p)。p=pLchild。 }else { Pop(amp。S,amp。p)。 p=pRChild。}}}，編寫算法將二叉樹左右子樹進(jìn)行交換?！窘獯稹? 算法(一) Void exchange ( BiTree root ){ p=root。 if ( pLChild != NULL || pRChild != NULL ) { temp = pLChild。pLChild = pRChild。 pRChild = temp。 exchange ( pLChild )。 exchange ( pRChild )。 } } 算法(二) Void exchange ( BiTree root ){ p=root。 if ( pLChild != NULL || pRChild != NULL ) { exchange ( pLChild )。 exchange ( pRChild )。 temp = pLChild。pLChild = pRChild。 pRChild = temp。 } } 第八章第八章答案8．1 【解答】 5ASLsucc=（1+2X2+3X4+4X3）/10= 【解答】(1) ASLSUCC=(1+2 X2+3 X3+4X3+5X2+6)/12=(2) 排序?yàn)椋篈pr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,Sep折半查找ASLSUCC=(1+2 X2+3 X4+4X5)/12=37/12 【解答】ASLSUCC=(1 X4+2 X3+6)/8=2ASLUNSUCC=(2+1+8+7+6+5+4+3+2+1+1)/11=40/1116
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1