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

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

2、樹(shù)的一個(gè)葉子是某子樹(shù)的中根遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的后根遍歷序列中的___第一個(gè)_____個(gè)結(jié)點(diǎn)。6、在____先序____遍歷二叉樹(shù)的序列中，任何結(jié)點(diǎn)的子樹(shù)上的所有結(jié)點(diǎn)，都是直接跟在該結(jié)點(diǎn)之后。7、具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，若按層次從上到下、從左到右對(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、先根遍歷樹(shù)和先根遍歷與該樹(shù)對(duì)應(yīng)的二叉樹(shù)，其結(jié)果___相同____（填“相同”或“不同”）。9、由____一顆樹(shù)___轉(zhuǎn)換成二叉樹(shù)時(shí)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。③在二叉鏈表上，求根，求左、右孩子等很容易實(shí)現(xiàn)④在二叉鏈表上，求雙親運(yùn)算的時(shí)間性能很好3、深度為6的二叉樹(shù)最多有(2)個(gè)結(jié)點(diǎn)()①64②63③32④314、將含有83個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始編號(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、任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在其先根、中根、后跟遍歷序列中的相對(duì)位置(3)①肯定發(fā)生變化②有時(shí)發(fā)生變化③肯定不發(fā)生變化④無(wú)法確定6、設(shè)深度為k的二叉樹(shù)上只有度為0和度為2的節(jié)點(diǎn)，則這類二叉樹(shù)上所含結(jié)點(diǎn)總數(shù)最少（3）個(gè)①k1②2k③2k1④2k17、下列說(shuō)法正確的是(1)①樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先根遍歷序列相同②樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后根遍歷序列相同③