一、树和二叉树

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) 算法分析的两个主要方面：____________、____________________.