《作业树和二叉树》由会员分享，可在线阅读，更多相关《作业树和二叉树（7页珍藏版）》请在金锄头文库上搜索。
1、树(树根结点的高度为1)一、选择题3如下说法错误的是( )。 A完全二叉树上结点之间的父子关系可由它们编号之间的关系来体现 B在三叉链表上，二叉树的求双亲操作很容易实现 C在二叉链表上，求根以及求左、右孩子等操作很容易实现 D在二叉链表上，求双亲操作的时间性能较好4如下说法错误的是( )。 A一般在哈夫曼树中，权值越大的叶子离根结点越近 B哈夫曼树中没有度数为1的分支结点 C若初始森林中共有n棵二叉树，最后求得的哈夫曼树共有2n-1个结点 D若初始森林中共有n棵二叉树，进行2n-1次合并后才干剩余一棵最后的哈夫曼树5深度为6的二叉树最多有( )个结点。 A64 B63 C32 D316将具有4
2、1个结点的完全二叉树从根结点开始编号，根为1号，背面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为( )。 A10 B11 C41 D207设深度为k的二叉树上只有度为0和度为2的结点，则此类二叉树上所含结点总数至少( )个。 Ak+l B2k C2k-1 D2k+18下列说法中对的的是( )。 A任何一棵二叉树中至少有一种结点的度为2 B任何一棵二叉树中每个结点的度都为2 C任何一棵二叉树中的每个结点的度肯定等于2 D任何一棵二叉树中的每个结点的度都可以不不小于29一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都不不小于它的左子树上所有结点的值，而不小于右
3、子树上所有结点的值。现采用( )遍历方式就可以得到这棵二叉树所有结点的递减序列。 A前序 B中序 C后序 D层次10如图6-1所示的二叉树的中序遍历序列是( )。 Aabcdgef Bdfebagc Cdbaefcg Ddefbagc11已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc，它的前序遍历序列是( )。 Aacbed Bbaedc Cdceab Dcedba12某二叉树的前序遍历的结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是( )。 Abdgcefha Bgdbecfha Cbdgechfa Dgdbehfca
4、13在图6-2中的二叉树中，( c )不是完全二叉树。14树最适合用来表达( )。 A有序数据元素 B无序数据元素 C元素之间具有分支层次关系的数据 D元素之间无联系的数据15哈夫曼树的带权途径长度是( )。A所有结点权值之和 B所有叶结点带权途径长度之和 C带权结点的值 D除根以外所有结点权值之和16设有一棵22个结点的完全二叉树，那么整棵二叉树有( )个度为0的结点。 A6 B7 C8 D1117已知完全二叉树有26个结点，则整棵二叉树有( )个度为1的结点。 A0 B1 C2 D1318 已知如图6-3所示的哈夫曼树，那么电文CDAA的编码是( )。 A110100 B11011100
5、C D1111110019在n个结点的完全二叉树中，对任一结点i(1in)，i的左孩子也许是( )。 Ai/2 B2i+1 C2i D都不是20已给出图6-3所示的二叉树，A，B，C，D的权值分别为7，5，2，4，则该树的带权途径长度为( )。 A46 B36 C35 D都不是21下列论述中对的的是( )。 A二叉树是度为2的有序树 B二叉树中结点只有一种孩子时无左右之分 C二叉树中必有度为2的结点 D二叉树中结点最多有两棵子树，并且有左右之分22图6-4所示的几种构造中属于树形构造的是( b)。二、判断题（标红色的是错误的）2树和二叉树之间最重要的差别是：二叉树的结点的子树要辨别为左右子树，
6、虽然在结点只有一棵子树的状况下也要明确指出该子树是左子树还是右子树。3若有一种结点是某二叉树子树的中序遍历序列中的最后一种结点，则它必须是该子树的前序遍历序列中的最后一种结点。4二叉树具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一种子女。5在二叉树中，具有一种子女的父结点，在中序遍历中，它没有后继的子女结点。6已知二叉树的前序遍历和后序遍历序列不能惟一地拟定这棵树。三、填空题1树(及一切树形构造)是一种_分支层次_构造。在树中，_根_结点没有直接前驱。对树上任一结点x来说，x是它的任一子树的根结点惟一的_双亲_。2一棵树上的任何结点(不涉及根自身)称为根的_子孙_。若B是A的
7、子孙，则称A是B的_祖先_。3二叉树第i(i0)层上至多有_2i-1_个结点。4深度为k(k0)的二叉树至多有_2k-1_个结点。5对任何二叉树，若度为2的节点数为n2，则叶子数n0=_n2+1_。6满二叉树上各层的节点数已达到了二叉树可以容纳的_最大值_。满二叉树也是_完全_二叉树，但反之否则。7具有n个结点的完全二叉树的深度为_log2n 取整+1_。8二叉树一般有_顺序_存储构造和_链式_存储构造两类存储构造。9每个二叉链表还必须有一种指向_根_结点的指针，该指针具有标记二叉链表的作用。10对二叉链表的访问只能从_根_指针开始。11二叉树有不同的链式存储构造，其中最常用的是_二叉链表_与
8、_三叉链表_。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，10，试为这8个字母设计相应的哈夫曼编码。答：略.8对于一种核心字序列10, 18, 3, 8, 12, 2, 7, 3，生成一种二叉排序树，并写出中序遍历该二叉排序树的成果。答：略.
