已知某二叉树的先序遍历和中序遍历的结果是先序遍历ABDEGCF

1、树与二叉树复习一、填空1、由二叉树的( 中 )序和( 前、后 )序遍历序列可以唯一确定一棵二叉树。2、任意一棵二叉树，假设度为0的结点个数为nO,度为2的结点个数为n2,那么n0 等于( n0=n2+1 )。3、 一棵二叉树的第i (i 1)层最多有(2i-1 )个结点。4、 一棵有n个结点的二叉树，假设它有nO个叶子结点，那么该二叉树上度为1的结点 个数 n1= (n-2nO+1 )。5、在一棵高度为 5的完全二叉树中，最少含有( 16 )个结点。6 2 有一个有序表为 1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100, 当折半查找值为 82

2、的结点时，( C )次比拟后查找成功。A 11B 5C 4D 87、在有 n 个叶结点的哈夫曼树中,总结点数( 2n-1)。8、假设一个问题的求解既可以用递归算法, 也可以用递推算法, 那么往往用 (递推 ) 算法,因为 (递推算法效率高 )。9、设一棵完全二叉树有 700 个结点,那么共有( 350 )叶子结点。10、设一棵完全二叉树具有 1000个结点,该树有( 500)个叶子结点,有( 499)个度为 2 的结点,有( 1 )个结点只有非空左子树。二、判断1、( x )在哈夫曼树中，权值最小的结点离根结点最近。2、( V )完全二叉树中，假设一个结点没有左孩子，那么它必是叶子结点。3、(

3、 V )二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。4、( x ) 假设一搜索树(查找树)是一个有 n 个结点的完全二叉树,那么该树的最 大值一定在叶结点上。5、( V ) 假设以二叉链表作为树和二叉树的存储结构, 那么给定任一棵树都可以找到 唯一的一棵二叉树与之对应。6、( V ) 假设一搜索树 (查找树) 是一个有 n 个结点的完全二叉树, 那么该树的最小值一定在叶结点上。三、选择1、树最适合用来表示C A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据2、 在有n n0个结点的二叉链表中，空链域的个数为B 。A、nB 、n+1C 、

4、n-1D、不确定3、一棵二叉树的前序遍历结果为 ABCDEF中序遍历结果为CBAEDR那么后序遍历 的结果为A。A、CBEFDAB 、FEDCBAC、 CBEDFAD 、不定4、对于有n个结点的完全二叉树，其高度为C A、nlog2nB、Iog2nC、og2n +1D 、不确定5、在有n个结点的二叉链表中，值为非空的链域的个数为A )A、n-1 B 、2n-1 C 、n+1 D、2n+16将一棵有100个结点的完全二叉树从根开始编号，每层上从左到右依次对结点进 行编号，跟结点的编号为1,那么编号为49的结点的左孩子编A、98 B、99 C 、50 D 、48、7、 设有一表示算术表达式的二叉树

5、见以下图，它所表示的算术表达式是C A. A*B+C/D*E+F-G B. A*B+C/D*E+F-GC. A*B+C/D*E+ F-G D. A*B+C/D*E+F-G8、 一算术表达式的中缀形式为 A+ B *C- D/E,后缀形式为ABC*+DE/ -,其前 缀形式为D 。A、- A+B*C/DEB 、- A+B*CD/E C、- +*ABC/DE D、- +A*BC/DE9、堆的形状是一棵C A. 二叉排序树 B .满二叉树 C .完全二叉树 D .平衡二叉树10、假设一组记录的排序码为46, 79, 56, 38, 40, 84，那么利用堆排序的方法建立的初始堆为B 0A. 79,

6、46, 56, 38, 40, 84B . 84, 79, 56, 38, 40, 46C . 84, 79, 56, 46, 40, 38D. 84, 56, 79, 40, 46, 3811查找效率最高的二叉排序树是 C 。A. 所有结点的左子树都为空的二叉排序树。B. 所有结点的右子树都为空的二叉排序树。C. 平衡二叉树。D. 没有左子树的二叉排序树。12.判断序列是否为堆小根堆或大根堆如果不是，将其调整为堆17，18，60，40，7， 32， 73， 6596，83，72，45，28， 54， 60， 23，38，1525，48，16，35，79， 82， 23， 40，36，7212

