作业树和二叉树

树(树根结点的高度为1)一、选择题3．以下说法错误的是()。A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B．在三叉链表上，二叉树的求双亲操作很容易实现C．在二叉链表上，求根以及求左、右孩子等操作很容易实现D．在二叉链表上，求双亲操作的时间性能很好4．以下说法错误的是()。A．一般在哈夫曼树中，权值越大的叶子离根结点越近B．哈夫曼树中没有度数为1的分支结点C．若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点D．若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树5．深度为6的二叉树最多有()个结点。A．64B．63C6．将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为()。A．10B．11C．41D．207．设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少()个。A．k+lB．2kC．2k-1D．2k+18．下列说法中正确的是()。A．任何一棵二叉树中至少有一个结点的度为2B．任何一棵二叉树中每个结点的度都为2C．任何一棵二叉树中的每个结点的度肯定等于2D．任何一棵二叉树中的每个结点的度都可以小于29．一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用()遍历方式就可以得到这棵二叉树所有结点的递减序列。A．前序B．中序C．后序D．层次10．如图6-1所示的二叉树的中序遍历序列是()。A．abcdgefB．dfebagcC．dbaefcgD．defbagc3．二叉树第i(i>0)层上至多有___2i-1_______个结点。4．深度为k(k>0)的二叉树至多有_____2k-1_____个结点。5．对任何二叉树，若度为2的节点数为n2，则叶子数n0=__n2+1________。6．满二叉树上各层的节点数已达到了二叉树可以容纳的___最大值______。满二叉树也是___完全_______二叉树，但反之不然。7．具有n个结点的完全二叉树的深度为___log2n取整+1_______。8．二叉树通常有______顺序_______存储结构和____链式______存储结构两类存储结构。9．每个二叉链表还必须有一个指向_根_______结点的指针，该指针具有标识二叉链表的作用。10．对二叉链表的访问只能从_____根______指针开始。11．二叉树有不同的链式存储结构，其中最常用的是___二叉链表_______与_三叉链表_________。12．具有100个结点的完全二叉树的深度是__7_________。13．在_____先序_____遍历二叉树的序列中，任何结点的子树上的所有结点都是直接跟在该结点之后。14．若一棵二叉树的叶子数为n，则该二叉树中左、右子树皆非空的结点个数为___n-1_______。15．一棵树的形状如图6-5所示，它的根结点是__A_______，叶结点是__E，J，K，G，L，O，P，Q，R，N，I________，结点H的度是___3______，这棵树的度是___4_____，这棵树的深度是___5______，结点F的儿子结点是___J，K____，结点G的父结点是___C______。18．含有2n个结点的二叉树高度至少是_n+1__________，至多是__2n_______(仅含根结点的二叉树高度为1)。四、应用题1．分别写出图6-7所示二叉树的前序、中序和后序序列。答：前序：ABCDEF、中序：CBEFDA和后序：CFEDBA2．已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树，并写出其前序遍历序列。答：前序遍历序列：ABCDEFGH3．设某密码电文由8个字母组成，a,b,c,d,e,f,g,h每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，