树和图的习题1课件.ppt

1、2005考研试题考研试题 所有分支结点的度为所有分支结点的度为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(t-lchild=NULL)|(t-rchild=NULL)return 0

2、;return(FormalTree(t-lchild)&(FormalTree(t-rchild);2005考研试题从空的平衡二叉排序树开始，按以下顺序插入关键从空的平衡二叉排序树开始，按以下顺序插入关键字，请给出最终的平衡二叉树。假设字，请给出最终的平衡二叉树。假设6 6个关键字的查找个关键字的查找概率相等，求该树的平均查找长度。概率相等，求该树的平均查找长度。27,31,49,38,41,6727,31,49,38,41,676731274927314938413127413849RR调整调整LR调整调整RR调整调整2005考研试题从空的平衡二叉排序树开始，按以下顺序插入关键从空的平衡二

3、叉排序树开始，按以下顺序插入关键字，请给出最终的平衡二叉树。假设字，请给出最终的平衡二叉树。假设6 6个关键字的查找个关键字的查找概率相等，求该树的平均查找长度。概率相等，求该树的平均查找长度。27,31,49,38,41,6727,31,49,38,41,67673127413849RR调整调整413149386727ASL=(3ASL=(3*3+23+2*2+12+1*1)/6 1)/6=14/6=14/62006考研试题下面不能唯一确定一棵二叉树的两个遍历序列是下面不能唯一确定一棵二叉树的两个遍历序列是_。A)A)先序序列和中序序列先序序列和中序序列 B)B)先序序列和后序序列先序序列和

4、后序序列C)C)后序序列和中序序列后序序列和中序序列 C)C)都不能都不能在树的孩子兄弟表示法中，二叉链表的左指针指向在树的孩子兄弟表示法中，二叉链表的左指针指向_，右指针指向，右指针指向_。B)先序序列和后序序列先序序列和后序序列第一个孩子第一个孩子下一个兄弟下一个兄弟在二叉链表的每个结点中添加一个域在二叉链表的每个结点中添加一个域int depthint depth，表示，表示以该结点为根的子树的深度，即：以该结点为根的子树的深度，即：typedef struct BiTNode typedef struct BiTNode /结点结构结点结构 TElemType data;TElemTy

5、pe data;struct BiTNode struct BiTNode*lchild,lchild,*rchild;/rchild;/左右孩子指针左右孩子指针 int depth;/int depth;/以该结点为根的子树的深度以该结点为根的子树的深度 BiTNode,BiTNode,*BiTree;BiTree;a.a.试编写一递归函数试编写一递归函数BiTreeDepth(BiTree T)BiTreeDepth(BiTree T)，计算二叉树计算二叉树T T中每个结点的中每个结点的depthdepth值，函数的返回值为值，函数的返回值为树树T T的深度。的深度。b.b.在在a a的基

6、础上（即已求出二叉树中每个结点的的基础上（即已求出二叉树中每个结点的depthdepth值），编写一递归函数值），编写一递归函数BiTreeBalance(BiTree 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-rchi

7、ld);if(ldepth=rdepth)T-depth=ldepth+1;else 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=-

8、1)&(BiTreeBalance(T-lchild)&BiTreeBalance(T-rchild)return TRUE;return FALSE;?2007考研试题考研试题 在中序线索二叉树中，若结点的左指针在中序线索二叉树中，若结点的左指针lchildlchild不是线索，则该结点的前驱结点应是遍历其左子树时不是线索，则该结点的前驱结点应是遍历其左子树时_;_;若结点的右指针若结点的右指针rchildrchild不是不是线索，则该结点的后继结点应是遍历其右子树时线索，则该结点的后继结点应是遍历其右子树时_。最后访问的一个结点；最后访问的一个结点；最先访问的一个结点最先访问的一个结点20

9、07考研试题如果两棵二叉树的形状相同，并且相应结点中的如果两棵二叉树的形状相同，并且相应结点中的数据也相同，则这两棵二叉树相等。试用二叉链表做数据也相同，则这两棵二叉树相等。试用二叉链表做存贮结构，编写判断两棵二叉树是否相等的递归算法存贮结构，编写判断两棵二叉树是否相等的递归算法，要求函数的原型为：，要求函数的原型为：int EqualBTree(BiTree T1,BiTree T2)。int EqualBTree(BiTree T1,BiTree T2)if(!T1&!T2)return 1;if(!T1|!T2)return 0;return(T1-data=T2-data)&Equal

10、BTree(T1-lchild,T2-lchild)&EqualBTree(T1-rchild,T2-rchild);?2008考研试题在在5 5阶阶B-B-树中，非终端根结点至少有树中，非终端根结点至少有_个孩子结个孩子结点，除根之外的所有非终端结点至少有点，除根之外的所有非终端结点至少有_孩子结点。孩子结点。23若一棵二叉树有若一棵二叉树有126个节点，在第个节点，在第7层（根结点在第层（根结点在第1层）至多有（）个结点。层）至多有（）个结点。A32 B64 C63 D不存在第不存在第7层层C)63 对于有对于有10001000个结点的完全二叉树从个结点的完全二叉树从0 0开始编号（从开始

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

