数据结构习题集第6章树和二叉树

《数据结构习题集第6章树和二叉树》由会员分享，可在线阅读，更多相关《数据结构习题集第6章树和二叉树（10页珍藏版）》请在装配图网上搜索。

1、第6章树和二叉树选择题有一“遗传”关系，设X是y的父亲，贝収可以把它的属性遗传给y,表示该遗传关系最适合的数据结构是（）A、向量B、树C、图D、二叉树树最适合用来表示（B）A、有序数据元素B、元素之间具有分支层次关系的数据C、无序数据元素D、元素之间无联系的数据树B的层号表示为la,2b,3d,3e,2c，对应于下面选择的（）A、1a（2b（3d,3e）,2c）B、a（b（D,e）,c）C、a（b（d,e）,c）D、a（b,d（e）,c）对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，贝可采用（C）次序的遍历实现

2、二叉树的结点编号。A、先序B、中序C、后序D、从根开始按层次遍历按照二叉树的定义，具有个结点的二叉树有（）种。A、3B、4C、5D、6在一棵有个结点的二叉树中，若度为的结点数为，度为的结点数为，度为的结点数为，则树的最大高度为（），其叶结点数为（）；树的最小高度为（），其叶结点数为（）；若采用链表存储结构，则有（）个空链域。A、n/2E、n+n+n0l2I、n+l对一棵满二叉树，B、bogn2F、n+nl2J、nl个树叶，个结点，C、longG、n+lD)D、nH、lL、n+llK、深度为2n2h则(A、n=m+hB、h+m=2nC、m=h-lD、n=2h-l设高度为的二叉树中只有度为和度为的

3、结点，则此类二叉树中所包含的结点数至少为（），至多为（）。A、2hB、2h-lC、2h-lD、2h-l在一棵二叉树上第5层的结点数最多为（）（假设根结点的层数为1）A、8B、l6C、15D、32用深度为5的二叉树至多有（C）个结点。A、l6B、32C、31D、10用一棵有，4个叶结点的完全二叉树，最多有（B）个结点A、247B、248C、249D、250含用有，个9叶子结点的完全二叉树，最少有（）个结点A、254B、255C、256D、257假.定有一棵二叉树，双分支结点数为，5，单分支结点数为30，则叶子结点数为（B）个。A、l5B、l6C、l7D、47用顺序存储的方法将完全二叉树中所有结点

4、逐层存放在数组中，结点若有左子树，则左子树是结点（B）。A、R2i+1B、R2iC、Ri/2D、R2i-1在.一棵非空二叉树的中序遍历序列中，根结点的右边（A）。A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的所有结点D、只有左子树上的部分结点.任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序（A）。A、不发生改变B、发生改变C、不能确定D、以上都不对A、n在m右方B、n是m祖先一.棵完全二叉树按层次遍历的序列为结点的直接后继是（）。A、BB、D设、为一棵树上的两个结点，在中序遍历时，在前的条件是（）。C、n在m左方D、n是m子孙），后序遍历中）。遍历方法最合适。

5、E则在先序遍历中结点的直接前驱为（C、AD、IE、FF、C已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（A、acbedB、decabC、deabcD、cedba已若二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（C）A、前序B、中序C、后序D、层次线索二叉树是一种（）结构。A、逻辑B、逻辑和存储C、物理D、线性如果是由有序树转换而来的二叉树，那么中结点的前序就是中结点的（）A、前序B、中序C、后序D、层次序设是哈夫曼树，具有个叶结点，树的高度最高可以是（）。A、1B、2C、3D、4E、5F、6已由带权为8，2，5，7的四个叶子结点

6、构造一棵哈夫曼树，该树的带权路径长度为（）A、23B、37C、46D、43已树的后根遍历序列等同于该树对应的二叉树的（）B。A、先序遍历B、中序遍历C、后序遍历D、层次遍历以已下说法错误的是（A）。A、树形结构的特点是一个结点可以有多个直接前趋B、线性结构中的一个结点至多只有一个直接后继C、二叉树与树是两种不同的数据结构D、树（及一切树形结构）是一种“分支层次”结构以已下说法错误的是（C）。A、二叉树可以是空集B、二叉树的任一结点都有两棵子树C、二叉树与树具有相同的树形结构D、二叉树中任一结点的两棵子树有次序之分已以下说法错误的是（D）。A、完全二叉树上结点之间的父子关系可由它们编号之间的关系

7、来表达B、在三叉链表上，二叉树的求双亲运算很容易实现C、在二叉链表上，求根，求左、右孩子等很容易实现D、在二叉链表上，求双亲运算的时间性能很好以下说法错误的是（）。A、一般在哈夫曼树中，权值越大的叶子离根结点越近B、哈夫曼树中没有度数为1的分支结点C、若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点4/7北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1数据结构课后练习题第章树和二叉树D、若初始森林中共有n棵二叉树，进行2n-l次合并后才能剩下一棵最终的哈夫曼树30. 将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点

8、编号，那么编号为21的双亲结点编号为（）。A、l0B、llC、4lD、2031. 任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置（C）。A、肯定发生变化B、有时发生变化C、肯定不发生变化D、无法确定32. 下列说法正确的是（A）。A、树的先根遍历序列与其对应的二叉树的前序遍历序列相同B、树的先根遍历序列与其对应的二叉树的后序遍历序列相同C、树的后根遍历序列与其对应的二叉树的前序遍历序列相同D、树的后根遍历序列与其对应的二叉树的后序遍历序列相同33下.列说法中正确的是（D）。A、任何一棵二叉树中至少有一个结点的度为2B、任何一棵二叉树中每个结点的度都为2C、任何一棵二叉树中的每个

9、结点的度肯定等于2D、任何一棵二叉树中的每个结点的度都可以小于234.一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（）遍历方式就可以得到这棵二叉树所有结点的递减序列。A、前序B、中序C、后序D、层次对含有（）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。A、0B、1C、2D、不存在这样的二叉树在图6.2中的二叉树中，（）不是完全二叉树。数据结构课后练习题第章树和二叉树数据结构课后练习题第章树和二叉树哈对夫曼树的带权路径长度是（B）。A、所有结点权值之和C、带权结点的值在对线索二叉树上，线索是（B

10、）A、两个标志域B、所有叶结点带权路径长度之和D、除根以外所有结点权值之和B、指向结点前驱和后继的指针C、数据域对已给出如图A、110100D、指向左、右子树的指针3/7数据结构课后练习题第6章树和二叉树A、t-lchild=NULLC、t-ltag=1&t-lchild=NULL已下列叙述中正确的是（D）。A、二叉树是度为2的有序树C、二叉树中必有度为2的结点B、t-ltag=1D、以上都不对图6.4所示的几种结构中属于树型结构的是（B）。已给出的图6.3所示二叉树，A,B,C,D分别带权值为7,5,2,4则该树的带权路径长度为（）。A、46B、36C、35D、都不是在线索化二叉树中，t所指

11、结点没有左子树的充要条件是（）。B、二叉树中结点只有一个孩子时无左右之分D、二叉树中结点最多有两棵子树，并且有左右之分二、判断题1. 二叉树是树的特殊形式。X2. 树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。V3. 一棵有n个结点的d度树，若用多重链表表示，树中每个结点都是有d个链域，则在树的n*d个链域中，有n*（d-1）+1个是空链域，只有n-1个是非空的。V4. 前序遍历树和前序遍历与该树对应的二叉树，其结果相同。V5. 后序遍历树和中序遍历与该树对应的二叉树，其结果不同。X6. 前序遍历森林和前序

12、遍历与该森林对应的二叉树，其结果相同。X7. 中序遍历森林和中序遍历与该森林对应的二叉树，其结果不同。V8. 若有一个结点是某二叉树子树的中序遍历序列中最后一个结点，则它必须是该子树的前序遍历序列中的最后一个结点。X9. 二叉树具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女。V10. 在二叉树中，具有一个子女的父结点，在中序遍历中，它没有后继的子女结点。X11. 中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。V12. 在二叉树中插入结点，该二叉树便不在是二叉树。X13. 用一维数组存储二叉树时，总是以前序遍历存储结点。X14. 已知二叉树的前序遍历和后序

13、遍历序列不能唯一地确定这棵树。V15. 不使用递归，也可以实现二叉树的前序，中序，后序遍历。V16. 在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。V17. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。X三、填空题1已在树型结构中，树根结点没有（双亲）结点，其余每个结点有且只有（1）个前驱结点；叶子结点没有（子）结点，其余每个结点的后继结点可以（是结点或叶子）。8.11.四1.2.3.4.5.6.7.8.9.10.假定一棵树的厂义表表示为A（B（E）,C（F（H,I,J）,G）,D），则该树的度为（），树的深度为（4），终端结

14、点的个数为（）6，单分支结点的个数为（1），双分支结点的个数为（）1，三分支结点的个数为（），C的双亲结点为（），其孩子结点为（）。设树T中除叶结点外，任意结点的度数都是3,贝忤的第I层结点的个数为（-在具有n（n=l）个结点的k叉树中，有（）个空指针。一棵含有n个结点的k叉树，可能达到的最大深度为（），最小深度为（）。一棵深度为k的满二叉树的结点总数为（），一棵深度为k的完全二叉树的结点总数的最小值为（），从左到右次序给结点编号（从1开始）则编号最小的叶子结点的编号是（），最大值为（）。设根结点的层次数为0,定义树的高度为树中层次最大的结点的层次加1,则高度为k的二叉树具有的结点数目，最少为

15、（），最多为（）。n个结点的完全二叉树，若按从上到下、从左到右给结点顺序编号，则编号最大的非叶结点编号为（），编号最小的叶结点编号为（）。在一棵二叉树中，度为0的结点个数为n,度为2的结点个数为n,贝In=（）。020一棵二叉树的第I层最多有（）个结点，一棵有n个结点的满二叉树共有（）个叶子结点和（）个非终端结点。一棵完全二叉树的第5层有5个结点，则共有（）个结点，其中度为1的结点有（）个，度为0的结点有（10）个。具有n个结点的完全二叉树，其叶子结点的个数为（）。对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为（）个，其中（）个用于链接孩子结点，（）个空闲。对于一

16、棵具有n个结点的二叉树，当它为一棵（完全）二叉树时具有最小咼度，咼度为（），当它为一棵单支树时具有（最大）高度，高度为（n）。对树所对应的二叉树其根结点的（右）子树一定为空。从对概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是（方便编程中的调用）。一棵完全二叉树按层次遍历的序列为ABCDEFGHI,则在先序遍历中结点E的直接前驱为（），后序遍历中结点B的直接后继为（）。某二叉树的中序遍历序列为ABCDEFG,后序序列为BDCAFGE,则该二叉树结点的前序序列为（），该二叉树对应的森林包括（）2棵树。对在一棵二叉排序树上按（中序）遍历得到的结点序列为有序序列。由n个权值构成

17、的哈夫曼树共有（）个结点。由带权为3,9,6,2,5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为（）设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，贝归中右指针域为空的结点有（）个。附加判断题树中任意结点的子树不必是有序的。（X）树可以看成特殊的的无向图。（X）可以使用双链表表示树形结构。（V）顺序存储方式只能用于存储线性结构。（X）完全二叉树的某结点若无左孩子，则必为叶结点。（V）如果一个二叉树的结点，或者没有子树，或者恰有两棵非空子树，则此二叉树称为完全二叉树。（X）包含两个结点的所有二叉树都是相同的。（X）二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。（

18、V）二叉树的前序和后序遍历能唯一确定一棵二叉树。（X）二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索。（X）11.中序线索二叉树中，右线索若不为空，则一定指向其父结点。(X)五、简答题1.分别画出含3个结点的树与二叉树的所有不同形态。三结点:二叉树2.3. 设在树中，结点x是结点y的双亲时，用(x,y)来表示边。已知一棵树边的集合为：(i,j),(i,k),(b,e),(e,i),(b,d),(a,b),(c,g),(c,f),(c,h),(a,c),用树形表示法画出此树,并回答下列问题：1) 哪个是根结点？a2) 哪些是叶子结点？k,j,d,g,f,h3) 哪个是g的双亲？c4

