2011级计算机学院课程设计题目及参考程序

问题A:整数排序一时间限制:20Sec内存限制:128MB题目描述经过三天的任务１的训练，大家的确辛苦了．因此，在任务２开始时，我为大家准备了一道令人非常愉快的热身题．即将一个杂乱无序的整数序列，按照从小到大的顺序排列并输出．输入测试数据不止一组，每组测试数据：１）先输入无序序列的整数个数n；(n不超过1000000)２）然后连续输入n个整数；若n的值输入为０值，则输入结束．输出与每组输入的测试数据相对应，输出其按从小到大排好序后的整数序列．注意：每组输出占一行．样例输入10987654321-1588776655330样例输出-11234567893355667788提示本题测试对第10章“内部排序”的理解程度。可采用冒泡排序、插入排序、选择排序、快速排序、希尔排序、堆排序等方法完成此题。警告：目的是让大家熟悉内部排序的各种算法，因此禁止调用sort或qsort等函数！不改正者降最终成绩等级．简单排序版：#includestdio.h#includestdlib.h#defineSIZE10000voidfastsort(inta[],intn){inti,j,k,temp;for(i=0;in-1;i++){k=i;for(j=i+1;jn;j++)if(a[j]a[k])k=j;if(i!=k){temp=a[i];a[i]=a[k];a[k]=temp;}}}intmain(){intsort[SIZE];intnum,i;while(1){scanf(%d,&num);if(num==0)exit(0);for(i=0;inum;i++){scanf(%d,&sort[i]);}fastsort(sort,num);for(i=0;inum;i++){if(i==num-1)printf(%d,sort[i]);elseprintf(%d,sort[i]);}printf(\n);}return0;}快速排序版：#includestdio.h#defineSIZE100000voidquick_sort(inta[],intlow,inthigh){inti,j,t;if(lowhigh){i=low;j=high;t=a[low];while(ij){while(ij&&a[j]t)j--;if(ij){a[i]=a[j];i++;}while(ij&&a[i]=t)i++;if(ij){a[j]=a[i];j--;}}a[i]=t;quick_sort(a,low,i-1);quick_sort(a,i+1,high);}}intmain(){intsort[SIZE];intnum,i;while(1){scanf(%d,&num);if(num==0)return0;for(i=0;inum;i++){scanf(%d,&sort[i]);}quick_sort(sort,0,num-1);for(i=0;inum;i++){if(i==num-1)printf(%d,sort[i]);elseprintf(%d,sort[i]);}printf(\n);}return0;}堆排序版：#defineMAX10000#includestdio.hvoidsift(int*x,intn,ints){intt,k,j;t=*(x+s);k=s;j=2*k+1;while(jn){if(jn-1&&*(x+j)*(x+j+1)){j++;}if(t*(x+j)){*(x+k)=*(x+j);k=j;j=2*k+1;}else{break;}}*(x+k)=t;}voidheap_sort(int*x,intn){inti,k,t;int*p;for(i=n/2-1;i=0;i--){sift(x,n,i);}for(k=n-1;k=1;k--){t=*(x+0);*(x+0)=*(x+k);*(x+k)=t;sift(x,k,0);}}intmain(){int*p,i,a[MAX],num;while(1){p=a;scanf(%d,&num);if(num==0)return0;for(i=0;inum;i++)scanf(%d,p++);p=a;heap_sort(p,num);for(i=0;inum;i++){if(i==num-1)printf(%d,a[i]);elseprintf(%d,a[i]);}printf(\n);}return0;}问题B:整数排序二时间限制:20Sec内存限制:128MB题目描述在完成了任务２的第一个热身题后，很多同学觉得不过瘾，那就用同样的题目让大家再交一次原来已经ＡＣ的程序，看是什么样的结果，应该怎样应对？题目跟第一个热身题是一样的（但我已经大幅增加了测试数据），还是要求将一个杂乱无序的整数序列，按照从小到大的顺序排列并输出．输入测试数据不止一组，每组测试数据：１）先输入无序序列的整数个数n；(n不超过1000000)２）然后连续输入n个整数；若n的值输入为０值，则输入结束．输出与每组输入的测试数据相对应，输出其按从小到大排好序后的整数序列．注意：每组输出占一行．样例输入10987654321-1588776655330样例输出-11234567893355667788提示本题测试对第10章“内部排序”的理解程度。但要考虑算法的优化及排序方法的选择(排序速度要快才行)。警告：目的是让大家熟悉内部排序的各种算法，因此禁止调用sort或qsort等函数！不改正者降最终成绩等级．#defineMAX1000000#includestdio.hvoidsift(int*x,intn,ints){intt,k,j;t=*(x+s);k=s;j=2*k+1;while(jn){if(jn-1&&*(x+j)*(x+j+1))j++;if(t*(x+j)){*(x+k)=*(x+j);k=j;j=2*k+1;}elsebreak;}*(x+k)=t;}voidheap_sort(int*x,intn){inti,k,t;int*p;for(i=n/2-1;i=0;i--)sift(x,n,i);for(k=n-1;k=1;k--){t=*(x+0);*(x+0)=*(x+k);*(x+k)=t;sift(x,k,0);}}intmain(){int*p,i,a[MAX],num;while(1){p=a;scanf(%d,&num);if(num==0)return0;for(i=0;inum;i++)scanf(%d,p++);p=a;heap_sort(p,num);for(i=0;inum;i++){if(i==num-1)printf(%d,a[i]);elseprintf(%d,a[i]);}printf(\n);}return0;}问题C:时间复杂度的估算时间限制:1Sec内存限制:128MB题目描述在数据结构里面，时间复杂度是决定算法效率的一项重要指标，常见的时间复杂度格式有三种：1、O(n)2、O(lg(n))3、O(sqrt(n))一个算法往往有多种解法，每种解法的复杂度由上述常见的的复杂度组合成，例如排序的两种算法：1、快速排序：时间复杂度为O(n*lg(n))2、冒泡排序：时间复杂度为O(n*n)现在先给定n的值，然后输入一个值m，随后输入m行数据表示有m个算法的复杂度。请确定这些复杂度是否会超时。若复杂度计算结果大于100000000，则为超时(TLE)，否则输出计算的复杂度，输出的结果保留两位小数。(lg(n)表示求以2为底数的n的对数)输入第一行输入n(1≤n≤10000000),m(1≤m≤100),其中n为表示问题规模的数，m为算法复杂度的个数。接下来m行，每行为一个串，每个串都包含O()，其中，字符'O'后的括号里面的字符串保证仅由n,lg(n),sqrt(n),*组成并且合法。如sampleinput所示。注意：lg()或sqrt()中只会出现字符'n'，不会再嵌套lg()或sqrt()。如果想做得难一点，可以去做编号为1049的题，1049题要考虑嵌套。输出对于每个串，若计算出来的复杂度大于100000000，则输出TLE，否则输出该复杂度的计算结果。样例输入100005O(n*n)O(n*n*n)O(sqrt(n))O(lg(n))O(n*lg(n))样例输出100000000.00TLE100.0013.29132877.12提示本题主要测试三个方面：1）对于时间复杂度的理解。2）字符串处理及数组的合理使用。3）编码能力。#includestdio.h#includemath.h#defineMAX100intmain(){intN_NUM,L_NUM,S_NUM;intnum;charstring[MAX];doubles;inti,p,n;while(scanf(%d%d,&n,&num)!=EOF){for(s=1.0,N_NUM=0,L_NUM=0,S_NUM=0,p=0;pnum;p++){scanf(%s,string);s=1.0;N_NUM=0;L_NUM=0;S_NUM=0;for(i=2;string[i]!='\0';i++){if(string[i]=='n'){N_NUM++;i++;}if(string[i]=='l'){L_NUM++;i=i+5;}if(string[i]=='s'){S_NUM++;i=i+7;}}for(i=0;iN_NUM;i++)s=s*n;for(i=0;iL_NUM;i++)s=s*(log(n)/log(2.0));for(i=0;iS_NUM;i++)s=s*sqrt(n);if(s100000000)printf(TLE\n);elseprintf(%.2f\n,s);}}}问题D:车站调度时间限制:1Sec内存限制:128MB题目描述有顺序排列的1,2,3,…,n节车厢在入站口等待调度。车站设置了一个栈作为缓冲，这样的话只可能进行下列两个操作之一：（1）如果还有车厢在入站口，将最前面的入栈缓冲（2）将栈顶的车厢驶出车站给定一个1至n的排列，问其作为出站序列是否合法。注意：入站顺序为1,2,3,…,n，即1先入栈...，n最后入栈。输入输入包含若干测试用例。每一个测试用例由多行组成。第一行是两个整数n（1=n=100）和m，n表示入站序列为1至n。m表示随后有m行出站序列。当n，m均为0时表示输入结束。输出对应每一个出站序列，合法则输出一行YES，否则输出一行NO。样例输入3612313221323131232100样例输出YESYESYESYESNOYES提示参见习题集p21题3.1。本题主要测试对栈的理解及灵活运用。解本题推荐采用模拟入栈出栈的方式，以训练对栈的运用熟练程度。当然也有其它方法，如推导出规律（出栈序列中存在“大小中”的组合是不行的）后编程求解。#includestdio.h#defineMAX100#defineSIZE100intclear(inta[],intp){inti;for(i=0;ip-1;i++){if(a[i]a[i+1])return0;}return1;}intJudge(inta[],intnum){intjudge[SIZE];intp;inti,k,j;for(i=0;inum-2;i++){for(k=i+1,p=0;knum;k++){if(a[i]a[k]){judge[p++]=a[k];}}if(clear(judge,p))continue;else{printf(NO\n);return-1;}}printf(YES\n);return0;}intmain(){intnum,time;inta[MAX];inti,j;while(1){scanf(%d%d,&num,&time);if