数据结构作业（四） 2013-11-12

《数据结构作业（四） 2013-11-12》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构作业（四）2013-11-12年级2012B班级姓名学号一、填空题1、一颗深度为6的二叉树总结点数值少为，最多为；一颗深度为6的完全二叉树第5层上的结点数为____，总结点数最小值为，总结点数最多时称为二叉树。2、对于一颗具有n个结点的二叉树，当它为一颗完全二叉树时具有最小高度，高度为，当它为一颗单支树具有最大高度，高度为。3、一颗完全二叉树第6层有7个结点，则共有个结点，其中度为1的结点有个，度为0的结点有个，若按从上到下，从左到右次序给结点编号（从1开始），编号最大的非叶子结点是，编号最小的叶子结点是。4、设高度

2、为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为，至多为。5、对于一颗具有n个结点的二叉树，当进行二叉链表存储时，其指针域的总数为个，其中个用于链接孩子结点，个空闲着。6、已知二叉树中叶子数为50，仅一个孩子的结点数为30，则总结点数____；在有50个叶子结点的哈夫曼树中，总结点数是____。7、有5813个结点构成一棵完全二叉树，其叶子结点数为；有5813个结点构成一棵二叉树，已知2度结点数为0，则树高是。8、先序为a,b,c,且后序为c,b,a,的二叉树有棵。9、在二叉链表中，数据域值为dat

3、a，左右子树的指针分别为lchild和rchild，则判断某指针p所指结点为0度结点的条件是；p所指结点为1度结点的条件是；p所指结点为2度结点的条件是。10、由带权为3，9，6，2，5的5个叶子结点构成一颗Huffman树，则带权路径长度为。二、选择题1、按照二叉树的定义，具有三个结点的二叉树有种形状。A、3B、4C、5D、62、一棵二叉树的叶子结点数为6，则度为1的结点个数为。A、5B、7C、6D、不能确定3、在非空二叉树的中序遍历序列中，根结点的右边。A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上

4、的部分结点D、只有左子树上的所有结点4、下列陈述中正确的是。A、二叉树是度为2的有序树B、二叉树中结点只有一个孩子时无左右之分C、二叉树中必有度为2的结点D、二叉树中最多只有两棵子树，并且有左右之分5、对有100个结点的完全二叉树按层次依次编号，则编号为49的结点右孩子编号为。A、98B、51C、99D、9746、如果n1和n2是二叉树T中两个不同结点，n2是n1的孩子，那么按遍历二叉树T时，结点n2一定比结点n1先被访问。A、先序B、中序C、后序D、逆中序7、某二叉树的中序序列和后序序列正好相反，则该二叉树一定是的二叉树。

5、A、空或只有一个结点 B、高度等于其结点数 C、任一结点无左孩子 D、任一结点无右孩子8、某二叉树的先序序列和后序序列正好相同，则该二叉树一定是的二叉树。A、空或只有一个结点B、高度等于其结点数C、任一结点无左孩子D、任一结点无右孩子9、一棵深度为8（根的层次号为1）的满二叉树有个叶子结点A、256B、255C、128D、12710、如图是用孩子兄弟链表法所表示的一个森林，则该森林是由棵树构成。A．1B．2C．3D．4三、算法阅读设二叉树以二叉链表为存储结构，结点类型定义如下：typedefstructtnode{chard

6、ata;structtnode*lchild,*rchild/*lchild指向左孩子，rchild指向右孩子*/}BiTNode,*BiTree;1、对应二叉链表存储的二叉树已建立（如下图），根结点地址为T，请给出调用ex1(T)函数的输出结果。voidex1(BiTreeT){if(T){ex1(T->lchild);ex1(T->rchild);if(T->data>=’0’&&T->data<=’9’)printf(“%c”,T->data);}}2、下面的函数ex2是统计二叉树中2度结点的个数，请填充适当的内容，使

7、得该算法可以完成相应的功能。voidex2(BiTreeT,int*n)/*n指向存放统计结果变量的指针变量*/{if(T){ex2(T->lchild,n);if();ex2(T->rchild,n);}}4四、应用题1、有一个完全二叉树按层次顺序存放在一维数组中，如下所示：请指出结点P的父结点，左子女，右子女。2、有一棵二叉树按顺序结构存放在一维数组中，如下所示：012345678910111213abcdefgh请画出该二叉树的二叉链表存储结构。3、假设在通信中要传输一组字符“ABC,AAABCC,ABC,DDC,AA

8、A”。（1）构造相应的赫夫曼树（左结点的权小于右结点的权）（2）求出带权路径的长度WPL（3）给出每个字符的赫夫曼编码（左分支为“0”，有分支为“1”）4、已知一颗二叉树的先序和中序遍历的结点序列分别为IJKLMNO及JLKINMO，试画出此二叉树，并给出后序遍历序列结果4五、算法设计题设