首页 > 2014年湖南省数据分析高级

2014年湖南省数据分析高级

发布时间：来源：文档文库

小中大

字号：

手机查看

1、设有一个数组中存放了一个无序的关键序列K1、K2、„、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。
51.借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。请编写出算法并简要说明算法思想。
2、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。3、设有一组初始记录关键字序列（K1，K2，„，Kn），要求设计一个算法能够在O(n的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。
voidquickpass(intr[],ints,intt{
inti=s,j=t,x=r[s];while(i
while(ixj=j-1;if(iwhile(i}
r[i]=x;}
4、约瑟夫环问题（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;/*调用函数*/}}

本文来源：https://www.2haoxitong.net/k/doc/9e1dc9f7ad02de80d4d840fb.html