《数据结构与算法设计》树-习题.ppt

《《数据结构与算法设计》树-习题.ppt》由会员分享，可在线阅读，更多相关《《数据结构与算法设计》树-习题.ppt（37页珍藏版）》请在三一办公上搜索。

1、1,树的练习题,具有n个顶点的二叉树，共有多少边？,2、若一个具有N个顶点，K条边的无向图是一个森林(NK)，那么该森林有多少棵树？,3、已知一棵度为m的树中有N1个度为1的节点，N2个度为2的节点，Nm个度为m的节点。问该树有多少叶子节点？,4、层数为k的二叉树中，最大和最小节点数各为多少？,5、有n个节点的二叉树中，有m个叶子节点，问非叶子节点中度为2和度为1的节点各有多少？,n-1,NK,N0=N2+2N3+(m-1)Nm+1,2k-1,k,n2=m-1;n1=n-2m+1,2,B,C,B,3,假定一棵树的广义表示为(A(B(C，D(E，F，G)，H(I，J)，则树中所含的结点数为（）个

2、，树的深度为（）个，树的度为（）。,3,2、在哈夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对（）个字符编码.,4,3、一颗二叉树的前序遍历序列为aebdc，后序遍历序列为bcdea，根节点的孩子节点A.只有e B.e和b C.e和c D.不确定,A,10,4,4,试问利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一棵树?1、树的先根次序遍历的结果与其对应二叉树的前序遍历结果相同 2、树的后根次序遍历结果与其对应二叉树的中序遍历结果相同;3、对于二叉树而言，先序遍历和中序遍历可以确定一个二叉树，因此，树的先根次序遍历结果和后根次序遍历结果能唯一

3、确定一棵树,5,用二叉链表作为二叉树的存储表示，统计二叉树中叶结点的个数，请完成下列递归程序。,int leaf(BiTNode*ptr)if()return 0;else if(ptr-lChild=NULL,typedef struct BiTNode/结点结构 TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;,ptr=NULL,leaf(ptr-lChild),leaf(ptr-rChild),6,二叉树的双序遍历(Double-order traversal)是指：对于二叉树的每一个结点来说，先访

4、问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。试写出执行这种双序遍历的算法。,void Double_order(BiTNode*current)if(current!=NULL)printf(“%f,”,current-data);printf(“%f,”,current-data);Double_order(current-rChild);,Double_order(current-rChild),7,已知一棵具有n个结点的完全二叉树被顺序存储于一维数组的A1An元素中，试找出编号为i的结点的双亲和所有孩子。假设每一个元素用一个整数表示。完成下列程

5、序,8,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 prinf(“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

6、!;else printf(no children!“);,in,j0,2*in,2*i=n,9,已知二叉树先序序列为：ABCDEF中序序列为：CBAEDF请画出该二叉树。,10,A,D,11,已知二叉树中序序列为：ABCEFGHD后序序列为：ABFHGEDC请画出该二叉树。中序：LDR后序：LRD,A B C E F G H D,A B F H G E D C,12,将下列森林转化为二叉树，然后对森林进行先序和后序遍历,7,13,将下列树进行中序线索化,中序：CBAGEDF,14,试分别找出满足以下条件的所有二叉树 二叉树的前序序列与中序序列相同 二叉树的中序序列与后序序列相同 二叉树的前序

7、序列与后序序列相同 如果一棵Huffman树有n0个叶子节点，那么该树有多少节点？已知如下序列：8、5、3、2、7、23、9、11、2、35，请构造一棵Huffman树。,2n0-1,请指出下列函数的功能,15,/先序遍历方式，递归void swap(BiTNode*b)BiTNode*t;if(b=NULL)return;t=b-lchild;b-lchild=b-rchild;b-rchild=t;swap(b-lchild);swap(b-rchild);,交换左右子树,16,请指出下列函数的功能,void preserve(BiTNode*b,ElemType a,int n)stat

8、ic int i=0;if(b!=NULL)preserve(b-lChild,a,n);ai+=b-data;preserve(b-rChild,a,n);,得到二叉树b的中序遍历序列，结果放在数组a中,2005考研试题,根据_可以唯一地确定一棵二叉树。A.先序遍历和后序遍历 B.先序遍历和层次遍历 C.中序遍历和层次遍历 D.中序遍历和后序遍历,D.中序遍历和后序遍历,2005考研试题,所有分支结点的度为2的二叉树称为正则二叉树，试用二叉链表做存储结构，编写一递归函数int FormalTree(Bitree t)，判断二叉树是否为正则二叉树。,int FormalTree(Bitree

9、t)if(t=NULL)return 1;if(t-lchild=NULL),2006考研试题,下面不能唯一确定一棵二叉树的两个遍历序列是_。A)先序序列和中序序列 B)先序序列和后序序列C)后序序列和中序序列 C)都不能,在树的孩子兄弟表示法中，二叉链表的左指针指向_，右指针指向_。,B)先序序列和后序序列,第一个孩子,下一个兄弟,在二叉链表的每个结点中添加一个域int depth，表示以该结点为根的子树的深度，即：typedef struct BiTNode/结点结构 TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 int dept

