数据结构-构造哈夫曼树一、填空题： 1、深度为k的完全二叉树至少有 个结点。 2、树中结点的最大层次称为树的 。 3、由

数据结构-构造哈夫曼树
一、填空题：
1、深度为k的完全二叉树至少有 个结点。
2、树中结点的最大层次称为树的 。
3、由一棵二叉树的前序序列和 序列可以唯一确定这棵二叉树。
4、一棵含有n个结点的完全二叉树，它的高度是 。
5、二叉树的存储结构有顺序存储和 。
6、哈夫曼树是带权路径长度 的二叉树。
7、n个顶点的连通图至少有 条边。
8、具有4个顶点的无向完全图有 条边。
9、图的深度优先遍历序列 唯一。
10、一个图的生成树的顶点是图的 顶点。
二、单项选择题：
1、具有35个结点的完全二叉树的深度为（ ）。
（A）5 （B）6 （C）7 （D）8
2、树最适合用来表示（ ）。
（A）有序数据元素 （B）无序数据元素
（C）元素之间无联系的数据 （D）元素之间有分支层次的关系
3、线索二叉树是一种（ ）结构。
（A）物理 （B）逻辑 （C）逻辑与存储 （D）线性
4、一棵n个结点的二叉树，其空指针域的个数为（ ）。
（A）n （B）n+1 （C）n-1 （D）不确定
5、如果某二叉树的前序为STUWV，中序为UWTVS，那么二叉树的后序序列为（ ）。
（A）UWVTS （B）VWUTS （C）WUVTS （D）WUTSV
6、图的深度优先遍历类似于二叉树的（ ）。
（A）先序遍历 （B）中序遍历 （C）后序遍历 （D）层次遍历
7、任何一个无向连通图的最小生成树（ ）。
（A）只有一棵 （B）一棵或多棵 （C）一定有多棵
（D）可能不存在
8、生成树的构造方法只有（ ）。
（A）深度优先 （B）深度优先与广度优先
（C）无前趋的顶点优先 （D）无后继的顶点优先
9、无向图顶点V的度是关联于该顶点（ ）的数目。
（A）顶点 （B）边 （C）序号 （D）下标
10、在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。
（A）0.5 （B）1 （C）2 （D）4
三、是非题：
1、 满二叉树一定是完全二叉树。()
2、 由树转换成二叉树，其根结点的右子树一定为空的。()
3、 用一维数组来存储二叉树时，总是以前序遍历存储结点。()
4、 二叉树按某种顺序线索后，任一结点均有指向其前驱和后继的线索。()
5、 树属于非线性结构。()
6、 图可以没有边，但不能没有顶点。()
7、 有向图的边一定是有两个方向的。()
8、 有向图不能进行广度优先遍历。()
9、 带权图最小生成树是唯一的。()
10、 图按某种方法可以转变成树。()
四、综合题：
给定权值{ 2，4，6，7，8，9}，构造一棵哈夫曼树，并求出其带权路径长度。