练习题 _树和二叉树

《练习题 _树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六、七章的练习题一、选择题1．任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。A．不发生改变B．发生改变C．不能确定D．以上都不对2．设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（）。A．n在m右方B．n是m的祖先C．n在m的左方D．n是m的子孙3．具有33个结点的完全二叉树的深度为（），有（）个叶子结点，有（）个度为1的结点。（1）A．5B．6C．7D．8（2）A．14B．15C．16D．17（3）A．0B．1C．12D．164．已知一棵二叉树有50个叶子结点，30个度为1的结点，则该二叉树的总

2、结点数为（）。A．129B．130C．131D．1325．设森林有三棵树组成，第一、第二和第三棵树中的结点个数分别为m1、m2和m3。那么在由该森林转化成的二叉树中根结点的右子树上的结点个数是（）。A．m1+m2B．m2+m3C．m1+m3D．m1+m2+m36．用n个权值构造出来的哈夫曼树的结点个数是（）。A．2n-1B．2nC．2n+1D．n+17．在下列关于二驻树遍历的说法中错误的是（）。A．在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行先序遍历和后序遍历将得到相同的结点序列；B．在一棵二叉树中，假定每个结点最

3、多只有左子女，没有右子女，对它分别进行中序遍历和后序遍历将得到相同的结点序列；C．在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行先序遍历和层次遍历将得到相同的结点序列；D．在一棵二叉树中，假定每个结点最多只有右子女，没有左子女，对它分别进行先序遍历和中序遍历将得到相同的结点序列；8．在下列关于二叉树遍历的说法中正确的是（）。A．若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的先序遍历结果序列的最后一个结点；B．若有一个结点是二叉树中某个子树的先序遍历结果序列的最后一个结点，则它一定是

4、该子树的中序遍历结果序列的最后一个结点；C．若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的先序遍历结果序列的最后一个结点；D．若有一个叶子结点是二叉树中某个子树的先序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点；9．先序为A、B、C，后序为C、B、A的二叉树共有（）个。A．1B．2C．3D．410．设结点x和y是二叉树中任意的两个结点。在该二叉树的先序遍历序列中x在y之前，而在后序遍历序列中x在y之后，则x和y的关系是（）。A．x是y的左兄弟B．x是y的右兄弟C．x是

5、y的祖先D．x是y的子孙11．设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶子结点，则B中右指针域为空的结点个数是（）。A．n-1B．nC．n+1D．n+212．若设一棵树具有n个结点，则它所有结点的度数之和为（）。设森林F对应的二叉树为B，它有m个结点。B的根为p，p的右子树中结点个数为n，则森林F中第一棵树的结点个数是（）。如果T2是由树T转换成的二叉树，那么T中结点的后序遍历顺序对应T2中结点的（）遍历顺序。（1）A．2nB．2n-1C．n+1D．n-1（2）A．m-nB．m-n-1C．n+1D．无法确定（3）A．先序B．

6、中序C．后序D．层次13．下列关于哈夫曼树的说法中不正确的是（）。A．对应一组权值构造出来的哈夫曼树一般不是唯一的；B．哈夫曼树具最小的带权路径长度；C．哈夫曼树中没有度为1的结点；D．哈夫曼树中除了有度为1的结点之外，还有度为2的结点和叶子结点14．树最适合用来表示（）。A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据15．在线索二叉树中，T所指结点没有左子树的充要条件是（）。A．T->lchild==NULLB．T->ltag==1C．T->ltag==1且T->lchild==NULLD．以

7、上都不对16．在一非空二叉树的中序遍历序列中，根结点的右边是（）。A．只有右子树上的所有结点B．只有右子树上的部分结点C．只有左子树上的部分结点D．只有左子树上的所有结点17．根据使用频率为5个字符设计的哈夫曼编码不可能是（）。A．111，110，10，01，00B．000，001，010，011，1C．100，11，10，1，0D．001，000，01，11，1018．根据使用频率为5个字符设计的哈夫曼编码不可能是（）。A．000，001，010，011，1B．0000，0001，001，01，1C．000，001，01，10，11D．

8、00，100，101，110，11119．已知一算术表达式的中缀表达式为a-(b+c/d)*e，其后缀形式为（）。A．-a+b*c/deB．-a+b*cd/eC．-+*abc/deD．abcd