12、 data;struct TreeNode*FirstChild;struct 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);?树和二叉树树和二叉树20092009试题试题 给定二叉树如下图所示。设给定二叉树如下图所示。设N N代表二叉树的根，代表二叉树的根，L L代表代表根结点的左子树，根结

13、点的左子树，R R代表根结点的右子树。若遍历后的代表根结点的右子树。若遍历后的结点序列为结点序列为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树和二叉树树和二叉树20092009试题试题下列二叉排序树中，满足平衡二叉

14、树定义的是下列二叉排序树中，满足平衡二叉树定义的是 BABCD下列叙述中，不符合下列叙述中，不符合m阶阶B树定义要求的是树定义要求的是A根结点最多有根结点最多有m棵子树棵子树B所有叶结点都在同一层上所有叶结点都在同一层上C各结点内关键字均升序或降序排列各结点内关键字均升序或降序排列D叶结点之间通过指针链接叶结点之间通过指针链接D树和二叉树树和二叉树20092009考博试题考博试题对二叉树的结点从对二叉树的结点从1 1开始进行连续编号，要求每个结点开始进行连续编号，要求每个结点的编号小于其左、右孩子的编号，同一结点的左右孩的编号小于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右

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

16、k bag”black 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”:11tu2kl4c4i7g8ab12“352015图图20052005试题试题 设图的

17、邻接表的类型定义如下。若带权图中边的权值类型为设图的邻接表的类型定义如下。若带权图中边的权值类型为整型，请对该邻接表的类型定义做出适当修改，使之能够用于整型，请对该邻接表的类型定义做出适当修改，使之能够用于表示边带权的图。表示边带权的图。#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex;struct ArcNode *nextarc;ArcNode;typedef struct Vnode VertexType data;ArcNode *finrstarc;Vnode,AdjListMAX_VERTEX_NUM;typede

18、f struct AdjList vexs;int vexnum,arcnum;ALGraph;typedef struct ArcNode int adjvex;int weight;struct ArcNode *nextarc;ArcNode;图图20062006试题试题算法算法FindPathFindPath是求图是求图G G中顶点中顶点v v到到s s的一条路径的一条路径PATHPATH（用（用线性表表示的一个顶点序列）。顶点均用顶点的编号。线性表表示的一个顶点序列）。顶点均用顶点的编号。Status FindPath(Graph G,int v,int s,List&PATH)St

