树与二叉树复习一、填空1、由二叉树的（中）序和（前、后）序遍历序列可以唯一确定一棵二叉树。
2、任意一棵二叉树，若度为0的结点个数为n0，度为2的结点个数为n2，则n0等于（n0=n2+1 ）。
3、一棵二叉树的第i（i≥1）层最多有（2i-1 ）个结点。
4、一棵有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点个数n1=（n-2n0+1 ）。
5、在一棵高度为5的完全二叉树中，最少含有（ 16 ）个结点。
6、 2．有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查找值为82的结点时，（ C ）次比较后查找成功。
A． 11 B 5 C 4 D 87、在有n个叶结点的哈夫曼树中，总结点数（ 2n-1 ）。
8、若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用（递推）算法，因为（递推算法效率高）。
9、设一棵完全二叉树有700个结点，则共有（ 350 ）叶子结点。
10、设一棵完全二叉树具有1000个结点，该树有（500）个叶子结点，有（499 ）个度为2的结点，有（ 1 ）个结点只有非空左子树。
二、判断1、( × )在哈夫曼树中，权值最小的结点离根结点最近。
2、( √ ) 完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。
3、( √ )二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。
4、( × ) 若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最大值一定在叶结点上。
5、( √ )若以二叉链表作为树和二叉树的存储结构，则给定任一棵树都可以找到唯一的一棵二叉树与之对应。
6、( √ )若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最小值一定在叶结点上。
三、选择1、树最适合用来表示( C )A 、有序数据元素B 、无序数据元素C 、元素之间具有分支层次关系的数据D 、元素之间无联系的数据2、在有n （n>0）个结点的二叉链表中，空链域的个数为( B )。
A 、nB 、n+1C 、n-1D 、不确定3、 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为( A )。
A 、CBEFDAB 、FEDCBAC 、CBEDFAD 、不定4、对于有n 个结点的完全二叉树, 其高度为( C )A 、nlog2nB 、log2nC 、⎣log2n ⎦+1D 、不确定5、在有n 个结点的二叉链表中，值为非空的链域的个数为（ A ）A 、n-1B 、2n-1C 、n+1D 、2n+16、将一棵有100个结点的完全二叉树从根开始编号，每层上从左到右依次对结点进行编号，跟结点的编号为1，则编号为49A 、98 B 、99 C 、50 D 、48、7、设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (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/EC 、 –+*ABC/DED 、–+A*BC/DE9、堆的形状是一棵（ Ｃ ）Ａ. 二叉排序树 Ｂ.满二叉树 Ｃ.完全二叉树 Ｄ. 平衡二叉树10、若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为（Ｂ）。
Ａ. 79, 46, 56, 38, 40, 84 Ｂ. 84, 79, 56, 38, 40, 46Ｃ. 84, 79, 56, 46, 40, 38 Ｄ. 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，24，18，65，33，56，33，92，86，7013、下面编码中哪一个不是前缀码（ B ）。
A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）11、在解决递归问题时，若不用递归函数就应借助于数据结构（ B ）。
A、线性表B、栈C、队列D、双向队列14、一棵完全二叉树的第6层有8个叶结点，该二叉树的结点个数最多是（ 111 ）。
15、在分量1~11的数组中按从小到大顺序存放11个元素，如果进行二分查找，查找次数最少的元素位于什么位置？A.1B.5C.6D.1116、如果一个完全二叉树最底下一层为第六层（根为第一层）且该层共有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 你选对了20、已知一二叉树的后序和中序遍历的结果分别是FDEBGCA 和FDBEACG,那么该二叉树的前序遍历结果是什么？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.524、25、在最大堆 {97,76,65,50,49,13,27}中插入83后，该最大堆为：A.{97,76,65,83,49,13,27,50}B.{97,83,65,76,49,13,27,50}C.{97,83,65,76,50,13,27,49}D.{97,83,65,76,49,50,13,27}26、下列序列中哪个是最小堆？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个整数构成的二叉搜索树（查找树）和最小堆，下面哪个说法是不正确的: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.000，001，01，10，11C.0000，0001，001，01，1D.000，001，010，011，130、如果哈夫曼树有67个结点，则可知叶结点总数为：A.22B.33C.34D.不确定四、应用1、设一正文所用的字符集为X＝{x1,x2,x3,x4,x5,x6,x7}，各字符在正文中出现的频率分别为2,3,4,6,8,11,12。
请用哈夫曼算法为这个字符集设计一套二进制编码，使正文中字符的二进制内部表示最短。
要求：(1)画出对应的哈夫曼树；(2)给出X中各字符的编码表；(3)以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 e s u g b j a k r i构成二叉搜索树，然后删除j。
4、试画出从空树开始，由字符序列{e,f,p,k,m,l,b}构成的AVL二叉平衡树，为每次平衡处理指明旋转类型。