選擇題14

45.下列結構中為非線性結構的是

A)樹              B)向量       

C)二維表            D)矩陣

A【解析】由定義可以知道，樹為一種簡單的非線性結構。在數這種資料結構中，所有資料元素之間的關系具有明顯的層次特性。

46.某棵樹的度為4，且度為4、3、2、1的結點個數分别為1、2、3、4，則該樹中的葉子結點數為

A)11        B)9           

C)10             D)8

A【解析】根據樹中的結點數=樹中所有結點的度之和+1，設葉子結點數為n，得4×1+3×2+2×3+1×4+n×0+1=21,則n=21-1-2-3-4=11。

47.設一棵度為3的樹，其中度為2，1，0的結點數分别為3，1，6。該樹中度為3的結點數為

A)1             B)2       

C)3            D)不可能有這樣的樹

A【解析】設樹的結點數為n，則度為3的結點數為n-3-1-6=n-10，根據樹中的結點數=樹中所有結點的度之和+1，得3×（n-10）+2×3+1×1+0×6+1=n，解得n=11，則度為3的結點數為n-10=11-10=1。

48.設一棵樹的度為3，其中沒有度為2的結點，且葉子結點數為5。該樹中度為3的結點數為 

A)

3            B)1            

C) 2            D)不可能有這樣的樹

C【解析】設樹的結點數為m，度為3的結點數為n，則度為1的結點數為m-n-5, 根據樹中的結點數=樹中所有結點的度之和+1，得3×n+1×（m-n-5）+5×0+1=m，則n=2。

49.設某棵樹的度為3，其中度為2,1,0的結點個數分别為3,4,15。則該樹中總結點數為

A)不可能有這樣的樹        B)30       

C)22            D)35

A【解析】設樹的總結點數為n，則度為3的結點數為n-3-4-15=n-22，根據樹中的結點數=樹中所有結點的度之和+1，得3×（n-22）+2×3+1×4+0×15+1=n，則n=27.5，求出的結點數不為整數，故不可能有這樣的樹存在。

50.某二叉樹共有845個結點，其中葉子結點有45個，則度為1的結點數為 

A)400          B)754            

C)756          D)不确定