树练习题(答案)

《树》练习题一、单项选择题1、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。A.4B.5C.6D.72、假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。A.15B.16C.17D.473、假定一棵三叉树的结点数为50，则它的最小高度为（）。（根为第0层）A.3B.4C.5D.64、在一棵二叉树上第3层的结点数最多为（）（根为第0层）。A.2B.4C.6D.85、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（）。（若存放在R[0..n-1]则左孩子R[2i+1]）A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]6、将含100个结点的完全二叉树，按照从上层到下层、同层从左到右的次序依次给它们编以从0开始的连续自然数，则编号为40的结点X的双亲的编号为()。A.19B.20C.21D.397、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A.24B.48C.72D.538、设n,m为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（）。A.n在m右方B.n在m左方C.n是m的祖先D.n是m的子孙9、如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（）。A.中序B.前序C.后序D.层次序10、下面叙述正确的是（）。A.二叉树不是树B.二叉树等价于度为2的树C.完全二叉树必为满二叉树D.二叉树的左右子树有次序之分11、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。A.不发生改变B.发生改变C.不能确定D.以上都不对12、已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（）。A.1B.2C.3D.413、下列图示的顺序存储结构表示的二叉树是()。0123456789101112ABCDEFABCDEFABCDEFABCDEFABCDEFA.B.C.D.14、设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定满足的条件是（）。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子15、根据先序序列ABDEC和中序序列BDEAC确定对应的二叉树，该二叉树（）。A.是完全二叉树但不是满二叉树B.不是完全二叉树C.是满二叉树D.不能确定16、对任何一棵二叉树T，设N0、N1、N2分别是度数为0、1、2的结点数，则下列判断正确的是（）。A．N0＝N2＋1B．N1＝N0＋1C．N2＝N0＋1D．N2＝N1＋1二、判断题1.二叉树中每个结点的度不能超过2。（1）2.二叉树的前序遍历中，任意结点均处在其子女结点之前。（1）3.哈夫曼树的总结点个数（多于1时）不能为偶数。（1）4.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。（0）5.树的后序遍历与其对应的二叉树的中序遍历序列相同。（0）6.根据任意一种遍历序列即可唯一确定对应的二叉树。（0）7.满二叉树也是完全二叉树。（1）8.哈夫曼树一定是完全二叉树。（0）9.树的子树是无序的。（0）10.度小于等于2的有序树即为二叉树。（0）三、填空题1、由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为_55__。2、在一棵二叉排序树上按中序遍历得到的结点序列是一个有序序列。3、对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中n-1个用于链接孩子结点，n+1个空闲着。4、在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。5、一棵深度为k的满二叉树的结点总数为2k-1，一棵深度为k的完全二叉树的结点总数的最小值为2k-1，最大值为2k。（根的深度为1）6、由三个结点构成的二叉树，共有5种不同的形态。7、设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为2h+1。（根的高度为1）8、对于一棵具有n个结点的二叉树，若一个结点的编号为i(0≤i≤n-1)，则它的左孩子结点的编号为2i+1，右孩子结点的编号为2i+2，双亲结点的编号为(i-1)/2。9、假设一棵二叉树的先序序列为ABCEDFG，中序序列为AECBFDG，则该二叉树的层序遍历序列中结点E的直接前驱是结点F。四、应用题1.已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。先序：ABDHIEJKCFLG中序：HDIBJEKALFCG后序：HIDJKEBLFGCA2.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请写出该二叉树的后序遍历序列。后序：ACDBGJKIHFE3．若有字符a,b,c,d,e,f,g,h的频度权值分别为（30，5，9，11,15，2，7，16），试为这组字符设计哈弗曼编码。2117929141557302016365995哈弗曼编码：a:01b:00001c:100d:101e:001f:00000g:0001h:11五、算法设计题按照以下树的定义，完成数类中的以下成员函数的编写。（1）voidPreOrder(Node*r));//先序遍历的递归算法（2）voidInOrder(Node*r));//中序遍历的递归算法（3）voidPostOrder(Node*r));//后序遍历的递归算法（4）intHigh(Node*bt);//求二叉树高度的递归算法#includeiostream#defineMaxSize100structNode{Node*lChild;//左子树指针Node*rChild;//右子树指针DataTypedata;};classBTree{private:Node*root;public:BTree();//构造函数voidPreOrder(Node*r));//先序遍历的递归算法voidInOrder(Node*r));//中序遍历的递归算法voidPostOrder(Node*r));//后序遍历的递归算法intHigh(Node*bt);//求二叉树高度的递归算法intNodeNum(Node*bt);//求二叉树结点数目};//二叉树先序遍历递归算法voidBTree::PreOrder(Node*r){if(r!=NULL){coutr-data;PreOrder(r-lChild);PreOrder(r-rChild);}}//二叉树中序遍历递归算法voidBTree::InOrder(Node*r,){if(r!=NULL){InOrder(r-lChildt);coutr-data;InOrder(r-rChild);}}//二叉树后序遍历递归算法voidBTree::PostOrder(Node*r,){if(r!=NULL){PostOrder(r-lChild);PostOrder(r-rChild;coutr-data;}}//求二叉树的高度intBTree::High(Node*r){intlh,rh;if(r==NULL)return0;else{lh=High(r-lChild);rh=High(r-rChild);if(lhrh)returnlh+1;elsereturnrh+1;}}