资源描述：
《第六章作业及答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第六章作业一、选择题1.若不考虑结点的数据信息的组合情况，具有3个结点的树共有种（）形态，而二叉树共有()种形态。A.2B.3C.4D.52.对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=()A.n1+1B.n1+n2C.n2+1D.2n1+13.已知某非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即ABC□DFE□□G□□H□□，该二叉树的中序遍历序列为()A.G,D,B,A,F,H,C,EB.G,B,D,A,F,H,C,EC.B,D,G,A,F,H,C,ED.B,G,D,A,F,H,C,E4、具有6
2、5个结点的完全二叉树的高度为（ ）。（根的层次号为1）A．8B．7C．6D．55、在有N个叶子结点的哈夫曼树中，其结点总数为（）。A不确定B2NC2N+1D2N-16、以二叉链表作为二叉树存储结构，在有N个结点的二叉链表中，值为非空的链域的个数为（）。AN-1B2N-1CN+1D2N+17、树的后根遍历序列等同于该树对应的二叉树的().A.先序序列B.中序序列C.后序序列8、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是 （）A．39 B.52 C.111 D.119 9、在一棵度为4的树T中，若有20个度为4
3、的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是（）A．41 B.82 C.113 D.122二、填空题。1、对于一个具有N个结点的二叉树，当它为一颗_____二叉树时，具有最小高度。2、对于一颗具有N个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_____个，其中_____个用于链接孩子结点，_____个空闲着。3、一颗深度为K的满二叉树的结点总数为_____，一颗深度为K的完全二叉树的结点总数的最小值为_____，最大值为_____。4、已知一棵二叉树的前序序列为ABDFCE，中序序列为DFB
4、ACE，后序序列为 三、应用题。ABCDEFGHIJ1、已知一棵树二叉如下，请分别写出按前序、中序、后序遍历时得到的结点序列，并将该二叉树还原成森林。2假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码。五、算法设计题1.已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。2.编写算法，求二叉树的深度。*3.已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。参考答案：一1D2C
5、3D4B5D6A7B8.c9B二1完全二叉树22NN-1N+132k-12k-12k-14FDBECA三1voidsearch(BiTree&T){if(T){cou++;if(T->lchild!=NULL&&T->rchild!=NULL)count++;search(T->lchild);search(T->rchild);}}2intDepth(BiTreeT){//返回二叉树的深度if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=
6、1+(depthLeft>depthRight?depthLeft:depthRight);}returndepthval;}3voidPreOrder_Nonrecursive(BitreeT)//先序遍历二叉树的非递归算法{ InitStack(S); Push(S,T);//根指针进栈 while(!StackEmpty(S)) { while(Gettop(S,p)&&p) { visit(p->data); push(S,p->lchild); }//向左走到尽头 pop(S,p); if(!
7、StackEmpty(S)) { pop(S,p); push(S,p->rchild);//向右一步 } }//while}//PreOrder_Nonrecursive
