數(shù)據(jù)結構——樹習題

1、數(shù)據(jù)結構數(shù)據(jù)結構——樹練習樹練習注：“[]”為向上取整，“”為向下取整。一、填空題1、二叉樹第i(i=1)層上至多有__2^(i1)___個結點。2、深度為k(k=1)的二叉樹至多有___2^k1__個結點。3、具有n個結點的完全二叉樹的深度為__log2(n1)____。4、具有n個結點的二叉樹中一共有____2n___個指針域其中只有____n1___個用來指向結點的左右孩子，其余的___n1_____個指針域為NULL。5、若二叉

2、樹的一個葉子是某子樹的中根遍歷序列中的第一個結點，則它必是該子樹的后根遍歷序列中的___第一個_____個結點。6、在____先序____遍歷二叉樹的序列中，任何結點的子樹上的所有結點，都是直接跟在該結點之后。7、具有n個結點的完全二叉樹，若按層次從上到下、從左到右對其編，號（根結點為1號），則編號最大的分支結點序號是____n2____，編號最小的分支結點序號是___1____，編號最大的葉子結點序號是_____n__，編號最小的葉子

3、結點序號是__n21_____。8、先根遍歷樹和先根遍歷與該樹對應的二叉樹，其結果___相同____（填“相同”或“不同”）。9、由____一顆樹___轉換成二叉樹時，其根結點的右子樹總是空的。③在二叉鏈表上，求根，求左、右孩子等很容易實現(xiàn)④在二叉鏈表上，求雙親運算的時間性能很好3、深度為6的二叉樹最多有(2)個結點()①64②63③32④314、將含有83個結點的完全二叉樹從根結點開始編號，根為1號，后面按從上到下、從左到右的順序對結

4、點編號，那么編號為41的雙結點編號為(4)①42②40③21④205、任何一棵二叉樹的葉結點在其先根、中根、后跟遍歷序列中的相對位置(3)①肯定發(fā)生變化②有時發(fā)生變化③肯定不發(fā)生變化④無法確定6、設深度為k的二叉樹上只有度為0和度為2的節(jié)點，則這類二叉樹上所含結點總數(shù)最少（3）個①k1②2k③2k1④2k17、下列說法正確的是(1)①樹的先根遍歷序列與其對應的二叉樹的先根遍歷序列相同②樹的先根遍歷序列與其對應的二叉樹的后根遍歷序列相同③