書(shū)面作業(yè)-第4次

①

樹(shù)中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（

）。A.

-1 B.

0 C.

1 D.

2②

在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，所有結(jié)點(diǎn)的空子樹(shù)個(gè)數(shù)等于（

）。A.

n B.n-1 C.

n+1 D.

2*n③

在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，分支結(jié)點(diǎn)的最大

為（A.(n-1)/2C.

n/2為0。）。假定樹(shù)根結(jié)點(diǎn)的B.

n/2

-1D.

n/2為i的結(jié)點(diǎn)存在左孩子，）。假定根結(jié)點(diǎn)的④在一棵完全二叉樹(shù)中，若則左

結(jié)點(diǎn)的為（為1A.

2i

.

-1D.

2i+2C.

2i+1⑤一棵完全二叉樹(shù)中，假定根結(jié)點(diǎn)的為0，則對(duì)于（為i（i＞0）的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的

為）。A.

(i+1)/2C.

(i-1)/2B.

i/2D.

i/2

-1⑥

已知一棵樹(shù)的邊集表示為

{<A,

B>,

<A,

C>,

<B,D>,

<C,

,

,

,

,

,

,

,

F,I>}，則該樹(shù)的高度為（

）。假定根結(jié)點(diǎn)的高度為0。A.

2 B.

4 C.

3 D.

5⑦

利用n個(gè)值作為葉結(jié)點(diǎn)上的權(quán)值生成的

樹(shù)包含有（A.

n-1）個(gè)分支結(jié)點(diǎn)。B.

n+1 C.

n D.

2*

-1⑧

利用3,6,7,11這四個(gè)值作為葉結(jié)點(diǎn)的權(quán)值生成一棵樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為（A.

27 B.

38 C.

52）。D.

58填空題①

對(duì)于一棵具有200個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為

。②

一棵高度為4的完全二叉樹(shù)中，最多包含有個(gè)結(jié)點(diǎn)。假定根結(jié)點(diǎn)的高度為0。③

在一棵二叉樹(shù)中，假定度為2的結(jié)點(diǎn)個(gè)數(shù)為6個(gè)，度為1的結(jié)點(diǎn)個(gè)數(shù)為5個(gè)，則葉子結(jié)點(diǎn)數(shù)為

個(gè)。④

假定一棵二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為18，則它的最小高度為。假定根結(jié)點(diǎn)的高度為0。填空題⑤

設(shè)樹(shù)林F中有3棵樹(shù)，第1、2、3棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為n1、n2、n3，當(dāng)把樹(shù)林F轉(zhuǎn)換成一棵二叉樹(shù)后，其根結(jié)點(diǎn)的右子樹(shù)中有

個(gè)結(jié)點(diǎn)。⑥

設(shè)樹(shù)林F中有4棵樹(shù)，第1、2、3、4棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為n1、n2、n3、n4，當(dāng)把樹(shù)林F轉(zhuǎn)換成一棵二叉樹(shù)后，其根結(jié)點(diǎn)的左子樹(shù)中有

個(gè)結(jié)點(diǎn)。⑦

將含有72個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始順序

，根結(jié)點(diǎn)為第0號(hào)，其他結(jié)點(diǎn)自上向下，同一層自左向右連續(xù)

。則第30號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的

為。問(wèn)答題①

已知一棵二叉樹(shù)的前序和中序序列，求該二叉樹(shù)的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,

A,E,F,D,I,H,J,G后序序列：②

已知一棵二叉樹(shù)的中序和后序序列如下，求該二叉樹(shù)的前序序列。中序序列：c,b,

d,

e,a,g,

i,h,j,f后序序列：c,e,d,

b,

i,j,h,g,

f,a前序序列：?jiǎn)柎痤}口

P166~167頁(yè)口

習(xí)題：2、3、6、8、13、16、18提交要求由通過(guò)教學(xué)網(wǎng)提交，由助教負(fù)責(zé)批改提交作業(yè)的和文件名采用