《《数据结构与算法设计》树-习题.ppt》由会员分享，可在线阅读，更多相关《《数据结构与算法设计》树-习题.ppt（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 1树的练习题树的练习题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+12 2BCB3 31.假定一棵树的广义表示为假定一棵树的广义表示为(A(B(C，D(E，F，G)，H(I，J)，则树中所含的结点数为，则树中所含的结点数为（）个，树的深）个，树的深度为（度为（）个，树的度为）个，树的度为（）。）。32、在哈夫曼编码中，若编码长度只允许小于等于、在哈夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为则除了已对两个字符编码为0和和10外，还可以最多对外，还可以最多对（）个
3、字符编码个字符编码.43、一颗二叉树的前序遍历序列为、一颗二叉树的前序遍历序列为aebdc，后序遍历序，后序遍历序列为列为bcdea，根节点的孩子节点，根节点的孩子节点A.A.只有只有e B.ee B.e和和b b C.eC.e和和c c D.D.不确定不确定A1044 4试问利用树的先根次序遍历结果和试问利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一后根次序遍历结果能否唯一确定一棵树棵树?1、树的先根次序遍历的结果与其对应二叉树的前序遍、树的先根次序遍历的结果与其对应二叉树的前序遍历结果相同历结果相同 2、树的后根次序遍历结果与其对应二叉树的中序遍历、树的后根次序遍历结果与其对应二
4、叉树的中序遍历结果相同结果相同;3、对于二叉树而言，先序遍历和中序遍历可以确定一、对于二叉树而言，先序遍历和中序遍历可以确定一个二叉树，个二叉树，因此，树的先根次序遍历结果和后根次序遍历结果能因此，树的先根次序遍历结果和后根次序遍历结果能唯一确定一棵树唯一确定一棵树5 5用二叉链表作为二叉树的存储表示，统计二叉树中用二叉链表作为二叉树的存储表示，统计二叉树中叶结点的个数，请完成下列递归程序叶结点的个数，请完成下列递归程序。int leaf(BiTNode*ptr)if()return 0;else if(ptr-lChild=NULL&ptr-rChild=NULL)return 1;else
5、 return +;typedef struct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针左右孩子指针 BiTNode,*BiTree;ptr=NULLleaf(ptr-lChild)leaf(ptr-rChild)6 6二叉树的双序遍历二叉树的双序遍历(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)7 7已知一棵具有已知一棵具有n个结点的个结点的完全二叉树完全二叉树被顺序存储于一被顺序存储于一维数组的维数组的A1An元素中，试找出编号为元素中，试找出编号为
7、i的结点的结点的双亲和所有孩子。假设每一个元素用一个整数表的双亲和所有孩子。假设每一个元素用一个整数表示。完成下列程序示。完成下列程序8 8void 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 chi
8、ld:%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);交换左右子树交换左右子树1616请指出下列函数的功能请指出下列函数的功能void preserve(BiTNode*b,ElemType a,int n)static int i=0;if(b!=
9、NULL)preserve(b-lChild,a,n);ai+=b-data;preserve(b-rChild,a,n);得到二叉树得到二叉树b的中序遍历序列，结果放在数组的中序遍历序列，结果放在数组a中中2005考研试题考研试题根据根据_可以唯一地确定一棵二叉树。可以唯一地确定一棵二叉树。A.A.先序遍历和后序遍历先序遍历和后序遍历 B.B.先序遍历和层次遍历先序遍历和层次遍历 C.C.中序遍历和层次遍历中序遍历和层次遍历 D.D.中序遍历和后序遍历中序遍历和后序遍历D.D.中序遍历和后序遍历中序遍历和后序遍历2005考研试题考研试题 所有分支结点的度为所有分支结点的度为2 2的二叉树称为
10、正则二叉树，的二叉树称为正则二叉树，试用二叉链表做存储结构，编写一递归函数试用二叉链表做存储结构，编写一递归函数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;return(FormalTree(t-lchild)&(FormalTree
11、(t-rchild);2006考研试题考研试题下面不能唯一确定一棵二叉树的两个遍历序列是下面不能唯一确定一棵二叉树的两个遍历序列是_。A)A)先序序列和中序序列先序序列和中序序列 B)B)先序序列和后序序列先序序列和后序序列C)C)后序序列和中序序列后序序列和中序序列 C)C)都不能都不能在树的孩子兄弟表示法中，二叉链表的左指针指向在树的孩子兄弟表示法中，二叉链表的左指针指向_，右指针指向，右指针指向_。B)先序序列和后序序列先序序列和后序序列第一个孩子第一个孩子下一个兄弟下一个兄弟在二叉链表的每个结点中添加一个域在二叉链表的每个结点中添加一个域int depthint depth，表示，表示
12、以该结点为根的子树的深度，即：以该结点为根的子树的深度，即：typedef struct BiTNode typedef struct BiTNode /结点结构结点结构 TElemType data;TElemType data;struct BiTNode*lchild,*rchild;/struct BiTNode*lchild,*rchild;/左右孩子指针左右孩子指针 int depth;/int depth;/以该结点为根的子树的深度以该结点为根的子树的深度 BiTNode,*BiTree;BiTNode,*BiTree;a.a.试编写一递归函数试编写一递归函数BiTreeDept
13、h(BiTree T)BiTreeDepth(BiTree T)，计算二叉树计算二叉树T T中每个结点的中每个结点的depthdepth值，函数的返回值为树值，函数的返回值为树T T的深度。的深度。b.b.在在a a的基础上（即已求出二叉树中每个结点的的基础上（即已求出二叉树中每个结点的depthdepth值），编写一递归函数值），编写一递归函数BiTreeBalance(BiTree BiTreeBalance(BiTree T)T)，判断二叉排序树，判断二叉排序树T T是否为平衡二叉树，如果是平衡是否为平衡二叉树，如果是平衡二叉树，则函数的返回值为真。二叉树，则函数的返回值为真。a.int
14、 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 lde
15、pth=-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考研试题考研试题 在中序线索二叉树中，若结点的左指针在中序线索二叉树中，若结点的左指针lchildlchild不是线索，则该结点的前驱结点应是遍历其左子树时不是线索，则该结点的前驱结点应是遍历其左子树时_;_;若结点的
16、右指针若结点的右指针rchildrchild不是不是线索，则该结点的后继结点应是遍历其右子树时线索，则该结点的后继结点应是遍历其右子树时_。最后访问的一个结点；最后访问的一个结点；最先访问的一个结点最先访问的一个结点2007考研试题考研试题如果两棵二叉树的形状相同，并且相应结点中的如果两棵二叉树的形状相同，并且相应结点中的数据也相同，则这两棵二叉树相等。试用二叉链表做数据也相同，则这两棵二叉树相等。试用二叉链表做存贮结构，编写判断两棵二叉树是否相等的递归算法，存贮结构，编写判断两棵二叉树是否相等的递归算法，要求函数的原型为：要求函数的原型为：int EqualBTree(BiTree T1,B
17、iTree T2)。int EqualBTree(BiTree T1,BiTree T2)if(!T1&!T2)return 1;if(!T1|!T2)return 0;return(T1-data=T2-data)&EqualBTree(T1-lchild,T2-lchild)&EqualBTree(T1-rchild,T2-rchild);?2008考研试题考研试题若一棵二叉树有若一棵二叉树有126个节点，在第个节点，在第7层（根结点在第层（根结点在第1层）至多有（）个结点。层）至多有（）个结点。A32 B64 C63 D不存在第不存在第7层层C)63 对于有对于有10001000个结点的
18、完全二叉树从个结点的完全二叉树从0 0开始编号（从开始编号（从上到下逐层编号，每层从左到右编号），结点上到下逐层编号，每层从左到右编号），结点174174的双的双亲结点编号为亲结点编号为_，结点，结点499499的右孩子结点的右孩子结点编号为编号为_。(174+1)/2-1=86没有没有(2*500+1-1=1000)试编写先根遍历树的递归算法试编写先根遍历树的递归算法PreOrderTree(T,visit),其中其中T为要遍历的树，为要遍历的树，visit为访问函数，树的存储结构为访问函数，树的存储结构采用孩子兄弟表示法，其类型定义如下：采用孩子兄弟表示法，其类型定义如下：typedef
19、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 N代表二叉树的根，代表
20、二叉树的根，L L代表代表根结点的左子树，根结点的左子树，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树和二叉树树和二叉树2009
21、考博试题考博试题对二叉树的结点从对二叉树的结点从1 1开始进行连续编号，要求每个结点开始进行连续编号，要求每个结点的编号小于其左、右孩子的编号，同一结点的左右孩的编号小于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，实现编子中，其左孩子的编号小于其右孩子的编号，实现编号应采用的遍历次序是号应采用的遍历次序是_。A A先序先序 B B中序中序 C C后序后序 D D都不是都不是 设二叉树只有度为设二叉树只有度为0 0和和2 2的结点，其结点个数为的结点，其结点个数为2121，则该二叉树的最大深度为则该二叉树的最大深度为_。A A5 5 B B6 6 C C1010D
22、 D1111A先序先序D11树和二叉树树和二叉树2009考博试题考博试题利用哈夫曼算法为报文利用哈夫曼算法为报文“a big black bug bit a big a big 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
23、:2l:2t:1u:1 ”:8a:000b:001c:0100g:011i:100k:1010l:1011t:01010u:01011”:11tu2kl4c4i7g8ab12“352015图图2005试题试题 设图的邻接表的类型定义如下。若带权图中边的权值类型为设图的邻接表的类型定义如下。若带权图中边的权值类型为整型，请对该邻接表的类型定义做出适当修改，使之能够用于整型，请对该邻接表的类型定义做出适当修改，使之能够用于表示边带权的图。表示边带权的图。#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex;struct ArcNode
24、 *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试题试题算法算法FindPathFindPath是求图是求图G G中顶点中顶点v v到到s s的一条路径的一条路径PATH
25、PATH（用（用线性表表示的一个顶点序列）。顶点均用顶点的编号。线性表表示的一个顶点序列）。顶点均用顶点的编号。Status FindPath(Graph 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;i
26、f(v=s)return TRUE;for(w=FirstAdjVex(G,v);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 TRUE;if(FindPath(G,w,s,PATH)return TRUE;ListDelete(PATH,_ _);ListDelete(PATH,_ _);return FALSE;return FALSE;visitedw=FALSEListLength(PATH)在求连通网的最小
27、生成树时，普里姆在求连通网的最小生成树时，普里姆（PrimPrim）算法适用于）算法适用于_，克鲁斯卡尔，克鲁斯卡尔（KruskalKruskal）算法适用于）算法适用于_。拓扑排序可以用来检查拓扑排序可以用来检查_中是否中是否存在回路。回路。图图2007试题试题 下列图的存储结构中，只能用来表示有向图的是下列图的存储结构中，只能用来表示有向图的是A.A.邻接矩阵邻接矩阵B.B.邻接表邻接表C.C.十字链表十字链表D.D.邻接多重表邻接多重表有向图有向图 边稠密的网边稠密的网 C.十字链表十字链表边稀疏的网边稀疏的网图图2008试题试题TopologicalSortTopologicalSor
28、t是一个利用队列对图是一个利用队列对图G G进行拓扑排序的算法，请进行拓扑排序的算法，请在该算法的空白处填入合适的语句或表达式。在该算法的空白处填入合适的语句或表达式。提示：数组提示：数组InDegreeInDegree事先已存放每个顶点的入度；数组事先已存放每个顶点的入度；数组TopOrderTopOrder在算法执行后将存放每个顶点在拓扑排序中的顺序。在算法执行后将存放每个顶点在拓扑排序中的顺序。int TopologicalSort(Graph G)int TopologicalSort(Graph G)Queue Q;int Counter=0;int I,V,W;InitQueue(
29、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(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
30、!=-1;W=NextAdjVex(G,V,W)if(_)Enqueue(Q,W);if(_)Enqueue(Q,W);DestroyQueue(Q);return(Counter=G.vexnum);DestroyQueue(Q);return(Counter=G.vexnum);!QueueEmpty(Q)-IndegreeW=0图图2009试题试题下列关于无向连通图特性的叙述中，正确的是下列关于无向连通图特性的叙述中，正确的是 I I所有顶点的度之和为偶数所有顶点的度之和为偶数 II II边数大于顶点个数减边数大于顶点个数减1 1 III III至少有一个顶点的度为至少有一个顶点的度为1
31、 1A A只有只有I I B B只有只有IIII C CI I和和IIII D DI I和和IIIIIIA只有只有I一棵树有一棵树有20112011个节点，叶子节点为个节点，叶子节点为116116个，与其对应的个，与其对应的2 2叉树有叉树有 个节点没有右孩子？个节点没有右孩子？A A115 115 B B116116 C C18951895 D D18961896D图图2009考博试题考博试题 在图中判断两个顶点是否相邻，采用在图中判断两个顶点是否相邻，采用_存储结存储结构效率最高。构效率最高。A A邻接矩阵邻接矩阵B B邻接表邻接表C C十字链表十字链表D D邻接多重表邻接多重表A邻接矩阵
32、邻接矩阵 普里姆算法是用于求解普里姆算法是用于求解_的最小生成树。的最小生成树。A A无向图无向图B B无向连通图无向连通图C C无向连通网无向连通网D D无向网无向网C无向连通网无向连通网图图2009考博试题考博试题有向图的邻接表如图所示。有向图的邻接表如图所示。（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