数据结构树和二叉树习题

1、树与二叉树一.选择题1. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。A15B16C17D472. 按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。A. 3B. 4C. 5D. 63. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。A. 5B. 6C. 30D. 324. 深度为5的二叉树至多有（）个结点。 深度为n的二叉树结点至多有2n-1A. 16B. 32C. 31D. 105. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A. 2hB. 2h-1C. 2h+1D. h+16. 对

2、一个满二叉树 满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树，m个树叶，n个结点，深度为h，则（）。A. n=h+m 对于深度为h的满二叉树，n=20+21+2h-1=2h-1，m=2h-1。故而n=h+m。B. h+m=2n C. m=h-1 D. n=2 h-17. 任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（）。A.不发生改变B.发生改变C.不能确定D.以上都不对8. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为（）。 A. uwvtsB. vwutsC. wuvtsD. wutsv9. 某二叉树的

3、前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（）。A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca10. 在一非空二叉树的中序遍历序列中，根结点的右边（）。A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的部分结点D. 只有左子树上的所有结点11. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历.中序遍历和后序遍历。这里，我们把由树转化得到的二叉树 树转化为二叉树的基本方法是把所有兄弟结点都用线连起来，然后去掉双亲到子女的连线，只留下

4、双亲到第一个子女的连线。因此原来的兄弟关系就变为双亲与右孩子的关系。叫做这棵数对应的二叉树。结论（）是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对12. 如图所示二叉树的中序遍历序列是（）。A. abcdgefB. dfebagcC. dbaefcgD. defbagc13. 一棵二叉树如图所示，其中序遍历的序列为（）。A. abdgcefhB. dgbaechfC. gdbehfcaD. abcdefgh14. 设a,b为一棵二叉树上的两个结点，在中序遍

