《练习题 _树和二叉树》由会员分享，可在线阅读，更多相关《练习题 _树和二叉树（5页珍藏版）》请在金锄头文库上搜索。
1、第六、七章的练习题一、 选择题1任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序 （ ）。A不发生改变 B发生改变 C不能确定 D以上都不对2设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（ ）。An在m右方 Bn是m的祖先 Cn在m的左方 Dn是m的子孙3具有33个结点的完全二叉树的深度为（ ），有（ ）个叶子结点，有（ ）个度为1的结点。（1）A5 B6 C7 D8（2）A14 B15 C16 D17（3）A0 B1 C12 D164已知一棵二叉树有50个叶子结点，30个度为1的结点，则该二叉树的总结点数为（ ）。A129 B130 C131 D1325设森
2、林有三棵树组成，第一、第二和第三棵树中的结点个数分别为m1、m2和m3。那么在由该森林转化成的二叉树中根结点的右子树上的结点个数是（ ）。Am1+m2 Bm2+m3 Cm1+m3 Dm1+m2+m36用n个权值构造出来的哈夫曼树的结点个数是（ ）。A2n-1 B2n C2n+1 Dn+17在下列关于二驻树遍历的说法中错误的是（ ）。A在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行先序遍历和后序遍历将得到相同的结点序列；B在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行中序遍历和后序遍历将得到相同的结点序列；C在一棵二叉树中，假定每个结点最多只有左子女，
3、没有右子女，对它分别进行先序遍历和层次遍历将得到相同的结点序列；D在一棵二叉树中，假定每个结点最多只有右子女，没有左子女，对它分别进行先序遍历和中序遍历将得到相同的结点序列；8在下列关于二叉树遍历的说法中正确的是（ ）。A若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的先序遍历结果序列的最后一个结点；B若有一个结点是二叉树中某个子树的先序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点；C若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的先序遍历结果序列的最后一个结点；D若有一个叶子结点是二叉树中
4、某个子树的先序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点；9先序为A、B、C，后序为C、B、A的二叉树共有（ ）个。A1 B2 C3 D410设结点x和y是二叉树中任意的两个结点。在该二叉树的先序遍历序列中x在y之前，而在后序遍历序列中x在y之后，则x和y的关系是（ ）。Ax是y的左兄弟 Bx是y的右兄弟 Cx是y的祖先 Dx是y的子孙11设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶子结点，则B中右指针域为空的结点个数是（ ）。An-1 Bn Cn+1 Dn+212若设一棵树具有n个结点，则它所有结点的度数之和为（ ）。设森林F对应的二叉树为B，它
5、有m个结点。B的根为p，p的右子树中结点个数为n，则森林F中第一棵树的结点个数是（ ）。如果T2是由树T转换成的二叉树，那么T中结点的后序遍历顺序对应T2中结点的（ ）遍历顺序。（1）A2n B2n-1 Cn+1 Dn-1（2）Am-n Bm-n-1 Cn+1 D无法确定（3）A先序 B中序 C后序 D层次13下列关于哈夫曼树的说法中不正确的是（ ）。A对应一组权值构造出来的哈夫曼树一般不是唯一的；B哈夫曼树具最小的带权路径长度；C哈夫曼树中没有度为1的结点；D哈夫曼树中除了有度为1的结点之外，还有度为2的结点和叶子结点14树最适合用来表示（ ）。A有序数据元素 B无序数据元素C元素之间具有分
6、支层次关系的数据 D元素之间无联系的数据15在线索二叉树中，T所指结点没有左子树的充要条件是（ ）。AT-lchild=NULL BT-ltag=1CT-ltag=1且T-lchild=NULL D以上都不对16在一非空二叉树的中序遍历序列中，根结点的右边是（ ）。A只有右子树上的所有结点 B只有右子树上的部分结点C只有左子树上的部分结点 D只有左子树上的所有结点17根据使用频率为5个字符设计的哈夫曼编码不可能是（ ）。A111，110，10，01，00 B000，001，010，011，1C100，11，10，1，0 D001，000，01，11，1018根据使用频率为5个字符设计的哈夫曼编
7、码不可能是（ ）。A000，001，010，011，1 B0000，0001，001，01，1C000，001，01，10，11 D00，100，101，110，11119已知一算术表达式的中缀表达式为a-(b+c/d)*e，其后缀形式为（ ）。A-a+b*c/de B-a+b*cd/e C-+*abc/de Dabcd/+e*-20一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。A250 B500 C505 D以上都不对二、 填空题1二叉树由（ ）、（ ）和（ ）三个基本单元组成。2已知一棵度为3的树中有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有（ ）个叶子
8、结点。3若以4、5、6、7、8为叶子结点的权值构造哈夫曼树，则其带权路径长度是（ ）。4设n为哈夫曼树中叶子结点个数，则该哈夫曼树共有（ ）个结点。5对于一棵n个结点的二叉树，当它为一棵（ ）二叉树时具有最小高度，当它为一棵（ ）二叉树时具有最大高度。6一个深度为k的具有最少结点数的完全二叉树按层次（同层从左到右），用自然数依次对结点编号，则编号最小的叶子结点的序号是（ ）。7在二叉链表存储中，指针p所指的结点为叶子结点的条件（ ）。8已知一棵二叉树的先序序列为ABDECFHG，中序序列为DBEAHFCG，则该二叉树的根为（ ），左子树中（ ），右子树中（ ）。9在一棵存储结构为三叉链表的二叉
9、树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是（ ）。10下面是求二叉树（以二叉链表形式存储）深度的递归算法，将其补充完整。int height( BiTree bt ) if ( ) if(bt-lchild=NULL) Lh= ; else Lh= ; if(bt-rchild=NULL) Rh= ; else Rh= ; if ( LhRh ) hi= ; else hi= ;else hi= ;return hi;三、 应用题1列出满足以下条件的所有二叉树。（1）先序遍历和后序遍历的结点序列正好相同；（2）先序遍历和后序遍历的结点序列正好相
10、反；（3）先序遍历和中序遍历的结点序列正好相同；（4）中序遍历和后序遍历的结点序列正好相同；（5）先序遍历和中序遍历的结点序列正好相反；（6）中序遍历和后序遍历的结点序列正好相反；2对给定的二叉树做以下操作：（1）写出四种遍历的结点序列；（2）画出先序遍历的线索二叉树； 第二题的图（3）将其转换成对应的森林或树。3画出满足以下条件的二叉树。（1）先序遍历的结点序列stuwv，中序遍历的结点序列uwtvs。（2）中序遍历的结点序列cbedahgijf，后序遍历的结点序列cedbhjigfa。（3）层次遍历的结点序列abcdefghij，中序遍历的结点序列dbgehjacif。4求表达式(a+b*(c-d)-e/f的前缀式和后缀式。5画出给定森林转换后得到的二叉树，并指出在二叉链表中某结点所对应的森林中结点为叶子结点的条件。6画出下列已知序列对应的树。（1）先根序列为：GFKDAIEBCHJ（2）后根序列为：DIAEKFCJHBG7有7个带权结点，其权值分别为：3，7，8，2，6，10，14，试以它们为叶子结点构造一棵哈夫曼树，画出所构造的哈夫曼树，并计算WPL。8有一份电文中共使用5个字符：A、B、C、D、E、F、K，它们的出现频率以次为4，3，2，11，12，7，8。试画出对应的哈夫曼树（要求