19、) 哪些是g的祖先？c,a5) 哪些是e的子孙？i,k,j6) 哪些是f的兄弟？g,h刀结点b和j的层次各是多少？2,58) 树的深度是多少？59) 树的度数是多少？34. 任意一个有n(n0)个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有m-1个度为2,其余度为1。5. 分别画出图6.6所示二叉树的二叉链表、三叉链表和顺序存储结构。9/7北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1数据结构课后练习题第6章树和二叉树10/7北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1数据结构课后练习题第6章树和二叉树#/7北京理工大学珠海学院计算机学院

20、“数据结构”课程组编制2011-3-1数据结构课后练习题第6章树和二叉树6.ACKBDHLE图6.9MAN分别写出图6.7所示一叉树的前序、中序和后序序列前序中序后续试分别画出图6.所8示树的孩子链表、孩子兄弟链表和静态双亲链表。将图6.所9示的森林转换成二叉树。#/7北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1数据结构课后练习题第6章树和二叉树，0试为这8个分别画出图所示各二叉树对应的森林。并写出森林的前序和中序遍历序列。Qj设某密码电文由个字母组成，每个字母在电文中的出现频率分别是7,26,3,字母设计相应的哈夫曼编码。團6.10将代数式：y=3*(x+a)-a/x2描述成表达式树，并写出前缀式和后缀式来。设下述编码0，001，1，011，0，1，00，11，010，11，0111哪一组不是前缀码？0，1，00，11，不是前缀码#/7北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1