5、历时，a在b前的条件是（）。Aa在b的右方Ba在b的左方Ca是b的祖先Da是b的子孙15. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。A. acbedB. decabC. deabcD. cedba16. 如下图所示的4棵二叉树，（）不是完全二叉树 深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，成为完全二叉树。即除第 h 层外，其它各层 (1h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。ABCD17. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案

6、是二叉树采用（）存储结构。A. 二叉链表B. 广义表存储结构C. 三叉链表 三叉链表是二叉树的另一种主要的链式存储结构。三叉链表与二叉链表的主要区别在于，它的结点比二叉链表的结点多一个指针域，该域用于存储一个指向本结点双亲的指针。三叉链表的结点形式如下D. 顺序存储结构18. 树最适合用来表示（）。A. 有序数据元素B. 无序数据元素C. 元素之间具有分支层次关系的数据D. 元素之间无联系的数据19. 某二叉树结点的中序序列为A.B.C.D.E.F.G，后序序列为B.D.C.A.F.G.E，则其左子树中结点数目为（）。A. 3B. 2C. 4D. 520. 二叉树是非线性数据结构，所以（）。A

7、.它不能用顺序存储结构存储;B.它不能用链式存储结构存储; C.顺序存储结构和链式存储结构都能存储; D.顺序存储结构和链式存储结构都不能使用 21. 具有n(n>0)个结点的完全二叉树的深度 K层完全二叉树，就是前（K-1）层为满二叉树，第K层均为叶结点，可以不满。所以结点与深度的关系为：2K-1-1<n 2K-1。所以K = log2(n) +1为（）。A. log2(n)B. 10（log2(n)）+1C. log2(n) +1D. log2(n)+122. 把一棵树转换为二叉树后，这棵二叉树的形态是（）。A.唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结

8、点都没有右孩子23. 线索二叉树是一种（）结构 逻辑结构：集合、线性、树和图物理结构：线性存储和非线性存储 线性存储结构有顺序、链接、索引、散列4种结构 非线性存储结构有：树形存储结构、图形存储结构。A 逻辑B 逻辑和存储C 物理D线性24. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（）。 A.98B.99C.50D.4825. 设森林F中有三棵树，第一.第二和第三棵树的结点个数分别为M1.M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。AM1BM1+M2CM3DM2+M326. 将一

9、棵有100个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为（）。 A.48B.49C.50D.5127. 引入二叉线索树的目的是（）。A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲     D.使二叉树的遍历结果唯一28. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。 二叉树有如下性质：N0 = N2 +1，叶子节点个数等于度为2的节点个数+1A9B11C15D不确定 29. 一棵树深度为K的完全二叉树至少有（

10、）个结点A2k 1B. 2k-1-1C. 2k-1D. 2k30. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。ACABDEFGBABCDEFGCDACEFBGDADCFEG  31. 有关二叉树下列说法正确的是（）。A二叉树的度为2B一棵二叉树的度可以小于2C二叉树中至少有一个结点的度为2D二叉树中任何一个结点的度都为232. 一个具有1025个结点的二叉树的高h为（）。A11B10C11至1025之间D10至1024之间33. 对于有n 个结点的二叉树, 其高度为（）。Anlog2nBlog2nCëlog2n+1D不确定34. 已知某

11、二叉树的后序遍历序列是dabec, 中序遍历序列是debac ,它的先序遍历是（）。AacbedBdecabCdeabcDcedba   35. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左.右子树的位置，利用（）遍历方法最合适。A前序B中序C后序D按层次36. 在下列存储形式中，（）一个不是树的存储形式？ A双亲表示法B孩子链表表示法 C孩子兄弟表示法D顺序存储表示法37. 在下列关于二叉树的叙述中，正确的是（）。只有一个结点的二叉树度为0; 二叉树的度为2； 二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。ABC

12、D38. 若x是二叉中序线索树中一个不为根的有左孩子的结点则x的前驱为（）。A.X的双亲B.X的右子树中最左的结点 C.X的左子树中最右结点D.X的左子树中最右叶结点 39. 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）。A都不相同B完全相同C先序和中序相同，而与后序不同D中序和后序相同，而与先序不同40. 在线索化二叉树中，t所指结点没有右子树的充要条件是（）。A.t->Rtag=1 rtag=1 时rchild指向后继；ltag=0 时lchild指向左子女；ltag=1 时lchild指向前驱；rtag=0 时rchild指向右子女；

13、B.t->Rchild=NULLC.t->Rtag=1 && t->Rchild=NULLD.以上都不对41. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A2hB2h-1C2h+1Dh+142. 如右图所示二叉树的中序遍历序列是（）。AabcdgefBdfebagcCdbaefcgDdefbagc43. 设a和b为一棵二叉树上的两个结点，在中序遍历时a在b前的条件是（）。Aa是b的左孩子Bb是a的右孩子Ca是b左子树上结点或b是a右子树上结点D以上三项均可44. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为

14、30，则叶子结点数为（）个。A45B15C16D3145. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A2m-1B2mC2m+1D4m46. 二叉树的第k层的结点数最多为（）。A2k-1B2K+1C2K-1D2K-147. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。A9B10C11D1248. 一棵有n个结点的树，在把它转换成对应的二叉树后，该二叉树根结点的左子树上共有（）个结点。An-2Bn-1Cn+1Dn+249. 对于一棵深度为4的三叉树，最多有（）个结点。A30B36C40D5450. 设结点A有3个兄弟结点且结点B

15、为结点A的双亲结点，则结点B的度数数为（）。A3B4C5D151. 关于哈夫曼树，下列说法正确的是( )。A在哈夫曼树中，权值相同的叶子结点都在同一层上B在哈夫曼树中，权值较大的叶子结点一般离根结点较远C哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近D在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理二.判断题1. 线索二叉树是一种逻辑结构。（×）2. 二叉树中每个结点的两棵子树是有序的。（） 3. 深度为K的完全二叉树至少有2K-1个结点。（） 4. 在哈夫曼树中，权值最小的结点离根结点最近。（×）5. 二叉树中每个结点的两棵子

16、树的高度差等于1。 （×） 6. 具有12个结点的完全二叉树有5个度为2的结点。（）7. 二叉树中每个结点有两棵非空子树或有两棵空子树。（×）8. 哈夫曼树中没有度为1的结点，所以必为满二叉树。（×）9. 二叉树中所有结点个数是2k-1-1，其中k是树的深度。（×）10. 二叉树的遍历操作实际上是将非线性结构线性化的过程。（）11. 具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。（）12. 前序和中序遍历用线索树方式存储的二叉树，不必使用栈。（）13. 树的先根遍历序列与其所转化的二叉树的先序遍历序列相同。（）14. 树的后根遍历序列与其所转化

17、的二叉树的后序遍历序列相同。（×）15. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。（×） 16. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（×） 17. 哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。（×）18. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面。（）19. 在二叉树结点的先序序列和后序序列中，所有叶子结点的先后顺序完全相同。（）20. 用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（）21. 对于一棵非空二叉树，它的根结点作为第一层，则它的

18、第i层上最多能有2i1个结点。（×）22. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n1个非空指针域。（）三.填空题1. 由个结点所构成的二叉树有种形态。 2. 线索二叉树的左线索指向其，右线索指向其。3. 一棵具有257个结点的完全二叉树，它的深度为。4. 如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为。5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有 个结点只有非空右子树。6. 一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为 。7. 若已知一棵二叉树的前

19、序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。 8. 在二叉树中，指针p所指结点为叶子结点的条件是。9. 有一棵树如右图所示，回答下面的问题：1) 这棵树的根结点是；2) 这棵树的叶子结点是；3) 结点k3的度是；4) 这棵树的度是；5) 这棵树的深度是；6) 结点k3的子女是；7) 结点k3的父结点是；10. 指出树和二叉树的三个主要差别：。11. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是。12. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如下图所示，则该二叉树的链接表示形式为_。13. 深度为k的完全二叉树至少有个结点。至多有个结点，