數(shù)據(jù)結(jié)構(gòu)——樹習(xí)題

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

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

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

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