一、樹和二叉樹

1.? 看圖，完成以下填空

(1).樹的度為________。
(2).樹中結點的最大層次，稱為樹的_____或樹的______，值是______。
(3).結點A和B的度分別為________ 和 ________。
(4).結點A是結點B的________。
(5).結點B是結點A的________。
(6).樹的葉子結點:_________________________。

(7). n>0 時，根結點是唯一的，不可能存在多個根結點。(是否正確)
(8). n>0 時，樹中任意結點的子樹個數沒有限制，但它們之間一定是互不相交的。(是否正確)
?

2.? 回答以下問題（概念相關）

(1) 從形態上考慮，3個結點的樹有幾種情況，并畫出來。

(2) 從形態上考慮，3個結點的二叉樹有幾種情況，并畫出來。

(3) 二叉樹中是否存在度大于2的結點。(回答:是、否)

(4) 如果一個二叉樹是滿二叉樹，它的結點總數小于50，且不是空樹，請列舉出可能的結點總數。

(5) 請敘述滿二叉樹與完全二叉樹的差異。

(6) 完全二叉樹是否可能存在度為1的結點。(回答:是、否)

3.? 完成以下填空（性質相關）

(1) 二叉樹的第i層上最多有______個結點 （i >=1 ）
(2) 深度為k的二叉樹最多有______個結點 （k >=1 ）
(3) 具有100個結點的完全二叉樹，樹的深度_______.

4.? 完成以下填空（存儲相關）

(1) 樹的存儲表示法有那些_________________、_________________、_________________。
(2) 以下代碼是樹的那種存儲表示法:_________________。

# define MAX_TREE_SIZE 100struct Node
{int data;struct Node *parent;
};struct Tree
{struct Node nodes[MAX_TREE_SIZE];int size;
};

（3）完全二叉樹，由于它定義的嚴格，用順序結構也可以很經濟的表示，例如

數組形式：char nodes[] = {'A','B','C','D','E','F','G','H','I'};

以下是一個普通的二叉樹，請按完全二叉樹思路，不存在的結點用-1表示

請試著寫出數組形式：char nodes[] = ___________________________;

（4）請試著補全二叉樹鏈表的定義

struct Node
{int data;struct Node ________, _________;
};

5.? 請寫出下圖二叉樹的遍歷序列（遍歷相關）

前序遍歷這顆二叉樹的節點順序是:_________________________________。

中序遍歷這顆二叉樹的節點順序是:_________________________________。

后序遍歷這顆二叉樹的節點順序是:_________________________________。

6.? 請將下圖，轉換為二叉樹

7.? 請畫出以下序列的哈夫曼樹，并計算該二叉樹的帶權路徑長度WPL值。

A:5, E:10, B:15, D:30, E:40

二、線性表

1. 從線性表的定義，找出請認為的2個核心關鍵詞

線性表定義: 零個或多個數據元素的有限序列。

2. 請描述順序存儲的優點、缺點

3. 請描述鏈式存儲的優點、缺點

三、隊列、棧

1. 具有“先進先出”特點的存儲結構是______.

2. 具有“先進后出”特點的存儲結構是______.

四、緒論（概念：總結、回顧）

(1) 數據結構可分為________結構和_________結構。

(2) 數據的邏輯結構有那些:___________________________________________________.

(3) 數據的物理結構有那些:___________________________________________________.

(4) 算法分析的兩個主要方面：____________、____________________.