數(shù)據(jù)結(jié)構(gòu)樹的測試題(二)-免費閱讀
【正文】 }(4) 找結(jié)點的后序前驅(qū)結(jié)點BiTNode *SuccPre (BiTNode *p)/*在后序線索二叉樹中查找p的后序前驅(qū)結(jié)點，并用pre指針返回結(jié)果*/{ if (pLtag= =1) pre = pLChild。 /*直接利用線索*/ else {/*在p的右子樹中查找“最左下端”結(jié)點*/ for ( q=pRChild。c)。} //父結(jié)點的左子女置空else Enqueue (Q,plchild)。 }// DeleteXTree //釋放被刪結(jié)點所占的存儲空間void Search(B:Tree bt,ElemType x)//在二叉樹上查找所有以x為元素值的結(jié)點，并刪除以其為根的子樹{BiTree Q[]。 //中序遍歷左子樹 prerchild=null。 //全局變量LinkedList InOrder(BiTree bt)//中序遍歷二叉樹bt，將葉子結(jié)點從左到右鏈成一個單鏈表，表頭指針為head {if(bt){InOrder(btlchild)。 btdata=tdata。while(p || top0) {while(p) {s[++top]=p。S,p)。 enqueue (q, plchild)。 //退棧if (top!=0)｛s[top].tag=1。i0。 s[top].tag=0。//棧，容量夠大BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉樹上結(jié)點p和q的最近的共同祖先結(jié)點r。本題要找p和q 的最近共同祖先結(jié)點r ,不失一般性，設p在q的左邊。 !tag) QueueIn(Q,prchild)。 //初始化隊列，根結(jié)點指針入隊while (!QueueEmpty(Q)){p=QueueOut(Q)。 btlchild=creat()。其哈夫曼編碼如下A:1，B:000，C:01，D:0011359000111五、算法設計題1．[題目分析]二叉樹是遞歸定義的，以遞歸方式建立最簡單。設n 為結(jié)點i的子女，則關系式(i1)k+2=n=ik+1成立，因i是整數(shù)，故結(jié)點n的雙親i的編號為235。log2i√12．將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點沒有左子樹。3. 二叉樹的遍歷只是為了在應用中找到一種線性次序。5．將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹。5．樹的主要遍歷方法有________、________、________等三種。( )10. 用鏈表(llinkrlink)存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n1個空指針。( )2．對于有N個結(jié)點的二叉樹，其高度為log2n。習題六 樹和二叉樹一、單項選擇題1． 以下說法錯誤的是 ( A )A．樹形結(jié)構(gòu)的特點是一個結(jié)點可以有多個直接前趨B．線性結(jié)構(gòu)中的一個結(jié)點至多只有一個直接后繼C．樹形結(jié)構(gòu)可以表達(組織)更復雜的數(shù)據(jù)D．樹(及一切樹形結(jié)構(gòu))是一種分支層次結(jié)構(gòu)E．任何只含一個結(jié)點的集合是一棵樹2．下列說法中正確的是 ( D )A．任何一棵二叉樹中至少有一個結(jié)點的度為2B．任何一棵二叉樹中每個結(jié)點的度都為2C．任何一棵二叉樹中的度肯定等于2D．任何一棵二叉樹中的度可以小于23．討論樹、森林和二叉樹的關系，目的是為了（ A ）A．借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算B．將樹、森林按二叉樹的存儲方式進行存儲C．將樹、森林轉(zhuǎn)換成二叉樹D．體現(xiàn)一種技巧，沒有什么實際意義4．樹最適合用來表示 ( C )A．有序數(shù)據(jù)元素 B．無序數(shù)據(jù)元素C．元素之間具有分支層次關系的數(shù)據(jù) D．元素之間無聯(lián)系的數(shù)據(jù)5．若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（ B ）A．9 B．11 C．15 D．不確定 6．設森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。( )3. 二叉樹的遍歷只是為了在應用中找到一種線性次序。( )11．樹形結(jié)構(gòu)中元素之間存在一個對多個的關系。6．一個深度為k的，具有最少結(jié)點數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依此對結(jié)點編號，則編號最小的葉子的序號是__ _；編號是i的結(jié)點所在的層次號是_ __（根所在的層次號規(guī)定為1層）。（只要求給出轉(zhuǎn)換結(jié)果）NPGHJMOLIKEDFBAC√4. 一棵一般樹的結(jié)點的前序遍歷和后序遍歷分別與它相應二叉樹的結(jié)點前序遍歷和后序遍歷是一致的。13．度為二的樹就是二叉樹。+17．48．任何結(jié)點至多只有右子女的二叉樹。n2)/k判定是否是完全二叉
范文總結(jié)相關推薦
鄂ICP備17016276號-1