数据结构与算法设计-树-习题ppt课件

1、具有具有n个顶点的二叉树，共有多少边？个顶点的二叉树，共有多少边？2、假设一个具有、假设一个具有N个顶点，个顶点，K条边的无向图是一个森条边的无向图是一个森林林(NK)，那么该森林有多少棵树？，那么该森林有多少棵树？3、知一棵度为、知一棵度为m的树中有的树中有N1个度为个度为1的节点，的节点，N2个度个度为为2的节点，的节点， Nm个度为个度为m的节点。问该树有多的节点。问该树有多少叶子节点？少叶子节点？4、层数为、层数为k的二叉树中，最大和最小节点数各为多少？的二叉树中，最大和最小节点数各为多少？5、有、有n个节点的二叉树中，有个节点的二叉树中，有m个叶子节点，问非叶个叶子节点，问非叶子节点

2、中度为子节点中度为2和度为和度为1的节点各有多少？的节点各有多少？n-1NKN0 = N2+ 2N3+ + (m-1)Nm+12k-1, kn2 = m-1; n1=n-2m +1BCB假定一棵树的广义表示为假定一棵树的广义表示为(A(B(C，D(E，F，G)，H(I，J)，那么树中所含的结点数为，那么树中所含的结点数为 个，树个，树的深度为的深度为 个，树的度为个，树的度为 。 32、在哈夫曼编码中，假设编码长度只允许小于等于、在哈夫曼编码中，假设编码长度只允许小于等于4，那么除了已对两个字符编码为那么除了已对两个字符编码为0和和10外，还可以最外，还可以最多对多对 个字符编码个字符编码.4

3、3、一颗二叉树的前序遍历序列为、一颗二叉树的前序遍历序列为aebdc，后序遍历序，后序遍历序列为列为bcdea，根节点的孩子节点，根节点的孩子节点A.只需只需e B. e和和b C. e和和c D. 不确定不确定A104 试问利用树的先根次序遍历结果和试问利用树的先根次序遍历结果和后根次序遍历结果能否独一确定一后根次序遍历结果能否独一确定一棵树棵树? 1、树的先根次序遍历的结果与其对、树的先根次序遍历的结果与其对应二叉树的前序遍历结果一样应二叉树的前序遍历结果一样 2、树的后根次序遍历结果与其对应、树的后根次序遍历结果与其对应二叉树的中序遍历结果一样二叉树的中序遍历结果一样; 3、对于二叉树而

4、言，先序遍历和中、对于二叉树而言，先序遍历和中序遍历可以确定一个二叉树，序遍历可以确定一个二叉树， 因此，树的先根次序遍历结果和后因此，树的先根次序遍历结果和后根次序遍历结果能独一确定一棵树根次序遍历结果能独一确定一棵树 用二叉链表作为二叉树的存储表示，统计二叉树中用二叉链表作为二叉树的存储表示，统计二叉树中叶结点的个数，请完成以下递归程序叶结点的个数，请完成以下递归程序 。int leaf (BiTNode * ptr ) if ( ) return 0;else if ( ptr-lChild = NULL & ptr-rChild = NULL ) return 1;else r

5、eturn + ; typedef struct BiTNode / 结点构造结点构造 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 BiTNode, *BiTree;ptr = NULLleaf ( ptr-lChild )leaf ( ptr-rChild ) 二叉树的双序遍历二叉树的双序遍历(Double-order traversal)是指：对是指：对于二叉树的每一个结点来说，先访问这个结点，再于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，按双序遍历它的左子树，

6、然后再一次访问这个结点，接下来按双序遍历它的右子树。试写出执行这种双接下来按双序遍历它的右子树。试写出执行这种双序遍历的算法。序遍历的算法。 void Double_order ( BiTNode *current ) if ( current != NULL ) printf(“%f, current-data); ; printf(“%f, current-data); Double_order ( current-rChild ); Double_order ( current-rChild ) 知一棵具有知一棵具有n个结点的完全二叉树被顺序存储于一维个结点的完全二叉树被顺序存储于一维数

7、组的数组的A1An元素中，试找出编号为元素中，试找出编号为i的结点的的结点的双亲和一切孩子。假设每一个元素用一个整数表示。双亲和一切孩子。假设每一个元素用一个整数表示。完成以下程序完成以下程序void Request(int A, int n, int i) /从数组从数组A中打印出编号为中打印出编号为i的结点的双亲和孩子的结点的双亲和孩子 if( ) exit(1); printf(current element:%f, Ai); int j=i/2; /下标为下标为j的结点是下标为的结点是下标为i结点的双亲结点的双亲 if( ) printf(“parent:%f，Aj); else pr

8、inf(“No parent!); if( ) printf(left child:%f,A2*i); printf(right child:%f“,A2*i+1; else if( ) printf(left child:%f,A2*i); printf(no right child!; else printf(no children!“); inj02*ilchild; b-lchild = b-rchild; b-rchild =t; swap(b-lchild ); swap(b-rchild );交换左右子树交换左右子树 请指出以下函数的功能请指出以下函数的功能void preser

9、ve(BiTNode *b, ElemType a, int n) static int i = 0; if(b != NULL) preserve(b-lChild, a,n); ai+ = b-data; preserve(b-rChild, a,n); 得到二叉树得到二叉树b的中序遍历序列，结果放在数组的中序遍历序列，结果放在数组a中中根据根据_可以独一地确定一棵二叉树。可以独一地确定一棵二叉树。 A. A. 先序遍历和后序遍历先序遍历和后序遍历 B. B. 先序遍历和层次遍历先序遍历和层次遍历 C. C. 中序遍历和层次遍历中序遍历和层次遍历 D. D. 中序遍历和后序遍历中序遍历和后

10、序遍历D. D. 中序遍历和后序遍历中序遍历和后序遍历 一切分支结点的度为一切分支结点的度为2 2的二叉树称为正那么二叉树，的二叉树称为正那么二叉树，试用二叉链表做存储构造，编写一递归函数试用二叉链表做存储构造，编写一递归函数int int FormalTree(Bitree t)FormalTree(Bitree t)，判别二叉树能否为正那么二，判别二叉树能否为正那么二叉树。叉树。int FormalTree(Bitree t) if (t = NULL) return 1; if (t-lchild = NULL) & (t-rchild = NULL) return 1; if

11、(t-lchild = NULL) | (t-rchild = NULL) return 0; return (FormalTree(t-lchild) & (FormalTree(t-rchild); 下面不能独一确定一棵二叉树的两个遍历序列是下面不能独一确定一棵二叉树的两个遍历序列是_。A)A)先序序列和中序序列先序序列和中序序列 B) B)先序序列和后序序列先序序列和后序序列C)C)后序序列和中序序列后序序列和中序序列 C) C)都不能都不能在树的孩子兄弟表示法中，二叉链表的左指针指向在树的孩子兄弟表示法中，二叉链表的左指针指向_，右指针指向，右指针指向_。B) 先序序列和后序序

