树和图的习题1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,5-2,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,*,页,2005,考研试题,根据,_,可以唯一地确定一棵二叉树。,A.,先序遍历和后序遍历,B.,先序遍历和层次遍历,C.,中序遍历和层次遍历,D.,中序遍历和后序遍历,D.,中序遍历和后序遍历,对于,m=4(4,阶,),的,B-,树，如果根的层次为第,1,层，则高度为,2,的,B-,树最少要存储,_,个数据，最多可以保存,_,个数据。,3,15,2005,考研试题,所有分支结点的度为,2,的二叉树称为正则二叉树，试用二叉链表做存储结构，编写一递归函数,int,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;,return,(,FormalTree(t,-,lchild,)&(,FormalTree(t,-,rchild,);,2005,考研试题,从空的平衡二叉排序树开始，按以下顺序插入关键字，请给出最终的平衡二叉树。假设,6,个关键字的查找概率相等，求该树的平均查找长度。,27,31,49,38,41,67,67,31,27,49,27,31,49,38,41,31,27,41,38,49,RR,调整,LR,调整,RR,调整,2005,考研试题,从空的平衡二叉排序树开始，按以下顺序插入关键字，请给出最终的平衡二叉树。假设,6,个关键字的查找概率相等，求该树的平均查找长度。,27,31,49,38,41,67,67,31,27,41,38,49,RR,调整,41,31,49,38,67,27,ASL=(3*3+2*2+1*1)/6=14/6,2006,考研试题,下面不能唯一确定一棵二叉树的两个遍历序列是,_,。,A),先序序列和中序序列,B),先序序列和后序序列,C),后序序列和中序序列,C),都不能,在树的孩子兄弟表示法中，二叉链表的左指针指向,_,，右指针指向,_,。,B),先序序列和后序序列,第一个孩子,下一个兄弟,在二叉链表的每个结点中添加一个域,int depth,，表示以该结点为根的子树的深度，即：,typedef struct BiTNode /,结点结构,TElemType data;,struct BiTNode*lchild,*rchild;/,左右孩子指针,int depth;/,以该结点为根的子树的深度,BiTNode,*BiTree;,a.,试编写一递归函数,BiTreeDepth(BiTree T),，计算二叉树,T,中每个结点的,depth,值，函数的返回值为树,T,的深度。,b.,在,a,的基础上（即已求出二叉树中每个结点的,depth,值），编写一递归函数,BiTreeBalance(BiTree 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;,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=-1),&,(BiTreeBalance(T-lchild),&BiTreeBalance(T-rchild),return TRUE;,return FALSE;,?,2007,考研试题,在中序线索二叉树中，若结点的左指针,lchild,不是线索，则该结点的前驱结点应是遍历其左子树时,_;,若结点的右指针,rchild,不是线索，则该结点的后继结点应是遍历其右子树时,_,。,最后访问的一个结点；,最先访问的一个结点,2007,考研试题,如果两棵二叉树的形状相同，并且相应结点中的数据也相同，则这两棵二叉树相等。试用二叉链表做存贮结构，编写判断两棵二叉树是否相等的递归算法，要求函数的原型为：,int,EqualBTree(BiTree,T1,BiTree,T2),。,int,EqualBTree,(,BiTree,T1,BiTree,T2),if(!T1,if(!T1|!T2)return 0;,return(T1-data=T2-data)&,EqualBTree(T1-,lchild,T2-,lchild,),&EqualBTree(T1-,rchild,T2-,rchild,);,?,?,2008,考研试题,在,5,阶,B-,树中，非终端根结点至少有,_,个孩子结点，除根之外的所有非终端结点至少有,_,孩子结点。,2,3,若一棵二叉树有,126,个节点，在第,7,层（根结点在第,1,层）至多有（）个结点。,A,32 B,64 C,63 D,不存在第,7,层,C)63,对于有,1000,个结点的完全二叉树从,0,开始编号（从上到下逐层编号，每层从左到右编号），结点,174,的双亲结点编号为,_,，结点,499,的右孩子结点编号为,_,。,(174+1)/2-1=86,没有,(2*500+1-1=1000),试编写先根遍历树的递归算法,PreOrderTree(T,visit),其中,T,为要遍历的树，,visit,为访问函数，树的存储结构采用孩子兄弟表示法，其类型定义如下：,typedef,struct,TreeNode,ElementType,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);,?,?,树和二叉树,2009,试题,给定二叉树如下图所示。设,N,代表二叉树的根，,L,代表根结点的左子树，,R,代表根结点的右子树。若遍历后的结点序列为,3,1,7,5,6,2,4,，则其遍历方式是,A,LRNB,NRLC,RLND,RNL,DRNL,C111,3,2,1,5,4,7,6,已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是,A39,B52,C111D119,树和二叉树,2009,试题,下列二叉排序树中，满足平衡二叉树定义的是,B,A,B,C,D,下列叙述中，不符合,m,阶,B,树定义要求的是,A,根结点最多有,m,棵子树,B,所有叶结点都在同一层上,C,各结点内关键字均升序或降序排列,D,叶结点之间通过指针链接,D,树和二叉树,2009,考博试题,对二叉树的结点从,1,开始进行连续编号，要求每个结点的编号小于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，实现编号应采用的遍历次序是,_,。,A,先序,B,中序,C,后序,D,都不是,设二叉树只有度为,0,和,2,的结点，其结点个数为,21,，则该二叉树的最大深度为,_,。,A,5 B,6 C,10D,11,A先序,D,11,树和二叉树,2009,考博试题,利用哈夫曼算法为报文“,a big black bug bit a big black bag”,设计一个编码（注意：包括空格），使该报文的长度最短。要求给出最终的哈夫曼树，每个字符的哈夫曼编码，以及报文最终的长度。,5*3+7*3+,*,+4*3+3*3+2*4+2*4+5+5+8*2=107,a:5b:7 c:2g:4i:3k:2l:2t:1u:1 ”:8,a:000,b:001,c:0100,g:011,i:100,k:1010,l:1011,t:01010,u:01011,”:11,t,u,2,k,l,4,c,4,i,7,g,8,a,b,12,“,35,20,15,图,2005,试题,设图的邻接表的类型定义如下。若带权图中边的权值类型为整型，请对该邻接表的类型定义做出适当修改，使之能够用于表示边带权的图。,#define MAX_VERTEX_NUM 20,typedef,struct,ArcNode,int,adjvex,;,struct,ArcNode,*,nextarc,;,ArcNode,;,typedef,struct,Vnode,VertexType,data;,ArcNode,*,finrstarc,;,Vnode,AdjListMAX_VERTEX_NUM,;,typedef,struct,AdjList,vexs,;,int,vexnum,arcnum,;,ALGraph,;,typedef,struct,ArcNode,int,adjvex,;,int,weight;,struct,ArcNode,*,nextarc,;,ArcNode,;,图,2006,试题,算法,FindPath,是求图,G,中顶点,v,到,s,的一条路径,PATH,（用线性表表示的一个顶点序列）。顶点均用顶点的编号。,Status FindPath(Graph G,int v,int s,List&PATH),visitedv=TRUE;/,标示第,v,个顶点已被访问,ListInsert(PATH,ListLength(PATH)+1,v);,if(v=s)return TRUE;,for(w=FirstAdjVex(G,v);w!=-1;,w=NextAdjVex(G,v,w),if(_),if(FindPath(G,w,s,PATH)return TRUE;,ListDelete(PATH,_,e);,return FALSE;,visitedw=FALSE,ListLength(PATH),在求连通网的最小生成树时，普里姆（,Prim,）算法适用于,_,，克鲁斯卡尔（,Kruskal,）算法适用于,_,。,拓扑排序可以用来检查,_,中是否存在回路。,图,2007,试题,下列图的存储结构中，只能用来表示有向图的是,A.,邻接矩阵,B.,邻接表,C.,十字链表,D.,邻接多重表,有向图,边稠密的网,C.,十字链表,边稀疏的网,图,2008,试题,TopologicalSort,是一个利用队列对图,G,进行拓扑排序的算法，请在该算法的空白处填入合适的语句或表达式。,提示：数组,InDegree,事先已存放每个顶点的入度；数组,TopOrder,在算法执行后将存放每个顶点在拓扑排序中的顺序。,int TopologicalSort(Graph G),Queue Q;int Counter=0;int I,V,W;InitQueue(Q);,for(I=0;I G.vexnum;I+),if(InDegreeI=0)Enqueue(Q,I);,while(_),Dequeue(Q,V);,TopOrderV=+Counter;,for(W=FirstAdjVex(G,V);W!=-1;W=NextAdjVex(G,V,W),if(_)Enqueue(Q,W);,DestroyQueue(Q);return(Counter=G.vexnum);,!QueueEmpty(Q),-,IndegreeW=0,图,2009,试题,下列关于无向连通图特性的叙述中，正确的是,I,所有顶点的度之和为偶数,II,边数大于顶点个数减,1,III,至少有一个顶点的度为,1,A,只有,I B,只有,II C,I,和,II D,I,和,III,A,只有,I,图,2009,试题,带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：,设最短路径初始时仅包含初始顶点，令当前顶点,u,为初始顶点；,选择离,u,最近且尚未在最短路径中的一个顶点,v,，加入到最短路径中，修改当前顶点,u=v,；,重复步骤，直到,u,是目标顶点时为止。,请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。,a,b,c,7,5,4,图,2009,考博试题,在图中判断两个顶点是否相邻，采用,_,存储结构效率最高。,A,邻接矩阵,B,邻接表,C,十字链表,D,邻接多重表,A邻接矩阵,普里姆算法是用于求解,_,的最小生成树。,A,无向图,B,无向连通图,C,无向连通网,D,无向网,C无向连通网,图,2009,考博试题,有向图的邻接表如图所示。,（,1,）画出该图；,（,2,）给出以,V0,为起始结点的深度优先遍历序列和广度优先遍历序列；,（,3,）简述在邻接表存储结构下，求图中某顶点,i,的入度的方法；,V0,0,1,2,3,4,4,3,1,2,V1,V2,V3,V4,0,4,2,2,（,1,）,（,2,）深度优先遍历序列：,v0 v4 v2 v3 v1,广度优先遍历序列：,v0 v4 v3 v1 v2,（,3,）遍历所有链表，计算包含,i,的结点个数,v4,v3,v2,v1,v0,