当前位置：首页> 2014广东省C语言版高级

2014广东省C语言版高级

时间：下载该word文档

1、约瑟夫环问题（Josephus问题）是指编号为1、2、„，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，„，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。#includetypedefintdatatype;typedefstructnode{datatypedata;structnode*next;}listnode;
typedeflistnode*linklist;
voidjose(linklisthead,ints,intm{linklistk1,pre,p;intcount=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(
{linklisthead,p,r;intn,s,m,i;printf("n=";scanf("%d",&n;printf("s=";scanf("%d",&s;

printf("m=",&m;scanf("%d",&m;
if(n<1printf("n<0";else{/*建表*/
head=(linklistmalloc(sizeof(listnode;/*建第一个结点*/head->data=n;r=head;
for(i=n-1;i>0;i--/*建立剩余n-1个结点*/{p=(linklistmalloc(sizeof(listnode;p->data=i;p->next=head;head=p;}
r->next=head;/*生成循环链表*/jose(head,s,m;/*调用函数*/}}
2、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。
intSimilar(BiTreep,q//判断二叉树p和q是否相似{if(p==null&&q==nullreturn(1;elseif(!p&&q||p&&!qreturn(0;
elsereturn(Similar(p->lchild,q->lchild&&Similar(p->rchild,q->rchild}//结束Similar
3、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。
voidPreToPost(ElemTypepre[],post[],intl1,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//将右子树先序序列转为后序序列}}//PreToPost32..叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。LinkedListhead,pre=null;//全局变量LinkedListInOrder(BiTreebt
//中序遍历二叉树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
4、若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。若第n件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s）。若最终s=0,则有一解；否则，若s<0或虽然s>0但物品数n<1,则无解。
（1）s-w[n],n-1//Knap(s-w[n],n-1=true（2）s,n-1//Knap←Knap(s,n-1
5、本题应使用深度优先遍历，从主调函数进入dfs(v时，开始记数，若退出dfs(前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs(过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。
intnum=0，visited[]=0//num记访问顶点个数,访问数组visited初始化。constn=用户定义的顶点数;
AdjListg;//用邻接表作存储结构的有向图g。voiddfs(v
{visited[v]=1;num++;//访问的顶点数＋1
if(num==n{printf(“%d是有向图的根。\n”,v;num=0;}//ifp=g[v].firstarc;while(p
{if(visied[p->adjvex]==0dfs(p->adjvex;p=p->next;}//while
visited[v]=0;num--;//恢复顶点v}//dfs
voidJudgeRoot(
//判断有向图是否有根，有根则输出之。{staticinti;
for(i=1;i<=n;i++//从每个顶点出发，调用dfs(各一次。{num=0;visited[1..n]=0;dfs(i;}}//JudgeRoot
算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。

6、二部图（bipartitegraph）G=（V，E）是一个能将其结点集V分为两不相交子集V1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。（1）．请各举一个结点个数为5的二部图和非二部图的例子。（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G