习题-树
1.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（a）
的二叉树。
A空或只有一个结点B任一结点无左子树
C高度等于其结点数D任一结点无右子树解：前序遍历：根、左子树、右子树
后序遍历：左子树、右子树、根
2.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加
（ 2 ）。
解：二叉链表中有n个结点时，一定存在2n个指针域，n+1个空链域，则非空链域为n-1个，所以，空链域=非空链域+2
3.假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则度为3、2、
0的结点数分别为_2____、___1___和___6___个。
4.一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) )) 结点f
的层数为（3）。假定根结点的层数为0。
5.一棵完全二叉树按层次遍历的序列为ＡＢＣＤＥＦＧＨＩ，则在
后序遍历中结点Ｂ的直接后继是Ｆ。( yes)
6.树的后根遍历序列等同于该树对应的二叉树的（中序遍历）．
7.具有5层结点的A VL树至少有（9）个结点。
8.在树中，如果从结点K出发，存在两条分别到达K`，K``的长度
相等的路径，则结点K`，K``互为兄弟。（no）
9.一棵二叉树的广义表表示为a(b(c,d),e(f(,g)))，它含有双亲结点
（ 4 ）个，单分支结点（2 ）个，叶子结点（ 3 ）个。
10.二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小
高度是（4 ）。
11.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉
树。( no )
12.若二叉树有7个度为2的结点，试问有（8 ）个终端结点。
13.完全二叉树的某结点若无左孩子，则必是叶结点。( yes )
14.二叉树的后序遍历序列中，任意一个结点均处在其子树结点的后
面。( yes )
15.设结点x和结点y是二叉树T中的任意两个结点，若在先根序列
中x在y之前，而在后根序列中x在y之后，则x和y的关系是（）。
16.树存储时采用双亲表示法时，求某个结点的孩子时需要遍历整个
结构，（yes ）。
17.设一棵二叉树结点的先根序列为ABDECFGH，中根序列为
DEBAFCHG，则二叉树中叶子结点是（E F H）。
18.树存储时采用的二叉链表表示法，又叫做（孩子兄弟表示法）。
19.一棵有n（n≥1）个结点的d叉树，若用多重链表表示，树中每个
结点都有d个链域，则在树的nd个链域中，有n（d-1）+1个是空链域，只有n-1个是非空链域。（yes ）
20.若有一个结点是某二叉树子树的中序遍历序列中的最后一个接
点，则它必是该子树的前序遍历序列中的最后一个结点。( no ) 21.一棵有124个叶结点的完全二叉树，最多有（247 ）个结点.
22.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（500）解：设分支总数变量为b，则n=b+1，得出分支数为1000，是偶数，所以不存在度为1的结点，只有度为2的结点和叶子结点。根据性质3，n0=n2+1,所以1001= n0+n2= 2*n0+1。n0=500。
数据结构树练习题
数据结构－树练习题 一、选择题 1、二叉树的深度为k，则二叉树最多有（ C ）个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1 2、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。 A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ 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、在一棵具有5层的满二叉树中结点总数为（ A ）。 A. 31 B. 32 C. 33 D. 16 6、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。 A. 能 B. 不能 7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ C ）。 A. 3 B. 2 C. 4 D. 5 8、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。 A. 67 B. 68 C. 69 D. 70 9、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A ）。 A. 98 B. 99 C. 50 D. 48 10、表达式a*(b+c)-d的后缀表达式是（ B ）。 A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 12、树最适合用来表示（ C ）。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 13、表达式A*(B+C)/(D-E+F)的后缀表达式是（ C ） A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-F+/ D. ABCDED*+/-+ 14、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 15、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（）个。 A. 15 B. 16 C. 17 D. 47 16、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。 A. 51 B. 23 C. 53 D. 74
安全评价事故树例题
某钢铁集团有限责任公司开展节能降耗和长江清洁生产型工厂工作，于1997年建立工 业煤气和民用煤气工程，使焦炉产生的余气及高炉煤气经过净化、输送、储存、供生产、生 活使用。 煤气含有CO、CO2、N2、H2S等多种成分，是一种易燃、易爆、无色、有毒的气体，如一 旦发生煤气输送管道事故，就会造成严重的人员伤亡和生产事故。因此，对煤气输送管道的 安全监控是实现煤气系统安全生产的关键。因此，该公司组织人员，针对煤气管线在运行过 程中曾经发生过的事故及可能的原因，管线发生穿孔、开裂、造成煤气泄漏事故的情况进行 分析，分析结果如下： 管道存在缺陷、管道腐蚀穿孔、外力破坏、人为操作失误、管线内超压、阀门泄漏等原 因是造成管道穿孔开裂泄漏事故发生的主要原因，管道腐蚀穿孔则是由于腐蚀严重和日常 管理维护不力造成的；外力破坏来自人为破坏或地震、雷电等自然灾害；管道缺陷由材质缺 陷或施工缺陷引起，材质缺陷包括强度设计不合规定、管材选择不当、管材质量差等三种类型，管材质量差是由于制造加工质量差和使用前未检测造成的，施工缺陷则包括安装质量差、焊接质量差、撞击挤压破坏三个原因。 （1）简述事故树分析方法的优缺点； （2）根据以上事故情景，利用事故树分析管线穿孔开裂造成煤气泄漏事故的原因，编 制事故树图，并进行定性分析，排出各基本事件的结构重要度顺序，并计算顶上事件的发 生概率。（各基本事件发生概率相等，均为0.1） 1、①事故树分析是一种图形演绎方式，是故障事件在一定条件下的逻辑推理方法。它可以就某些特定的事故状态作层次深入的分析，分析各层次之间各因素的相互联系与制约关系，即输入（原因）与输出（结果）的逻辑关系，并且用专门的符号标示出。 ②事故树分析能对导致灾害或功能事故的各种因素及其逻辑关系做出全面、简洁和形象的描述，为改进设计、制造安全技术措施提供了依据。 ③事故树分析不仅可以分析某些元件、部件故障对系统的影响，而且可对导致这些元件、部件的特殊原因进行分析。 ④事故树分析即可用于定性分析也可定量计算系统的故障概率及其可靠性参数，为改善评价系统的安全性和可靠性提供定量分析依据。
数据结构查找习题及复习资料
第9章查找 一、单选题 1.对一棵二叉搜索树按（）遍历，可得到结点值从小到大的排列序列。 A. 先序 B. 中序 C. 后序 D. 层次 2.从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂度大致为（）。 A. O(n) B. O(1) C. O(logn) D. O(n2) 3.从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂度为（）。 A. O(n) B. O(1) C. O(logn) D. O(n2) 4.在二叉搜索树中插入一个结点的时间复杂度为（）。 A. O(1) B. O(n) C. O(logn) D. O(n2) 5.分别以下列序列构造二叉搜索树，与用其它三个序列所构造的结果不同的是（）。 A．（100，80，90，60，120，110，130） B.（100，120，110，130，80，60，90） C.（100，60，80，90，120，110，130） D.（100，80，60，90，120，130，110） 6.在一棵AVL树中，每个结点的平衡因子的取值范围是（）。 A. -1~1 B. -2~2 C. 1~2 D. 0~1 7.根据一组关键字（56，42，50，64，48）依次插入结点生成一棵A VL树，当插入到值 为（）的结点时需要进行旋转调整。 A. 42 B. 50 C. 64 D. 48 8.深度为4的A VL树至少有（）个结点。 A．9 B. 8 C. 7 D. 6 9.一棵深度为k的A VL树，其每个分支结点的平衡因子均为0，则该平衡二叉树共有（） 个结点。 A.2k-1-1 B.2k-1+1 C.2k-1 D.2k 10.在A VL树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左 孩子的平衡因子为0，右孩子的平衡因子为1，则应作（）型调整以使其平衡。 A. LL B. LR C. RL D. RR 二、判断题
树和二叉树习题集与答案解析
一、填空题 1. 不相交的树的聚集称之为森林。 2. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树可采用孩子-兄弟链表（二叉链表）做存储结构，目的是利用二叉树的已有算法解决树的有关问题。 3. 深度为k的完全二叉树至少有2 k-1个结点。至多有2 k-1个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2 k-2+1。 4. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为n 2，则有n0= n2+1。 5. 一棵二叉树的第i（i≥1）层最多有2 i-1个结点；一棵有n（n>0）个结点的满二叉树共有（n+1）/2个叶子和（n-1）/2个非终端结点。 6.现有按中序遍历二叉树的结果为abc，问有5种不同形态的二叉树 可以得到这一遍历结果。 7. 哈夫曼树是带权路径最小的二叉树。 8. 前缀编码是指任一个字符的编码都不是另一个字符编码的前缀的一种编码方法，是设计不等长编码的前提。 9. 以给定的数据集合{4，5，6，7，10，12，18}为结点权值构造的Huffman树的加权路径长度是165 。 10. 树被定义为连通而不具有回路的（无向）图。 11. 若一棵根树的每个结点最多只有两个孩子，且孩子又有左、右之分，次序不能颠倒，则称此根树为二叉树。
12. 高度为k，且有个结点的二叉树称为二叉树。 2k-1 满 13. 带权路径长度最小的二叉树称为最优二叉树，它又被称为树。 Huffman 14. 在一棵根树中，树根是为零的结点，而为零的结点是 结点。 入度出度树叶 15. Huffman树中，结点的带权路径长度是指由到之间的路径长度与结点权值的乘积。 结点树根 16. 满二叉树是指高度为k，且有个结点的二叉树。二叉树的每一层i上，最多有个结点。 2k-1 2i-1 二、单选题 1. 具有10个叶结点的二叉树中有(B) 个度为2的结点。 (A)8 (B)9 (C)10 (D)11 2．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_（3）次序的遍历实现编号。 （1）先序（2）中序 （3）后序（4）从根开始按层遍历 3. 由2、3、4、7作为结点权值构造的树的加权路径长度 B 。
事故树分析范例
事故树分析案例 起重作业事故树分析 一、概述 在工矿企业发生的各种类型的工伤事故中，起重伤害所占的比例是比较高的，所以，起重设备被列为特种设备，每二年需强制检测一次。本工程在施工安装、生产检修中使用起重设备。伤害事故的因素很多，在众多的因素中，找出问题的关键，采取最有效的安全技术措施来防止此类事故的发生，最好的方法是对起重机事故采取事故树分析方法，现对“起吊物坠落伤人”进行事故树分析。 二、起重作业事故树分析 1、事故树图 图6-2 起吊物坠落伤人事故树 T——起重物坠落伤人； A1——人与起吊物位置不当；A2——起吊物坠落；
B1——人在起吊物下方；B2——人距离起吊物太近； B3——吊索物的挂吊部位缺陷；B4——吊索、吊具断裂； B5——起吊物的挂吊部位缺陷；B6——司机、挂吊工配合缺陷； B7——起升机构失效；B8——起升绳断裂； B9——吊钩断裂； C1——吊索有滑出吊钩的趋势；C2——吊索、吊具损坏； C3——司机误解挂吊工手势； D1——挂吊不符合要求；D2——起吊中起吊物受严重碰撞； X1——起吊物从人头经过；X2——人从起吊下方经过； X3——挂吊工未离开就起吊；X4——起吊物靠近人经过； X5——吊钩无防吊索脱出装置；X6——捆绑缺陷； X7——挂吊不对称；X8——挂吊物不对； X9——运行位置太低；X10——没有走规定的通道； X11——斜吊；X12——运行时没有鸣铃； X13——司机操作技能缺陷；X14——制动器间隙调整不当； X15——吊索吊具超载；X16——起吊物的尖锐处无衬垫； X17——吊索没有夹紧；X18——起吊物的挂吊部位脱落； X19——挂吊部位结构缺陷；X20——挂吊工看错指挥手势； X21——司机操作错误；X22——行车工看错指挥手势； X23——现场环境照明不良；X24——制动器失效； X25——卷筒机构故障；X26——钢丝磨损；
树结构习题及答案
第5章树 【例5-1】写出如图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-7】如图5-5所示的二叉树，要求： （1）写出按先序、中序、后序遍历得到的结点序列。 （2）画出该二叉树的后序线索二叉树。 解： （1） 先序遍历序列：ABDEFC 中序遍历序列：DEFBAC 后序遍历序列：FEDBCA b a c d e f 图5-5 A B C D E F G H I J 图5-4
（2）其后序线索二叉树如图5-6所示。 5％、、G 、H 的 3.假定一棵三叉树的结点数为50，则它的最小高度为（3.C ）。 A.3 B.4 C.5 D.6 4.在一棵二叉树上第4层的结点数最多为（4.D ）。 第六步： 25 30 9 9 18 7 12 8 15 27 43 图5-13
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.设 10. A. 11. A. 12. A. B. C. D. 13. A. C. 14. A. 15. A. C. 1. 2. 3. 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
数据结构第六章树和二叉树习题及答案
习题六树和二叉树 一、单项选择题 1．以下说法错误的是（） A. 树形结构的特点是一个结点可以有多个直接前趋 B. 线性结构中的一个结点至多只有一个直接后继 C. 树形结构可以表达（组织）更复杂的数据 D. 树（及一切树形结构）是一种”分支层次”结构 E. 任何只含一个结点的集合是一棵树 2. 下列说法中正确的是（） A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中每个结点的度都为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 3. 讨论树、森林和二叉树的关系，目的是为了（） A. 借助二叉树上的运算方法去实现对树的一些运算 B. 将树、森林按二叉树的存储方式进行存储 C. 将树、森林转换成二叉树 D. 体现一种技巧，没有什么实际意义4．树最适合用来表示（） A. 有序数据元素 B .无序数据元素 C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B ．11 C ．15 D ．不确定 6. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F 对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B ．M1+M2 C ．M3 D ．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A．250 B ．500 C ．254 D ．505 E ．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为（） A. 不确定 B . 2n C . 2n+1 D . 2n-1 9．二叉树的第I 层上最多含有结点数为（） I I-1 I-1 I A．2I B ．2 I-1 -1 C ．2 I-1 D ．2 I -1 10．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A.指向最左孩子 B .指向最右孩子 C .空D .非空 12．已知一棵二叉树的前序遍历结果为为（）。 A．CBEFDA B ．FEDCBA 13．已知某二叉树的后序遍历序列是（）。 ABCDEF中序遍历结果 为 C ．CBEDFA D dabec, 中序遍历序列是 CBAEDF则后序遍历的结 果 ．不定 debac , 它的前序遍历是
数据结构课程设计题目
《数据结构》课程设计题目 1. 排序算法的性能分析 问题描述 设计一个测试程序，比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 基本要求 （1）对冒泡排序、直接排序、选择排序、箱子排序、堆排序、快速排序及归并排序算法进行比较。 （2）待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。 （3）输出比较结果。 选做内容 （1）对不同表长进行比较。 （2）验证各算法的稳定性。 （3）输出界面的优化。 2. 排序算法思想的可视化演示—1 基本要求 排序数据随机产生，针对随机案例，对冒泡排序、箱子排序、堆排序、归并算法，提供排序执行过程的动态图形演示。 3. 排序算法思想的可视化演示—2 基本要求 排序数据随机产生，针对随机案例，，对插入排序、选择排序、基数排序、快速排序算法，提供排序执行过程的动态图形演示。 4. 线性表的实现与分析 基本要求 ①设计并实现线性表。 ②线性表分别采取数组（公式化描述）、单链表、双向链表、间接寻址存储方 式 ③针对随机产生的线性表实例，实现线性表的插入、删除、搜索操作动态演示(图 形演示)。 5. 等价类实现及其应用 问题描述：某工厂有一台机器能够执行n个任务，任务i的释放时间为r i（是一个整数），最后期限为d i（也是整数）。在该机上完成每个任务都需要一个单元的时间。一种可行的调
度方案是为每个任务分配相应的时间段，使得任务i的时间段正好位于释放时间和最后期限之间。一个时间段不允许分配给多个任务。 基本要求： 使用等价类实现以上机器调度问题。 等价类分别采取两种数据结构实现。 6. 一元稀疏多项式计算器 问题描述 设计一个一元稀疏多项式简单计算器。 基本要求 一元稀疏多项式简单计算器的基本功能是： （1）输入并建立多项式； （2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，…,c n，e n，其中n是多项式的项数，c i，e i，分别是第i项的系数和指数，序列按指数降序排序； （3）多项式a和b相加，建立多项式a+b； （4）多项式a和b相减，建立多项式a-b； （5）计算多项式在x处的值； （6）计算器的仿真界面（选做） 7. 长整数的代数计算 问题描述 应用线性数据结构解决长整数的计算问题。设计数据结构完成长整数的表示和存储，并编写算法来实现两长整数的加、减、乘、除等基本代数运算。 基本要求 ①长整数长度在一百位以上。 ②实现两长整数在取余操作下的加、减、乘、除操作，即实现算法来求解a+b mod n, a-b mod n, a?b mod n, a÷b mod n。 ③输入输出均在文件中。 ④分析算法的时空复杂性。 8. 敢死队问题。 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 要求：至少采用两种不同的数据结构的方法实现。 9. 简单计算器
树结构习题及答案
第5章 树 【例5-1】写出如图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-7】如图5-5所示的二叉树,要求: (1)写出按先序、中序、后序遍历得到的结点序列。 (2)画出该二叉树的后序线索二叉树。 解: b a c d e f 图5-5 A B C D E F G H I J 图5-1 图5-4
(1) 先序遍历序列:ABDEFC 中序遍历序列:DEFBAC 后序遍历序列:FEDBCA (2)其后序线索二叉树如图5-6所示。 C、D、 的结点 图5-13 第六步: 30 27 43
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、√)
树练习题(答案)
《树》练习题 一、单项选择题 1、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1 的结点数为2个，则度为0的结点数为（）个。 A. 4 B. 5 C. 6 D. 7 2、假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数 为（）个。 A. 15 B. 16 C. 17 D. 47 3、假定一棵三叉树的结点数为50，则它的最小高度为（）。（根为第0层） A. 3 B. 4 C. 5 D. 6 4、在一棵二叉树上第3层的结点数最多为（）（根为第0层）。 A. 2 B. 4 C. 6 D. 8 5、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点 R[i]若有左孩子，其左孩子的编号为结点（）。（若存放在R[0..n-1]则左孩子R[2i+1]） A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1] 6、将含100个结点的完全二叉树，按照从上层到下层、同层从左到右的次序依次给它 们编以从0开始的连续自然数，则编号为40的结点X的双亲的编号为( )。 A.19 B.20 C. 21 D.39 7、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为 （）。 A. 24 B. 48 C. 72 D. 53 8、设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（）。 A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孙 9、如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（）。 A. 中序 B. 前序 C. 后序 D. 层次序 10、下面叙述正确的是（）。 A. 二叉树不是树 B. 二叉树等价于度为2的树 C. 完全二叉树必为满二叉树 D. 二叉树的左右子树有次序之分 11、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 12、已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（）。 A. 1 B. 2 C. 3 D. 4 13、下列图示的顺序存储结构表示的二叉树是( )。
二叉树练习题答案
一、下面是有关二叉树的叙述，请判断正误 （∨）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中 只有n—1个非空指针域。 （ X ）2.二叉树中每个结点的两棵子树的高度差等于1。 （∨）3.二叉树中每个结点的两棵子树是有序的。 （ X ）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （ X）5.二叉树中所有结点个数是2k-1-1，其中k是树的深度。 （ X ）6.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ X ）7.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最 多能有2i－1个结点。 （∨）8.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （ X ）9. 具有12个结点的完全二叉树有5个度为2的结点。 二、填空 1．由３个结点所构成的二叉树有 5 种形态。 2. 一棵深度为6的满二叉树有 26-33 个分支结点和 32 个叶子。 3．一棵具有２５７个结点的完全二叉树，它的深度为 9 。
4. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。（分析：完全二叉树中三种节点个数n0，n1，n2,其中 n1为0或1；n0=n2+1；总节点个数N=n0+n1+n2=n0+n1+n0-1=2*n0-1+n1.由此推 出当完全二叉树中节点个数为偶数时n1为1，否则为0，则可计算本题） 5. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉 树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即 按 LRN 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法 相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 FEGHDCB 。 6. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度 是 (1+2)*3+3*2+(4+5)*2= 33 。 7.一个深度为h的二叉树最多有 2h-1 结点，最少有 h 结点。
语言学课后习题树形图
8.（c）the argument against the proposals PP NP P NP Det N Det N against the (d)already above the windows PP AdvP P NP Adv Det N already above the window
NP Infl VP Det AP N pst V PP A P NP Det AP N A huge moon hung in the black sky (C) The man examined his car carefully yeseterday S NP Infl VP Det N pst V NP AdvP Det N AdvP Adv Adv A man examined his car carefully yesterday 10．（b）Helen put on her clothes and went out S
N pst V PP Con V PP P NP P Det N Helen put on her clothes and went out c)Mary is fond of literature but tired of statistics. S NP Infl VP N Pre V AP Con AP A PP A PP P NP P NP N Mary is fond of literature but tired of statistics 11.(b) Gerry belives the fact that Anna fluncked the English exam. S NP Infl VP
数据结构练习题--树(题)
第六章树 一．名词解释： 1 树 2。结点的度 3。叶子 4。分支点 5。树的度 6．父结点、子结点 7兄弟 8结点的层数 9树的高度 10 二叉树 11 空二叉树 12 左孩子、右孩子 13孩子数 14 满二叉树 15完全二叉树 16 先根遍历 17 中根遍历 18后根遍历 19二叉树的遍历 20 判定树 21 哈夫曼树 二、填空题 1、树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。 对树上任一结点X来说，X是它的任一子树的根结点惟一的________。 2、一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是B 的________ 3、一般的，二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______ 的二叉树、同时有______的二叉树五种基本形态。 4、二叉树第i(i>=1)层上至多有______个结点。 5、深度为k(k>=1)的二叉树至多有______个结点。 6、对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。 7、满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉 树，但反之不然。 8、具有n个结点的完全二叉树的深度为______。 9、如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有： （1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。 （2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。 （3）若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。 10.二叉树通常有______存储结构和______存储结构两类存储结构。 11.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。 12.对二叉链表的访问只能从______指针开始，若二叉树为空，则______=NULL. 13.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指针，或者是______。 14.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。 17．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。 Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为0*/ {if(t!=NULL) {if((t->lchild==NULL)&&(t->rchild==NULL))________; countleaf(t->lchild,&count); ________ } } 18．一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成________、________、________三项“子任务”。 19．若以D、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有：
数据结构第六章 树和二叉树课后习题答案
第六章课后习题 6、1、各层的结点数目是：K 2、编号为n的结点的双亲结点是：<=(n-2)/k的最大整数 3、编号为n的结点的第i个孩子结点编号是：k*(n-1)+1+i 4、编号为n的结点有右兄弟的条件是：(n-1)能被k整除 右兄弟的编号是：n+1. 7、1、先序序列和中序序列相同：空二叉树或没有左子树的二叉树。 2、中序序列和后序序列相同：空二叉树或没有右子树的二叉树。 3、先序序列和后序序列相同：空二叉树或只有根的二叉树。 9、中序序列：BDCEAFHG和后序序列：DECBHGFA的二叉树为： A B F C G D E H 先序序列：ABCDEFGH 算法设计： 3、typedef struct { int data[100]; int top; }seqstack; seqstack *s; Perorder(char a[],int n) { int i=1,count=1; s->top=-1;
if(n==0)return(0); else { if(I<=n) { s->top++; s->data[s->top]=a[I]; } while(count
《数据结构与操作系统》试题.doc
谢谢阅读一、单项选择题：1～40小题，每小题2分，共80分。在每小题给出的四 个选项中，请选出一项最符合题目要求的。 1.在下面的程序段中，时间复杂度为（）。 int fun( int n) { if( n = = 1 ) return 1; return n * fun( n - 1 ); } A．O( 2n ) B．0(nlogn) C．0(n2) D．O(n) 2.下列排序算法中，平均时间复杂度最小的是（）。 A．归并排序B．起泡排序 C．简单选择排序 D．直接插入排序 3.关于线性表的描述正确的是（）。 A. 采用顺序存储时，随机存取的时间复杂度是O(1) B. 采用链式存储时，随机存取的时间复杂度是O(1) C. 采用顺序存储时，其存储地址一定是不连续的 D. 采用链式存储时，其存储地址一定是不连续的 4.往队列中输入序列{1,2,3,4}，然后出队1个数字，则出队的数字是（）。 A．4 B．3 C．1 D．不确定 5.往栈中输入序列{1,2,3,4}，然后出栈1个数字，则出栈的数字是（）。 A．4 B．3 C．1 D．不确定 6.假设二叉排序（查找）树上有n个节点，树的高度为h，则查找的平均 时间复杂度是（）。 A．O( n ) B．0(nlogn) C．0(logn) D．O(h) 7.有10个节点的无向图，至少需要多少条边才能成为一个连通图（）。 A．5 B．45 C．9 D．10 8.关于邻接矩阵，下列说法中错误的是（）。 A．有向图的邻接矩阵不一定是对称矩阵 B. 无向图的邻接矩阵不一定是对称矩阵 C．若图G的邻接矩阵是对称的，则G不一定是无向图 D．若图G的邻接矩阵是对称的，则G不一定是有向图 9.折半查找算法中查找的时间复杂度是（）。 A．O( n ) B．0(nlogn) C．0(logn) D．O(n2) 谢谢阅读
树结构习题及答案
【例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所示的二叉树，试分别写出它的顺序表示和链接表示（二叉链表）。 解： （2）该二叉树的二叉链表表示如图5-4所示。
【例5-6】试找出满足下列条件的所有二叉树： （1）先序序列和中序序列相同； （2）中序序列和后序序列相同； （3）先序序列和后序序列相同。 解： （1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树； （2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树； （3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。 【例5-7】如图5-5所示的二叉树，要求： （1）写出按先序、中序、后序遍历得到的结点序列。 （2）画出该二叉树的后序线索二叉树。 解： （1） 先序遍历序列：ABDEFC 中序遍历序列：DEFBAC 后序遍历序列：FEDBCA （2）其后序线索二叉树如图5-6所示。 b a c d e f 图5-5 图5-6
计算机习题-树
1.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（b） 的二叉树。 A空或只有一个结点B任一结点无左子树 C高度等于其结点数D任一结点无右子树解：前序遍历：根、左子树、右子树 后序遍历：左子树、右子树、根 2.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加 （ 2 ）。 解：二叉链表中有n个结点时，一定存在2n个指针域，n+1个空链域，则非空链域为n-1个，所以，空链域=非空链域+2 3.假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则度为3、2、 0的结点数分别为_2____、___1___和___6___个。 4.一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) )) 结点f 的层数为（3）。假定根结点的层数为0。 5.一棵完全二叉树按层次遍历的序列为ＡＢＣＤＥＦＧＨＩ，则在 后序遍历中结点Ｂ的直接后继是Ｆ。( yes) 6.树的后根遍历序列等同于该树对应的二叉树的（中序遍历）． 7.具有5层结点的A VL树至少有（9）个结点。 8.在树中，如果从结点K出发，存在两条分别到达K`，K``的长度 相等的路径，则结点K`，K``互为兄弟。（no） 9.一棵二叉树的广义表表示为a(b(c,d),e(f(,g)))，它含有双亲结点 （4 ）个，单分支结点（2 ）个，叶子结点（3 ）个。
10.二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小 高度是（4 ）。 11.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉 树。( no ) 12.若二叉树有7个度为2的结点，试问有（8 ）个终端结点。 13.完全二叉树的某结点若无左孩子，则必是叶结点。( yes ) 14.二叉树的后序遍历序列中，任意一个结点均处在其子树结点的后 面。( yes ) 15.设结点x和结点y是二叉树T中的任意两个结点，若在先根序列 中x在y之前，而在后根序列中x在y之后，则x和y的关系是（）。 16.树存储时采用双亲表示法时，求某个结点的孩子时需要遍历整个 结构，（yes ）。 17.设一棵二叉树结点的先根序列为ABDECFGH，中根序列为 DEBAFCHG，则二叉树中叶子结点是（E F H）。 18.树存储时采用的二叉链表表示法，又叫做（孩子兄弟表示法）。 19.一棵有n（n≥1）个结点的d叉树，若用多重链表表示，树中每个 结点都有d个链域，则在树的nd个链域中，有n（d-1）+1个是空链域，只有n-1个是非空链域。（yes ） 20.若有一个结点是某二叉树子树的中序遍历序列中的最后一个接 点，则它必是该子树的前序遍历序列中的最后一个结点。( no ) 21.一棵有124个叶结点的完全二叉树，最多有（247 ）个结点.
二叉树习题及答案
1.设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数？ 1根据“二叉树的第i层至多有2^(i ? 1)个结点;深度为k的二叉树至多有2^k ? 1个结点(根结点的深度为1)”这个性质: 因为2^9-1 < 699 < 2^10-1 ,所以这个完全二叉树的深度就是10,前9层就是一个满二叉树, 这样的话,前九层的结点就有2^9-1=511个;而第九层的结点数就是2^(9-1)=256 所以第十层的叶子结点数就是699-511=188个; 现在来算第九层的叶子结点个数。 由于第十层的叶子结点就是从第九层延伸的,所以应该去掉第九层中还有子树的结点。因为第十层有188个,所以应该去掉第九层中的188/2=94个; 所以,第九层的叶子结点个数就是256-94=162,加上第十层有188个,最后结果就是350个 2完全二叉树:若二叉树中最多只有最下面两层的结点的度可以小于2,并且最下面一层的结点(叶结点)都依次排列在该层最左边的位置上,这样的二叉树为完全二叉树。 比如图: 完全二叉树除叶结点层外的所有结点数(叶结点层以上所有结点数)为奇数,此题中,699就是奇数,叶结点层以上的所有结点数为保证就是奇数,则叶结点数必就是偶数,这样我们可以立即选出答案为B！ 如果完全二叉树的叶结点都排满了,则就是满二叉树,易得满二叉树的叶结点数就是其以上所有层结点数+1比如图: 此题的其实就是一棵满二叉树,我们根据以上性质,699+1=700,700/2=350,即叶结点数为350,叶结点层以上所有结点数为350-1=349。 3完全二叉树中,只存在度为2的结点与度为0的结点,而二叉树的性质中有一条就是:n0=n2+1;n0指度为0的结点,即叶子结点,n2指度为2的结点,所以2n2+1=699 n2=349;n0=350 2.在一棵二叉树上第5层的结点数最多就是多少 一棵二叉树,如果每个结点都就是就是满的,那么会满足2^(k-1)1。 所以第5层至多有2^(5-1)=16个结点！ 3、在深度为5的满二叉树中,叶子结点的个数为 答案就是16 ~ 叶子结点就就是没有后件的结点~ 说白了~ 就就是二叉树的最后一层~ 深度为K的二叉树~ 最多有2^k-1个结点~ 最多有2^(k-1)个结点~ 所以此题~ 最多有2^5-1=31个结点~ 最多有2^(5-1)=16个叶子结点~ 4、某二叉树中度为2的结点有18个,则该二叉树中有几个叶子结点？ 结点的度就是指树中每个结点具有的子树个数或者说就是后继结点数。 题中的度为2就是说具有的2个子树的结点; 二叉树有个性质:二叉树上叶子结点数等于度为2的结点数加1。 5、在深度为7的满二叉树中,度为2的结点个数为多少, 就就是第一层只有一个节点,她有两个子节点,第二层有两个节点,她们也都有两个子节点以此类推,所以到第6层,就有2的5次方个节点,她们都有两个子节点 最后第7层都没有子节点了。因为就是深度为7的。 所以就就是1+2+4+8+16+32了