12、列先序序列和后序序列第一个孩子第一个孩子下一个兄弟下一个兄弟在二叉链表的每个结点中添加一个域在二叉链表的每个结点中添加一个域int depthint depth，表示，表示以该结点为根的子树的深度，即：以该结点为根的子树的深度，即：typedef struct BiTNode typedef struct BiTNode / / 结点构造结点构造 TElemType data; TElemType data; struct BiTNode struct BiTNode * *lchild,lchild,* *rchild;/rchild;/左右孩子指针左右孩子指针 int depth; / i

13、nt depth; /以该结点为根的子树的深度以该结点为根的子树的深度 BiTNode, BiTNode, * * BiTree; BiTree; a. a. 试编写一递归函数试编写一递归函数BiTreeDepth( BiTree T )BiTreeDepth( BiTree T )，计算二叉树计算二叉树T T中每个结点的中每个结点的depthdepth值，函数的前往值为值，函数的前往值为树树T T的深度。的深度。 b. b. 在在a a的根底上即已求出二叉树中每个结点的的根底上即已求出二叉树中每个结点的depthdepth值，编写一递归函数值，编写一递归函数BiTreeBalance ( B

14、iTree BiTreeBalance ( BiTree T )T )，判别二叉排序树，判别二叉排序树T T能否为平衡二叉树，假设是平能否为平衡二叉树，假设是平衡二叉树，那么函数的前往值为真。衡二叉树，那么函数的前往值为真。a. int BiTreeDepth(BiTree T) int ldepth, rdepth; if ( !T ) return -1; ldepth = BiTreeDepth ( T-lchild ) ; rdepth = BiTreeDepth ( T-rchild ) ; if ( ldepth = rdepth ) T-depth = ldepth+1; els

