2016 秋 -Quiz

一 二叉树的性质

1-1

在二叉树中，以根节点为第 0 层，则第 1 层上有多少个结点？

1-2

根结点为第 0 层，深度为层数最大的叶结点的层数，则深度为 k 的二叉树至多有多少个结点？

1-3

一棵二叉树，若其叶子结点数为 $n_0$ , 度为 2 的结点数为 $n_2$ , 则 $n_0$ 和 $n_2$ 的关系是什么？

1-4

根结点为第 0 层，深度为层数最大的叶结点的层数，则有 n 个结点的完全二叉树的深度为多少？

1-5

画出如下数组表示的完全二叉树，并写出数组表示的完全二叉树中子结点和其父结点的下标关系 (数组下标从 0 开始).

二 请写出二叉树的非递归中序遍历算法

三 请写出二叉树的层序遍历算法

四 已知一棵树的先序遍历序列和中序遍历序列分别为 ABDGHCEFI 和 GDHBAECIF, 请画出此二叉树

五 简述最小堆的定义. 并画出下列操作的调整过程：向一个空堆中，逐步插入如下序列

$12,70,8,65,24,56,10,92,86,33$ , 并要确保每插入一步所得到的堆都是最小堆.

六 若森林中有 n 个结点和 b 条边 $(b<n)$ , 则该森林中有多少棵树？

七 请简单描述二叉搜索树的定义，并写出将指定 K 值插入到二叉搜索树中的算法

八 已知二叉树按二叉链表形式存储，设计算法求二叉树第 k 层 (根结点为第 0 层) 上结点的个数

九 已知二叉树按二叉链表形式存储，设计递归算法求出给定二叉树的深度 (只含根节点的树深度为 0)