发布时间 : 星期日 文章数据结构习题集2015更新完毕开始阅读
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 17
C． p结点右孩子为空 D．p结点有左孩子
15、在具有n个结点的完全二叉树中，若结点i有左孩子，则结点i的左孩子编号为（ ）。
A．2i B．不存在 C．2i+1 D．2i-1
16、将含100个结点的完全二叉树从根这一层开始，按从上到下从左到右依次对结点编号，根结点的编号为１。编号为50的结点X的双亲的编号为（ ）。
A．25 B．48 C．100 D．无法确定 17、三个结点可以构成（ ）种不同形状的二叉树。
A． １ Ｂ．2 C．3 D．5
18、若由树转化得到的二叉树是非空的二叉树，则二叉树形状是（ ）。
A．根结点无右子树的二叉树 B．根结点无左子树的二叉树 C．根结点可能有左子树和右子树 D．各结点只有一个孩子的二叉树 19、哈夫曼树是访问叶结点的带权路径长度（ ）的二叉树。
A．最短 B．最长 C．可变 D．不定
20、某二叉树的前序和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A．空或只有一个结点 B．高度等于其结点数 C．任一结点无左孩子 D．任一结点无右孩子 21、树中所有结点的度之和等于所有结点数加（ ）。
A． 0 B．1 C．-1 D．2
22、含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（ ）
A．3 B．4 C．5 D．6
23、除第一层外，满二叉树中每一层结点个数是上一层结点个数的（ ）
A．1/2倍 B．1倍 C．2倍 D．3倍
24、对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（ A．24 B．25 C．98 D．99 25、在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个数为（ A． 4 B．5 C．6 D．7 26、树最适合用来表示（ ）。
A． 有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 27、判定线索二叉树中某结点P没有左孩子的条件是（ ）
A）P!=NULL B） P->lchild!=NULL C）P->Ltag=0 D）P->Ltag=1 28、在一个非空二叉树的中序遍历序列中，根结点的右边（ ）。 A． 只有右子树上的所有结点 B．只有右子树上的部分结点
C．只有左子树的上的部分结点 D．只有左子树上的所有结点 29、权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是（ ）。 A． 18 B．28 C．19 D．29 30、对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（ ）。 A． n=m+1 B．m+1=2n C．m=k-1 D．n=2k+1 31、有30个结点的完全二叉树的高度为（ ）。 A． 4 B．5 C．6 D．7
二、 填空题：
1、12个结点的完全二叉树的叶结点有（ ）个。
2、在任何一棵二叉树中，度为０的结点n0和度为２的结点n2之间的关系是（ ）。 3、已知完全二叉树的第4层有4个结点，则其叶子结点数是（ ）。
）
。 ） 淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 18
4、10个结点的完全二叉树的叶结点有（ ）个。
5、一个二叉树中，度为2的结点有3个，则叶结点有（ ）个。
6、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的（ ）个结点。
7、下图为某树的静态双亲表示，则结点D、E的双亲结点分别为（ ）和（ ）。
0 A -1 1 B 0 2 C 0 3 D 1 4 E 2
8、二叉树通常有（ ）存储结构和（ ）存储结构两种。 9、树内各结点的度（ ）称为树的度。
10、已知完全二叉树T的第5层只有7个结点，则该树共有（ ）个叶子结点。 11、一棵具有257个结点的完全二叉树，它的深度为（ ）。
三、 判断题：
1、完全二叉树中，若一个结点没有左孩子，则它必须是叶子。 （ ） 2、由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。 （ ） 3、一般在哈夫曼树中，权值越大的叶子离根结点越近。 （ ） 4、二叉树中任何一个结点的度都是2。 （ ） 5、一棵哈夫曼树中不存在度为1的结点。 （ ）
6、若一个二叉树的叶结点是先根遍历序列的最后一个结点，则它必是中根遍历的序列中的最后一个结点。
（ ） 7、中序遍历二叉排序树的结点不能得到排好序的结点序列。 （ ） 8、完全二叉树一定是满二叉树。 （ ） 9、由二叉树的前序和中序遍历序列可以推导出此二叉树的后序遍历序列。 （ ） 10、满二叉树一定是完全二叉树。 （ ） 11、完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。 （ ）
四、 应用题：
1、对给定的一组权值W=｛5，2，9，11，8，3，7｝，试构造相应的哈夫曼树，并计算它的带权路径长度。 答：
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 19
2、设有一组结点，其权值W=｛1，4，9，16，25，36，49｝，画出由这些结点所构成的哈夫曼树，并计算带权路径长度。 答：
3、已知一棵二叉树如图所示。请分别写出按前序、中序、后序和层次遍历是得到的顶点序列。
4、已知一棵二叉树的先根遍历序列和中根遍历序列分别是ABDGHE及GDHBEA，画出这棵二叉树。 答：
5、已知一棵二叉树的前序序列为ABCDEFGH，中序序列为CBEDFAGH，请画出该二叉树。
A B D G H E F C 淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 20
五、 程序设计题：
1．利用二叉树遍历算法输出二叉树中叶子结点。
解：
2．利用二叉树遍历算法求二叉树的高度，假设根结点的高度为1.
成绩____________ 日期____________________