19、atus 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);w!=-1;for(w=FirstAdjVex(G,v);w!=-1;w=NextAdjVex(G,v,w)w=NextAdj

20、Vex(G,v,w)if(_)if(_)if(FindPath(G,w,s,PATH)return TRUE;if(FindPath(G,w,s,PATH)return TRUE;ListDelete(PATH,_,e);ListDelete(PATH,_,e);return FALSE;return FALSE;visitedw=FALSEListLength(PATH)在求连通网的最小生成树时，普里姆在求连通网的最小生成树时，普里姆（PrimPrim）算法适用于）算法适用于_，克鲁斯卡尔，克鲁斯卡尔（KruskalKruskal）算法适用于）算法适用于_。拓扑排序可以用来检查拓扑排序可以用

21、来检查_中是否存中是否存在回路。在回路。图图20072007试题试题 下列图的存储结构中，只能用来表示下列图的存储结构中，只能用来表示有向图的是有向图的是A.A.邻接矩阵邻接矩阵B.B.邻接表邻接表C.C.十字链表十字链表D.D.邻接多重表邻接多重表有向图有向图 边稠密的网边稠密的网 C.十字链表十字链表边稀疏的网边稀疏的网图图20082008试题试题TopologicalSortTopologicalSort是一个利用队列对图是一个利用队列对图G G进行拓扑排序的算法，请进行拓扑排序的算法，请在该算法的空白处填入合适的语句或表达式。在该算法的空白处填入合适的语句或表达式。提示：数组提示：数组

22、InDegreeInDegree事先已存放每个顶点的入度；数组事先已存放每个顶点的入度；数组TopOrderTopOrder在算法执行后将存放每个顶点在拓扑排序中的顺序。在算法执行后将存放每个顶点在拓扑排序中的顺序。int TopologicalSort(Graph G)int TopologicalSort(Graph G)Queue Q;int Counter=0;int I,V,W;InitQueue(Q);Queue Q;int Counter=0;int I,V,W;InitQueue(Q);for(I=0;I G.vexnum;I+)for(I=0;I G.vexnum;I+)if

23、(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,V);W!=-1;W=NextAdjVex(G,V,W)if(_)Enqueue(Q,W);if(_)Enqueue(Q,W);DestroyQueue(Q);return(Counter=G.v

24、exnum);DestroyQueue(Q);return(Counter=G.vexnum);!QueueEmpty(Q)-IndegreeW=0图图20092009试题试题下列关于无向连通图特性的叙述中，正确的是下列关于无向连通图特性的叙述中，正确的是 I I所有顶点的度之和为偶数所有顶点的度之和为偶数 II II边数大于顶点个数减边数大于顶点个数减1 1 III III至少有一个顶点的度为至少有一个顶点的度为1 1A A只有只有I I B B只有只有IIII C CI I和和IIII D DI I和和IIIIIIA只有只有I图图20092009试题试题 带权图（权值非负，表示边连接的两顶

25、点间的距带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：存在路径，现有一种解决该问题的方法：设最短路径初始时仅包含初始顶点，令当前顶设最短路径初始时仅包含初始顶点，令当前顶点点u u为初始顶点；为初始顶点；选择离选择离u u最近且尚未在最短路径中的一个顶点最近且尚未在最短路径中的一个顶点v v，加入到最短路径中，修改当前顶点加入到最短路径中，修改当前顶点u=vu=v；重复步骤，直到重

26、复步骤，直到u u是目标顶点时为止。是目标顶点时为止。请问上述方法能否求得最短路径？若该方法可行，请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。请证明之；否则，请举例说明。abc754图图20092009考博试题考博试题 在图中判断两个顶点是否相邻，采用在图中判断两个顶点是否相邻，采用_存储结存储结构效率最高。构效率最高。A A邻接矩阵邻接矩阵B B邻接表邻接表C C十字链表十字链表D D邻接多重表邻接多重表A邻接矩阵邻接矩阵 普里姆算法是用于求解普里姆算法是用于求解_的最小生成树。的最小生成树。A A无向图无向图B B无向连通图无向连通图C C无向连通网无向连通网D

27、 D无向网无向网C无向连通网无向连通网图图20092009考博试题考博试题有向图的邻接表如图所示。有向图的邻接表如图所示。（1 1）画出该图；）画出该图；（2 2）给出以）给出以V0V0为起始结点的深度优先遍历序列和广为起始结点的深度优先遍历序列和广度优先遍历序列；度优先遍历序列；（3 3）简述在邻接表存储结构下，求图中某顶点）简述在邻接表存储结构下，求图中某顶点i i的的入度的方法；入度的方法；V0012344312V1V2V3V40422（1）（2）深度优先遍历序列：）深度优先遍历序列：v0 v4 v2 v3 v1 广度优先遍历序列：广度优先遍历序列：v0 v4 v3 v1 v2（3）遍历所有链表，计算包含）遍历所有链表，计算包含i的结点个数的结点个数v4v3v2v1v0