上机实验二 重要算法练习
目的和要求：
（1）熟悉排序、查找算法 （2）了解省考题型 实验内容：
先在D盘根文件夹下创建一个名为“my”的文件夹（以备后用）
完善题（将以下4题分别以my1.c、my2.c、my3.c、my4.c为文件名，保存到my文件夹中。 1、冒泡排序（起泡排序）
假设要对含有n个数的序列进行升序排列，冒泡排序算法步骤是：
①从存放序列的数组中的第一个元素开始到最后一个元素，依次对相邻两数进行比较，若前者大后者小，则交换两数的位置；
②第①趟结束后，最大数就存放到数组的最后一个元素里了，然后从第一个元素开始到倒数第二个元素，依次对相邻两数进行比较，若前者大后者小，则交换两数的位置； ③重复步骤①n-1趟，每趟比前一趟少比较一次，即可完成所求。 题目：任意读入10个整数，将其用冒泡法按升序排列后输出。 #define n 10 main() {int a[n],i,j,t;
for(i=0;i for(j=1;j<=n-1;j++) /*n个数处理n-1趟*/ for(i=0; _________________; i++) /*每趟比前一趟少比较一次*/ if(a[i]>a[i+1]){_____________; _____________;_____________;} for(i=0;i 2、选择法排序 选择法排序是相对好理解的排序算法。假设要对含有n个数的序列进行升序排列，算法步骤是： ①从数组存放的n个数中找出最小数的下标，然后将最小数与第1个数交换位置； ②除第1个数以外，再从其余n-1个数中找出最小数（即n个数中的次小数）的下标，将此数与第2个数交换位置； ③重复步骤①n-1趟，即可完成所求。 题目：任意读入10个整数，将其用选择法按升序排列后输出。 #define n 10 main() {int a[n],i,j,k,t; for(i=0;i for(i=0; ________________; i++) {k = i; /*总是假设此趟处理的第一个（即全部数的第i个）数最小，k记录其下标*/ for(j=_____________;j for(i=0;i printf(\ 3、归并排序 即将两个都升序（或降序）排列的数据序列合并成一个仍按原序排列的序列。 题目：有一个含有6个数据的升序序列和一个含有4个数据的升序序列，将二者合并成一个含有10个数据的升序序列。 #define m 6 #define n 4 main() {int a[m]={-3,6,19,26,68,100} ,b[n]={8,10,12,22}; int i,j,k,c[m+n]; ________________________; while(i else {c[k]=b[j]; ___________;} ___________; } while(______________________) /*若a中数据全部存放完毕，将b中余下的数全部存放到c中*/ {c[k]=b[j]; k++; j++;} while(______________________) /*若b中数据全部存放完毕，将a中余下的数全部存放到c中*/ {c[k]=a[i]; k++; i++;} for(i=0;i 4、折半查找（即二分法） 顺序查找的效率较低，当数据很多时，用二分法查找可以提高效率。使用二分法查找的前提是数列必须有序。 二分法查找的思路是：要查找的关键值同数组的中间一个元素比较，若相同则查找成功，结束；否则判别关键值落在数组的哪半部分，就在这半部分中按上述方法继续比较，直到找到或数组中没有这样的元素值为止。 题目：任意读入一个整数x，在升序数组a中查找是否有与x等值的元素。 #define n 10 main() {int a[n]={2,4,7,9,12,25,36,50,77,90}; int x,high,low,mid;/*x为关键值*/ scanf(\ high=_________; low=0; mid=(high+low)/2; while(a[mid]!=x&&low {if(x if(______________) printf(\ else printf(\} 上交作业方法是：将所做程序文件选中，单击右键，选择其中的“添加到my.rar”，再将压缩文件“my.rar”更名为“自己的姓名.rar”后，复制到ftp://202.195.168.121上“刘颖的班级”?“上交作业”?“重修班”?“作业2”文件夹中。 若仍有时间，请完成一套省二级C考题： 江苏省高等学校非计算机专业学生 计算机基础知识和应用能力等级考试上机试卷（2010年秋） 二级 C语言 （试卷代号C01） （本试卷完成时间 70分钟） 一、改错题（16分） 【程序功能】 查找介于n1与n2（0 测试数据： n1=900 n2=1200 屏幕输出： 911 919 929 977 991 997 1009 1013 1019 1021 1031 1033 1051 1061 1091 1103 1109 1123 1129 1153 1163 1187 1193 【含有错误的源程序】 #include int validate( int n ) { int i, j, k=0, num[5]={ 0 }, size=0; do { num[size]=n; n=n/10; size++; }while( n<0 ); for( i=0;i return 1; else return 0; } int prime( int ) { int i; for( i=2;i<=(int)sqrt(n);i++) if( n%i==0)return 0; return 1; } void main( ) { int i, count=0,n1,n2; scanf( “%d%d”, &n1,&n2); for( i=n1;i<=n2;i++ ) { if ( validate( int i )&&prime( int i )) { count++; printf( “%d\\t”, i ); if( count%8==0 )printf( “\\n” ); } } } 【要求】 1. 将上述程序录入到文件myf1.c中，根据题目要求及程序中语句之间的逻辑关系对程序中的错误进行修改 2. 改错时，可以修改语句中的一部分内容，调整语句次序，增加少量的变量说明或编译预处理命令，但不能增加其他语句，也不能删去整条语句。 3. 改正后的源程序（文件名myf1.c）保存在T：盘根目录中供阅卷使用，否则不予评分。 二、编程题（24分） 【程序功能】 字符串变换。 【编程要求】 1. 编写函数void change( char*a,char*b,char*c)。函数功能是首先把b指向的字符串逆向存放，然后将a指向的字符串和b指向的字符串按排列顺序交叉合并到c指向的数组中， 两个字符串中过长的剩余字符串接在c指向数组的尾部。例如，当a指向的字符串为“abcdefg”，b指向的字符串为“1234”时，c指向的数组中字符串应为“a4b2c3d1efg”。 2. 编写main函数。函数功能是声明字符型数组s1、s2和t，用测试数据初始化数组s1和s2，再用s1、 s2和t作为实参调用函数change，将数组s1、s2和t中的字符串输出到屏幕及文件myf2.out中。最后将考生本人的准考证号字符串输出到文件myf2.out中。 【测试数据与运行结果】 测试数据：s1：abcdefg s2：1324 屏幕输出：s1：abcdefg s2：4231 The result is : a4b2c3d1efg 【要求】 1. 源程序文件名myf2.c ，输出结果文件名为myf2.out。 2. 数据文件的打开、使用、关闭均用C语言标准库中缓冲文件系统的文件操作函数实现。 3. 源程序文件和运行结果文件均需保存在T：盘根目录中供阅卷使用。 4. 不要复制扩展名为obj和exe的文件到T：盘中。
