第六章树和二叉树习题_数据结构

习题六树和二叉树一、单项选择题1．以下说法错误的是()A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继C．树形结构可以表达(组织)更复杂的数据D．树(及一切树形结构)是一种分支层次结构E．任何只含一个结点的集合是一棵树2．下列说法中正确的是()A．任何一棵二叉树中至少有一个结点的度为2B．任何一棵二叉树中每个结点的度都为2C．任何一棵二叉树中的度肯定等于2D．任何一棵二叉树中的度可以小于23．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储C．将树、森林转换成二叉树D．体现一种技巧，没有什么实际意义4．树最适合用来表示()A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M37．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250B．500C．254D．505E．以上答案都不对8.设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-19．二叉树的第I层上最多含有结点数为（）A．2IB．2I-1-1C．2I-1D．2I-110．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点A．2hB．2h-1C．2h+1D．h+111.利用二叉链表存储树，则根结点的右指针是（）。A．指向最左孩子B．指向最右孩子C．空D．非空12．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定13．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。A．acbedB．decabC．deabcD．cedba14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同15．在完全二叉树中，若一个结点是叶结点，则它没（）。A．左子结点B．右子结点C．左子结点和右子结点D．左子结点，右子结点和兄弟结点16．在下列情况中，可称为二叉树的是（）A．每个结点至多有两棵子树的树B.哈夫曼树C．每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树E．以上答案都不对17.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：()。A.0B.1C.2D.不确定18.引入二叉线索树的目的是（）A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一19．n个结点的线索二叉树上含有的线索数为（）A．2nB．n－lC．n＋lD．n20．由3个结点可以构造出多少种不同的二叉树？（）A．2B．3C．4D．521．下面几个符号串编码集合中，不是前缀编码的是（）。A．{0,10,110,1111}B．{11,10,001,101,0001}C．{00,010,0110,1000}D．{b,c,aa,ac,aba,abb,abc}22.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（）A．A[2i](2i=n)B．A[2i+1](2i+1=n)C．A[i-2]D．条件不充分，无法确定23、以下说法错误的是()A．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。B．若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。C．已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。D．在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。二、判断题（在各题后填写“√”或“×”）1.完全二叉树一定存在度为1的结点。()2．对于有N个结点的二叉树，其高度为log2n。()3.二叉树的遍历只是为了在应用中找到一种线性次序。()4.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。()5.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。()6．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。()7．完全二叉树中，若一个结点没有左孩子，则它必是树叶。()8.二叉树只能用二叉链表表示。()9.给定一棵树，可以找到唯一的一棵二叉树与之对应。()10.用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。()11．树形结构中元素之间存在一个对多个的关系。()12．将一棵树转成二叉树，根结点没有左子树。()13．度为二的树就是二叉树。()14.二叉树中序线索化后，不存在空指针域。()15．霍夫曼树的结点个数不能是偶数。()16．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。()三、填空题1．在二叉树中，指针p所指结点为叶子结点的条件是______。2．深度为k的完全二叉树至少有_______个结点，至多有_______个结点。3．高度为8的完全二叉树至少有______个叶子结点。4.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。5．树的主要遍历方法有________、________、________等三种。6．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是___；编号是i的结点所在的层次号是___（根所在的层次号规定为1层）。7．如果结点A有3个兄弟，而且B是A的双亲，则B的度是______。8．二叉树的先序序列和中序序列相同的条件是______。9．一个无序序列可以通过构造一棵______树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。10．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。11．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。12．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。Voidcountleaf(bitreptrt,int*count)/*根指针为t，假定叶子数count的初值为0*/{if(t!=NULL){if((t-lchild==NULL)&&(t-rchild==NULL))________;countleaf(t-lchild,&count);________}}13．以下程序是二叉链表树中序遍历的非递归算法，请填空使之完善。二叉树链表的结点类型的定义如下：typedefstructnode/*C语言/{chardata;structnode*lchild,*rchild;}*bitree;voidvst(bitreebt)/*bt为根结点的指针*/{bitreep;p=bt;initstack(s);/*初始化栈s为空栈*/while(p||!empty(s))/*栈s不为空*/if(p){push(s,p);(1)___;}/*P入栈*/else{p=pop(s);printf(“%c”,p-data);(2)____;}/*栈顶元素出栈*/}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)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。typedefstructnode{intdata;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)___;}}}//四、应用题BACEDFNPGHJMOLIK1．树和二叉树之间有什么样的区别与联系？2．分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。3．分别给出下图所示二叉树的先根、中根和后根序列。4．一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：1）各层的结点的数目是多少？2）编号为n的结点的双亲结点（若存在）的编号是多少？3）编号为n的结点的第i个孩子结点（若存在）的编号是多少？4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？请给出计算和推导过程。5．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）6．设二叉树BT的存储结构如下:12345678910Lchild00237580101DataJHFDBACEGIRchild0009400000其中BT为树根结点的指针，其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。试完成下列各题:（l）画出二叉树BT的逻辑结构;（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列;（3）画出二叉树的后序线索树。7．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。五、算法设计题1．要求二叉树按二叉链表形式存储，（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。2．设一棵二叉树的结点结构为(LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。3．有一二叉链表，试编写按层次顺序遍历二叉树的算法。4．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。5．对于二叉树的链接实现,完成非递归的中序遍历过程。6．试写出复制一棵二叉树的算法。二叉树采用标准链接结构。。7．请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。8．已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。9．设一棵二叉树的根结点指针为T，C为计数变量，初值为0，试写出对此二叉树中结点计数的算法：BTLC（T，C）。10．分别写出算法，实现在中序线索二叉树T中查找给定结点*p在中序序