第六章树 名词解释 树2。结点的度3。叶子 分支点5。树的度 6.父结点、子结点7兄弟8结点的层数9树的高度10二叉树 11空二叉树12左孩子、右孩子13孩子数14满二叉树15完全二叉树 16先根遍历17中根遍历18后根遍历19二叉树的遍历20判定树 1哈夫曼树 填空题 1、树(及一切树形结构)是一种“ 结构。在树上, 结点没有直接前趋 对树上任一结点X来说,X是它的任一子树的根结点惟一的 、一棵树上的任何结点(不包括根本身)称为根的 。若B是A的子孙,则称A是B 的 3、一般的,二叉树有二叉树、的二叉树、只有的二叉树、只有 的二叉树、同时有的二叉树五种基本形态。 4、二叉树第i(i>=1)层上至多有 个结点。 5、深度为kk>=1)的二叉树至多有个结点 6、对任何二叉树,若度为2的节点数为n2,则叶子数n= 7、满二叉树上各层的节点数已达到了二叉树可以容纳的 满二叉树也是 二叉 树,但反之不然。 8、具有n个结点的完全二叉树的深度为 9、如果将一棵有n个结点的完全二叉树按层编号,则对任一编号为i(1n,则结点X无 且无 否则,X的左孩子 LCHILD(X)的编号为 (3)若2i+1>n,则结点X无:否则,X的右孩子 RCHILD(X)的编号为 0.二叉树通常有存储结构和 存储结构两类存储结构 11.每个二叉链表的访问只能从结点的指针,该指针具有标识二叉链表的作用。 12.对二叉链表的访问只能从指针开始,若二叉树为空,则=NUL 13.二叉链表中每个存储结点的每个指针域必须有一个值,这个值或者是 的指 针,或者是 14.具有n个结点的二叉树中,一共有 个指针域,其中只有 个用来指向结点 的左右孩子,其余的 个指针域为NULL。 15.二叉树有不同的链式存储结构,其中最常用的是 16.可通过在非完全二叉树的“残缺”位置上增设“ 将其转化为完全二叉树。 17.以下程序段采用先根遍历方法求二叉树的叶子数,请在横线处填充适当的语句 Void countleaf( bitreptr t,int* count)/*根指针为t,假定叶子数 count的初值为 lif(t!=NULL lif((t->lchild==NULL)&&(t->rchild==NULL)) countleaf(t->lchild, &count) 18.一棵二叉树由根、左子树和右子树三部分组成,因此对二叉树的遍历也可相应地分解成
1 第六章 树 一．名词解释： 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(1n，则结点 X 无______且无______；否则，X 的左孩子 LCHILD(X)的编号为 ______。 （3） 若 2i+1>n，则结点 X 无______；否则，X 的右孩子 RCHILD(X)的编号为______。 10.二叉树通常有______存储结构和______存储结构两类存储结构。 11.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。 12.对二叉链表的访问只能从______指针开始，若二叉树为空，则______=NULL. 13.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指 针，或者是______。 14.具有 n 个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点 的左右孩子，其余的________个指针域为 NULL。 15．二叉树有不同的链式存储结构，其中最常用的是________与________。 16．可通过在非完全二叉树的“残缺”位置上增设“________”将其转化为完全二叉树。 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．一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成
项“子任务”。 9.若以D、L、R分别表示二叉树的三项子任务,限定“先左后右”,这样可能的次序有: 种,按这三种次序进行的遍历分别称为 0.树的主要遍历方法有 等三种 判定树的每个 包含一个条件,对应于一次比较或判断,每个 对应一种 分类结果。 22.设定T是一判定树,其终端结点为n n。每个终端结点ni对应的百分为pi(通 常将p;称为n的权)。再假定n的祖先数为1;,这样,按T进行分类的平均比较次数为 23.根据文字说明,请在以下横线处填充适当的语句。 采用静态链表作存储结构,设置一个大小为2n-1的数组,令数组每个元素由四个域组成 Wt是结点的权值; Child、 rchild分别为结点的左、右孩子指针; parent是结点的双亲在 数组中的下标。其数组元素类型定义如下: typedef struct Float wt /*权值*/ nt parent, Child rchild /*指针域*/ )nod typedef node hftree [2*n-1 在这种存储结构上的哈夫曼算法可描述如下: void Huff man(int k, float w[k], hftree T) /*求给定权值W的哈夫曼树T*/ lint i, j,x,y; float mn for(i=0;i<2*k-1;i++) I Tli]. parent=-1: T[i]. lchild=-1: T[i].rchild=-1 Tli. wt=Wli] else Tlil wt=0 for(i=0;i<k-1;i++) x=0;y=0; m=maxint: n=maxint if((t[j]. wt<m)&&(T[j]. parent==-1))n=m;y= else if((T[j]. wt<n)&&(T[jl. parint==-1))In=tLj]. wt; y=j: K TIx]. parent= TLy]. parent TIk+i].wt= TLk+i]. lchild= TLk+i]. rchild 24.若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点,则它必是该子树的后根 遍历序列中的 个结点。 在 遍历二叉树的序列中,任何结点的子树上的所有结点,都是直接跟在该结点 6.具有n个结点的完全二叉树,若按层次从上到下、从左到右对其编,号(根结点为1号), 则编号最大的分支结点序号是 编号最小的分支结点序号是 编号最大的 叶子结点序号是 ,编号最小的叶子结点序号是 27.二叉树的先根遍历序列中,除根结点外,任一结点均处在其双亲结点的
2 ________、________、________三项“子任务”。 19．若以 D、L、R 分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有： ________、________、________三种，按这三种次序进行的遍历分别称为________、________、 ________。 20．树的主要遍历方法有________、________、________等三种。 21．判定树的每个________包含一个条件，对应于一次比较或判断，每个________对应一种 分类结果。 22．设定 T 是一判定树，其终端结点为 n1,……，nk。每个终端结点 ni 对应的百分为 pi（通 常将pi称为n1的权）。再假定ni的祖先数为li，这样，按T进行分类的平均比较次数为________。 23．根据文字说明，请在以下横线处填充适当的语句。 采用静态链表作存储结构，设置一个大小为 2n-1 的数组,令数组每个元素由四个域组成： wt 是结点的权值；lchild、rchild 分别为结点的左、右孩子指针；parent 是结点的双亲在 数组中的下标。其数组元素类型定义如下： typedef struct {float wt /*权值*/ int parent,lchild rchild; /*指针域*/ }node; typedef node hftree[2*n-1]; 在这种存储结构上的哈夫曼算法可描述如下： void Huffman(int k,float W[k],hftree T) /*求给定权值 W 的哈夫曼树 T*/ {int i,j,x,y; float m,n; for(i=0;i<2*k-1;i++) { T[i].parent=-1;T[i].lchild=-1;T[i].rchild=-1; if(________)T[i].wt=W[i]; else T[i].wt=0 } for(i=0;i<k-1;i++) { x=0;y=0;m=maxint;n=maxint; for(j=0;j<k=i;j++) if((T[j].wt<m)&&(T[j].parent==-1)){n=m;y=________;m=________;x=j;} else if((T[j].wt<n)&&(T[j].parint==-1)){n=T[j].wt;y=j;} T[x].parent=________;T[y].parent=________; T[k+i].wt=________; T[k+i].lchild=________;T[k+i].rchild=________; } 24．若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根 遍历序列中的________个结点。 25．在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点 之后。 26．具有 n 个结点的完全二叉树，若按层次从上到下、从左到右对其编，号（根结点为 1 号）， 则编号最大的分支结点序号是________，编号最小的分支结点序号是________，编号最大的 叶子结点序号是________，编号最小的叶子结点序号是________。 27．二叉树的先根遍历序列中，除根结点外，任一结点均处在其双亲结点的________
28.先根遍历树和先根遍历与该树对应的二叉树,其结果 9.树与二叉树之间最主要的差别是:二叉树中各结点的子树要区分为 和 即使在结点只有一棵子树的情况下,也要明确指出该子树是 还是 0.由 转换成二叉树时,其根结点的右子树总是空的 31.哈夫曼树是带权路径度 的树,通常权值较大的结点离根 2.有m个叶子结点的哈夫曼树,其结点总数为 p00 填空题33 33.一棵树的形状如图填空题33所示,它的根结点是 ,叶子结点是,结点 H的度是,这棵树的度是 这棵树的深度是 结点F的儿子结点 是 结点G的父结点是 34.树的结点数目至少为 二叉树的结点数目至少为 中结点的最大度数允许大于2,而 中结点的最大度数不允许大于2 36.结点最少的树为 ,结点最少的二叉树为 37.若一棵二叉树的叶子数为n,则该二叉树中,左、右子树皆非空的结点个数为。 38.任意一棵具有n个结点的二叉树,若它有m个叶子,则该二叉树上度数为1的结点为 个 9.现有按中序遍历二叉树的结果为ABC,问有 种不同形态的二叉树可以得到这 遍历结果,这些二叉树分别是 40.以数据集{4,5,6,7,10,12,18}为叶结点权值所构造的哈无曼树为 其带 权路径长度为 41.有m个叶子结点的哈夫曼树上的结点数是 42.已知一棵度为3的树有2个度为1的结点,3个度过为2的结点,4个度为3的结点,则 该树中有 个叶子结点 43.设树T的度为4,其中度为1、2、3和4的结点个数分别是4、2、1和1,则T中叶子结 点的个数是 三、单向选择题 以下说法错误的是 ①树形结构的特点是一个结点可以有多个直接前趋 ②线性结构中的一个结点至多只有一个直接后继 ③树形结构可以表达(组织)更复杂的数据 ④树(及一切树形结构)是一种”分支层次"结构 ⑤任何只含一个结点的集合是一棵树 2,以下说法错误的是 3
3 28．先根遍历树和先根遍历与该树对应的二叉树，其结果________。 29．树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为________和________， 即使在结点只有一棵子树的情况下，也要明确指出该子树是________还是________。 30．由________转换成二叉树时，其根结点的右子树总是空的。 31．哈夫曼树是带权路径度________的树，通常权值较大的结点离根________。 32．有 m 个叶子结点的哈夫曼树，其结点总数为________。 33．一棵树的形状如图填空题 33 所示，它的根结点是________，叶子结点是________，结点 H 的度是________，这棵树的度是________，这棵树的深度是________，结点 F 的儿子结点 是________，结点 G 的父结点是________。 34．树的结点数目至少为________，二叉树的结点数目至少为________。 35．________中结点的最大度数允许大于 2，而________中结点的最大度数不允许大于 2。 36．结点最少的树为________，结点最少的二叉树为________。 37．若一棵二叉树的叶子数为 n，则该二叉树中，左、右子树皆非空的结点个数为________。 38．任意一棵具有 n 个结点的二叉树，若它有 m 个叶子，则该二叉树上度数为 1 的结点为 ________个。 39．现有按中序遍历二叉树的结果为 ABC，问有________种不同形态的二叉树可以得到这一 遍历结果，这些二叉树分别是________。 40．以数据集{4，5，6，7，10，12，18}为叶结点权值所构造的哈无曼树为________，其带 权路径长度为________。 41．有 m 个叶子结点的哈夫曼树上的结点数是________。 42．已知一棵度为 3 的树有 2 个度为 1 的结点，3 个度过为 2 的结点，4 个度为 3 的结点，则 该树中有________个叶子结点。 43．设树 T 的度为 4，其中度为 1、2、3 和 4 的结点个数分别是 4、2、1 和 1，则 T 中叶子结 点的个数是________。 三、单向选择题 1． 以下说法错误的是 ( ) ①树形结构的特点是一个结点可以有多个直接前趋 ②线性结构中的一个结点至多只有一个直接后继 ③树形结构可以表达(组织)更复杂的数据 ④树(及一切树形结构)是一种"分支层次"结构 ⑤任何只含一个结点的集合是一棵树 2，以下说法错误的是 ( )
①二叉树可以是空集 ②二叉树的任一结点都有两棵子树 叉树与树具有相同的树形结构 ④二叉树中任一结点的两棵子树有次序之分 3、以下说法错误的是 ①完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 ②在三叉链表上,二叉树的求双亲运算很容易实现 ③在二叉链表上,求根,求左、右孩子等很容易实现 ④在二叉链表上,求双亲运算的时间性能很好 4、以下说法错误的是 ①一般在哈夫曼树中,权值越大的叶子离根结点越近 ②哈夫曼树中没有度数为1的分支结点 ③若初始森林中共有n裸二叉树,最终求得的哈夫曼树共有2n-1个结点 ④若初始森林中共有n裸二叉树,进行2n-1次合并后才能剩下一棵最终的哈夫曼树 5.深度为6的二叉树最多有()个结点 ③32 ④31 6.将含有83个结点的完全二叉树从根结点开始编号,根为1号,后面按从上到下、从左到 右的顺序对结点编号,那么编号为41的双结点编号为 ①42②40 321 ④20 7.任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置( ①肯定发生变化②有时发生变化 ③肯定不发生变化④无法确定 8.设二叉树有n个结点,则其深度为 n-1②n③5 floor(log2n)④无法确定 9.设深度为k的二叉树上只有度为0和度为2的节点,则这类二叉树上所含结点总数最少 ①k+1 ②2k③2k-1④2k+1 10.下列说法正确的是 ①树的先根遍历序列与其对应的二叉树的先根遍历序列相同 ②树的先根遍历序列与其对应的二叉树的后根遍历序列相同 ③树的后根遍历序列与其对应的二叉树的先根遍历序列相同 ④树的后根遍历序列与其对应的二叉树的后根遍历序列相同 11.下列说法中正确的是 ①任何一棵二叉树中至少有一个结点的度为2 ②任何一棵二叉树中每个结点的度都为2 ③任何一棵二叉树中的度肯定等于2 ④任何一棵二叉树中的度可以小于2 12.一棵二叉树满足下列条件:对任意结点,若存在左、右子树,则其值都小于它的左子树 上所有结点的值,而大于右子树上所有结点的值。现采用()遍历方式就可以得到这棵 二叉树所有结点的递增序列 ①先根②中根③后根④层次 13.设森林T中有4棵树,第 、四棵树的结点个数分别是n1,n2,n3,n4,那么当把 森林T转换成一棵二叉树后,且根结点的右子树上有()个结点 ①n-1②m③n1+n2+n3④n2tn3+n
4 ①二叉树可以是空集 ②二叉树的任一结点都有两棵子树 ③二叉树与树具有相同的树形结构 ④二叉树中任一结点的两棵子树有次序之分 3、以下说法错误的是 ( ) ①完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 ②在三叉链表上，二叉树的求双亲运算很容易实现 ③在二叉链表上，求根，求左、右孩子等很容易实现 ④在二叉链表上，求双亲运算的时间性能很好 4、以下说法错误的是 ( ) ①一般在哈夫曼树中，权值越大的叶子离根结点越近 ②哈夫曼树中没有度数为 1 的分支结点 ③若初始森林中共有 n 裸二叉树，最终求得的哈夫曼树共有 2n-1 个结点 ④若初始森林中共有 n 裸二叉树，进行 2n-1 次合并后才能剩下一棵最终的哈夫曼树 5．深度为 6 的二叉树最多有( )个结点 ( ) ①64 ②63 ③32 ④31 6．将含有 83 个结点的完全二叉树从根结点开始编号，根为 1 号，后面按从上到下、从左到 右的顺序对结点编号，那么编号为 41 的双结点编号为 ( ) ①42 ②40 ③21 ④20 7．任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置 ( ) ①肯定发生变化 ②有时发生变化 ③肯定不发生变化 ④无法确定 8．设二叉树有 n 个结点，则其深度为 ( ) ①n-1 ②n ③5floor(log2n) ④无法确定 9．设深度为 k 的二叉树上只有度为 0 和度为 2 的节点，则这类二叉树上所含结点总数最少 （ ）个 ①k+1 ②2k ③2k-1 ④2k+1 10.下列说法正确的是 ( ) ①树的先根遍历序列与其对应的二叉树的先根遍历序列相同 ②树的先根遍历序列与其对应的二叉树的后根遍历序列相同 ③树的后根遍历序列与其对应的二叉树的先根遍历序列相同 ④树的后根遍历序列与其对应的二叉树的后根遍历序列相同 11．下列说法中正确的是 ( ) ①任何一棵二叉树中至少有一个结点的度为 2 ②任何一棵二叉树中每个结点的度都为 2 ③任何一棵二叉树中的度肯定等于 2 ④任何一棵二叉树中的度可以小于 2 12．一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树 上所有结点的值，而大于右子树上所有结点的值。现采用（ ）遍历方式就可以得到这棵 二叉树所有结点的递增序列。 ①先根 ②中根 ③后根 ④层次 13．设森林 T 中有 4 棵树，第一、二、三、四棵树的结点个数分别是 n1,n2,n3,n4,那么当把 森林 T 转换成一棵二叉树后，且根结点的右子树上有（ ）个结点。 ①n1-1 ②n1 ③n1+n2+n3 ④n2+n3+n4
14.森林T中有4棵树,第一、二、三、四棵树的结点个数分别是nl,n2,n3,n4,那么当把森 林T转换成一棵二叉树后,且根结点的左孩子上有()个结点。 ①n ②n③n+n2+n3④n2+n3 15.对含有( 个结点的非空二叉树,采用任何一种遍历方式,其结点访问序列均相 ①0 ④不存在这样的二叉树 16.讨论树、森林和二叉树的关系,目的是为了() ①借助二叉树上的运算方法去实现对树的一些运算 ②将树、森林按二叉树的存储方式进行存储 ③将树、森林转换成二叉树 ④体现一种技巧,没有什么实际意义 17.如图选择题17所示二叉树的中序遍历序列是 ③ dbaefcg ④ debbage 8.已知某二叉树的后续遍历序列是 dabic,中序遍历序列是 dabo,它的前序遍历序列是() ① ached ② deabc ③ decal ④ ceda 19.如果T2是由有序树T转化而来的二叉树,那么T中结点的前序就是T2中结点的() ①前序 ②中序 ③后序 ④层次序 20.如果12是由有序树T转化而来的二叉树,那么T中结点的后序就是T2中结点的() ①前序 ②中序 ③后序 ④层次序 21.某二叉树的前序遍历结点访问顺序是 abdgcefh,中序遍历的结点访问顺序是 dgbaechf 则其后序遍历的结点访问顺序是 ① bdgcefha ② gdbecfha ③④ bdgechfa④ gdbehfca 2.在图选择题22中的二叉树中,()不是完全二叉树
5 14．森林 T 中有 4 棵树，第一、二、三、四棵树的结点个数分别是 n1,n2,n3,n4,那么当把森 林 T 转换成一棵二叉树后，且根结点的左孩子上有（ ）个结点。 ①n1-1 ②n1 ③n1+n2+n3 ④n2+n3+n4 15.对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相 同。 ①0 ②1 ③2 ④不存在这样的二叉树 16．讨论树、森林和二叉树的关系，目的是为了（ ） ①借助二叉树上的运算方法去实现对树的一些运算 ②将树、森林按二叉树的存储方式进行存储 ③将树、森林转换成二叉树 ④体现一种技巧，没有什么实际意义 17．如图选择题 17 所示二叉树的中序遍历序列是（ ） ①abcdgef ② dfebagc ③dbaefcg ④defbagc 18.已知某二叉树的后续遍历序列是 dabec,中序遍历序列是 deabc,它的前序遍历序列是（ ） ①acbed ②deabc ③decab ④cedba 19.如果 T2 是由有序树 T 转化而来的二叉树，那么 T 中结点的前序就是 T2中结点的（ ） ①前序 ②中序 ③后序 ④层次序 20．如果 T2 是由有序树 T 转化而来的二叉树，那么 T 中结点的后序就是 T2 中结点的（ ） ①前序 ②中序 ③后序 ④层次序 21．某二叉树的前序遍历结点访问顺序是 abdgcefh,中序遍历的结点访问顺序是 dgbaechf, 则其后序遍历的结点访问顺序是 （ ） ①bdgcefha ②gdbecfha ③④ bdgechfa ④ gdbehfca 22.在图选择题 22 中的二叉树中，（ ）不是完全二叉树
① ○O 图选择题22 3、二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法() ①正确 ②错误 24、由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法() ①五确 ②错误 25,二叉树是每个结点的度不超过2的有序树的特殊情况,这种说法 ①正确 ②错误 6·树最适合用来表示 ①有序数据元素 ②无序数据元素 ③元素之间具有分支层次关系的数据 ④元素之间无联系的数据 27,深度为5的二叉树至多有()个结点 ①16 ③31 ④I 10 28、在计算递归函数时,如不使用递归过程,则一般情况下必须借助于()数据结构 ①栈 ②树 ③双向队列 ④顺序表 29.堆(Heap)是 ①完全二叉树 ②线性表 ③满二叉树 30、下列说法中正确的是 ①二叉树中任何一个结点的度都为2 ②二叉树的度为2 任何一棵二叉树中至少有一个结点的度为2④一棵二叉树的度可以小于 31、设二叉树根结点的层次为0,一棵高度为h的满二叉树中的结点个数是( ①2 ③2-1 ④2- 32、设二叉树结点的先根序列、中根序列和后根序列中,所有叶子结点的先后顺序() ①都不相同 ②完全相同 ③先序和中序相同,而与后序不同④中序和后序相同,而与先序不同 33·以下说法错误的是 ①存在这样的二叉树,对它采用任何次序的遍历,其结点访问序列均相同 ②二叉树是树的特殊情形 ③由树转换成二叉树,其根结点的右子树总是空的 ④在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树 34、以下说法正确的是 ①先根遍历树和前序遍历与该树对应的二叉树,其结果不同 ②后根遍历树和前序遍历与该树对应的二叉树,其结果不同 ③前序遍历森林和前序遍历与该森林对应的二叉树,其结果相同 6
6 23、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 ( ) ①正确 ②错误 24、由于二叉树中每个结点的度最大为 2，所以二叉树是一种特殊的树，这种说法 ( ) ①五确 ②错误 25，二叉树是每个结点的度不超过 2 的有序树的特殊情况，这种说法 ( ) ①正确 ②错误 26·树最适合用来表示 ( ) ①有序数据元素 ②无序数据元素 ③元素之间具有分支层次关系的数据 ④元素之间无联系的数据 27，深度为 5 的二叉树至多有( )个结点。 ①16 ②32 ③31 ④10 28、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（ ）数据结构 ①栈 ②树 ③双向队列 ④顺序表 29.堆(Heap)是 ( ) ①完全二叉树 ②线性表 ③满二叉树 30、下列说法中正确的是 ( ) ①二叉树中任何一个结点的度都为 2 ②二叉树的度为 2 ③任何一棵二叉树中至少有一个结点的度为 2 ④一棵二叉树的度可以小于 2 31、设二叉树根结点的层次为 0，一棵高度为 h 的满二叉树中的结点个数是（ ） ①2 h ②2 h-1 ③2 h -1 ④2 h+1 -1 32、设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( ) ①都不相同 ②完全相同 ③先序和中序相同，而与后序不同 ④中序和后序相同，而与先序不同 33·以下说法错误的是 ( ) ①存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同 ②二叉树是树的特殊情形 ③由树转换成二叉树，其根结点的右子树总是空的 ④在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树 34、以下说法正确的是 ( ) ①先根遍历树和前序遍历与该树对应的二叉树，其结果不同 ②后根遍历树和前序遍历与该树对应的二叉树，其结果不同 ③前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同
④后序遍历森林和中序遍历与该森林对应的二叉树,其结果不同 35·以下说法正确的是 ①一般来说,若深度为k的n个结点的二叉树具有最小路径长度,那么从根结点到第k-1层 具有最多的结点数为2--1余下的n-2-+1个结点在第k层的任一位置上 ②若有一个结点是某二叉树子树的前序遍历序列中的最后一个结点,则它必是该子树的前序 遍历序列中的最后一个结点 ③若一个结点是某二叉树子树的前序遍历序列中的最后一个结点,则它必是该子树的中序遍 历序列中的最后一个结点。 ④在二叉树中插人结点,该二叉树便不再是二叉树 36、以下说法正确的是 ①若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点,则它必是该子树的前序遍 历序列中的最后一个结点 ②若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点,则它必是该子树的中序离 历序列中的最后一个结点 ③二叉树中,具有两个子女的父结点,在中序遍历序列中,它的后继结点最多只能有一个子 女结点。 ④在二叉树中,具有一个子女结点,在中序遍历序列中,它没有后继子女结点 37、以下说法错误的是 ①哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近 ②若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点,则它必是该子树的后序遍 历序列中的第一个结点。 ③已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树,因为不知道树的根结点 是哪一个。 ④在前序遍历二叉树的序列中,任何结点的子树的所有结点都是直接跟在该结点的之后。 四、简答及应用题 1.简述二叉链表的类型定义 2.简述三叉链表的类型定义。 3.简述孩子链表表示法的类型定义 分别就图简答题4.1中的二叉树和树回答下列问题 (1)哪个是根结点? (2)哪些是叶结点? (3)哪个是G的双亲? (4)哪些是G的祖先? (5)哪些是G的孩子? (6)哪些是E的子孙? (7)哪些是E的兄弟?哪些是C的兄弟? (8)结点B和I的层数分别是多少? (9)树的深度是多少? (10)以结点G为根的子树的深度是多少? (11)树的度数是多少?
7 ④后序遍历森林和中序遍历与该森林对应的二叉树，其结果不同 35·以下说法正确的是 ( ) ①一般来说，若深度为 k 的 n 个结点的二叉树具有最小路径长度，那么从根结点到第 k-1 层 具有最多的结点数为 2 k-1 -1 余下的 n-2 k-1 +1 个结点在第 k 层的任一位置上 ②若有一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点。 ③若一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序遍 历序列中的最后一个结点。 ④在二叉树中插人结点，该二叉树便不再是二叉树 36、以下说法正确的是 ( ) ①若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍 历序列中的最后一个结点。 ②若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序离 历序列中的最后一个结点 ③二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子 女结点。 ④在二叉树中，具有一个子女结点，在中序遍历序列中，它没有后继子女结点。 37、以下说法错误的是 ( ) ①哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 ②若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍 历序列中的第一个结点。 ③已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点 是哪一个。 ④在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。 四、简答及应用题 1．简述二叉链表的类型定义。 2．简述三叉链表的类型定义。 3．简述孩子链表表示法的类型定义。 4．分别就图简答题 4.1 中的二叉树和树回答下列问题 (1)哪个是根结点? (2)哪些是叶结点? (3)哪个是 G 的双亲? (4)哪些是 G 的祖先? (5)哪些是 G 的孩子? (6)哪些是 E 的子孙? (7)哪些是 E 的兄弟? 哪些是 C 的兄弟? (8)结点 B 和 I 的层数分别是多少? (9)树的深度是多少? (10)以结点 G 为根的子树的深度是多少? (11)树的度数是多少？
简答题4,1()二又树 树的孩子歌癥示注示意 5.为什么图简答题5所示的结构都不是树形结构?详细说明理由。 o d o e 图摘签懸5非軻形构示例 6.分别画出含3个结点的树与二叉树的所有不同形态。 7.分别画出图简答题7-1所示二叉树的二叉链表、三叉链表和顺序存储结构 田简賽题7-1 8.分别写出图简答题4.1(a)所示二叉树的先根、中根和后根序列 9.试找出分别满足下列条件的所有二叉树: (1)先根序列和中根序列相同:(2)中根序列和后根序列相同 (3)先根序列和后根序列相同 10.已知一棵二叉树的中根序列和后根序列分别为 BDCEAFHG和 EDCBHGEA,试画出这棵二叉 树 试分别画出图简答题11-1所示树的孩子链表、孩子兄弟链表和静态双亲链表
8 5．为什么图简答题 5 所示的结构都不是树形结构？详细说明理由。 6．分别画出含 3 个结点的树与二叉树的所有不同形态。 7．分别画出图简答题 7-1 所示二叉树的二叉链表、三叉链表和顺序存储结构。 8．分别写出图简答题 4.1（a）所示二叉树的先根、中根和后根序列。 9.试找出分别满足下列条件的所有二叉树： （1） 先根序列和中根序列相同； （2）中根序列和后根序列相同； （ 3 ）先根序列和后根序列相同。 10．已知一棵二叉树的中根序列和后根序列分别为 BDCEAFHG 和 EDCBHGEA，试画出这棵二叉 树。 11． 试分别画出图简答题 11-1 所示树的孩子链表、孩子兄弟链表和静态双亲链表
阳冷饗题11-1 12.分别给出简答题11.1图中树的先根、后根和层次遍历的结点访问序列 13.将图简答题13-1所示的林转换成二叉树 ⊙oob 6⊙ 图筒箐履13-4 14.分别画出图简答题14-1所示各二叉树对应的林。 奥简各题14- 15.给定权值7,18,3,32,5,26,12,8,构造相应的哈夫曼树。 16.试以三种遍历为基础,分别写出在二叉树上查找直接前趋或直接后继的关键操作步骤。 17.已知一棵二叉树的前根序列和中根序列分别为 ABDGHECFIJ及 GDHBEACIJF,请画出这棵 叉树 18.设某密码电文由8个字母组成,每个字母在电文中的出现频率分别是7,19,2,6,32, 3,21,10,试为这8个字母设计相应的哈夫曼编码 19.有一二叉树如图19-1所示,试画出它的顺序存储结构示意图 9
9 12．分别给出简答题 11.1 图中树的先根、后根和层次遍历的结点访问序列。 13．将图简答题 13-1 所示的林转换成二叉树。 14．分别画出图简答题 14-1 所示各二叉树对应的林。 15．给定权值 7，18，3，32，5，26，12，8，构造相应的哈夫曼树。 16．试以三种遍历为基础，分别写出在二叉树上查找直接前趋或直接后继的关键操作步骤。 17．已知一棵二叉树的前根序列和中根序列分别为 ABDGHECFIJ 及 GDHBEACIJF，请画出这棵 二叉树。 18．设某密码电文由 8 个字母组成，每个字母在电文中的出现频率分别是 7，19，2，6，32， 3，21，10，试为这 8 个字母设计相应的哈夫曼编码。 19．有一二叉树如图 19-1 所示，试画出它的顺序存储结构示意图
图筒答题19-1 20.将图简答20-1所示森林转换为二叉树 图简爸题20-1 五,算法设计 1、以二叉链表为存储结构,分别实现二叉树的下列运算 (1) PARENT (BT, X) (2)CREATE(X, LBT RBT) (3) DELLEFT (BT, X) 2.以三叉链表作存储结构重做上题。 3.以二叉链表作存储结构,试编写求二叉树深度的算法 4.一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中,试编写非递归算法对该树进 行先根遍历。 5.试编写算法判断两棵二叉树是否等价。若二叉树T1和T2等价,则们和T2都是空的二叉 时;或T1和T2的根结点的值相同,并且T1的左子树与T2的左子树是等价的,T1的右子树 与T2的右子树是等价的 6.试编写算法交换二叉树中所有结点的左、右子树(自选存储结构)。 7.试编写算法査找二叉链表中数据域值为X的结点(假定各结点的数据域值各不相同),并 打印出X所有祖先的数据域值(提示:利用后根遍历非递归算法)。 8.试以孩子链表为存储结构,实现树数据结构的下列运算: (1) PARENT(T, X) (2) CHILD (T, X, 1): (3)DELETE (T, X, i) 9.试分别以孩子兄弟链表和静态双亲链表为存储结构,重做上题。 0.试分别编写二叉树中根遍历在下列存储结构上的非递归算法 (1)二叉链表 (2)三叉链表(提示:考虑是否需要引入工作栈); 11.试分别编写二叉树后根遍历在下列存储结构上的非递归算法 (1)二叉链表(提示:可在指针进栈的同时将一个标志进栈) (2)在存储结点中增设了标志域的mark:0..2的三叉链表(要求不用工作栈); 12.试编写一个将百分制转换成五分制的算法,要求其时间性能尽可能地高(即平均比较次
10 20．将图简答 20-1 所示森林转换为二叉树。 五，算法设计 1、以二叉链表为存储结构，分别实现二叉树的下列运算: （1）PARENT (BT,X)； （2）CREATE ( X, LBT.RBT)； (3)DELLEFT(BT,X)。 2.以三叉链表作存储结构重做上题。 3．以二叉链表作存储结构，试编写求二叉树深度的算法。 4．一棵 n 个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进 行先根遍历。 5．试编写算法判断两棵二叉树是否等价。若二叉树 T1 和 T2 等价，则 T1 和 T2 都是空的二叉 树；或 T1 和 T2 的根结点的值相同，并且 T1 的左子树与 T2 的左子树是等价的，T1 的右子树 与 T2 的右子树是等价的。 6．试编写算法交换二叉树中所有结点的左、右子树（自选存储结构）。 7．试编写算法查找二叉链表中数据域值为 X 的结点（假定各结点的数据域值各不相同），并 打印出 X 所有祖先的数据域值（提示：利用后根遍历非递归算法）。 8．试以孩子链表为存储结构，实现树数据结构的下列运算： （1）PARENT（T，X）； （2） CHILD (T,X,i)； （3）DELETE(T,X，i)。 9．试分别以孩子兄弟链表和静态双亲链表为存储结构，重做上题。 10．试分别编写二叉树中根遍历在下列存储结构上的非递归算法： （1） 二叉链表； （2） 三叉链表（提示：考虑是否需要引入工作栈）； 11．试分别编写二叉树后根遍历在下列存储结构上的非递归算法： （1） 二叉链表（提示：可在指针进栈的同时将一个标志进栈）； （2） 在存储结点中增设了标志域的 mark:0..2 的三叉链表（要求不用工作栈）； 12．试编写一个将百分制转换成五分制的算法，要求其时间性能尽可能地高（即平均比较次