树结构习题及答案教学提纲.doc
《树结构习题及答案教学提纲.doc》由会员分享,可在线阅读,更多相关《树结构习题及答案教学提纲.doc(12页珍藏版)》请在咨信网上搜索。
树结构习题及答案 精品资料 第5章 树 【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。 A B C D E F G H I J 图5-1 解: (1)叶子结点有:B、D、F、G、H、I、J。 (2)非终端结点有:A、C、E。 (3)每个结点的度分别是:A的度为4,C的度为2,E的度为3,其余结点的度为0。 (4)树的深度为3。 【例5-2】一棵度为2的树与一棵二叉树有什么区别? 解:度为2的树有两个分支,但分支没有左右之分;一棵二叉树也有两个分支,但有左右之分,左右子树的次序不能交换。 【例5-3】树与二叉树有什么区别? 解:区别有两点: (1)二叉树的一个结点至多有两个子树,树则不然; (2)二叉树的一个结点的子树有左右之分,而树的子树没有次序。 【例5-4】分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。 解:如图5-2(a)所示,具有3个结点的树有两种不同形态。 图5-2(a) 如图5-2(b)所示,具有3个结点的二叉树有以下五种不同形态。 图5-2(b) 【例5-5】如图5-3所示的二叉树,试分别写出它的顺序表示和链接表示(二叉链表)。 解: (1)顺序表示。 1 2 3 4 5 6 7 8 9 10 11 a b c d e ^ ^ ^ ^ f g (2)该二叉树的二叉链表表示如图5-4所示。 a b c d ∧ e f g 图5-4 ∧ ∧ ∧ ∧ ∧ ∧ ∧ 【例5-6】试找出满足下列条件的所有二叉树: (1)先序序列和中序序列相同; (2)中序序列和后序序列相同; (3)先序序列和后序序列相同。 解: (1)先序序列和中序序列相同的二叉树为:空树或者任一结点均无左孩子的非空二叉树; (2)中序序列和后序序列相同的二叉树为:空树或者任一结点均无右孩子的非空二叉树; (3)先序序列和后序序列相同的二叉树为:空树或仅有一个结点的二叉树。 b a c d e f 图5-5 【例5-7】如图5-5所示的二叉树,要求: (1)写出按先序、中序、后序遍历得到的结点序列。 (2)画出该二叉树的后序线索二叉树。 解: (1) 先序遍历序列:ABDEFC 中序遍历序列:DEFBAC 后序遍历序列:FEDBCA (2)其后序线索二叉树如图5-6所示。 NULL c a b d e f 图5-6 A 图5-7 B C D E F G H I K L M J 【例5-8】将图5-7所示的树转换为二叉树。 解:第一步,加线。第二步,抹线。第三步,旋转。过程如图5-8所示。 A 图5-8(a) 第一步 加线 B C D E F G H I K L M J A 图5-8(b) 第二步 抹线 B C D E F G H I K L M J A B 图5-8(c) 第三步 旋转 C F D K G E L H M I J A B C D E F H I J 图5-9 【例5-9】将如图5-9所示的二叉树转换为树。 解: 第一步,加线。第二步,抹线。第三步,调整。过程如图5-10所示。 A B D H C F E J I B A C D E F H I J 第一步 第二步 第三步 B A C D E F H I J 图5-10 【例5-10】将如图5-11所示的森林转换成二叉树。 图5-11 C D E F G A B H I L J K 解: 步骤略,结果如图5-12所示。 C D E F G A B H I L J K 图5-12 【例5-11】假定用于通信的电文由8个字符A、B、C、D、E、F、G、H组成,各字母在电文中出现的概率为5%、25%、4%、7%、9%、12%、30%、8%,试为这8个字母设计哈夫曼编码。 解: 根据题意,设这8个字母对应的权值分别为(5,25,4,7,9,12,30,8),并且n=8。 第一步: 25 5 4 7 9 12 30 8 (1)设计哈夫曼树的步骤如图5-13所示。 第四步: 25 7 9 12 30 8 15 5 4 9 18 第五步: 25 7 9 12 30 8 15 5 4 9 18 27 第六步: 25 30 9 5 4 9 18 7 12 8 15 27 43 第二步: 25 7 9 12 30 5 4 9 8 第三步: 25 7 9 12 30 5 4 9 8 15 第七步: 25 30 9 5 4 9 18 7 12 8 15 27 43 57 第八步: 25 9 5 4 9 18 43 30 7 12 8 15 27 57 100 图5-13 (2)设计哈夫曼编码 利用第八步得到的哈夫曼树,规定左分支用0表示,右分支用1表示,字母A、B、C、D、E、F、G、H的哈夫曼编码如下表示: A:0011 B:01 C:0010 D:1010 E:000 F:100 G:11 H:1011 习题5 一、单项选择题 1. 在一棵度为3的树中,度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,则度为0的结点数为( 1. C)个。 A. 4 B. 5 C. 6 D. 7 2. 假设在一棵二叉树中,双分支结点数为15,单分支结点数为30个,则叶子结点数为(2. B )个。 A. 15 B. 16 C. 17 D. 47 3. 假定一棵三叉树的结点数为50,则它的最小高度为(3. C )。 A. 3 B. 4 C. 5 D. 6 4. 在一棵二叉树上第4层的结点数最多为( 4. D)。 A. 2 B. 4 C. 6 D. 8 5. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n],结点R[i]若有左孩子,其左孩子的编号为结点(5. B)。 A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1] 6. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为(6. D )。 A. 24 B. 48 C. 72 D. 53 7. 线索二叉树是一种( 7. C)结构。 A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性 8. 线索二叉树中,结点p没有左子树的充要条件是( 8. B)。 A. p->lc=NULL B. p->ltag=1 C. p->ltag=1 且p->lc=NULL D. 以上都不对 9. 设n , m 为一棵二叉树上的两个结点,在中序遍历序列中n在m前的条件是(9. B)。 A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孙 10. 如果F是由有序树T转换而来的二叉树,那么T中结点的前序就是F中结点的(10. B )。 A. 中序 B. 前序 C. 后序 D. 层次序 11. 欲实现任意二叉树的后序遍历的非递归算法而不必使用栈,最佳方案是二叉树采用( 11. A)存储结构。 A. 三叉链表 B. 广义表 C. 二叉链表 D. 顺序 12. 下面叙述正确的是( 12. D)。 A. 二叉树是特殊的树 B. 二叉树等价于度为2的树 C. 完全二叉树必为满二叉树 D. 二叉树的左右子树有次序之分 13. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序(13. A )。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 14. 已知一棵完全二叉树的结点总数为9个,则最后一层的结点数为(14. B )。 A. 1 B. 2 C. 3 D. 4 15. 根据先序序列ABDC和中序序列DBAC确定对应的二叉树,该二叉树( 15. A )。 A. 是完全二叉树 B. 不是完全二叉树 C. 是满二叉树 D. 不是满二叉树 二、判断题 1. 二叉树中每个结点的度不能超过2,所以二叉树是一种特殊的树。 (1.× ) 2. 二叉树的前序遍历中,任意结点均处在其子女结点之前。 ( 2.√ ) 3. 线索二叉树是一种逻辑结构。 ( 3.×) 4. 哈夫曼树的总结点个数(多于1时)不能为偶数。 (4.√) 5. 由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。 (5.×) 6. 树的后序遍历与其对应的二叉树的后序遍历序列相同。 (6.√) 7. 根据任意一种遍历序列即可唯一确定对应的二叉树。 (7.√) 8. 满二叉树也是完全二叉树。 ( 8.√) 9. 哈夫曼树一定是完全二叉树。 (9.×) 10. 树的子树是无序的。 (10.× ) 三、填空题 1. 假定一棵树的广义表表示为A(B(E),C(F(H,I,J),G),D),则该树的度为_____,树的深度为_____,终端结点的个数为______,单分支结点的个数为______,双分支结点的个数为______,三分支结点的个数为_______,C结点的双亲结点为_______,其孩子结点为_______和_______结点。1. 3,4,6,1,1,2,A,F,G 2. 设F是一个森林,B是由F转换得到的二叉树,F中有n个非终端结点,则B中右指针域为空的结点有_______个。2. n+1 3. 对于一个有n个结点的二叉树,当它为一棵________二叉树时具有最小高度,即为_______,当它为一棵单支树具有_______高度,即为_______。3. 完全,,最大,n 4. 由带权为3,9,6,2,5的5个叶子结点构成一棵哈夫曼树,则带权路径长度为___。4. 55 5. 在一棵二叉排序树上按_______遍历得到的结点序列是一个有序序列。5. 中序 6. 对于一棵具有n个结点的二叉树,当进行链接存储时,其二叉链表中的指针域的总数为_______个,其中_______个用于链接孩子结点,_______个空闲着。6. 2n,n-1,n+1 7. 在一棵二叉树中,度为0的结点个数为n0,度为2的结点个数为n2,则n0=______。7. n2+1 8. 一棵深度为k的满二叉树的结点总数为_______,一棵深度为k的完全二叉树的结点总数的最小值为_____,最大值为______。8. 2k-1,2k-1,2k-1 9. 由三个结点构成的二叉树,共有____种不同的形态。9. 5 10. 设高度为h的二叉树中只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为____。10. 2h-1 11. 一棵含有n个结点的k叉树,______形态达到最大深度,____形态达到最小深度。11. 单支树,完全二叉树 12. 对于一棵具有n个结点的二叉树,若一个结点的编号为i(1≤i≤n),则它的左孩子结点的编号为________,右孩子结点的编号为________,双亲结点的编号为________。12. 2i,2i+1,i/2(或ëi/2û) 13. 对于一棵具有n个结点的二叉树,采用二叉链表存储时,链表中指针域的总数为_________个,其中___________个用于链接孩子结点,_____________个空闲着。13. 2n,n-1,n+1 14. 哈夫曼树是指________________________________________________的二叉树。14. 带权路径长度最小 15. 空树是指________________________,最小的树是指_______________________。15. 结点数为0,只有一个根结点的树 16. 二叉树的链式存储结构有______________和_______________两种。16. 二叉链表,三叉链表 17. 三叉链表比二叉链表多一个指向______________的指针域。17. 双亲结点 18. 线索是指___________________________________________。18. 指向结点前驱和后继信息的指针 19. 线索链表中的rtag域值为_____时,表示该结点无右孩子,此时______域为指向该结点后继线索的指针。19. 1,RChild 20. 本节中我们学习的树的存储结构有_____________、___________和___________。20. 孩子表示法,双亲表示法,长子兄弟表示法 四、应用题 1. 已知一棵树边的集合为{<i,m>,<i,n>,<e,i>,<b,e>,<b,d>,<a,b>,<g,j>,<g,k>,<c,g>,<c,f>,<h,l>,<c,h>,<a,c>},请画出这棵树,并回答下列问题: (1)哪个是根结点? (2)哪些是叶子结点? (3)哪个是结点g的双亲? (4)哪些是结点g的祖先? (5)哪些是结点g的孩子? (6)哪些是结点e的孩子? (7)哪些是结点e的兄弟?哪些是结点f的兄弟? (8)结点b和n的层次号分别是什么? (9)树的深度是多少? (10)以结点c为根的子树深度是多少? 1. 解答: a b c d e g f h i m n j k i 图5-15 根据给定的边确定的树如图5-15所示。 其中根结点为a; 叶子结点有:d、m、n、j、k、f、l; c是结点g的双亲; a、c是结点g的祖先; j、k是结点g的孩子; m、n是结点e的子孙; e是结点d的兄弟; g、h是结点f的兄弟; 结点b和n的层次号分别是2和5; 树的深度为5。 4. 已知用一维数组存放的一棵完全二叉树:ABCDEFGHIJKL,写出该二叉树的先序、中序和后序遍历序列。 4. 解答: 先序序列:ABDHIEJKCFLG 中序序列:HDIBJEKALFCG 后序序列:HIDJKEBLFGCA 6. 找出所有满足下列条件的二叉树: (1)它们在先序遍历和中序遍历时,得到的遍历序列相同; (2)它们在后序遍历和中序遍历时,得到的遍历序列相同; (3)它们在先序遍历和后序遍历时,得到的遍历序列相同; 6. 解答: (1)先序序列和中序序列相同的二叉树为:空树或者任一结点均无左孩子的非空二叉树; (2)中序序列和后序序列相同的二叉树为:空树或者任一结点均无右孩子的非空二叉树; (3)先序序列和后序序列相同的二叉树为:空树或仅有一个结点的二叉树。 7. 假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请写出该二叉树的后序遍历序列。 7. 解答:后序序列:ACDBGJKIHFE 8. 假设一棵二叉树的后序序列为DCEGBFHKJIA,中序序列为DCBGEAHFIJK,请写出该二叉树的后序遍历序列。 8. 解答:先序序列:ABCDGEIHFJK 9. 给出如图5-14所示的森林的先根、后根遍历结点序列,然后画出该森林对应的二叉树。 9. 解答: 先根遍历:ABCDEFGHIJKLMNO 后根遍历:BDEFCAHJIGKNOML 森林转换成二叉树如图5-16所示。 10.给定一组权值(5,9,11,2,7,16),试设计相应的哈夫曼树。 10. 解答:构造而成的哈夫曼树如图5-17所示。 A B D E F C G H J I K N O M L 图5-14 仅供学习与交流,如有侵权请联系网站删除 谢谢12- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 结构 习题 答案 教学 提纲
咨信网温馨提示:
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
关于本文