數(shù)據(jù)結(jié)構(gòu)樹的測(cè)試題(二)-文庫吧在線文庫
【正文】 n) C．A[i2] D．條件不充分，無法確定二、判斷題（在各題后填寫“√”或“”）1. 完全二叉樹一定存在度為1的結(jié)點(diǎn)。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（ D ）。( )4. 一棵一般樹的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點(diǎn)前序遍歷和后序遍歷是一致的。( )12．將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點(diǎn)沒有左子樹。7．如果結(jié)點(diǎn)A有 3個(gè)兄弟，而且B是A的雙親，則B的度是______。6．設(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為樹根結(jié)點(diǎn)的指針，其值為6,Lchild,Rchild分別為結(jié)點(diǎn)的左、右孩子指針域,data為結(jié)點(diǎn)的數(shù)據(jù)域。5. 用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。14. 二叉樹中序線索化后，不存在空指針域。9．二叉排序樹10．前序11．6912． *count++, countleaf(lrchile,count)13．(1) p=plchild // 沿左子樹向下 （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．樹和二叉樹邏輯上都是樹形結(jié)構(gòu)，樹和二叉樹的區(qū)別有三：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個(gè)分枝的情況下， 也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空（個(gè)別書上允許為空）。+1。BiTree Creat() //建立二叉樹的二叉鏈表形式的存儲(chǔ)結(jié)構(gòu){ElemType x；BiTree bt。 } else error(“輸入錯(cuò)誤”)；return(bt)。amp。 else tag=1。將?？饺肓硪惠o助棧中。 bt=ROOT。} //沿左分枝向下if(bt==p) //不失一般性，假定p在q的左側(cè),遇結(jié)點(diǎn)p時(shí)，棧中元素均為p的祖先結(jié)點(diǎn){for(i=1。for (j=top1。｝ //沿右分枝向下遍歷}//結(jié)束while(bt!=null ||top0)return(null)。 enqueue (q, prchild)。 }else { Pop(amp。} //中序遍歷左子樹 if(top0){p=s[top]。btrchild=Copy(trchild)。amp。 } //InOrder時(shí)間復(fù)雜度為O(n),輔助變量使用head和pre,?？臻g復(fù)雜度O(n)8.[題目分析] 刪除以元素值x為根的子樹，只要能刪除其左右子樹，就可以釋放值為x的根結(jié)點(diǎn)，因此宜采用后序遍歷。 exit(0)。 prchild=null。 /*直接利用線索*/ else {/*在p的左子樹中查找“最右下端”結(jié)點(diǎn)*/ for ( q=pLChild。 q=qLChild)。 return (pre)。 else succ= pRChild。 } return (pre)。c)。if(plchild) // 若左子女非空 if(plchilddata==x) //左子女結(jié)點(diǎn)值為 x,應(yīng)刪除當(dāng)前結(jié)點(diǎn)的左子樹 {DeleteXTree(plchild)。 DeleteXTree(btrchild)。 pre=bt。第一個(gè)葉子結(jié)點(diǎn)由指針head指向，遍歷到葉子結(jié)點(diǎn)時(shí)，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點(diǎn)的rchild為空。 if (t==null) bt=null。}}}5．．void InOrder(BiTree bt) {BiTree s[],p=bt。 while(p!=NULL || !IsEmpty(S) ) { if(p!=NULL) {Visit(pdata)。 /*入隊(duì)列*/ while (not emptyqueue (q) ) /*若隊(duì)列非空*/ {outqueue (q, p) 。amp。 }//將棧s的元素轉(zhuǎn)入輔助棧s1 保存if(bt==q) //找到q 結(jié)點(diǎn)。amp。//tag=0 表示結(jié)點(diǎn)的左子女已被訪問，tag=1表示結(jié)點(diǎn)的右子女已被訪問}stack。2.[題目
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1