1、设一棵树中度为k的结点数是nk（2≤k），求它的树叶的数目？ 2、证明: 简单连通无向图G的任何一条边，都是G的某一棵生成树的边。 3、画出产生前缀码{11,01,001,1001,1010}的二元树。
1、设一棵树中度为k的结点数是nk（2≤k），求它的树叶的数目？ 2、证明: 简单连通无向图G的任何一条边，都是G的某一棵生成树的边。 3、画出产生前缀码{11,01,001,1001,1010}的二元树。
参考答案和解析
12
相关考题：
阅读下列C程序和程序说明，将应填入(n)处的字句写在答题纸的对应栏内。【说明】用克鲁斯卡尔算法求解给定图的最小生成树。include ＜stdio. h＞include ＜stdlib. h＞define MAXN 30typedef struct{ int v1,v2; /*一条边依附的两个顶点*/int weight; /*边上的权值*/}EDGE;typedef struct{ int Vnum; /*图中的顶点数目*/EDGE e[MAXN*(MAXN-1)/2]; /*图中的边*/}Graph;typedef struct node{ /*用链表存储同一个连通分量的顶点*/int v;struct node *next;}Alist;void heapadjust(EDGE data[], int s, int m){ /*将元素序列data[s..m]调整为小顶堆, 堆顶元素(最小元素)为data[s]*/int j;EDGE t;t=data[s]; /*备份元素data[s], 为其找到适当位置后再插入*/for(j=2*s+1; j＜=m; j=j*2+1){/*沿值较小的子结点向下筛选*/if(j＜m (1)) ++j;if(!(t. weight＞data[j]. weight)) break;data[s]=data[j];s=j; /*用s记录待插入元素的位置(下标)*/}/*for*/data[s]=t; /*将备份元素插入由s所指出的插入位置*/}/*heapadjust*/int creat_graph(Graph *p) /*输入图中的顶点及边, 返回图中边的数目*/{ int k=0; /*记录图中边的数目*/int n;int v1,v2;int w;printf("vertex number of the graph:");scanf("%d", n); /*输入图中的顶点数目*/if(n＜1) return 0;p-＞Vnum=n;do{ printf("edge(vertex1,vertex2,weight):");scanf("%d %d %d", V1, v2, w);if(v1＞=0 v1＜n v2＞=0 v2＜n){p-＞e[k]. v1=v1; p-＞e[k]. v2=v2; p-＞e[k]. weight=w;k++;}/*if*/}while(!( (2) ));return k; /*返回图中边的数目*/}/*creat_graph*/int kruskal(Graph G, int enumber, int tree[][3]){ /*用kruskal算法求无向连通图G的最小生成树, 图中边所得数目为enumber, *//*数组tree[][3]中存放生成树中边的顶点和边上的权值, 函数返回生成树的代价*/int i, k, m, c=0;int v1, v2;Alist *p, *q, *a[MAXN];for(i=0; i＜G．Vnum; ++i){ /*将每个连通分量中的顶点存放在一个单链表中*/a[i]=(Alist*)malloc(sizeof(Alist));if(!a[i]) {printf("\n mernory allocation error!");exit(0);}/*if*/a[i]-＞v=i; a[i]-＞next=NULL;}/*for*/for(i=enumber-1; i＞=0; --i)/*按照边上的权值建立小顶堆*/heapadjust( (3) );k=G. Vnum; /*k用于计算图中的连通分量数目*/m=enumber-1;i=0;do{v1=G. e[0]. v1; v2=G. e[0]. v2;p=a[v1];while(p p-＞v!=v2){ /*判断当前选择的边的顶点是否在一个连通分量中*/q=p; p=p-＞next;}if(!p){ /*当前边的顶点不在一个连通分量中*/p=q;p-＞next=a[G. e[0]. v2];&nb
阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】 应用Prim算法求解连通网络的最小生成树问题。请阅读程序后填空。const int MaxInt＝INT MAX； //INT MAX的值在＜limits．h＞中const int n＝6； //图的顶点数，应由用户定义typedef int AdjMatrix[n][n]； //用二维数组作为邻接矩阵表示typedef struct{ //生成树的边结点int fromVex，to Vex； //边的起点与终点int weight； //边上的权值}TreeEdSenode；typedef TreeEdgeNode MST[n-1]； //最小生成树定义void PrimMST (AdjMatrix G，MST T，int rt){//从顶点rt出发构造图G的最小生成树T，rt成为树的根结点TreeEdgeNode e； int i，k＝0，min，minpos，v；for(i＝0；i＜n；i++) //初始化最小生成树Tif(i!＝rt){T[k]．fromVex＝rt；(1)；T[k++].weight＝G[rt][i]；}for(k＝0；k＜n-1；k++){ //依次求MST的候选边(2)；for(i＝k；i＜n-1；i++) 八遍历当前候选边集合if(T[i].weight＜min) //选具有最小权值的候选边{min＝T[i]．weight；(3)；}if(min＝＝MaxInt) //图不连通，出错处理{cerr＜＜“Graph is disconnected!”＜＜endl； exit(1)；}e=T[minpos]；T[minpos]＝T[k]；(4)；v=T[k].to Vex；for(i＝k+1；i＜n-1；i++) //修改候选边集合if(G[v][T[i].to Vex]＜T[i].weight){T[i]．weight＝G[v][T[i].toVex]；(5)；}}}
●试题四阅读下列算法说明和算法，将应填入(n)的字句写在答题纸的对应栏内。【说明】下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。图5算法流程图【算法】/*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个"有序表"。以顺序表MSTree返回生成树上各条边。*/typedef struct{VertexType vex1；VertexType vex2；VRType weight；}EdgeType；typedef ElemType EdgeType；typedef struct{//有向网的定义VertexType vexs[MAX_VERTEX_NUM]；//顶点信息EdgeType edge[MAX_EDGE_NUM]；//边的信息int vexnum，arcnum；//图中顶点的数目和边的数目}ELGraph；void MiniSpanTree_Kruskal(ELGraph G，SqList MSTree){//G.edge 中依权值从小到大存放有向网中各边//生成树的边存放在顺序表MSTree中MFSetF；InitSet(F，G.vexnum)；//将森林F初始化为n棵树的集合InitList(MSTree，G.vexnum)；//初始化生成树为空树i=0；k=1；while(k (1) ){e=G.edge[i]；//取第i条权值最小的边/*函数fix_mfset返回边的顶点所在树的树根代号，如果边的两个顶点所在树的树根相同，则说明它们已落在同一棵树上。*/rl=fix_mfset(F，LocateVex(e.vex1))；r2= (2) //返回两个顶点所在树的树根if(r1 (3) r2){//选定生成树上第k条边if(ListInsert(MSTree，k，e){ (4) ；//插入生成树mix_mfset(E，rl，r2)；//将两棵树归并为一棵树}(5) ；//继续考察下一条权值最小边}DestroySet(F)；}
多选题关于树，以下叙述（）正确。A树是连通、无圈的图B任一树，添加一条边便含圈C任一树的边数等于点数减1D任一树的点数等于边数减1E任一树，去掉_条边便不连通