作业树和叉树.docVIP

树 (树根结点的高度为1) 一、选择题 3．以下说法错误的是( )。 A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B．在三叉链表上，二叉树的求双亲操作很容易实现 C．在二叉链表上，求根以及求左、右孩子等操作很容易实现 D．在二叉链表上，求双亲操作的时间性能很好 4．以下说法错误的是( )。 A．一般在哈夫曼树中，权值越大的叶子离根结点越近 B．哈夫曼树中没有度数为1的分支结点 C．若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点 D．若初始森林中共有n棵二叉树， 进行2n-1次合并后才能剩下一棵最终的哈夫曼树 5．深度为6的二叉树最多有( )个结点。 A．64 B．63 C．32 D．31 6．将含有41个结点的完全二叉树从根结点开始编号，根为1号， 后面按从上到下、从左到右的顺序对结点编号， 那么编号为21的双亲结点编号为( )。 A．10 B．11 C．41 D．20 7．设深度为k的二叉树上只有度为0和度为2的结点， 则这类二叉树上所含结点总数最少( )个。 A．k+l B．2k C．2k-1 D．2k+1 8．下列说法中正确的是( )。 A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的每个结点的度肯定等于2 D．任何一棵二叉树中的每个结点的度都可以小于2 9．一棵二叉树满足下列条件：对任意结点，若存在左、右子树， 则其值都小于它的左子树上所有结点的值， 而大于右子树上所有结点的值。 现采用( )遍历方式就可以得到这棵二叉树所有结点的递减序列。 A．前序 B．中序 C．后序 D．层次 10．如图6-1所示的二叉树的中序遍历序列是( )。 A．abcdgef B．dfebagc C．dbaefcg D．defbagc 11．已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc， 它的前序遍历序列是( )。 A．acbed B．baedc C．dceab D．cedba 12．某二叉树的前序遍历的结点访问顺序是abdgcefh， 中序遍历的结点访问顺序是dgbaechf， 则其后序遍历的结点访问顺序是( )。 A．bdgcefha B．gdbecfha C．bdgechfa D．gdbehfca 13．在图6-2中的二叉树中，( c )不是完全二叉树。 14．树最适合用来表示( )。 A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 15．哈夫曼树的带权路径长度是( )。 A．所有结点权值之和 B．所有叶结点带权路径长度之和 C．带权结点的值 D．除根以外所有结点权值之和 16．设有一棵22个结点的完全二叉树， 那么整棵二叉树有( )个度为0的结点。 A．6 B．7 C．8 D．11 17．已知完全二叉树有26个结点，则整棵二叉树有( )个度为1的结点。 A．0 B．1 C．2 D．13 18． 已知如图6-3所示的哈夫曼树，那么电文CDAA的编码是( )。 A．110100 B C．010110111 D 19．在n个结点的完全二叉树中，对任一结点i(1≤i≤n)， i的左孩子可能是( )。 A．i/2 B．2i+1 C．2i D．都不是 20．已给出图6-3所示的二叉树， A，B，C，D的权值分别为7，5，2，4， 则该树的带权路径长度为( )。 A．46 B．36 C．35 D．都不是 21．下列叙述中正确的是( )。 A．二叉树是度为2的有序树 B．二叉树中结点只有一个孩子时无左右之分 C．二叉树中必有度为2的结点 D．二叉树中结点最多有两棵子树，并且有左右之分 22．图6-4所示的几种结构中属于树形结构的是( b)。 二、判断题（标红色的是错误的） 2．树和二叉树之间最主要的差别是： 二叉树的结点的子树要区分为左右子树， 即使在结点只有一棵子树的情况下 也要明确指出该子树是左子树还是右子树。 3．若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点， 则它必须是该子树的前序遍历序列中的最后一个结点。 4．二叉树具有两个子女的父结点，在中序遍历序列中， 它的后继结点最多