当前位置:首页 >> 其它课程 >>

2012年云南省数据概述基础


1、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n-1条边为止。
void SpnTree (AdjList g)
//

用“破圈法”求解带权连通无向图的一棵最小代价生成树。
{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数
node edge[];
scanf( "%d%d",&e,&n) ; //输入边数和顶点数。
for (i=1;i<=e;i++) //输入e条边:顶点,权值。
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i<=e;i++) //按边上的权值大小,对边进行逆序排序。
{edge[0]=edge[i]; j=i-1;
while (edge[j].w<edge[0].w) edge[j+1]=edge[j--];
edge[j+1]=edge[0]; }//for
k=1; eg=e;
while (eg>=n) //破圈,直到边数e=n-1.
{if (connect(k)) //删除第k条边若仍连通。
{edge[k].w=0; eg--; }//测试下一条边edge[k],权值置0表示该边被删除
k++; //下条边
}//while
}//算法结束。
  connect()是测试图是否连通的函数,可用图的遍历实现,

2、给定n个村庄之间的交通图,若村庄i和j之间有道路,则将顶点i和j用边连接,边上的Wij表示这条道路的长度,现在要从这n个村庄中选择一个村庄建一所医院,问这所医院应建在哪个村庄,才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法,并应用该算法解答如图所示的实例。(20分)
3、设t是给定的一棵二叉树,下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量,且在调用count(t)之前都置为0.
typedef struct node
{int data; struct node *lchild,*rchild;}node;
int N2,NL,NR,N0;
void count(node *t)
{if (t->lchild!=NULL) if (1)___ N2++; else NL++;
else if (2)___ NR++; else (3)__ ;
if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;
}
26.树的先序非递归算法。
void example(b)
btree *b;
{ btree *stack[20], *p;
int top;
if (b!=null)
{ top=1; stack[top]=b;
while (top>0)
{ p=stack[top]; top--;
printf(“%d”,p->data);
if (p->rchild!=null)
{(1)___; (2)___;
}
if (p->lchild!=null)
(3)___; (4)__;
}}}}


相关文章:
2012云南省数据简介基础
2012云南省数据简介基础_中医中药_医药卫生_专业资料。1、对一般二叉树,仅根据一个先序、中序、后序遍历,不能确定另一个遍历序列。但对于满 二叉树,任一结点的...
2012年云南省数据总结基础
2012年云南省数据总结基础_韩语学习_外语学习_教育专区。2012年云南省数据总结基础 1、 根据二叉排序树中序遍历所得结点值为增序的性质, 在遍历中将当前遍历结点...
2012年云南省基础数据基础
2012年云南省基础数据基础_韩语学习_外语学习_教育专区。2012年云南省基础数据基础 1、 我们可用 “破圈法” 求解带权连通无向图的一棵最小代价生成树。 所谓 ...
2012年云南省基础数据基础
2012年云南省基础数据基础_韩语学习_外语学习_教育专区。2012年云南省基础数据基础 1、 我们可用 “破圈法” 求解带权连通无向图的一棵最小代价生成树。 所谓 ...
2012年云南省数据整理基础
2012年云南省数据整理基础_韩语学习_外语学习_教育专区。2012年云南省数据整理基础 1、假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和...
2012年云南省数据概述要领
2012年云南省数据概述要领_韩语学习_外语学习_教育专区。2012年云南省数据概述要领 1、冒泡排序算法是把大的元素向上移(气泡的上浮) ,也可以把小的元素向下移(...
2012年云南省数据分析基础
2012年云南省数据分析基础_韩语学习_外语学习_教育专区。2012年云南省数据分析基础 1、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列中的...
2012年云南省数据统计基础
2012年云南省数据统计基础_韩语学习_外语学习_教育专区。2012年云南省数据统计基础 1 、二路插入排序是将待排关键字序列 r[1..n] 中关键字分二路分别按序插入...
2012年云南省理论数据基础
2012年云南省理论数据基础_韩语学习_外语学习_教育专区。2012年云南省理论数据基础 1、设指针变量 p 指向双向链表中结点 A,指针变量 q 指向被插入结点 B,要求给...
2012年云南省数据入门
2012年云南省数据入门_韩语学习_外语学习_教育专区。2012年云南省数据入门 1、两棵空二叉树或仅有根结点的二叉树相似;对非空二叉树,可判左右子树是否相似,采用 ...
更多相关标签:
云南省地理区位概述 | 2012年10月4日 云南省 | 云南省基础设施配套费 | 云南省基础设施建设 | 云南省公共基础知识 | 2012年云南省著名商标 | 云南省基础研究 | 云南省综合货运量2012 |