数据结构第二单元练习题答案.doc

数据结构第二单元练习题答案一、选择1.树最适合用来表示( )A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2.在下述结论中，正确的是( )只有一个结点的二叉树的度为0; 二叉树的度为2； 二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A. B. C. D.3.以下说法正确的是( )A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中每个结点的度都为2C.任何一棵二叉树的度肯定等于2D.任何一棵二叉树的度可以小于24.在下列情况中，可称为二叉树的是( )A.每个结点至多有两棵子树的树 B.哈夫曼树C.每个结点至多有两棵子树的有序树 D.每个结点只有一棵右子树 E.以上答案都不对5.深度为h的满m叉树的第k层有( )个结点(1=k=h) A.mk-1 B.mk-1 C.mh-1 D.mh-16.在一棵高度为k的满二叉树中，结点总数为( )A.2k-1 B.2k C.2k-1 D.log2k+17.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为( )个 A.4 B.5 C.6 D.7 8.具有10个叶结点的二叉树中有( )个度为2的结点。 A.8 B.9 C.10 D.ll9.二叉树有n个结点，则其深度为（ ）A.n-1 B.n C.(log2n)+1 D.无法确定该题是二叉树不是完全二叉树由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。10.一个具有1025个结点的二叉树的高h为( )A.11 B10 C.11至1025之间 D.10至1024之间11.一棵具有 n个结点的完全二叉树的深度是( )A.log2n+1 B.log2n+1 C.log2n D.log2n-112.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度( )A.4 B.5 C.6 D.7 13.将一棵有100个结点的完全二叉树从根结点这一层开始，每一层上从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ ）A.98 B.99 C.50 D.48利用二叉树的性质514.在完全二叉树中，若一个结点是叶结点，则它没( )A.左子结点 B.右子结点 C.左子结点和右子结点 D.左子结点，右子结点和兄弟结点15.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 Al.n中时，数组中第i个结点的左孩子为( )A.A2i(2i=n) B.A2i+1(2i+1=1）个结点的各棵树中，其深度最小的那棵树的深度是_(1) 2 _。它共有_(2) n-1 _个叶子结点和_(3) 1 _个非叶子结点，其中深度最大的那棵树的深度是_(4) n _，它共有_(5)_ 1 _个叶子结点和_(6) n-1_个非叶子结点。2.如果结点A有 3个兄弟，而且B是A的双亲，则B的度是_4 _。3.二叉树由_(1) 根结点_，_(2) 左子树_，_(3) 右子树 _三个基本单元组成。4设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为_(1)2K+1-1_,最小结点数为_(2)_ k+1_。5.在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =_ N2+1_6.如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_69_。7.高度为K的完全二叉树至少有_2k-2_个叶子结点。8.高度为8的完全二叉树至少有_64 _个叶子结点。9.已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_ 99_。10.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_12 _个叶子结点。11.一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为_21_。11.一棵有n个结点的满二叉树有_(1) 0 _个度为1的结点、有_(2) (n-1)/2_个分支 （非 终端）结点和_(3) (n+1)/2 _个叶子，该满二叉树的深度为_(4) log2n +1_。12.深度为k（设根的层数为1）的完全二叉树至少有 (1) 2k-1 个结点，至多有 (2) 2k-1 个结点，k和结点数n之间的关系是 (3) k= log2n 1 。13在完全二叉树中，编号为i和j的两个结点处于同一层的条件是_log2i=log2j _。14.对于一个具有n个结点的二叉树，当它为一棵_(1) 完全二叉树_二叉树时具有最小高度，当它为一棵_(2) 单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或只有右子女。_时，具有最大高度。15.假设根结点的层数为，具有个结点的二叉树的最大高度是_ n _。16.具有256个结点的完全二叉树的深度为_9 _。17.一棵完全二叉树有999个结点，它的深度是 10 。18.一个有2001个结点的完全二叉树的高度为_ 11 _。19.二叉树有不同的链式存储结构，其中最常用的是 (1)二叉链表 与 三叉链表 。20.二叉树的先序序列和中序序列相同的条件是_任一结点均无左孩子_。21.在一棵二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是_双亲的右子树中最左下的叶子结点_。22.每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是_(1) FEGHDCB _。设上述二叉树是由某棵树（或森林）转换而成，则第一棵树的先根次序序列是_(2)_ BEF23.二叉树结点的中序序列为ABCDEFG,后序序列为BDCAFGE,则该二叉树结点的前序序列为_(1) EACBDGF _,则该二叉树对应的树林包括_(2) 2_棵树。24.已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为_(1) a _，左子树中结点有_(2) dbe _， 右子树中结点有_(3) hfcg _。25.现有按中序遍历二叉树的结果为abc，问有_(1) 5 _种不同的二叉树可以得到这一遍历结果，这些二叉树分别是_(2)_ 略 _（画出树型）。26.中缀式a+b*3+4*（c-d）对应的前缀式为_(1) +a*b3*4-cd _，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_(2) 18_。27.线索二叉树的左线索指向其 (1) 前驱 ,右线索指向其 (2) 后继 .28.一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：_2_。29.树在计算机内的表示方式有_(1) 双亲表示法_，_(2) 孩子表示法_，_(3) 孩子兄弟表示法30.利用树的孩子兄弟表示法存储，可以将一棵树转换为_二叉树 _。31.设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有_(1) n1-1_个结点，右子树中有_(2) n2+n3 _个结点。32.先根次序遍历树林正好等同于按_(1) 先序_遍历对应的二叉树，后根次序遍历树林正好等同于按_(2) 中序_遍历对应的二叉树。33.先根次序遍历森林正好等同于按_先序_遍历对应的二叉树；中根次序遍历森林正好等同于_中序_遍历对应的二叉树。34.哈夫曼树是_带权路径长度最小的二叉树，又称最优二叉树_。35.设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有 2n0-1 个结点。36.哈夫曼树是带权路径长度 最短 的树,通常权值较大的结点离根 较近 .37.若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_69 _。38.有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1) 80_，字符c的编码是_(2) 001（不唯一）_。39.下面是求二叉树高度的类C写的递归算法试补充完整。二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根，lh和rh分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。height(p)if (1) p _) if(p-lchild=null) lh=(2)_ 0_; else lh=(3)_ height(p-lchild)_;if(p-rchild=null) rh=(4)_ 0_; else rh=(5)_ height(p-rchild)_;if (lhrh) hi=(6) lh+1_；else hi=(7)_ rh+1_; else hi=(8) 0_;return hi;/ 40.二叉树用二叉链表存储，以下程序为求二叉树深度的递归算法，请填空完善之。 int depth(bitree bt) /*bt为根结点的指针*/int hl,hr; if (bt=NULL) return(1) 0 _); hl=depth(bt-lchild); hr=depth(bt-rchild); if(2) hlhr _) (3)_ hr=hl _； return(hr+1);三、判断题1.二叉树是一般树的特殊情形。2.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法( X )3.二叉树中每个结点至多有两个子结点,而对一般树则无此限制.因此,二叉树是树的特殊情形. 4.树形结构中元素之间存在一个对多个的关系。5.二叉树是度为2的有序树。6.如果二叉树中某结点的度为1，则说该结点只有一棵子树( )7.深度为K的二叉树中结点总数2k-1。8.完全二叉树中，若一个结点没有左孩子，则它必是树叶。9.对于有N个结点的二叉树，其高度为log2n。10.深度为k具有n个结点的完全二叉树，其编号最小的结点序号为 2k-2+1。11.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。12.完全二叉树的存储结构通常采用顺序存储结构。13.二叉树只能用二叉链表表示。14.用链表存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。15.二叉树的遍历结果不是唯一的. 只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。16.二叉树的遍历只是为了在应用中找到一种线性次序。17.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法( )18.非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。19.由一棵二叉树的前序序列和后序序列可以唯一确定它。20.在中序线索二叉树中，每一非空的线索均指向其祖先结点。在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。21.线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。22.二叉树中序线索化后，不存在空指针域。非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。23.给定一棵树，可以找到唯一的一棵二叉树与之对应。24.必须把一般树转换成二叉树后才能进行存储。25.将一棵树转成二叉树，根结点没有左子树；26.采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。27.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。28.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。29.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法（ X）。30.在二叉树中插入结点，则它不再是二叉树了。31.哈夫曼树的结点个数不能是偶数。32.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。33.当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。四解答应用题1. 一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。 证明：设二叉树度为0和2的结点数及总的结点数分别为n0，n2 和n，则n=n0+n2 (1)再设二叉树的分支数为B,除根结点外，每个结点都有一个分支所指，则 n=B+1 (2)度为零的结点是叶子，没有分支，而度为2的结点有两个分支，因此（2）式可写为n=2*n2+1 (3)由（1）、（3）得n2=n0-1,代入（1），并由（1）和（2）得B=2*(n0-1)。 证毕。2任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m-1）个度为2，其余度为1。证明：设度为1和2 的结点数是n1和n2，则二叉树结点数n为n=m+n1+n2 (1)由于二叉树根结点没有分枝所指，度为1和2的结点各有1个和2个分枝，度为0 的结点没有分枝，故二叉树的结点数n与分枝数B有如下关系 n=B+1=n1+2*n2+1.(2)由（1）和（2），得n2=m-1。即n个结点的二叉树，若叶子结点数是m，则非叶子结点中有（m-1）个度为2，其余度为1。3一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。先序序列是“根左右” 后序序列是“左右根”，可见对任意结点，若至多只有左子女或至多只有右子女，均可使前序序列与后序序列相反，图示如下：4画出同时满足下列两条件的两棵不同的二叉树。 (1)按先根序遍历二叉树顺序为ABCDE。 (2)高度为5其对应的树（森林）的高度最大为4。AABCDEBDCE5已知二叉树的先序、中序和后序遍历序列分别如下(但其中一些模糊不清)先序： ABC_EF_ _ 中序： BDE_AG_ H 后序： _DC_GH_ _ 要求：（1）补充模糊的地方，并重新写出先序、中序和后序遍历序列（2）画出该二叉树（3）画出该二叉树的中序线索树（4）画出该二叉树对应的森林 （5）画出森林中第一棵树的孩子兄弟表示法答案：（1）先序：ABCDEFGH; 中序BDECAGFH; EDCBGHFA（2）二叉树: （4）森林：HGFEDCBAEDCHGFBA五、算法设计1二叉树用二叉链表存储，编写算法求二叉树度为1的结点 （1）给出二叉链表的类型定义 （2）用类C语言写出递归算法类型定义： typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;int num(BiTree T) if(!T)return 0;elsenl=num(T-lchild);nr=num(T-rchild);if(T-lchild&!T-rchild|! T-lchild&T-rchild)return nl+nr+1;else return nl+nr;2编写算法以中序编立的顺序给出每个结点以及该结点的层次（二叉树用二叉链表存储，类型定义如（1）void inorder (BiTree T,int l) if (T) inorder(T-lchild,l+1);printf(“%c,%d” ,T-data,l); inorder(T-rchild,l+1);