首页 范文大全 古典文学 职场知识 中国文学 公文书信 外国名著 寓言童话 百家讲坛 散文/诗歌 美文欣赏 礼仪知识 民俗风情
  • 工作总结
  • 工作计划
  • 心得体会
  • 竞聘演讲
  • 会议发言
  • 爱国演讲
  • 就职演说
  • 开业开幕
  • 思想学习
  • 征文演讲
  • 经验材料
  • 述职报告
  • 调研报告
  • 工作汇报
  • 年终总结
  • 申报材料
  • 学习体会
  • 企划方案
  • 活动方案
  • 技巧经验
  • 模板范例
  • 思想宣传
  • 经济工作
  • 工作报告
  • 组织人事
  • 反腐倡廉
  • 慰问贺电
  • 先进事迹
  • 思想汇报
  • 入党申请书
  • 党会发言
  • 先进性教育
  • 入团申请书
  • 个人简历
  • 演讲稿
  • 调查报告
  • 实习报告
  • 和谐社会
  • 观后感
  • 读后感
  • 作文范文
  • 自我鉴定
  • 讲话稿
  • 自查报告
    • 蒲公英阅读网 > 范文大全 > 先进性教育 > 正文

    数据结构第06章,树和二叉树习题

    时间：2021-01-06 10:06:55 来源：蒲公英阅读网 本文已影响人 蒲公英阅读网手机站

    相关热词搜索：数据结构 习题 二叉树

    　第六章 树和二叉树 一、选择题 1、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..n]中，若结点R[i]有左孩子，则其左孩子是（

    　 ）。

    　A. R[2i-1]

    　B. R[2i+1]

    　 C. R[2i]

    　D. R[2/i] 2、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..n]中，若结点R[i]有右孩子，则其右孩子是（

    　 ）。

    　A. R[2i-1]

    　 B. R[2i+1] C. R[2i]

    　D. R[2/i] 3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（

    　 ）。

    　A. a在b的右方

    　B. a在b的左方

    　C. a是b的祖先

    　D. a是b的子孙 4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（

    　 ）。

    　A. adbce

    　 B. decab

    　 C. debac

    　 D. abcde 5、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（

    　 ）。

    　A. DBFEAC

    　B. DFEBCA

    　C. BDFECA

    　D. BDEFAC 6、树最适合用来表示（

    　 ）。

    　A. 有序数据元素

    　 B. 无序数据元素

    　C. 元素之间具有分支层次关系的数据

    　D. 元素之间无联系的数据 7、在线索二叉树中，t所指结点没有左子树的充要条件是（

    　 ）。

    　A. t->left==NULL

    　 B. t->ltag==1

    　C. t->ltag==1&&t->left==NULL

    　D. 以上都不对 8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（

    　 ）。

    　A. 不发生改变

    　 B. 发生改变

    　C. 不能确定

    　D. 以上都不对 9、假定一棵二叉树，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（

    　）。

    　A. 15

    　B. 16

    　C. 17

    　D. 47 10、在下列情况中，可称为二叉树的是（

    　 ）。

    　A. 每个结点至多有两棵子树的树

    　 B. 哈夫曼树

    　C. 每个结点至多有两棵子树的有序树

    　 D. 每个结点只有一棵子树 11、二叉树是（

    　 ）。

    　A. 度为2的树

    　 B. 度为2的有序树

    　C. 子树有严格左右之分的树

    　D. 子树有严格左右之分，且度不超过2的树 12、树的先根序列等同于与该树对应的二叉树的（

    　 ）。

    　A. 先序序列

    　 B. 中序序列

    　 C. 后序序列

    　D. 层序序列

    　 13、根据使用频率为 5 的字符设计的哈夫曼编码不可能是（

    　）

    　A．111，110，10，01，00

    　 B、000，001，010，011，1 C．100，11，10，1，0

    　D、001，000，01，11，10 14、根据使用频率为 5 的字符设计的哈夫曼编码不可能是（

    　）

    　A、000，001，010，011，1

    　 B、0000，0001，001，01，1 C．000，001，01，10，11

    　D、00，100，101，110，111 15、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（

    　 ）。

    　A. 3

    　B. 2

    　 C. 4

    　D. 5

    　二、判断题

    　1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。

    　2. 二叉树中每个结点的两棵子树的高度差等于 1。

    　3. 二叉树中每个结点的两棵子树是有序的。

    　4. 二叉树中每个结点有两棵非空子树或有两棵空子树。

    　 5. 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。

    　6. 二叉树中所有结点个数是 2 k-1 -1，其中 k 是树的深度。

    　 7. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

    　8. 对于一棵非空二叉树，它的根结点作为第一层，则它的第 i 层上最多能有 2 i -1 个结点。

    　9. 用二叉链表法（link-rlink）存储包含 n 个结点的二叉树，结点的 2n 个指针区域中有 n+1个为空指针。

    　10. 具有 12 个结点的完全二叉树有 5 个度为 2 的结点。

    　11、存在这样的二叉树，对它采用任何次序的遍历，结果相同。

    　12、中序遍历一棵二叉排序树的结点，可得到排好序的结点序列。

    　13、对于任意非空二叉树，要设计其后序遍历的非递归算法而不使用堆栈结构，最适合的方法是对该二叉树采用三叉链表。

    　14、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。

    　15、完全二叉树的某结点若无左孩子，则它必是叶结点。

    　三、填空题 1、具有n个结点的完全二叉树的深度是________。

    　2、哈夫曼树是其树的带权路径长度________的二叉树。

    　3、在一棵二叉树中，度为0的结点的个数是n0，度为2的结点的个数为n2，则有n0=____。

    　4、树内各结点度的________称为树的度。

    　5、按照二叉树的定义，具有3个结点的二叉树有________种。

    　6、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为______。

    　7、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为________。

    　8、二叉树的深度为k，则二叉树最多有________个结点。

    　9、在一棵具有 5 层的满二叉树中结点总数为________。

    　10、由二叉树的前序和后序遍历序列________惟一确定这棵二叉树。

    　四、综合题 1、假设以有序对<p,c>表示从双亲结点到孩子结点的一条边，若已知树中边的集合为{<a,b>,<a,d>,<a,c>,<c,e>,<c,f>,<c,g>,<c,h>,<e,i>,<e,j>,<g,k>}，请回答下列问题：

    　（1）哪个结点是根结点？（2）哪些结点是叶子结点？（3）哪些结点是 k 的祖先？ （4）哪些结点是 j 的兄弟？（5）树的深度是多少？ 2、假设一棵二叉树的先序序列为 EBADCFHGIKJ，中序序列为 ABCDEFGHIJK，请画出该二叉树。

    　3、假设用于通讯的电文仅由 8 个字母 A、B、C、D、E、F、G、H 组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。请为这 8 个字母设计哈夫曼编码。

    　4、已知二叉树的先序遍历序列为 ABCDEFGH，中序遍历序列为 CBEDFAGH，画出二叉树。

    　5、试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。

    　6、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度 WPL。

    　7、已知一棵二叉树的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。画出二叉树的形态。

    　8、一份电文中有 6 种字符：A,B,C,D,E,F，它们的出现频率依次为 16，5，9，3，30，1，完成问题：

    　（1）设计一棵哈夫曼树；（画出其树结构）

    　（2）计算其带权路径长度 WPL； 9、已知某森林的二叉树如下所示，试画出它所表示的森林。

    　AB DC E HFG

    　10、有一分电文共使用 5 个字符：a,b,c,d,e，它们的出现频率依次为 4、7、5、2、9，试构造哈夫曼树，并给出每个字符的哈夫曼编码。

    　11、如下所示的二叉树，请写出先序、中序、后序遍历的序列。

    　FDBA CEGIH J

    　12、一棵度为 2 的树与一棵二叉树有何区别？ 13、已知二叉树的前序、中序和后序遍历序列如下，其中有一些看不清的字母用*表示，请先填写*处的字母，再构造一棵符合条件的二叉树，最后画出带头结点的中序线索链表。

    　 (1)前序遍历序列是：*BC***G*

    　 (2)中序遍历序列是：CB*EAGH*

    　 (3)后序遍历序列是：*EDB**FA

  • [cng加气站实习心得]
  • 给女孩聊天的话题 和女生聊天的话
  • 【笔画3画的字取名_这么简单你还不来】笔画
  • 一年级体育下册教学计划 一年级科学下册书
  • [世界上国家间最大的陆地争议地区] 世界上
  • 【成功餐饮企业创业故事】 餐饮免费模式成
  • 人际关系面试题及答案【关于人际关系的面试
  • [女性哲学语句]哲学语句
  • 【三只小猪读后感4篇】 三只小猪盖房子读
    • 范文大全
    • 职场知识
    • 精美散文
    • 名著
    • 讲坛
    • 诗歌
    • 礼仪知识
    最新文章

    推荐访问

    大反思大讨论活动 保安全” 筑防线 “查思想 贡献伟大时代” “以青春之我 工作评议报告 创建活动综述 市社保局党支部 自述报告 “党员先锋示范岗” 党建德育工作 达标创星活动 “星级党支部”创建 评星定级管理 社会组织党支部 第四巡察组 新进年轻干部 委厅机关 党性教育培训班 履职能力建设专题培训班 新考录社区工作者 “头雁领航”重点培训班 党组织业务培训 能力提升培训会 赋能经济高质量发展 “五好”园区 三年攻坚行动 行政管理能力建设提升班 高质量发展能力提升培训班 市疾控系统 中基层管理人员 专业能力提升专题培训班 新发展预备党员 进驻工作 迎接审计组 讲评推进大会 “三抓三促”行动动员 “永不过时的红岩精神” 市委党史研究室 科学绿化现场会 深化以案促改 一体推进不敢腐不能腐不想腐 奋斗精神 专题辅导讲稿 坚守使命追求 涉密 《党史学习教育工作条例》 百年新征程 “百年定位” 党课教育

    本文数据结构第06章,树和二叉树习题由蒲公英阅读网整理提供，版权归原作者、原出处所有。

    Copyright © 蒲公英阅读网 All Rights Reserved.