习题答案(word版)

《习题答案(word版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。A．-A+B*C/DEB．-A+B*CD/EC．-+*ABC/DED．-+A*BC/DE参考答案：D3．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。A．250B．500C．254D．505E．以上答案都不对参考答案：E8．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。A．4B．5C．6D．7参考答案：C10．具有10个叶结点的二叉树中有（）个度为2的结点。A．8B．9C．10D．11参考答案：B53．由3个结

2、点可以构造出（）种不同的二叉树。A．2B．3C．4D．5参考答案：D47．引入二叉线索树的目的是（）。A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一19．将如下由三棵树组成的森林转换为二叉树。NPGHJMOLIKEDFBAC参考答案：HGDACJIBFEMPONKOL反过来，将一个二叉树转化成森林或树？（注意：转化成森林的结果和转化成树的结果不一样）21．设某二叉树的前序遍历序列为ABCDEFGGI，中序遍历序列为BCAEDGHFI，试画出该二叉树。参考答案：AIDBECHFG27．设二叉树T的存储结构如

3、下：12345678910Lchild00237580101DataJHFDBACEGIRchild0009400000其中Lchild、Rchild分别为结点的左、右孩子指针域，Data为结点的数据域，若根指针T的值为6，试：(1)画出二叉树的逻辑结构；(2)写出按前序、中序、后序遍历该二叉树所得到的结点序列；(3)画出二叉树的后序线索树。参考答案：前序序列：ABCEDFHGIJ中序序列：ECBHFDJIGA后序序列：ECHFJIGDBA31．假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个

4、字母设计哈夫曼编码树。参考答案：各字母编码如下：c1:0110c2:10c3:0010c4:0111c5:000c6:010c7:11c8:0011注意虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。33．设T是一棵二叉树，除叶子结点外，其它结点的度皆为2，若T中有6个叶结点，试问：(1)树T的最大深度和最小可能深度分别是多少？(2)树T中共有多少非叶结点？(3)若叶结点的权值分别为1、2、3、4、5、6，请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。参考答案：(1)最大深度6，最小深度4；(2)非叶结点数5；(3)哈夫曼树见下图，其带权路径长度wpl=51。34．一

5、棵深度为Ｈ的满ｋ叉树有如下性质：第Ｈ层上的结点都是叶子结点，其余各层上每个结点都有ｋ棵非空子树。若按层次顺序从１开始对全部结点编号，问：(1)第ｉ层上有多少个结点？(2)编号为ｐ的结点的第ｉ个孩子结点（若存在）的编号是多少？(3)编号为ｐ的结点的双亲结点（若存在）的编号是多少？参考答案：(1)个(2)（１＋（ｐ－１）＊ｋ）＋ｉ(3)（ｐ≠１）】2．给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。参考答案：本题是将符号算术表达式用二叉树表示的逆问题，即将二叉树表示的表达式还原成原表达式。二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树表示中消除了括号

6、。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树（或右子树）根结点运算符时，就需要加括号。intPrecede(charoptr1,charoptr2)//比较运算符级别高低，optr1级别高于optr2时返回1，相等时返回0，低于时返回-1{switch(optr1){case‘+’:case‘-’:if(optr2==‘+’

7、

8、optr2==‘-’)return(0);elsereturn(-1);case‘*’:case‘/’:if(optr1==‘*’

9、

10、optr2==‘/’)return(0);elsereturn(1);}}voidInorderExp(B

11、iTreebt)//输出二叉树表示的算术表达式，设二叉树的数据域是运算符或变量名{intbracket;if(bt){if(bt->lchild!=null){bracket=Precede(bt->data,bt->lchild->data)//比较双亲与左子女运算符优先级if(bracket==1)printf(‘(’);InorderExp(bt->lchild);//输出左子女表示的算术表达式if(bracket==1)printf(‘)’);//加上右括号}