树和二叉树作业(一)

第五章树和二叉树一、单项选择题1．关于二叉树的下列说法正确的是 (1)。

A．二叉树的度为2 B．二叉树的度可以小于2C．每一个结点的度都为2 D．至少有一个结点的度为2．设深度为h(h>0)的二叉树中只有度为0和度为2的结点，则此二叉树中所含的结点总数至少为（2）。

A．2h B．2h-1 C．2h+1 D．h+13．在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为 (3) 。

A．3 B．4 C．5 D．64．若一棵完全二叉树中某结点无左孩子，则该结点一定是 (4) 。

A.度为1的结点 B．度为2的结点 C．分支结点 D．叶子结点5．深度为k的完全二叉树至多有 (5) 个结点，至少有 (6) 个结点。

A．2k-1-1 B．2k-1 C．2k-1 D．2k6．前序序列为ABC的不同二叉树有 (7) 种不同形态。

A．3 B．4 C．5 D．67．若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其后序序列为 (8) ，层次序列为 (9) 。

A．BCAGFED B．DAEBCFG C．ABCDEFG D．BCAEFGD8．在具有200个结点的完全二叉树中，设根结点的层次编号为1，则层次编号为60的结点，其左孩子结点的层次编号为 (10) ，右孩子结点的层次编号为 (11) ，双亲结点的层次编号为 (12)。

A．30 B．60 C．120 D．1219．遍历一棵具有n个结点的二叉树，在前序序列、中序序列和后序序列中所有叶子结点的相对次序 (13) 。

A.都不相同 B．完全相同 C．前序和中序相同 D．中序与后序相同10．在由4棵树组成的森林中，第一、第二、第三和第四棵树组成的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为（14），根结点的右子树中结点个数为 (15) 。

A．20 B．29 C．30 D．3511.具有n个结点(n>1)的二叉树的前序序列和后序序列正好相反，则该二叉树中除叶子结点外每个结点 (16) 。

数据结构树和二叉树习题一、树的基本概念1.请简要描述树的基本概念及其特点。

答：树是由n(n≥0)个节点组成的有限集合。

其中：-若n=0，则为空树。

-若n＞0，则树有且仅有一个称为根的节点，其他节点可以分为多个互不相交的有限集合，每个集合本身又是一棵树，称之为根的子树。

树的特点包括：-每个节点存放的数据可以是同种或不同种的数据类型。

-每个节点最多有一个父节点和多个子节点。

2.请列举树的应用场景。

答：树的应用场景包括但不限于以下几个方面：-文件系统：操作系统中的文件系统通常使用树来组织文件和目录。

-数据库：数据库中的索引通常使用树来存储和组织数据。

-编译原理：编译器使用语法树来解析源代码。

-社交网络：社交网络中的关注和粉丝关系可以表示为树。

二、二叉树3.请定义二叉树。

答：二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

4.请画出以下二叉树的结构图：A/\BC/\/\DEFG答：以下是该二叉树的结构图：A/\BC/\/\DEFG5.请写出以下二叉树的前序遍历、中序遍历和后序遍历结果：/\23/\45答：-前序遍历结果：1,2,4,5,3-中序遍历结果：4,2,5,1,3-后序遍历结果：4,5,2,3,1三、二叉树的操作6.请实现二叉树的插入操作。

答：以下是二叉树的插入操作的示例代码：```class Node:def __init__(self, value):self.value = valueself.left = Noneself.right = Nonedef insert(root, value):if root is None:root = Node(value)else:if value < root.value:if root.left is None:root.left = Node(value)else:insert(root.left, value)else:if root.right is None:root.right = Node(value)else:insert(root.right, value)```7.请实现二叉树的查找操作。

第6章树和二叉树作业1、假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。

已知一棵树的树边集合为{ (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) } ，用树型表示法表示该树，并回答下列问题：①哪个是根结点? 哪些是叶子结点? 哪个是g的双亲? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孙? 哪些是e的兄弟? 哪些是f 的兄弟?②b和n的层次各是多少? 树的深度是多少? 以结点c为根的子树的深度是多少?2、一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。

如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：①各层的结点数是多少?②编号为i的结点的双亲结点(若存在)的编号是多少?③编号为i的结点的第j个孩子结点(若存在)的编号是多少?④编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?3、设有如图6-27所示的二叉树。

①分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。

②写出该二叉树的先序、中序、后序遍历序列。

4、已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。

5、设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG 和DECBHGFA ，请画出这棵二叉树，然后给出该树的先序序列。

6、已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif 和gdbkeihfca，请画出这棵二叉树对应的中序线索树和后序线索树。

7、以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法。

8、设图6-27所示的二叉树是森林F所对应的二叉树，请画出森林F。

9、设有一棵树，如图6-28所示。

①请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。

1、括号的匹配（表达式的合法性检查）[问题描述]假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。

请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。

假设表达式长度小于255，左圆括号少于20个。

[问题分析]假设输入的字符串存储在c中（var c:string[255]）。

我们可以定义一个栈：var s:array[1..maxn] of char;top:integer;用它来存放表达式中从左往右的左圆括号（maxn=20）。

