數(shù)據(jù)結構樹的測試題(二)-全文預覽
【正文】 Copy(BiTree t)//復制二叉樹t{BiTree bt。 bt=plchild。 p=pRChild。p=pLchild。 p=root。 /*入隊列*/ } if (prchild!=NULL) {printf(“%”, prchilddata)。 enqueue (q, T)。bt=s[top].trchild。}｝while(top!=0 amp。i)//；將棧中元素的樹結點到s1去匹配{pp=s[i].t。 top1=top。 bt=btlchild。 bt!=p amp。{top=0。int tag。后序遍歷必然先遍歷到結點p，棧中元素均為p的祖先。判斷時易犯的錯誤是證明其左子樹和右子數(shù)都是完全二叉樹，由此推出整棵二叉樹必是完全二叉樹的錯誤結論。 //右子女入隊 else if (prchild) return 0。 //前邊已有結點為空，本結點不空 else tag=1。 //出隊 if (plchild amp。 // Q是隊列，元素是二叉樹結點指針，容量足夠大if(p==null) return (1)。 btrchild=creat()。 //本題假定結點數(shù)據(jù)域為整型if(x==0) bt=null。判定是否是完全二叉樹，可以使用隊列，在遍歷中利用完全二叉樹“若某結點無左子女就不應有右子女”的原則進行判斷。HGDACJIBFEMPONKOL5.6．（l）圖略；（2）n2)/k中根序列：B C D A F E H J I G。+17．48．任何結點至多只有右子女的二叉樹。√三、填空題1．plchild==null amp。13．度為二的樹就是二叉樹。9. 給定一棵樹，可以找到唯一的一棵二叉樹與之對應。√4. 一棵一般樹的結點的前序遍歷和后序遍歷分別與它相應二叉樹的結點前序遍歷和后序遍歷是一致的。（3）畫出二叉樹的后序線索樹。（只要求給出轉換結果）NPGHJMOLIKEDFBAC10．若一個二叉樹的葉子結點是某子樹的中序遍歷序列中的最后一個結點，則它必是該子樹的____ __序列中的最后一個結點。6．一個深度為k的，具有最少結點數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依此對結點編號，則編號最小的葉子的序號是__ _；編號是i的結點所在的層次號是_ __（根所在的層次號規(guī)定為1層）。2．深度為k的完全二叉樹至少有___ ____個結點，至多有___ ____個結點。( )11．樹形結構中元素之間存在一個對多個的關系。 ( )7．完全二叉樹中，若一個結點沒有左孩子，則它必是樹葉。( )3. 二叉樹的遍歷只是為了在應用中找到一種線性次序。A．CBEFDA B． FEDCBA C． CBEDFA D．不定 13．已知某二叉樹的后序遍歷序列是dabec, 中序遍歷序列是debac , 它的前序遍歷是（ D ）。習題六 樹和二叉樹一、單項選擇題1． 以下說法錯誤的是 ( A )A．樹形結構的特點是一個結點可以有多個直接前趨B．線性結構中的一個結點至多只有一個直接后繼C．樹形結構可以表達(組織)更復雜的數(shù)據(jù)D．樹(及一切樹形結構)是一種分支層次結構E．任何只含一個結點的集合是一棵樹2．下列說法中正確的是 ( D )A．任何一棵二叉樹中至少有一個結點的度為2B．任何一棵二叉樹中每個結點的度都為2C．任何一棵二叉樹中的度肯定等于2D．任何一棵二叉樹中的度可以小于23．討論樹、森林和二叉樹的關系，目的是為了（ A ）A．借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算B．將樹、森林按二叉樹的存儲方式進行存儲C．將樹、森林轉換成二叉樹D．體現(xiàn)一種技巧，沒有什么實際意義4．樹最適合用來表示 ( C )A．有序數(shù)據(jù)元素 B．無序數(shù)據(jù)元素C．元素之間具有分支層次關系的數(shù)據(jù) D．元素之間無聯(lián)系的數(shù)據(jù)5．若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數(shù)是（ B ）A．9 B．11 C．15 D．不確定 6．設森林F中有三棵樹，第一，第二，第三棵樹的結點個數(shù)分別為M1，M2和M3。A．指向最左孩子 B．指向最右孩子 C．空 D．非空12．已知一棵二叉樹的前序遍歷結果為ABCDEF,中序遍歷結果為CBAEDF,則后序遍歷的結果為（ A
范文總結相關推薦
鄂ICP備17016276號-1