《树和图的习题》PPT课件.ppt

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),2005考研试题,从空的平衡二叉排序树开始，按以下顺序插入关键字，请给出最终的平衡二叉树。假设6个关键字的查找概率相等，求该树的平均查找长度。27,31,49,38,41,67,67,27,31,49,38,41,RR调整,LR调整,RR调整,2005考研试题,从空的平衡二叉排序树开始，按以下顺序插入关键字，请给出最终的平衡二叉树。假设6个关键字的查找概率相等，求该树的平均查找长度。27,31,49,38,41,67,67,RR调整,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),?,2007考研试题,在中序线索二叉树中，若结点的左指针lchild不是线索，则该结点的前驱结点应是遍历其左子树时_;若结点的右指针rchild不是线索，则该结点的后继结点应是遍历其右子树时_。,最后访问的一个结点；,最先访问的一个结点,2007考研试题,如果两棵二叉树的形状相同，并且相应结点中的数据也相同，则这两棵二叉树相等。试用二叉链表做存贮结构，编写判断两棵二叉树是否相等的递归算法，要求函数的原型为：int EqualBTree(BiTree T1,BiTree T2)。,int EqualBTree(BiTree T1,BiTree T2)if(!T1,?,?,2008考研试题,在5阶B-树中，非终端根结点至少有_个孩子结点，除根之外的所有非终端结点至少有_孩子结点。,2,3,若一棵二叉树有126个节点，在第7层（根结点在第1层）至多有（）个结点。A32 B64 C63 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，则其遍历方式是,ALRNBNRLCRLNDRNL,DRNL,C111,已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是A39B52C111D119,树和二叉树2009试题,下列二叉排序树中，满足平衡二叉树定义的是,B,A,B,C,D,下列叙述中，不符合m阶B树定义要求的是A根结点最多有m棵子树B所有叶结点都在同一层上C各结点内关键字均升序或降序排列D叶结点之间通过指针链接,D,树和二叉树2009考博试题,对二叉树的结点从1开始进行连续编号，要求每个结点的编号小于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，实现编号应采用的遍历次序是_。A先序 B中序 C后序 D都不是,设二叉树只有度为0和2的结点，其结点个数为21，则该二叉树的最大深度为_。A5 B6 C10D11,A先序,D11,树和二叉树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,图2005试题,设图的邻接表的类型定义如下。若带权图中边的权值类型为整型，请对该邻接表的类型定义做出适当修改，使之能够用于表示边带权的图。#define MAX_VERTEX_NUM 20typedef 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,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至少有一个顶点的度为1A只有I B只有II CI和II DI和III,A只有I,图2009试题,带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；重复步骤，直到u是目标顶点时为止。请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。,图2009考博试题,在图中判断两个顶点是否相邻，采用_存储结构效率最高。A邻接矩阵B邻接表C十字链表D邻接多重表,A邻接矩阵,普里姆算法是用于求解_的最小生成树。A无向图B无向连通图C无向连通网D无向网,C无向连通网,图2009考博试题,有向图的邻接表如图所示。,（1）画出该图；（2）给出以V0为起始结点的深度优先遍历序列和广度优先遍历序列；（3）简述在邻接表存储结构下，求图中某顶点i的入度的方法；,（1）,（2）深度优先遍历序列：v0 v4 v2 v3 v1 广度优先遍历序列：v0 v4 v3 v1 v2（3）遍历所有链表，计算包含i的结点个数,v4,v3,v2,v1,v0,