算法的思路为：顺序（从左往右）扫描表达式的每个字符c[i]，若是“（”，则让它进栈；若遇到的是“）”，则让栈顶元素出栈；当栈发生下溢或当表达式处理完毕而栈非空时，都表示不匹配，返回“NO”；否则表示匹配，返回“YES”。

[参考程序]program lx5;const maxn=20;var c:string;function judge(c:string):boolean;var s:array[1..maxn] of char;top,i:integer;ch:char;beginjudge:=true;top:=0;i:=1;ch:=c[i];while ch<>'@' dobeginif (ch='(') or (ch=')') thencase ch of'(' : begin top:=top+1;s[top]:='(' end;')' : if top>0 then top:=top-1else begin judge:=false;exit end;end;i:=i+1;ch:=c[i];end;if top<>0 then judge:=false;end;begin {main}assign(input,'match.in');assign(output,'match.out');reset(input);rewrite(output);readln(c);if judge(c) then writeln('YES') else writeln('NO');close(input);close(output);end.2、编程把中缀表达式转换成后缀表达式[问题描述]输入一个中缀表达式，编程输出其后缀表达式，要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序一致。

第六章树和二叉树作业一、选择题（每题2分，共24分）。

1. 一棵二叉树的顺序存储情况如下：树中，度为2的结点数为（ C ）。

A．1 B．2 C．3 D．42. 一棵“完全二叉树”结点数为25，高度为（B ）。

A．4 B．5 C．6 D．不确定3．下列说法中，（B ）是正确的。

A. 二叉树就是度为2的树B. 二叉树中不存在度大于2的结点C. 二叉树是有序树D. 二叉树中每个结点的度均为24.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是（B ）。

A. CABDEFGB. BCDAEFGC. DACEFBGD. ADBCFEG5．线索二叉树中的线索指的是（C ）。

A．左孩子 B.遍历 C.指针 D.标志6. 建立线索二叉树的目的是（A ）。

A. 方便查找某结点的前驱或后继B. 方便二叉树的插入与删除C. 方便查找某结点的双亲D. 使二叉树的遍历结果唯一7. 有 D ）示意。

A.B.C.D.8. 一颗有2046个结点的完全二叉树的第10层上共有（B ）个结点。

A. 511B. 512C. 1023D. 10249. 一棵完全二叉树一定是一棵（A ）。

A. 平衡二叉树B. 二叉排序树C. 堆D. 哈夫曼树10．某二叉树的中序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ C ）的二叉树。

A ．空或只有一个结点B ．高度等于其结点数C ．任一结点无左孩子D ．任一结点无右孩子11．一棵二叉树的顺序存储情况如下：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D E 0 F 0 0 G H 0 0 0 X结点D 的左孩子结点为（ D ）。

A ．EB ．C C ．FD ．没有12．一棵“完全二叉树”结点数为25，高度为（ B ）。

A ．4B ．5C ．6D ．不确定二、填空题（每空3分，共18分）。

1. 树的路径长度：是从树根到每个结点的路径长度之和。

对结点数相同的树来说，路径长度最短的是 完全 二叉树。

1、树最适合用来表示（）。

A.元素之间无联系的数据B.元素之间具有层次关系的数据C.无序数据元素D.有序数据元素正确答案：B2、现有一“遗传”关系，设x是y的父亲，则x可以把他的属性遗传给y。

表示该遗传关系最适合的数据结构为（）。

A.线性表B.树C.数组D.图正确答案：B3、一棵节点个数为n、高度为h的m（m≥3）次树中，其分支数是（）。

A.n+hB.h-1C.n-1D.nh正确答案：C4、若一棵3次树中有2个度为3的节点，1个度为2的节点，2个度为1的节点，该树一共有（）个节点。

A.11B.5C.8D.10正确答案：A解析： A、对于该3次树，其中有n3=2，n2=1，n1=2，总分支数=总度数=n-1，总度数=1×n1+2×n2+3×n3=10，则n=总度数+1=11。

5、设树T的度为4，其中度为1、2、3、4的节点个数分别为4、2、1、1，则T中的叶子节点个数是（）。

A.6B.8C.7D.5正确答案：B解析： B、这里n1=4，n2=2，n3=1，n4=1，度之和=n-1=n1+2n2+3n3+4n4=15，所以n=16，则n0=n-n1-n2-n3-n4=16-8=8。

6、有一棵三次树，其中n3=2，n2=1，n0=6，则该树的节点个数为（）。

A.9B.12C.大于等于9的任意整数D.10正确答案：C解析： C、n=n0+n1+n2+n3=6+n1+1+2=9+n1。

7、假设每个节点值为单个字符，而一棵树的后根遍历序列为ABCDEFGHIJ，则其根节点值是（）。

A.JB.BC.以上都不对D.A正确答案：A8、一棵度为5、节点个数为n的树采用孩子链存储结构时，其中空指针域的个数是（）。

A.4nB.4n-1C.4n+1D.5n正确答案：C解析： C、总指针数=5n，非空总指针数=分支数=n-1，空指针域的个数=5n-(n-1)=4n+1。

9、有一棵三次树，其中n3=2，n2=2，n1=1，该树采用孩子兄弟链存储结构时，则总的指针域数为（）。