数据结构练习2-08答案

数据结构练习（二）答案

一、填空题：

1．若一棵树的括号表示为A（B（E，F），C（G（H,I,J,K）,L）,D（M（N））），则该树的度为 （1）4 ，树的深度为 （2）4 ，树中叶子结点的个数为（3）8。

2．一棵满二叉树中有m个叶子，n个结点，深度为h，请写出m、n、h之间hh-1 关系的表达式 （4）n=2-1,m=n+1-2。

3．一棵二叉树中如果有n个结点。k-1k一棵深度为k的完全二叉树中最少有 2（6） 个结点，最多有（7）2-1 个结点。

4．具有n个结点的二叉树，当它是一棵二叉树时具有最小高度（9） log2n」+1 ，当它为一棵单支树时具有高度 (10) n 。

5．对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为_(11)__[i/2]__，左孩子的编号为___2i____，右孩子的编号为__2i+1______。

6．若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有__2n_个指针域，其中有_n-1_个指针域用于链接孩子结点，__n+1_个指针域空闲存放着NULL 。

7．二叉树的遍历方式通常有__先序__、___中序__、__后序__和___层序___四种。

8．已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为___DCBFGEA__。

9．已知某完全二叉树采用顺序存储结构，结点的存放次序为

A,B,C,D,E,F,G,H,I,J，该完全二叉树的后序序列为___HIDJEBFGCA____。

10．若具有n个结点的非空二叉树有n0个叶结点，则该二叉树有__n0-1_个度为2的结点，____n-2n0+1____个度为1的结点。

11．任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的__根____。度为k的树中第i层最多有___ki-1_______个结点(i>=1)，深度为h的k叉树最多有___k0+k1+....+kh-1____个结点。

12．非空二叉树一共有__4__种基本形态，第i层最多有__ 2i-1___个结点。

13．在一棵完全二叉树中，编号i和编号j的两个结点处于同一层的条件是_log2i=log2j__

14．有n个顶点的强连通图至少有n个顶点的连通图至少有

（8）n-1 边。

15．设无向图G的顶点数为n，图G最少有最多有 条边；若边数为e，用邻接矩阵表示图，求每一顶点度的时间复杂性为 (14)

第1页下一页