搜索
单元练习7一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）树结构中每个结点最多只有一个直接前驱。（ㄨ）（2）完全二叉树一定是满二查树。（ㄨ）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。（√）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。（√）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。（√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。（√）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。（ㄨ）（8）在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。（ㄨ）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。（√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。二．填空题（1）在树中，一个结点所拥有的子树数称为该结点的度。（2）度为零的结点称为叶（或叶子，或终端）结点。（3）树中结点的最大层次称为树的深度（或高度）。（4）对于二叉树来说，第i层上至多有2i-1个结点。（5）深度为h的二叉树至多有2h-1个结点。（6）由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。（7）有20个结点的完全二叉树，编号为10的结点的父结点的编号是5。（8）哈夫曼树是带权路径长度最小的二叉树。（9）由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。（10）某二叉树的中序遍历序列为:DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为：DABEC。（11）设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是：E、F、H。（12）已知完全二叉树的第8层有8个结点，则其叶结点数是68。（13）由树转换成二叉树时，其根结点无右子树。（14）采用二叉链表存储的n个结点的二叉树，一共有2n个指针域。（15）采用二叉链表存储的n个结点的二叉树，共有空指针n+1个。（16）前序为A，B，C且后序为C，B，A的二叉树共有4种。ACBABCABCACB（17）三个结点可以组成2种不同形态的树。（18）将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为：2*i。（19）给定如下图所示的二叉树，其前序遍历序列为：ABEFHCG。（20）给定如下图所示的二叉树，其层次遍历序列为：ABCEFGH。三．选择题（1）树最适合用来表示（D）。A．有序数据元素B．无序数据元素C．元素之间无联系的数据D．元素之间有分支的层次关系（2）前序为A，B，C的二叉树共有（D）种。A．2B．3C．4D．5（3）根据二叉树的定义，具有3个结点的二叉树有（C）种树型。A．3B．4C．5D．6（4）在一棵具有五层的满二叉树中，结点的总数为（B）A．16B．31C．32D．33（5）具有64个结点的完全二叉树的深度为（C）A．5B．6C．7D．8（6）任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（A）。A．不发生改变B．发生改变C．不能确定D．以上都不对ABFGHDCEABFGHDCE（7）A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（C）。A．A在B右方B．A是B祖先C．A在B左方D．A是B子孙（8）下列4棵树中，（B）不是完全二叉树。A．B．C．D．（9）如右图所示的二叉树，后序遍历的序列是（D）A．A、B、C、D、E、F、G、H、IB．A、B、D、H、I、E、C、F、GC．H、D、I、B、E、A、F、C、GD．H、I、D、E、B、F、G、C、A（10）对于下边的二叉树，其中序序列为（A）A．DBEHAFCGB．DBHEAFCGC．ABDEHCFGD．ABCDEFGHBDEHCFGA（11）某二叉树的后序遍历序列为：DABEC，中序遍历序列为:DEBAC，则前序遍历序列为（D）。A．ACBEDB．DECABC．DEABCD．CEDBA（12）具有n（n1）个结点的完全二叉树中，结点i（2in）的左孩子结点是（D）。A．2iB．2i+1C．2i-1D．不存在（若2i=n，则答案为A）（13）把一棵树转换为二叉树后，这棵二叉树的形态是（A）。A．唯一的B．有多种C．有多种，但根结点都没有左孩子D．有多种，但根结点都没有右孩子（14）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（B）。A．46B．47C．90D．91ABEGFDCDABEFCDABECDABCDABADECFGHI（15）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子编号为（B）。A．98B．99C．50D．100（16）二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法（B）。A．正确B．错误C．不确定D．都有可能（17）下列陈述正确的是（D）。A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，且有左右子树之分（18）用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是（B）。Ａ．32Ｂ．33Ｃ．34Ｄ．15（先构造哈夫曼树，WPL=（1+2）*3+（3+4+5）*2=33）（19）在树结构中，若结点B有4个兄弟，A是B的父亲结点，则A的度为为（C）。A．3B．4C．5D．6（20）二叉树的叶结点个数比度为2的结点的个数（C）。A．无关B．相等C．多一个D．少一个四.简答题1．已知一棵树边的集合如下，请画出此树，并回答问题。{(L,M),(L,N),(E,L),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(H,I),(C,H),(A,C)}（1）哪个是根结点？（2）哪些是叶结点？（3）哪个是G的双亲？（4）哪些是G的祖先？（5）哪些是G的孩子？（6）哪些是E的子孙？（7）哪些是E的兄弟？哪些是F的兄弟？（8）结点B和N的层次各是多少？（9）树的深度是多少？（10）以结点C为根的子树的深度是多少？（11）树的度数是多少？答：（1）A是根结点。（2）叶结点：M，N，D，J，K，F，I。（3）G的双亲：C。（4）G的祖先：A，C。（5）G的孩子：J，K。（6）E的子孙：L，M，N。（7）E的兄弟：D；F的兄弟：G，H。（8）结点B的层次为2；结点N的层次是5。（9）树的深度是5。（10）以结点C为根的子树的深度是3。（11）树的度数是3。2．设下列二叉树是与某森林对应的二叉树，试回答下列问题。（1）森林中有几棵树？（2）每一棵树的根结点分别是什么？（3）第一棵树有几个结点？（4）第二棵树有几个结点？（5）森林中有几个叶结点？解：（1）4（2）A，C，G，K（3）6（4）2（5）73．二叉树按中序遍历的结果为：ABC，试问有几种不同形态的二叉树可以得到这一遍历结果？并画出这些二叉树。答：（1）5种。（2）4.分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。答：（1）三个结点的树（2）三个结点的二叉树树DABEGICFHJLKABCAADCBBABCACCB五.应用题1．已知一棵二叉树的后序遍历和中序遍历的序列分别为：A，C，D，B，G，I，H，F，E和A，B，C，D，E，F，G，H，I。请画出该二叉树，并写出它的前序遍历的序列。答：恢复的二叉树为：其前序遍历的序列为：EBADCFHGI2．已知一棵二叉树的前序遍历和中序遍历的序列分别为：A，B，D，G，H，C，E，F，I和G，D，H，B，A，E，C，I，F。请画出此二叉树，并写出它的后序遍历的序列。。答：恢复的二叉树为：其后序遍历的序列为：GHDBEIFCA3．已知一棵树的层次遍历的序列为：ABCDEFGHIJ，中序遍历的序列为：DBGEHJACIF，请画出该二叉树，并写出它的后序遍历的序列。解：后序遍历的序列：DGJHEBIFCABCHDDFGEIAGHABDCEFIABCHDDFGEIJ4.把下列一般树转换为二叉树(1)(2)解：（1）（2）5.把下列森林转换为二叉树解：12435678ABFEGHIJCDACBDEKIJHFGABCHDDFGEIJ124688D537KABCHDDFGEIJ6．把下列二叉树还原为森林解：还原后的二叉树为：7．某二叉树的结点数据采用顺序存储，其结构如下：1234567891011121314151617181920EAFDHCGIB（1）画出该二叉树（3分）（2）写出按层次遍历的结点序列（2分）解：（1）（2）层次遍历的结点序列：EAFDHCGIB8．某二叉树的存储如下：12345678910lchild00237580101dataJHFDBACEGIrchild0009400000ADBICHFGEADHFGECBIABCHDDFGEI其中根结点的指针为6，lchild、rchild分别为结点的左、右孩子的指针域，data为数据域。（1）画出该二叉树（3分）（2）写出该树的前序遍历的结点序列（2分）解：（1）（2）前序遍历的结点序列：ABCEDFHGIJ9．给定如图所示二叉树T，请画出与其对应的中序线索二叉树。解：（1）中序遍历序列：5540256028083354（2）中序线索二叉树：10.画出表达式：-A+B-C+D的标识符树，并求它们的后缀表达式。330828D25D33D40D60D08D54D55DBDJHGACFEINULLNULL0828D25D33D40D60D08D54D55D解：后缀表达式：0A–B+C–D+11．画出表达式：（A+B/C-D）*（E*（F+G））的标识符树，并求它们的后缀表达式。解：后缀表达式：ABC/+D–EFG+**12．对于算术表达式（A+B*C/D）*E+F*G，画出标识符树，并求它们的后缀表达式。解：后缀表达式：ABCD/*+E*FG*++¯+¯BDCAD0ABC+DDFGE/+*¯**EGFD*B++*AD/C13．给定一个权集W={4，5，7，8，6，12，18}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。解：45678121891317253560WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=15914．给定一个权集W={3，15，17，14，6，16，9，2}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。解2369141516175293311204982WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=22915．假设用于通信的电文仅由A、B、C、D、E、F、G8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。解：以权值：2、3、6、7、10、19、21、32构造哈夫曼树：351325D12660181798D457491733D1698229201514D56113D2651911281740D213260D10000D023D710D0000011111101字母编号对应编码出现频率A10107B0019C100002D10016E1132D100013E0121F101110六．算法设计题以二叉链表为存储结构，设二叉树BT结构为：typedefstructBT{chardata;BT*lchild;BT*rchild;}BT;1．求二叉树中的度数为2的结点。2．求二叉树中值为最大的元素。3．将二叉树各结点存储到一维数组中。4．前序输出二叉树中各结点及其结点所在的层号。5．求二叉树的宽度6．交换二叉树各结点的左右子树。7．写出在二叉树中查找值为x的结点在树中层数的算法。解：1．求二叉树中的度数为2的结点。voidcount(BTt){if(t){if(t-lchild&&t-rchild)k++;count(t-lchild);count(t-rchild)