数据结构树和二叉树练习及答案.doc

《数据结构树和二叉树练习及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、选择题1、设T是一棵树，T’是对应于x的二叉树，则T的先根次序遍历和T’的（）次序遍历相同。A、先根B、中根C、后根D、以上都不是2、3、若二叉树的后序遍历序列为dabec，中序遍历序列为debac，则前序序列遍历为（）。A、acbedB、decabC、deabcD、cedba4、具有35个结点的完全二叉树的深度为（）A、5B、6C、7D、85、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子结点编号为（）A、98B、99C、50D、486、某二叉树

2、的前序和后序序列正好相反，则该二叉树一定是（）的二叉树。A、空或只有一个结点B、高度等于其结点数C、任一结点无左孩子D、任一结点无左孩子7、二叉树在线索化后，仍不能有效求解的问题是（）A、先根线索二叉树中求先根后继B、中根线索二叉树中求中根后继C、中根线索二叉树中求中根前驱D、后根线索二叉树中求后根后继8、在线索化二叉树中，t所指结点没有左子树的充足条件是（）A、t-lchild==NULLB、t->ltag==1C、t->ltag==1&&t->lchild==NULLD、以上都不对9、设高度为h的二叉树上只有度为0

3、和度为2的结点，则此类二叉树中所包含的结点数至少为（）A、2hB、2h-1C、2h+1D、h+110、深度为5的二叉树至多有（）个结点。A、16B、32C、31D、1011、在一非空二叉树的中序遍历序列中，根结点的右边（）A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的所有结点D、只有左子树上的部分结点12、树最适合用来表示（）A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据13、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A、不发生改

4、变B、发生改变C、不能确定D、以上都不对14、设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（）A、n在m右方B、n是m祖先C、n在m左方D、n是m子孙15、线索二叉树是一种（）结构A、逻辑B、逻辑和存储C、物理D、线性16、森林的后根遍历序列与其对应二叉树的（）遍历序列一致。A、先根B、后根C、中根D、不可能二、填空题1、由一棵二叉树后序序列和（中序）可唯一确定这棵二叉树。2、含有n个结点的二叉树用二叉链表表示时，有（N+1）个空链域。3、有m个叶子结点的哈夫曼树有（2*M-1）个结点。4、前序为a

5、,b,c且后序c,b,a的二叉树共有（4）棵。5、已知完全二叉树的第4层有6个结点，则其叶子结点数是（7）。6、已知二叉树有31个叶子结点，且仅有一个孩子的结点数为40，则总结点数为（101）。7、树和二叉树的两个主要差别是（二叉树是有序树）和（二叉树的度最大为2）。8、从概念上讲，树与二叉树是两种不同的数据结构，将树转化成二叉树的基本目的是（通过与树对应的二叉树的操作来实现树的操作）。9、深度为k的完全二叉树至少有（2k-1）个结点，至多有（2k-1）个结点，若按自上而下，从左至右的次序给结点编号从1开始，则编号最小

6、的叶子结点的编号是（2k-1）。10、结点最少的树为（空树），结点最少的二叉树是（空二叉树）。12、以数据集（4，5，6，7，10，12，18）为结点权值的Huffman树的带权路径长度为（168）。（可画出图形）