1、已知有向图g=(v,e)，其中v=，e=
写出g的拓扑排序的结果。
g拓扑排序的结果是：v1、v2、v4、v3、v5、v6、v7
2、设t是一棵满二叉树，编写一个将t的先序遍历序列转换为后序遍历序列的递归算法。
3、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。
若仍连通，继续向下删；直到剩n-1条边为止。
void spntree (adjlist g)
//用“破圈法”求解带权连通无向图的一棵最小代价生成树。
typedef struct 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++)按边上的权值大小，对边进行逆序排序。
//fork=1; eg=e;
while (eg>=n破圈，直到边数e=n-1.
if (connect(k)) 删除第k条边若仍连通。
edge[k].w=0; eg--;测试下一条边edge[k]，权值置0表示该边被删除。
k++;下条边。
while
//算法结束。
connect()是测试图是否连通的函数，可用图的遍历实现，4、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
29. ①试找出满足下列条件的二叉树。
1）先序序列与后序序列相同 2）中序序列与后序序列相同。
3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同
5、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。
void longestpath(bitree bt)//求二叉树中的第一条最长路径长度。
bitree p=bt,l,s;l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点。
int i，top=0,tag,longest=0;
while(p ||top>0)
//沿左分枝向下。
if(tag[top]==1) /当前结点的右分枝已遍历。
/保留当前最长路径到l栈，记住最高栈顶指针，退栈。
else if(top>0) 沿右子分枝向下。
}//while(p!=null||top>0)
//结束longestpath
6、设t是一棵满二叉树，编写一个将t的先序遍历序列转换为后序遍历序列的递归算法。
7、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。
后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。
typedef struct
//沿左分枝向下。
if(bt==p) /不失一般性，假定p在q的左侧，遇结点p时，栈中元素均为p的祖先结点。
for(i=1;i<=top;i++)s1[i]=s[i]; top1=top; }将栈s的元素转入辅助栈s1 保存。
if(bt==q) /找到q 结点。
for(i=top;i>0;i--)将栈中元素的树结点到s1去匹配。
pp=s[i].t;
for (j=top1;j>0;j--)
if(s1[j].t==pp)
while(top!=0 &&s[top].tag==1) top退栈。
if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ 沿右分枝向下遍历。
//结束while(bt!=null ||top>0)
return(null);/p无公共祖先。
//结束ancestor
8、二部图（bipartite graph） g=（v，e）是一个能将其结点集v分为两不相交子集v 1和v2=v-v1的无向图，使得：v1中的任何两个结点在图g中均不相邻，v2中的任何结点在图g中也均不相邻。
1）．请各举一个结点个数为5的二部图和非二部图的例子。
2）．请用c或pascal编写一个函数bipartite判断一个连通无向图g是否是二部图，并分析程序的时间复杂度。设g用二维数组a来表示，大小为n*n（n为结点个数）。请在程序中加必要的注释。
若有必要可直接利用堆栈或队列操作。【
9、 将顶点放在两个集合v1和v2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。
int bpgraph (adjmatrix g)
判断以邻接矩阵表示的图g是否是二部图。
//初始化，各顶点未确定属于那个集合。
q[1]=1; r=1; s[1]=1;//顶点1放入集合s1
while(f /邻接点入队列。
else if (s[j]==s[v]) return(0);}非二部图。
}//if (!visited[v])
//while
return(1); 是二部图。
算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。
10、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
29. ①试找出满足下列条件的二叉树。
1）先序序列与后序序列相同 2）中序序列与后序序列相同。
3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同
11、在有向图g中，如果r到g中的每个结点都有路径可达，则称结点r为g的根结点。编写一个算法完成下列功能：
1）．建立有向图g的邻接表存储结构；
2）．判断有向图g是否有根，若有，则打印出所有根结点的值。
12、约瑟夫环问题（josephus问题）是指编号为、…n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。
#include<>
typedef int datatype;
typedef struct node
2024年福建省
2010年福建省 闽江杯 优质工程奖 建筑装修工程 项目名单。序。工程名称。号。漳州天利房地产发展有限厦门市港龙装修工程有。1天利仁和商务中心装修工程。公司。五缘水乡工程b标b2标段 2 厦门路桥建设集团有限公厦门市港龙装修工程有。2号楼 游泳馆网球馆 装修。司。工程。五缘水乡工程b标b3标段装厦门...
2024年福建省高考
文科数学试卷分析及对平时教学的启示。永安三中张建钢。2009年的高考数学试卷是我省实施课标课程后的第一份 课标卷 因此受到各方高度关注。本人作为09届高三的一线执教的教师，借此机会向各位老师谈一些自己对今年文科数学卷的认识和对平时教学的体会 一。2009年文科数学试卷考查主要内容 二。对2009年文...
2019福建省实用类
福建省实用类。乙 实用类文本阅读 15分 阅读下面的文字，完成l3 15题。蟋蟀之话。夏丏尊。鸣虫是秋季的报知者。蟋蟀的鸣声，本质上与鸟或蝉的鸣声大异其趣。乌或蝉的鸣声是肉声，而蟋蟀的鸣声是器乐。丝不如竹，竹不如肉 我国从来有这样的话，意思是说器乐不如肉声。其实就 上说，乐器比之我们人的声带，构造要...