7、，24，18，65，33， 56， 33， 92，86，7013、下面编码中哪一个不是前缀码B。A.(00，01，10，11)B.(0，1， 00，11C.(0，10，110，111)D.(1，01， 000， 001)11、在解决递归问题时，假设不用递归函数就应借助于数据结构B 。A、线性表 B 、栈 C 、队列 D 、双向队列14、一棵完全二叉树的第 6层有 8个叶结点，该二叉树的结点个数最多是 111 。15、在分量 111的数组中按从小到大顺序存放 11 个元素，如果进行二分查找，查 找次数最少的元素位于什么位置？A. 1B.5C.6D.1116、 如果一个完全二叉树最底下一层为第六层

8、根为第一层且该层共有8 个叶结 点，那么该完全二叉树共有多少个结点？A.31B.39C.63D.7117、假设有一二叉树的总结点数为 98，只有一个儿子的结点数为 48，那么该树的叶结点 数是多少？A.25B.50C.不确定D.这样的树不存在18、假定只有四个结点 A、B C D的二叉树，其前序遍历序列为 ABCD那么下面哪 个序列是不可能的中序遍历序列？A. ABCDB. ACDBC. DCBAD. DABC19、对于二叉树，如果其中序遍历结果与前序遍历结果一样，那么可以断定该二叉树A. 是完全二叉树B. 所有结点都没有左儿子C. 所有结点都没有右儿子D. 这样的树不存在正确答案：B你选对了

9、20、一二叉树的后序和中序遍历的结果分别是FDEBGC和FDBEACGF么该二叉树的前序遍历结果是什么？A.ABDFECGB. ABDEFCGC. ABDFEGCD. ABCDEFG21、一棵由1、2、3、4、5、6 7共7个结点组成的二叉搜索树查找树，其 结构如下图，问：根结点是什么？A.1B. 4C. 5D. 不能确定22、在上题的搜索树中删除结点1,那么删除后该搜索树的后序遍历结果是:A.243765B. 432765C. 234567D. 76543223、将1、2、3、4、5、6顺序插入初始为空的AVL树中，当完成这6个元素的插入 后，该AVL树共有多少层？A.2B.3C.4D.52

10、4、25、在最大堆97,76,65,50,49,13,27 中插入83后，该最大堆为：A. 97,76,65,83,49,13,27,50B. 97,83,65,76,49,13,27,50C. 97,83,65,76,50,13,27,49D. 97,83,65,76,49,50,13,2726、以下序列中哪个是最小堆？A.2, 55, 52, 72, 28, 98, 71B. 2, 28, 71, 72, 55, 98, 52C. 2, 28, 52, 72, 55, 98, 71D. 28, 2, 71, 72, 55, 98, 5227、对由同样的 n 个整数构成的二叉搜索树(查找树)

11、和最小堆，下面哪个说法是 不正确的 :A. 二叉搜索树(查找树)高度大于等于最小堆高度B. 对该二叉搜索树(查找树)进行中序遍历可得到从小到大的序列C. 从最小堆根节点到其任何叶结点的路径上的结点值构成从小到大的序列D. 对该最小堆进行按层序( level order )遍历可得到从小到大的序列28、一段文本中包含对象 a,b,c,d,e ，其出现次数相应为 3,2,4,2,1 ，那么经过哈 夫曼编码后，该文本所占总位数为：A.12B.27C.36D.以上都不是29、为五个使用频率不同的字符设计哈夫曼编码，以下方案中哪个不可能是哈夫曼 编码？A. 00，100，101，110，111B. 00

12、0，001，01，10，11C. 0000，0001，001，01，1D. 000，001，010，011，130、如果哈夫曼树有 67 个结点，那么可知叶结点总数为：A.22B.33C.34 D.不确定四、应用1、设一正文所用的字符集为 X=x1,x2,x3,x4,x5,x6,x7,各字符在正文中出现的频率分别为 2,3,4,6,8,11,12 。请用哈夫曼算法为这个字符集设计一套二进制编码， 使正文中字符的二进制内部表示最短。要求：(1) 画出对应的哈夫曼树；(2) 给出X中各字符的编码表； 以X中各字符出现的频度为权，计算其带权路径的长度。2设有序顺序表中的元素依次为 017, 094, 154, 170, 275,503, 509, 512, 553,612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。折半搜索时的判定树：ASLsucc=1/14 (1+2*2+3*4+4*7) =45/14ASLunsucc=1/15 (4*1+5*14) =74/153、试画出从空树开始，由字符序列t d