2011年甘肃省数据分析高级

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\ free(p);

k1=pre->next; /*新的报数起点*/ }

printf(\"%4d\输出最后一个结点*/ free(k1); }

main()

{linklist head,p,r; int n,s,m,i; printf(\"n=\"); scanf(\"%d\ printf(\"s=\");

scanf(\"%d\ printf(\"m=\ scanf(\"%d\

if (n<1) printf(\"n<0\"); 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); /*调用函数*/ } }

3、本题要求建立有序的循环链表。从头到尾扫描数组A，取出A[i]（0<=i//由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点 {LinkedList h;

h=(LinkedList)malloc(sizeof(LNode));//申请结点 h->next=h; //形成空循环链表 for(i=0;inext;

while(p!=h && p->data{pre=p; p=p->next;} //查找A[i]的插入位置

if(p==h || p->data!=A[i]) //重复数据不再输入 {s=(LinkedList)malloc(sizeof(LNode));

s->data=A[i]; pre->next=s; s->next=p;//将结点s链入链表中 }

}//for

return(h); }算法结束

4、二部图（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为结点个数）。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【