10、h;/以该结点为根的子树的深度 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=BiTreeDept

11、h(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|lrdep

12、th=1|lrdepth=-1),?,2007考研试题,在中序线索二叉树中，若结点的左指针lchild不是线索，则该结点的前驱结点应是遍历其左子树时_;若结点的右指针rchild不是线索，则该结点的后继结点应是遍历其右子树时_。,最后访问的一个结点；,最先访问的一个结点,2007考研试题,如果两棵二叉树的形状相同，并且相应结点中的数据也相同，则这两棵二叉树相等。试用二叉链表做存贮结构，编写判断两棵二叉树是否相等的递归算法，要求函数的原型为：int EqualBTree(BiTree T1,BiTree T2)。,int EqualBTree(BiTree T1,BiTree T2)if(!T1

13、,?,?,2008考研试题,若一棵二叉树有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 d

14、ata;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，则其

15、遍历方式是,ALRNBNRLCRLNDRNL,DRNL,C111,已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是A39B52C111D119,树和二叉树2009考博试题,对二叉树的结点从1开始进行连续编号，要求每个结点的编号小于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，实现编号应采用的遍历次序是_。A先序 B中序 C后序 D都不是,设二叉树只有度为0和2的结点，其结点个数为21，则该二叉树的最大深度为_。A5 B6 C10D11,A先序,D11,树和二叉树2009考博试题,利用哈夫曼算法为报文“a big black b

16、ug 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*next

17、arc;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 Fin

18、dPath(Graph G,int v,int s,List,visitedw=FALSE,ListLength(PATH),在求连通网的最小生成树时，普里姆（Prim）算法适用于_，克鲁斯卡尔（Kruskal）算法适用于_。,拓扑排序可以用来检查_中是否存在回路。,图2007试题,下列图的存储结构中，只能用来表示有向图的是A.邻接矩阵B.邻接表C.十字链表D.邻接多重表,有向图,边稠密的网,C.十字链表,边稀疏的网,图2008试题,TopologicalSort是一个利用队列对图G进行拓扑排序的算法，请在该算法的空白处填入合适的语句或表达式。提示：数组InDegree事先已存放每个顶点的入度

19、；数组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.vexn

20、um);,!QueueEmpty(Q),-IndegreeW=0,图2009试题,下列关于无向连通图特性的叙述中，正确的是 I所有顶点的度之和为偶数 II边数大于顶点个数减1 III至少有一个顶点的度为1A只有I B只有II CI和II DI和III,A只有I,一棵树有2011个节点，叶子节点为116个，与其对应的2叉树有 个节点没有右孩子？A115 B116 C1895 D1896,D,图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,