第6章 树和二叉树练习题及答案.doc

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

1、__________________________________________________一、判断题（√）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（×）2.二叉树中每个结点的两棵子树的高度差等于1。（√）3.二叉树中每个结点的两棵子树是有序的。（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。（×）5.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1）（×）6.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（×）7.对于一棵非空二叉树，它的根结点作为第一层，

2、则它的第i层上最多能有2i—1个结点。（应2i-1）（√）8.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（√）9.具有12个结点的完全二叉树有5个度为2的结点。(r)10、哈夫曼树中没有度为1的结点，所以必为满二叉树。(r)11、在哈夫曼树中，权值最小的结点离根结点最近。(r)12、线索二叉树是一种逻辑结构。（√）13、深度为K的完全二叉树至少有2K-1个结点。(√)14、具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。(√)15、前序和中序遍历用线索树方式存储的二叉树，不必使用栈。(╳)16、哈夫曼树

3、是带权路径长度最短的树，路径上权值较大的点离根较远。（√）17、在二叉树结点的先序序列和后序序列中，所有叶子结点的先后顺序完全相同。（√）18、二叉树的遍历操作实际上是将非线性结构线性化的过程（√）19、树的先根遍历序列与其所转化的二叉树的先序遍历序列相同。（╳）20、树的后根遍历序列与其所转化的二叉树的后序遍历序列相同。二、填空1．由３个结点所构成的二叉树有5种形态。2.线索二叉树的左线索指向其_前驱_____，右线索指向其__后继____。3．一棵具有257个结点的完全二叉树，它的深度为9。4、如某二叉树有20个叶子结点，有30个结点仅有一个孩

4、子，则该二叉树的总结点数为_69_____。5.设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。答：最快方法：用叶子数＝[n/2]＝500，n2=n0-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.6.一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。收集于网络，如有侵权请联系管理员删除_________________________

5、_________________________7.若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是FEGHDCB。8.在二叉树中，指针p所指结点为叶子结点的条件是_p->lchild==null&&p->rchlid==null 。三、选择题1．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为（C）A）3　B）2C）4D）52．二叉树是非线性数据结构，所以（C）。Ａ、它不能用顺序存储结构存储;Ｂ、它不能用链式存储结构存储;Ｃ、顺序存储结构和链

6、式存储结构都能存储;Ｄ、顺序存储结构和链式存储结构都不能使用3.具有n(n>0)个结点的完全二叉树的深度为（C）。(Ａ)élog2(n)ù(Ｂ)ëlog2(n)û(Ｃ)ëlog2(n)û+1(Ｄ)élog2(n)+1ù4．把一棵树转换为二叉树后，这棵二叉树的形态是（A）。（Ａ）唯一的（Ｂ）有多种（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子5.线索二叉树是一种（ C  ）结构。A．逻辑   B．逻辑和存储  C．物理    D．线性6、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号

7、为1，则编号为49的结点的左孩子的编号为（A）A、98B、99C、50D、487、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（D）A）M1B）M1+M2C）M3D）M2+M38、将一棵有100个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为（C）A、48B、49C、50D、519、引入二叉线索树的目的是（   A）A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便的进行插入与删除C、为了能方便的找到双亲 

8、   D、使二叉树的遍历结果唯一10．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B）A