15、e T-depth = rdepth+1; return T-depth;?b. Status BiTreeBalance(BiTree T) int ldepth, rdepth; if ( T=NULL ) return TRUE; if (T-lchild) ldepth = T-lchild-depth; else ldepth = -1; if (T-rchild) rdepth = T-rchild-depth; else rdepth = -1; lrdepth = ldepth rdepth; if ( ( lrdepth = 0 | lrdepth = 1 | lrdepth

16、 = -1 ) & ( BiTreeBalance( T-lchild ) & BiTreeBalance( T-rchild ) ) return TRUE; return FALSE;? 在中序线索二叉树中，假设结点的左指针在中序线索二叉树中，假设结点的左指针lchildlchild不是线索，那么该结点的前驱结点应是遍历其不是线索，那么该结点的前驱结点应是遍历其左子树时左子树时_;_;假设结点的右指针假设结点的右指针rchildrchild不是线索，那么该结点的后继结点应是遍历其不是线索，那么该结点的后继结点应是遍历其右子树时右子树时_。最后访问的一个结点；最后访问的一个结

17、点；最先访问的一个结点最先访问的一个结点假设两棵二叉树的外形一样，并且相应结点中的假设两棵二叉树的外形一样，并且相应结点中的数据也一样，那么这两棵二叉树相等。试用二叉链表数据也一样，那么这两棵二叉树相等。试用二叉链表做存贮构造，编写判别两棵二叉树能否相等的递归算做存贮构造，编写判别两棵二叉树能否相等的递归算法，要求函数的原型为：法，要求函数的原型为：int EqualBTree(BiTree T1, BiTree T2)。 int EqualBTree( BiTree T1, BiTree T2 ) if ( !T1 & !T2 ) return 1; if ( !T1 | !T2 )

18、 return 0; return ( (T1-data = T2-data) & EqualBTree(T1-lchild, T2-lchild)&EqualBTree(T1-rchild, T2-rchild) ;?假设一棵二叉树有假设一棵二叉树有126个节点，在第个节点，在第7层根结点在第层根结点在第1层至多有个结点。层至多有个结点。A32 B64 C63 D不存在第不存在第7层层C) 63 对于有对于有10001000个结点的完全二叉树从个结点的完全二叉树从0 0开场编号从开场编号从上到下逐层编号，每层从左到右编号，结点上到下逐层编号，每层从左到右编号，结点174174

19、的双的双亲结点编号为亲结点编号为_，结点，结点499499的右孩子结的右孩子结点编号为点编号为_。(174+1)/2- 1=86没有没有(2*500 + 1 - 1 =1000)试编写先根遍历树的递归算法试编写先根遍历树的递归算法PreOrderTree(T, visit), 其中其中T为要遍历的树，为要遍历的树，visit为访问函数，树的存储构造为访问函数，树的存储构造采用孩子兄弟表示法，其类型定义如下：采用孩子兄弟表示法，其类型定义如下：typedef struct TreeNode ElementType data; struct TreeNode *FirstChild; struct

20、 TreeNode *NextSibling; TreeNode, *Tree;void PreOrderTree(Tree T, void (* visit) (ElementType) if (!T) return; (*visit)(T-data); for ( p = T-FirstChild; p; p = p-NextSibling ) PreOrderTree(p, visit);? 给定二叉树如以下图所示。设给定二叉树如以下图所示。设N N代表二叉树的根，代表二叉树的根，L L代代表根结点的左子树，表根结点的左子树，R R代表根结点的右子树。假设遍历代表根结点的右子树。假设遍历

21、后的结点序列为后的结点序列为3, 1, 7, 5, 6, 2, 43, 1, 7, 5, 6, 2, 4，那么其遍历方，那么其遍历方式是式是A ALRNLRNB BNRLNRLC CRLNRLND DRNLRNLDRNLC1113215476知一棵完全二叉树的第知一棵完全二叉树的第6 6层设根为第层设根为第1 1层有层有8 8个叶结个叶结点，那么该完全二叉树的结点个数最多是点，那么该完全二叉树的结点个数最多是A A3939B B5252C C111111D D119119对二叉树的结点从对二叉树的结点从1 1开场进展延续编号，要求每个结点开场进展延续编号，要求每个结点的编号小于其左、右孩子的编

22、号，同一结点的左右孩的编号小于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，实现编子中，其左孩子的编号小于其右孩子的编号，实现编号应采用的遍历次序是号应采用的遍历次序是_。A A先序先序 B B中序中序 C C后序后序 D D都不是都不是 设二叉树只需度为设二叉树只需度为0 0和和2 2的结点，其结点个数为的结点，其结点个数为2121，那么该二叉树的最大深度为那么该二叉树的最大深度为_。 A A5 5 B B6 6 C C1010D D1111A先序先序D11利用哈夫曼算法为报文利用哈夫曼算法为报文“a big black bug bit a big a big

23、black bug bit a big black bagblack bag设计一个编码留意：包括空格，使该设计一个编码留意：包括空格，使该报文的长度最短。要求给出最终的哈夫曼树，每个字报文的长度最短。要求给出最终的哈夫曼树，每个字符的哈夫曼编码，以及报文最终的长度。符的哈夫曼编码，以及报文最终的长度。5*3 + 7*3 +* + 4*3 + 3*3 + 2*4 + 2*4 + 5 + 5 + 8*2 = 107a:5b:7 c:2g:4i:3k:2l:2t:1u:1 :8a: 000b: 001c: 0100g: 011i: 100k: 1010l: 1011t: 01010u: 01011

24、: 11tu2kl4c4i7g8ab12“352015 设图的邻接表的类型定义如下。假设带权图中边的权值类型设图的邻接表的类型定义如下。假设带权图中边的权值类型为整型，请对该邻接表的类型定义做出适当修正，使之可以用为整型，请对该邻接表的类型定义做出适当修正，使之可以用于表示边带权的图。于表示边带权的图。#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode;typedef struct Vnode VertexType data; ArcNode * finrsta

25、rc; Vnode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vexs; int vexnum, arcnum; ALGraph;typedef struct ArcNode int adjvex; int weight; struct ArcNode *nextarc; ArcNode;算法算法FindPathFindPath是求图是求图G G中顶点中顶点v v到到s s的一条途径的一条途径PATHPATH用用线性表表示的一个顶点序列。顶点均用顶点的编号。线性表表示的一个顶点序列。顶点均用顶点的编号。Status FindPath(Graph

26、 G,int v,int s,List &PATH)Status FindPath(Graph G,int v,int s,List &PATH) visitedv = TRUE; / visitedv = TRUE; / 标示第标示第 v v 个顶点已被访问个顶点已被访问 ListInsert(PATH,ListLength(PATH)+1,v); ListInsert(PATH,ListLength(PATH)+1,v); if ( v = s ) return TRUE; if ( v = s ) return TRUE; for(w=FirstAdjVex(G,v);

27、w!=-1; for(w=FirstAdjVex(G,v); w!=-1;w=NextAdjVex(G, v,w)w=NextAdjVex(G, v,w) if ( _ ) if ( _ ) if (FindPath(G, w, s, PATH) return if (FindPath(G, w, s, PATH) return TRUE;TRUE; ListDelete(PATH, _ _); ListDelete(PATH, _ _); return FALSE; return FALSE; visitedw = FALSEListLength(PATH) 在求连通网的最小生成树时，普里姆

28、在求连通网的最小生成树时，普里姆PrimPrim算法适用于算法适用于_，克鲁斯卡尔，克鲁斯卡尔KruskalKruskal算法适用于算法适用于_。 拓扑排序可以用来检查拓扑排序可以用来检查_中能否存中能否存在回路。在回路。 以下图的存储构造中，只能用来表示有向图的是以下图的存储构造中，只能用来表示有向图的是A. A. 邻接矩阵邻接矩阵B. B. 邻接表邻接表C. C. 十字链表十字链表D. D. 邻接多重表邻接多重表有向图有向图 边稠密的网边稠密的网 C. 十字链表十字链表边稀疏的网边稀疏的网TopologicalSortTopologicalSort是一个利用队列对图是一个利用队列对图G G

29、进展拓扑排序的算法，请进展拓扑排序的算法，请在该算法的空白处填入适宜的语句或表达式。在该算法的空白处填入适宜的语句或表达式。提示：数组提示：数组InDegreeInDegree事先已存放每个顶点的入度；数组事先已存放每个顶点的入度；数组TopOrderTopOrder在算法执行后将存放每个顶点在拓扑排序中的顺序。在算法执行后将存放每个顶点在拓扑排序中的顺序。int TopologicalSort( Graph G )int TopologicalSort( Graph G ) Queue Q; int Counter = 0; int I, V, W; Queue Q; int Counter

30、 = 0; int I, V, W; InitQueue(Q); InitQueue(Q); for (I = 0; I G.vexnum; I+)for (I = 0; I G.vexnum; I+) if (InDegreeI = 0) Enqueue(Q, I); if (InDegreeI = 0) Enqueue(Q, I); while (_) while (_) Dequeue(Q, V); Dequeue(Q, V); TopOrderV = +Counter; TopOrderV = +Counter; for(W=FirstAdjVex(G,V); W!=-1; W=NextAdjVex(G,V,W) for(W=FirstAdjVex(G