《数据结构》习题集：第6章_树和二叉树

《《数据结构》习题集：第6章_树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课后练习题第6章树和二叉树第6章树和二叉树一、选择题1.有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是（B）A、向量B、树C、图D、二叉树2.树最适合用来表示（B）A、有序数据元素B、元素之间具有分支层次关系的数据C、无序数据元素D、元素之间无联系的数据3.树B的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（C）A、1a(2b(3d,3e),2c)B、a(b(D,e),c)C、a(b(d,e),c)D、a(b,d(e),c)4.对二叉树的结点从1开始连续编号

2、，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（C）次序的遍历实现二叉树的结点编号。A、先序B、中序C、后序D、从根开始按层次遍历5.按照二叉树的定义，具有3个结点的二叉树有（C）种。A、3B、4C、5D、66.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高度为（E）说明：1.标准答案为E或D。2.本意认为每个结点构成一层，而得出最大高度，但若成立则需n2=0,n0=1.此时，叶子结点数为1,第二空的答

3、案还应包含H.13.建议答案为：n2+n1+1，其叶结点数为（H）；树的最小高度为（B），其叶结点数为（G）；若采用链表存储结构，则有（I）个空链域。A、n/2B、+1C、log2nD、nE、n0+n1+n2F、n1+n2G、n2+1H、1I、n+1J、n1K、n2L、n1+17.对一棵满二叉树，m个树叶，n个结点，深度为h，则（D）A、n=m+hB、h+m=2nC、m=h-1D、n=2h-18.设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B），至多为（D）。A、2hB、2h-1C、2h

4、-1D、2h-19.在一棵二叉树上第5层的结点数最多为（B）（假设根结点的层数为1）A、8B、16C、15D、3210.深度为5的二叉树至多有（C）个结点。A、16B、32C、31D、1011.一棵有124个叶结点的完全二叉树，最多有（B）个结点A、247B、248C、249D、25012.含有129个叶子结点的完全二叉树，最少有（D）个结点A、254B、255C、256D、25713.假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（B）个。A、15B、16C、17D、4714.用顺序存储的方法将完

5、全二叉树中所有结点逐层存放在数组R[1…6/7北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1数据结构课后练习题第6章树和二叉树n]中，结点R[i]若有左子树，则左子树是结点（B）。A、R[2i+1]B、R[2i]C、R[i/2]D、R[2i-1]1.在一棵非空二叉树的中序遍历序列中，根结点的右边（A）。A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的所有结点D、只有左子树上的部分结点2.任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序（A）。A、不发生改变B、发生改变C、不

6、能确定D、以上都不对3.设n、m为一棵树上的两个结点，在中序遍历时，n在m前的条件是（C）。A、n在m右方B、n是m祖先C、n在m左方D、n是m子孙4.一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前驱为（D），后序遍历中结点B的直接后继是（E）。A、BB、DC、AD、IE、FF、C5.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（D）。A、acbedB、decabC、deabcD、cedba6.若二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子

7、树的位置，利用（C）遍历方法最合适。A、前序B、中序C、后序D、层次7.线索二叉树是一种（C）结构。A、逻辑B、逻辑和存储C、物理D、线性8.如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的（A）。A、前序B、中序C、后序D、层次序9.设T是哈夫曼树，具有5个叶结点，树T的高度最高可以是（E）。A、1B、2C、3D、4E、5F、610.由带权为8，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（D）。A、23B、37C、46D、4311.树的后根遍历序列等同于该树对应的二叉树的（B）。

8、A、先序遍历B、中序遍历C、后序遍历D、层次遍历12.以下说法错误的是（A）。A、树形结构的特点是一个结点可以有多个直接前趋B、线性结构中的一个结点至多只有一个直接后继C、二叉树与树是两种不同的数据结构D、树(及一切树形结构)是一种“分支层次”结构13.以下说法错误的是（C）。A、二叉树可