数据结构-树和二叉树-习题(共10页).docx

《数据结构-树和二叉树-习题(共10页).docx》由会员分享，可在线阅读，更多相关《数据结构-树和二叉树-习题(共10页).docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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. 2

2、h+1D. h+16. 对一个满二叉树 满二叉树是除最后一层无任何子外，每一层上的所有结点都有两个子结点的二叉树，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. wu

3、tsv9. 某二叉树的前序遍历结点访问顺序是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. 二叉树是非线性

7、数据结构，所以（）。A.它不能用顺序存储结构存储;B.它不能用链式存储结构存储; C.顺序存储结构和链式存储结构都能存储; D.顺序存储结构和链式存储结构都不能使用 21. 具有n(n0)个结点的完全二叉树的深度 K层完全二叉树，就是前（）层为，第K层均为叶结点，可以不满。所以结点与深度的关系为：2K-1-1Rtag=1 rtag=1 时rchild指向后继；ltag=0 时lchild指向左子女；ltag=1 时lchild指向前驱；rtag=0 时rchild指向右子女；B.t-Rchild=NULLC.t-Rtag=1 & t-Rchild=NULLD.以上都不对41. 设高度为h的二叉

8、树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A2hB2h-1C2h+1Dh+142. 如右图所示二叉树的中序遍历序列是（）。AabcdgefBdfebagcCdbaefcgDdefbagc43. 设a和b为一棵二叉树上的两个结点，在中序遍历时a在b前的条件是（）。Aa是b的左孩子Bb是a的右孩子Ca是b左子树上结点或b是a右子树上结点D以上三项均可44. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。A45B15C16D3145. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A2m-

9、1B2mC2m+1D4m46. 二叉树的第k层的结点数最多为（）。A2k-1B2K+1C2K-1D2K-147. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。A9B10C11D1248. 一棵有n个结点的树，在把它转换成对应的二叉树后，该二叉树根结点的左子树上共有（）个结点。An-2Bn-1Cn+1Dn+249. 对于一棵深度为4的三叉树，最多有（）个结点。A30B36C40D5450. 设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。A3B4C5D151. 关于哈夫曼树，下列说法正确的是( )。A在哈夫曼树中，权值相同的叶子结点都在同一层上B在哈夫曼

10、树中，权值较大的叶子结点一般离根结点较远C哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近D在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理二.判断题1. 线索二叉树是一种逻辑结构。（）2. 二叉树中每个结点的两棵子树是有序的。（） 3. 深度为K的完全二叉树至少有2K-1个结点。（） 4. 在哈夫曼树中，权值最小的结点离根结点最近。（）5. 二叉树中每个结点的两棵子树的高度差等于1。 （） 6. 具有12个结点的完全二叉树有5个度为2的结点。（）7. 二叉树中每个结点有两棵非空子树或有两棵空子树。（）8. 哈夫曼树中没有度为1的结点，所以必为满二叉

11、树。（）9. 二叉树中所有结点个数是2k-1-1，其中k是树的深度。（）10. 二叉树的遍历操作实际上是将非线性结构线性化的过程。（）11. 具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。（）12. 前序和中序遍历用线索树方式存储的二叉树，不必使用栈。（）13. 树的先根遍历序列与其所转化的二叉树的先序遍历序列相同。（）14. 树的后根遍历序列与其所转化的二叉树的后序遍历序列相同。（）15. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。（） 16. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（） 17. 哈夫曼树是带权路径长度最短的树，路径上权值较大

12、的点离根较远。（）18. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面。（）19. 在二叉树结点的先序序列和后序序列中，所有叶子结点的先后顺序完全相同。（）20. 用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（）21. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i1个结点。（）22. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n1个非空指针域。（）三.填空题1. 由个结点所构成的二叉树有种形态。 2. 线索二叉树的左线索指向其，右线索指向其。3. 一棵具有257个结点的完全二叉树，它的深度为。4. 如某

13、二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为。5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有 个结点只有非空右子树。6. 一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为 。7. 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。 8. 在二叉树中，指针p所指结点为叶子结点的条件是。9. 有一棵树如右图所示，回答下面的问题：1) 这棵树的根结点是；2) 这棵树的叶子结点是；3) 结点k3的度是；4) 这棵树的度是；5) 这棵树的深度是；6) 结点k3

14、的子女是；7) 结点k3的父结点是；10. 指出树和二叉树的三个主要差别：。11. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是。12. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如下图所示，则该二叉树的链接表示形式为_。13. 深度为k的完全二叉树至少有个结点。至多有个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是。14. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n0=。15. 一棵二叉树的第i（i1）层最多有个结点；一棵有n（n0）个结点的满二叉树共有个叶子和个非终端结点。1

15、6. 结点最少的树为，结点最少的二叉树为。17. 现有按中序遍历二叉树的结果为abc，问有种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是。18. 一棵含有N个结点的k叉树,可能达到的最大深度为和最小深度为。19. 由如右图所示的二叉树，回答以下问题：1) 其中序遍历序列为；2) 其前序遍历序列为；3) 其后序遍历序列为；四. 简答题1. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。2. 假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。3. 由如下图所示的二叉树，请画出该二叉树对应的森林。4. 已知一棵树如图6.8所示，转化为一棵二叉树。5. 以数据集4，5，6，7，10，12，18为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度为。6. 假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这八个字母设计哈夫曼编码。专心-专注-专业