树(树根结点的高度为1)一、选择题3．以下说法错误的是()。A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B．在三叉链表上，二叉树的求双亲操作很容易实现C．在二叉链表上，求根以及求左、右孩子等操作很容易实现D．在二叉链表上，求双亲操作的时间性能很好4．以下说法错误的是()。A．一般在哈夫曼树中，权值越大的叶子离根结点越近B．哈夫曼树中没有度数为1的分支结点C．若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点D．若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树5．深度为6的二叉树最多有()个结点。A．64B．63C．32D．316．将含有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．defbagc11．已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc，它的前序遍历序列是()。A．acbedB．baedcC．dceabD．cedba12．某二叉树的前序遍历的结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是()。A．bdgcefhaB．gdbecfhaC．bdgechfaD．gdbehfca13．在图6-2中的二叉树中，(c)不是完全二叉树。14．树最适合用来表示()。A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据15．哈夫曼树的带权路径长度是()。A．所有结点权值之和B．所有叶结点带权路径长度之和C．带权结点的值D．除根以外所有结点权值之和16．设有一棵22个结点的完全二叉树，那么整棵二叉树有()个度为0的结点。A．6B．7C．8D．1117．已知完全二叉树有26个结点，则整棵二叉树有()个度为1的结点。A．0B．1C．2D．1318．已知如图6-3所示的哈夫曼树，那么电文CDAA的编码是()。A．110100B．11011100C．010110111D．1111110019．在n个结点的完全二叉树中，对任一结点i(1≤i≤n)，i的左孩子可能是()。A．i/2B．2i+1C．2iD．都不是20．已给出图6-3所示的二叉树，A，B，C，D的权值分别为7，5，2，4，则该树的带权路径长度为()。A．46B．36C．35D．都不是21．下列叙述中正确的是()。A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中结点最多有两棵子树，并且有左右之分22．图6-4所示的几种结构中属于树形结构的是(b)。二、判断题（标红色的是错误的）2．树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。3．若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必须是该子树的前序遍历序列中的最后一个结点。4．二叉树具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女。5．在二叉树中，具有一个子女的父结点，在中序遍历中，它没有后继的子女结点。6．已知二叉树的前序遍历和后序遍历序列不能惟一地确定这棵树。三、填空题1．树(及一切树形结构)是一种_分支层次_____结构。在树中，____根_____结点没有直接前驱。对树上任一结点x来说，x是它的任一子树的根结点惟一的___双亲_____。2．一棵树上的任何结点(不包括根本身)称为根的___子孙_______。若B是A的子孙，则称A是B的_____祖先_____。3．二叉树第i(i>0)层上至多有___2i-1_______个结点。4．深度为k(k>0)的二叉树至多有__...
