重邮考研复试大纲-程序设计

《程序设计》考试大纲一、适用范围：计算机专业研究生复试二、考试题型：读程序、改程序、算法设计、写程序及综合题三、考试要求：1．掌握结构化程序设计方法或面向对象编程技术2．掌握程序语言的基础知识3．掌握算法描述方法4．掌握程序调试方法5．具有读程序和改错能力6．具有良好的程序编制风格7．用C、C++或其它语言熟练编制程序四、主要内容：1．数据类型及其操作：基本数据类型、数组、结构、链表等的定义、初始化、引用和操作2．程序语言的控制结构：顺序、选择、循环3．程序输入输出实现：程序中定义、键盘输入、通过文件进行数据存取4．函数：函数定义、函数调用、参数传递5．算法描述方法：程序流程图、伪代码、N-S盒图等6．算法示例：（１）加法器与累乘器1).算法思想：加法器：循环体中，将循环体变量（假设为i）累加到变量（假设为S中；累乘器：循环体中，将循环体变量（假设为i）累乘到变量（假设为S）。2).算法示例：加法器：ints=0,i=1;while(in){s=s+i;}累乘器：ints=1,i=1;while(in){s=s*i;}3).时间复杂度：O(n);（２）求最大数与最小数1).算法思想：从一个数组中找出最大（或最小）,即通过下标循环遍历整个数组，设定最大（或最小）起始为数组首个元素，依次比较各个元素。2）算法示例：inta[5]={1,2,3,4,5};inti=1,max=a[0];while(i5){if(a[i]max){max=a[i];}3).时间复杂度：O(n);（３）排序（冒泡排序、选择排序等）（４）大小写字母转换#includestdio.hvoidmain(){charc1,c2;c1='a';c2='b';c1=c1-32;c2=c2-32;printf(%c%c,c1,c2);}（５）判别键盘输入字符的类别#includestdio.hvoidmain(){charstring;intenglish_letters=0,spaces=0,numbers=0,others=0;printf(请输入一行字符：\n);while((string=getchar())!='\n'){if(string='a'&&string='z'||string='A'&&string='Z'){english_letters++;}elseif(string==''){spaces++;}elseif(string='0'&&string='9'){numbers++;}else{others++;}}printf(英文字母数为：%d\n空格数为：%d\n数字为：%d\n其它字符个数为：%d\n,english_letters,spaces,numbers,others);}（６）判别闰年（７）百分制成绩与等级制成绩互相转换#includestdio.hvoidmain(){floatscore;chargrade;printf(请输入学生成绩：\n);scanf(%f,&score);while(score100||score0){printf(输入学生成绩有误，请重新输入\n);scanf(%f,&score);}switch((int)score/10){case10:case9:grade='A';break;case8:grade='B';break;case7:grade='C';break;case6:grade='D';break;case5:case4:case3:case2:case1:case0:grade='E';break;}printf(成绩是%3.1f,等级是%c\n,score,grade);}（８）求两个数的最大公因数和最小公倍数#includestdio.hvoidmain(){//利用辗转相除法求最大公约数/*当两个数都较大时，采用辗转相除法比较方便．其方法是：以小数除大数，如果能整除，那么小数就是所求的最大公约数．否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数．依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数．例如：求4453和5767的最大公约数时，可作如下除法．5767÷4453＝1余13144453÷1314＝3余5111314÷511＝2余292511÷292＝1余219292÷219＝1余73219÷73＝3于是得知，5767和4453的最大公约数是73．*/inta,b,r,temp,p;printf(请输入两个正整数：\n);scanf(%d,%d,&a,&b);if(ab)//把大数赋给a，小数赋给b{temp=a;a=b;b=temp;}p=a*b;while(b!=0){r=a%b;a=b;b=r;}printf(最大公约数为：%d\n,a);printf(最小公倍数为：%d\n,p/a);///最小公倍数*最大公约数=两数之乘积}（９）求菲比拉契数列有限项P125Fibonacci（１０）统计学生成绩，包括总成绩、平均成绩、各分数段人数等（１１）验证哥德巴赫猜想（１２）用穷举法求某数段的素数、水仙花数、完全平方数等①求某数段的素数：#includestdio.hvoidmain(){inti,t,k,a,b;printf(输入任意两个数a,b：\n);scanf(%d,%d,&a,&b);for(i=a;i=b;i++){t=1;for(k=2;ki;k++){if(i%k==0){t=0;break;}}if(t){printf(%d,i);}}}②水仙花数#includestdio.hvoidmain(){intnum,div,ten,hondred;printf(水仙花数为：\n);for(num=100;num1000;num++){hondred=num/100;ten=num/10-hondred*10;div=num%10;if(num==div*div*div+ten*ten*ten+hondred*hondred*hondred){printf(%d,num);}}printf(\n);}（１３）求近似数（如定积分、用牛顿迭代法或二分法或弦截法求多元方程的根）（１４）求两个矩阵之和、之积（１５）统计输入字符中的单词个数P150#includestdio.hvoidmain(){charstring[81];inti,num=0,word=0;charc;gets(string);for(i=0;(c=string[i])!='\0';i++)if(c==''){word=0;}elseif(word==0){word=1;num++;}printf(有%d个单词\n,num);}五、参考教材：1．《C语言程序设计（第三版）》谭浩强，清华大学出版社2．《C++程序设计教程》（第二版）钱能，清华大学出版社3.排序1）数组排序：假设升序冒泡排序选择排序VoidBubble_Sort(inta[],intn){inti=0,j=0,temp;for(i=0;in;++i)for(j=n-1;ji;--j)if(a[j]a[j-1]){temp=a[j];a[j]=a[j-1];a[j-1]=temp;}}VoidSelect_sort(inta[],intn){inti=0,j=0,temp=0,k=0;for(i=0;in-1;++i){k=i;for(j=i+1;jn;++j)if(a[j]a[i])k=j;if(k!=i){temp=a[i];a[i]=a[k];a[k]=temp;}}时间复杂度：O(n2)O(n2)2)链表排序：升序1.数据结构：typedefstructLnode{intdata;structLnode*next;}*LinkList,Lnode;冒泡排序选择排序VoidBubble_Sort(LinkListhead){LinkListp,pre,q,s;pre=head;p=head-next;while(p){while(p&&p-datapre-data){pre=p;p=p-next;}q=p;pre-next=p-next;s=pre;pre=head;p=head-next;while(p&&p-dataq-data){pre=p;voidSelect_sort(LinkListhead){LinkListh=head,p,q,r,s,L;L=NULL;while(h){p=s=h;q=r=NULL;while(p){if(p-datas-data){s=p;r=q;}q=p;p=p-next;}if(s==h)h=h-next;elser-next=s-next;p=p-next;}pre-next=q;q-next=p;pre=s;p=pre-next;}}s-next=L;L=s;}head=L;}时间复杂度：O(n2)O(n2)3).大小写字母转换：1.算法思想：由大转小，通过ASCII码转换。例，’A’-’a’,则有:’a’=’A’+32即可；反之亦然。大转小voidCast_upper_to_lower(){FILE*fp;charch;charfilename[20];fp=fopen(filename,r);if(!fp){printf(Openfileerror!\n);exit(0);}ch=fgetc(fp);while(ch!=EOF){if(ch64&&ch97)ch=ch+32;putchar(ch);ch=fgetc(fp);}fclose(fp);}voidCast_Lower_to_Upper(){FILE*fp;charch;charfilename[20];fp=fopen(filename,r);if(!fp){printf(Openfileerror!\n);exit(0);}ch=fgetc(fp);while(ch!=EOF){if(ch96&&ch123)ch=ch-32;putchar(ch);ch=fgetc(fp);}fclose(fp);}填空、改错、写结果、说明函数功能【60分】1.判断闰年；2.递归计算1~2+2~2+3~2+...+n~2;3.从文件中读取字符串（一个字符一个字符的读）；4.判断成绩等级；6.函数调用以及变量的作用域；7.strcpy(),strcat()函数的作用；8.‘\0’的意义，数组元素循环左移；9.判断素数......还有些记不到了~~~算法设计与编程题：（画流程图、写代码）【40分】1.计算本金和利息和；2.有30个人去吃饭，男人每个花5元，女人每个花3元，小孩每个花1元，30个人总共花了50元，问有分别有多少个男人、女人、小孩？3.删除一个字符串中的某个字符，如已知字符串aasfsfgdsa,删除字符s后的结果为aaffgda.