数据结构树和二叉树习题

1、习题六树和二叉树一、单项选择题1以下说法错误的选项是()A树形结构的特色是一个结点能够有多个直接前趋B线性结构中的一个结点至多只有一个直接后继C树形结构能够表达(组织)更复杂的数据D树(及全部树形结构)是一种分支层次结构E任何只含一个结点的会合是一棵树2以下说法中正确的选项是()A任何一棵二叉树中起码有一个结点的度为2B任何一棵二叉树中每个结点的度都为2C任何一棵二叉树中的度必定等于2D任何一棵二叉树中的度能够小于23议论树、丛林和二叉树的关系，目的是为了（）A借助二叉树上的运算方法去实现对树的一些运算B将树、丛林按二叉树的储存方式进行储存C将树、丛林变换成二叉树D表现一种技巧，没有什么实质意

2、义4树最适适用来表示()A有序数据元素B无序数据元素C元素之间拥有分支层次关系的数据D元素之间无联系的数据5若一棵二叉树拥有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（A9B11C15D不确立）6设丛林F中有三棵树，第一，第二，第三棵树的结点个数分别为点的右子树上的结点个数是（）。AM1BM1+M2CM3DM2+M3M1，M2和M3。与丛林F对应的二叉树根结7一棵完整二叉树上有A250B5001001个结点，此中叶子结点的个数是（）C254D505E以上答案都不对设给定权值总数有n个，其哈夫曼树的结点总数为()A不确立B2nC2n+1D2n-19二叉树的第I层上最多含有结点数为

3、（）A2IB2I-1-1C2I-1D2I-110一棵二叉树高度为h,全部结点的度或为0，或为2，则这棵二叉树最罕有()结点A2hB2h-1C2h+1Dh+111.利用二叉链表储存树，则根结点的右指针是（）。A指向最左孩子B指向最右孩子C空D非空12已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。ACBEFDABFEDCBACCBEDFAD不定13已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。AacbedBdecabCdeabcDcedba14在二叉树结点的先序序列，中序序列和后序序列中，全部叶子结点的先后次

4、序（）A都不同样B完整同样C先序和中序同样，而与后序不一样D中序和后序同样，而与先序不一样15在完整二叉树中，若一个结点是叶结点，则它没（）。A左子结点B右子结点C左子结点和右子结点D左子结点，右子结点和兄弟结点16在以下状况中，可称为二叉树的是（）A每个结点至多有两棵子树的树哈夫曼树C每个结点至多有两棵子树的有序树每个结点只有一棵右子树E以上答案都不对17.一棵左右子树均不空的二叉树在先序线索化后，此中空的链域的个数是：()。A.0B.1C.2D.不确立18.引入二叉线索树的目的是（）A加速查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲D使二叉树的遍历

5、结果独一19n个结点的线索二叉树上含有的线索数为（）A2nBnlCnlDn20由3个结点能够结构出多少种不一样的二叉树？（）A2B3C4D521下边几个符号串编码会合中，不是前缀编码的是（）。A0,10,110,1111B11,10,001,101,0001C00,010,0110,1000Db,c,aa,ac,aba,abb,abc22.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右次序储存在一维数组A1.n中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的地点是（）AA2i(2i=n)BA2i+1(2i+1lchild=NULL)&(t-rchild=NULL

6、)_;countleaf(t-lchild,&count);_13以下程序是二叉链表树中序遍历的非递归算法，请填空使之完美。二叉树链表的结点种类的定义以下：typedefstructnode/*C语言/chardata;structnode*lchild,*rchild;*bitree;voidvst(bitreebt)/*btbitreep;p=bt;initstack(s);/*while(p|!empty(s)/*if(p)push(s,p);(1)_;/*Pelsep=pop(s);printf(“%c”,p为根结点的指针*/初始化栈s为空栈*/栈s不为空*/入栈*/-data);(2

7、)_;/*栈顶元素出栈*/14二叉树储存结构同上题，以下程序为求二叉树深度的递归算法，请填空完美之。intdepth(bitreebt)/*bt为根结点的指针*/inthl,hr;if(bt=NULL)return(1)_);hl=depth(bt-lchild);hr=depth(bt-rchild);if(2)_)(3)_；return(hr+1);15将二叉树bt中每一个结点的左右子树交换的C语言算法以下，此中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和鉴别行列能否为空的函数，请填写算法中得空白处，达成其功能。typedefstructnodeintdata;

8、structnode*lchild,*rchild;btnode;voidEXCHANGE(btnode*bt)btnode*p,*q;if(bt)ADDQ(Q,bt);while(!EMPTY(Q)p=DELQ(Q);q=(1)_;p-rchild=(2)_;(3)_=q;if(p-lchild)(4)_;if(p-rchild)(5)_;/第六章树和二叉树一、单项选择题D9C10B11.C12A13D14B15C16C20D21B22.D23C二、判断题（在各题后填写“”或“”）1.完整二叉树必定存在度为1的结点。2.关于有N个结点的二叉树，其高度为log2n。3.二叉树的遍历不过为了在应

9、用中找到一种线性序次。4.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。5.用一维数组储存二叉树时，老是从前序遍历次序储存结点。6中序遍历一棵二叉排序树的结点便可获得排好序的结点序列7完整二叉树中，若一个结点没有左孩子，则它必是树叶。8.二叉树只好用二叉链表表示。9.给定一棵树，能够找到独一的一棵二叉树与之对应。10.用链表(llink-rlink)储存包括n个结点的二叉树，结点的2n个指针地区中有11树形结构中元素之间存在一个对多个的关系。12将一棵树转成二叉树，根结点没有左子树。13度为二的树就是二叉树。14.二叉树中序线索化后，不存在空指针域。15霍夫曼树的结点个数不可以是偶数。16哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。n-1个空指针。三、填空题1p-lchild=null&p-rchlid=null2.(1)2k-1(2)2k-13644.2nn-1n+15先序遍历后序遍历中序遍历6.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2)log2i+1748任何结点至多只有右儿女的二叉树。9二叉排序树10前序116912*count+,