1、若第n 件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。若第n 件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s ）。若最终s=0,则有一解；否则，若s0但物品数n
（1）s-w[n],n-1 //Knap(s-w[n],n-1)=true
（2）s,n-1 // Knap←Knap(s,n-1)
2、(1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild)
(5)ADDQ(Q,p->rchild)
25. (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild)
(5)count(t->rchild)
26. .(1)top++ (2) stack[top]=p->rchild (3)top++
(4)stack[top]=p->lchild
27. (1)*ppos // 根结点（2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1
3、连通图的生成树包括图中的全部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
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i
{edge[0]=edge[i]; j=i-1;
while (edge[j].w
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()是测试图是否连通的函数，可用图的遍历实现，
4、若第n 件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。若第n 件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s ）。若最终s=0,则有一解；否则，若s0但物品数n
（1）s-w[n],n-1 //Knap(s-w[n],n-1)=true
（2）s,n-1 // Knap←Knap(s,n-1)
5、约瑟夫环问题（Josephus 问题）是指编号为1、2、„，n 的n （n>0）个人按顺时针方向围坐成一圈，现从第s 个人开始按顺时针方向报数，数到第m 个人出列，然后从出列的下一个人重新开始报数，数到第m 的人又出列，„，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。
#include
typedef int datatype;
typedef struct node
{datatype data;
struct node *next;
}listnode;
typedef listnode *linklist;
void jose(linklist head,int s,int m)
{linklist k1,pre,p;
int count=1;
pre=NULL;
k1=head; /*k1为报数的起点*/
while (count!=s) /*找初始报数起点*/
{pre=k1;
k1=k1->next;
count++;
}
while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/
{ p=k1; /*从k1开始报数*/
count=1;
while (count!=m) /*连续数m 个结点*/
{ pre=p;
p=p->next;
count++;
}
pre->next=p->next; /*输出该结点，并删除该结点*/
printf("%4d",p->data);
free(p);
k1=pre->next; /*新的报数起点*/
}
printf("%4d",k1->data); /*输出最后一个结点*/
free(k1);
}
main()
{linklist head,p,r;
int n,s,m,i;
printf("n=");
scanf("%d",&n);
printf("s=");
scanf("%d",&s);
printf("m=",&m);
scanf("%d",&m);
if (n
else
{/*建表*/
head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/
head->data=n;
r=head;
for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/
{ p=(linklist)malloc(sizeof(listnode));
p->data=i;
p->next=head;
head=p;
}
r->next=head; /*生成循环链表*/
jose(head,s,m); /*调用函数*/
}
}
6、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre （初值为null ）和全局变量flag ，初值为true 。若非二叉排序树，则置flag 为false 。
#define true 1
#define false 0
typedef struct node
{datatype data; struct node *llink,*rlink;} *BTree;
void JudgeBST（BTree t,int flag）
// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论。 { if（t!=null && flag）
{ Judgebst（t->llink,flag）；// 中序遍历左子树
if（pre==null）pre=t；// 中序遍历的第一个结点不必判断
else if（pre->datadata）pre=t；//前驱指针指向当前结点
else{flag=flase；} //不是完全二叉树
Judgebst （t->rlink,flag）；// 中序遍历右子树
}//JudgeBST算法结束
7、连通图的生成树包括图中的全部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
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i
{edge[0]=edge[i]; j=i-1;
while (edge[j].w
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()是测试图是否连通的函数，可用图的遍历实现，
8、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,} 写出G 的拓扑排序的结果。
G 拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7
9、4、 void LinkList_reverse(Linklist &L)
//链表的就地逆置; 为简化算法, 假设表长大于2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next; //把L 的元素逐个插入新表表头
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse
10、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。
void Translation（float *matrix，int n）
//本算法对n ×n 的矩阵matrix ，通过行变换，使其各行元素的平均值按递增排列。 {int i,j,k,l；
float sum，min ； //sum暂存各行元素之和
float *p, *pi, *pk;
for(i=0; i
{sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1个元素.
for (j=0; j
*(p+i)=sum; //将一行元素之和存入一维数组.
}//for i
for(i=0; i
{min=*(p+i); k=i; //初始设第i 行元素之和最小.
for(j=i+1;j
pi=matrix+n*i; //pi指向第i 行第1个元素.
for(j=0;j
{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}
sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和.
}//if
}//for i
free(p); //释放p 数组.
}// Translation
[算法分析] 算法中使用选择法排序, 比较次数较多, 但数据交换(移动) 较少. 若用其它排序方法, 虽可减少比较次数, 但数据移动会增多. 算法时间复杂度为O(n2).
11、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）
有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完; 已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs （v ）结束前出现顶点u 到v 的回边，则图中必有包含顶点v 和u 的回路。对应程序中v 的状态为1，而u 是正访问的顶点，若我们找出u 的下一邻接点的状态为1，就可以输出回路了。
void Print(int v,int start ) //输出从顶点start 开始的回路。
{for(i=1;i
if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i ），且顶点i 的状态为1。 {printf(“%d”,v);
if(i==start) printf(“\n”); else Print(i,start);break;}//if
void dfs(int v)
{visited[v]=1;
for(j=1;j
if (g[v][j]!=0) //存在边(v,j)
if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if
else {cycle=1; Print(j,j);}
visited[v]=2;
}//dfs
void find_cycle() //判断是否有回路，有则输出邻接矩阵。visited 数组为全局变量。 {for (i=1;i
for (i=1;i
}//find_cycle
12、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p 和q 分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR （ROOT ，p,q,r ）, 该算法找到p 和q 的最近共同祖先结点r 。
13、约瑟夫环问题（Josephus 问题）是指编号为1、2、„，n 的n （n>0）个人按顺时针方向围坐成一圈，现从第s 个人开始按顺时针方向报数，数到第m 个人出列，然后从出列的下一个人重新开始报数，数到第m 的人又出列，„，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。
#include
typedef int datatype;
typedef struct node
{datatype data;
struct node *next;
}listnode;
typedef listnode *linklist;
void jose(linklist head,int s,int m)
{linklist k1,pre,p;
int count=1;
pre=NULL;
k1=head; /*k1为报数的起点*/
while (count!=s) /*找初始报数起点*/
{pre=k1;
k1=k1->next;
count++;
}
while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/
{ p=k1; /*从k1开始报数*/
count=1;
while (count!=m) /*连续数m 个结点*/
{ pre=p;
p=p->next;
count++;
}
pre->next=p->next; /*输出该结点，并删除该结点*/
printf("%4d",p->data);
free(p);
k1=pre->next; /*新的报数起点*/
}
printf("%4d",k1->data); /*输出最后一个结点*/
free(k1);
}
main()
{linklist head,p,r;
int n,s,m,i;
printf("n=");
scanf("%d",&n);
printf("s=");
scanf("%d",&s);
printf("m=",&m);
scanf("%d",&m);
if (n
else
{/*建表*/
head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/
head->data=n;
r=head;
for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/
{ p=(linklist)malloc(sizeof(listnode));
p->data=i;
p->next=head;
head=p;
}
r->next=head; /*生成循环链表*/
jose(head,s,m); /*调用函数*/
}
}
14、给定n 个村庄之间的交通图，若村庄i 和j 之间有道路，则将顶点i 和j 用边连接，边上的Wij 表示这条道路的长度，现在要从这n 个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短? 试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。20分
void Hospital(AdjMatrix w,int n)
//在以邻接带权矩阵表示的n 个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。
{for (k=1;k
for (i=1;i
for (j=1;j
if (w[i][k]+w[k][j]
m=MAXINT; //设定m 为机器内最大整数。
for (i=1;i
{s=0;
for (j=1;js) s=w[i][j];
if (s
Printf(“医院应建在%d村庄，到医院距离为%d\n”,i,m);
}//for
}//算法结束
对以上实例模拟的过程略。各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中, 离医院最远的村庄到医院的距离是6。
1、对图1所示的连通网G ，请用Prim 算法构造其最小生成树（每选取一条边画一个图）。
15、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。
void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2)
//将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。 {if(h1>=l1)
{post[h2]=pre[l1]; //根结点
half=(h1-l1)/2; //左或右子树的结点数
PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列 PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列 } }//PreToPost
32. . 叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre ，初始为空。第一个叶子结点由指针head 指向，遍历到叶子结点时，就将它前驱的rchild 指针指向它，最后叶子结点的rchild 为空。
LinkedList head,pre=null; //全局变量
LinkedList InOrder(BiTree bt)
//中序遍历二叉树bt ，将叶子结点从左到右链成一个单链表，表头指针为head {if(bt){InOrder(bt->lchild); //中序遍历左子树
if(bt->lchild==null && bt->rchild==null) //叶子结点
if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点
else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表
InOrder(bt->rchild); //中序遍历左子树
pre->rchild=null; //设置链表尾
}
return(head); } //InOrder
时间复杂度为O(n),辅助变量使用head 和pre, 栈空间复杂度O(n)
1、若第n 件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。若第n 件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s ）。若最终s=0,则有一解；否则，若s0但物品数n
（1）s-w[n],n-1 //Knap(s-w[n],n-1)=true
（2）s,n-1 // Knap←Knap(s,n-1)
2、(1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild)
(5)ADDQ(Q,p->rchild)
25. (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild)
(5)count(t->rchild)
26. .(1)top++ (2) stack[top]=p->rchild (3)top++
(4)stack[top]=p->lchild
27. (1)*ppos // 根结点（2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1
3、连通图的生成树包括图中的全部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
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i
{edge[0]=edge[i]; j=i-1;
while (edge[j].w
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()是测试图是否连通的函数，可用图的遍历实现，
4、若第n 件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。若第n 件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s ）。若最终s=0,则有一解；否则，若s0但物品数n
（1）s-w[n],n-1 //Knap(s-w[n],n-1)=true
（2）s,n-1 // Knap←Knap(s,n-1)
5、约瑟夫环问题（Josephus 问题）是指编号为1、2、„，n 的n （n>0）个人按顺时针方向围坐成一圈，现从第s 个人开始按顺时针方向报数，数到第m 个人出列，然后从出列的下一个人重新开始报数，数到第m 的人又出列，„，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。
#include
typedef int datatype;
typedef struct node
{datatype data;
struct node *next;
}listnode;
typedef listnode *linklist;
void jose(linklist head,int s,int m)
{linklist k1,pre,p;
int count=1;
pre=NULL;
k1=head; /*k1为报数的起点*/
while (count!=s) /*找初始报数起点*/
{pre=k1;
k1=k1->next;
count++;
}
while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/
{ p=k1; /*从k1开始报数*/
count=1;
while (count!=m) /*连续数m 个结点*/
{ pre=p;
p=p->next;
count++;
}
pre->next=p->next; /*输出该结点，并删除该结点*/
printf("%4d",p->data);
free(p);
k1=pre->next; /*新的报数起点*/
}
printf("%4d",k1->data); /*输出最后一个结点*/
free(k1);
}
main()
{linklist head,p,r;
int n,s,m,i;
printf("n=");
scanf("%d",&n);
printf("s=");
scanf("%d",&s);
printf("m=",&m);
scanf("%d",&m);
if (n
else
{/*建表*/
head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/
head->data=n;
r=head;
for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/
{ p=(linklist)malloc(sizeof(listnode));
p->data=i;
p->next=head;
head=p;
}
r->next=head; /*生成循环链表*/
jose(head,s,m); /*调用函数*/
}
}
6、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre （初值为null ）和全局变量flag ，初值为true 。若非二叉排序树，则置flag 为false 。
#define true 1
#define false 0
typedef struct node
{datatype data; struct node *llink,*rlink;} *BTree;
void JudgeBST（BTree t,int flag）
// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论。 { if（t!=null && flag）
{ Judgebst（t->llink,flag）；// 中序遍历左子树
if（pre==null）pre=t；// 中序遍历的第一个结点不必判断
else if（pre->datadata）pre=t；//前驱指针指向当前结点
else{flag=flase；} //不是完全二叉树
Judgebst （t->rlink,flag）；// 中序遍历右子树
}//JudgeBST算法结束
7、连通图的生成树包括图中的全部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
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i
{edge[0]=edge[i]; j=i-1;
while (edge[j].w
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()是测试图是否连通的函数，可用图的遍历实现，
8、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,} 写出G 的拓扑排序的结果。
G 拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7
9、4、 void LinkList_reverse(Linklist &L)
//链表的就地逆置; 为简化算法, 假设表长大于2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next; //把L 的元素逐个插入新表表头
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse
10、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。
void Translation（float *matrix，int n）
//本算法对n ×n 的矩阵matrix ，通过行变换，使其各行元素的平均值按递增排列。 {int i,j,k,l；
float sum，min ； //sum暂存各行元素之和
float *p, *pi, *pk;
for(i=0; i
{sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1个元素.
for (j=0; j
*(p+i)=sum; //将一行元素之和存入一维数组.
}//for i
for(i=0; i
{min=*(p+i); k=i; //初始设第i 行元素之和最小.
for(j=i+1;j
pi=matrix+n*i; //pi指向第i 行第1个元素.
for(j=0;j
{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}
sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和.
}//if
}//for i
free(p); //释放p 数组.
}// Translation
[算法分析] 算法中使用选择法排序, 比较次数较多, 但数据交换(移动) 较少. 若用其它排序方法, 虽可减少比较次数, 但数据移动会增多. 算法时间复杂度为O(n2).
11、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）
有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完; 已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs （v ）结束前出现顶点u 到v 的回边，则图中必有包含顶点v 和u 的回路。对应程序中v 的状态为1，而u 是正访问的顶点，若我们找出u 的下一邻接点的状态为1，就可以输出回路了。
void Print(int v,int start ) //输出从顶点start 开始的回路。
{for(i=1;i
if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i ），且顶点i 的状态为1。 {printf(“%d”,v);
if(i==start) printf(“\n”); else Print(i,start);break;}//if
void dfs(int v)
{visited[v]=1;
for(j=1;j
if (g[v][j]!=0) //存在边(v,j)
if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if
else {cycle=1; Print(j,j);}
visited[v]=2;
}//dfs
void find_cycle() //判断是否有回路，有则输出邻接矩阵。visited 数组为全局变量。 {for (i=1;i
for (i=1;i
}//find_cycle
12、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p 和q 分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR （ROOT ，p,q,r ）, 该算法找到p 和q 的最近共同祖先结点r 。
13、约瑟夫环问题（Josephus 问题）是指编号为1、2、„，n 的n （n>0）个人按顺时针方向围坐成一圈，现从第s 个人开始按顺时针方向报数，数到第m 个人出列，然后从出列的下一个人重新开始报数，数到第m 的人又出列，„，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。
#include
typedef int datatype;
typedef struct node
{datatype data;
struct node *next;
}listnode;
typedef listnode *linklist;
void jose(linklist head,int s,int m)
{linklist k1,pre,p;
int count=1;
pre=NULL;
k1=head; /*k1为报数的起点*/
while (count!=s) /*找初始报数起点*/
{pre=k1;
k1=k1->next;
count++;
}
while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/
{ p=k1; /*从k1开始报数*/
count=1;
while (count!=m) /*连续数m 个结点*/
{ pre=p;
p=p->next;
count++;
}
pre->next=p->next; /*输出该结点，并删除该结点*/
printf("%4d",p->data);
free(p);
k1=pre->next; /*新的报数起点*/
}
printf("%4d",k1->data); /*输出最后一个结点*/
free(k1);
}
main()
{linklist head,p,r;
int n,s,m,i;
printf("n=");
scanf("%d",&n);
printf("s=");
scanf("%d",&s);
printf("m=",&m);
scanf("%d",&m);
if (n
else
{/*建表*/
head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/
head->data=n;
r=head;
for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/
{ p=(linklist)malloc(sizeof(listnode));
p->data=i;
p->next=head;
head=p;
}
r->next=head; /*生成循环链表*/
jose(head,s,m); /*调用函数*/
}
}
14、给定n 个村庄之间的交通图，若村庄i 和j 之间有道路，则将顶点i 和j 用边连接，边上的Wij 表示这条道路的长度，现在要从这n 个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短? 试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。20分
void Hospital(AdjMatrix w,int n)
//在以邻接带权矩阵表示的n 个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。
{for (k=1;k
for (i=1;i
for (j=1;j
if (w[i][k]+w[k][j]
m=MAXINT; //设定m 为机器内最大整数。
for (i=1;i
{s=0;
for (j=1;js) s=w[i][j];
if (s
Printf(“医院应建在%d村庄，到医院距离为%d\n”,i,m);
}//for
}//算法结束
对以上实例模拟的过程略。各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中, 离医院最远的村庄到医院的距离是6。
1、对图1所示的连通网G ，请用Prim 算法构造其最小生成树（每选取一条边画一个图）。
15、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。
void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2)
//将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。 {if(h1>=l1)
{post[h2]=pre[l1]; //根结点
half=(h1-l1)/2; //左或右子树的结点数
PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列 PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列 } }//PreToPost
32. . 叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre ，初始为空。第一个叶子结点由指针head 指向，遍历到叶子结点时，就将它前驱的rchild 指针指向它，最后叶子结点的rchild 为空。
LinkedList head,pre=null; //全局变量
LinkedList InOrder(BiTree bt)
//中序遍历二叉树bt ，将叶子结点从左到右链成一个单链表，表头指针为head {if(bt){InOrder(bt->lchild); //中序遍历左子树
if(bt->lchild==null && bt->rchild==null) //叶子结点
if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点
else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表
InOrder(bt->rchild); //中序遍历左子树
pre->rchild=null; //设置链表尾
}
return(head); } //InOrder
时间复杂度为O(n),辅助变量使用head 和pre, 栈空间复杂度O(n)