计算机程序设计基础复习大纲
(2016-9)
一、考试范围:大纲范围,教材+实验任务+课后作业
二、考试题型与分数布局:
1.单选题(30?1分,共30分)
2.判断题(15?1分,共15分)
3.填空题(3?6分,共18分)
4.阅读题(3?5分,共15分)
5.编程题(3题,共22分)
考试方式:闭卷,考试时间:十七周周三(12月21日)晚上7:00~9:00
三、各章节主要知识点
1、基础编程
求和运算:奇数、偶数求和;求阶乘的累加和;判定素数,求某一范围内的素数求和或素数的个数;利用辗转相除法(阿基里德算法)求最大公约数和最小公倍数;求回文;“数据---各位数字”的获取、逆序输出;十进制转换为二进制、十进制转换为八进制。
**************************************************************************************** 2、数组的应用
数组的基本操作:数组元素求和、求平均值;求最大(最小)元素的值及其在数组中的位置;删除数组元素;在有序数列中插入元素;起泡法、选择法的排序;折半查找;按规律自动产生一维或二维N*N 数据;Fibonacci 数列;杨辉三角。字符串类的应用:以string s1,s2;为例,掌握getline(cin,s1)、s1.size()、s[i]以及s1 与s2的比较操作。
**************************************************************************************** 3、指针的应用
利用指针在数组中完成:利用指针变量操作普通变量(数据的间接访问方式);利用指针变量操作一维数组,包括:数据的有序插入、计算并输出交集、折半查找、将数组中的最大最小值进行交换、将数组中的数据按相反顺序存放。
****************************************************************************************
4、函数的应用
(1)库函数:随机函数的使用,例如利用随机函数产生数组的所有元素并执行相应操作,比如左移或右移操作。
(2)用户自定义函数:注意主函数与子函数之间的数据交换,包括:值传递、指针传递、数组传递、引用传递。
(3)递归函数:阶乘运算n!、幂运算a b、斐波那契数列。
容易出错的地方
●少头文件
#include
#include
#include
#include
●判等==不等!= 大于等于>= 小于等于<=
●条件式中注意与&& 和或|| 的区别
字符是否为元音字符:
(ch=='a'|| ch =='A'|| ch =='e'|| ch =='E'|| ch =='i'|| ch =='I'|| ch =='o'|| ch =='O'|| ch =='u'|| ch =='U')
字符是否为英文字母:
( ch>=’a’&&ch<=’z’ || ch>=’A’&&ch<=’Z’)
字符是否为数字:
( ch>=’0’&&ch<=’9’)
●Break(退出最近的封闭的循环)和continue(退出本次循环)的区别
●a=b=1; 40 ●注意if /else的配对关系 ●注意两种排序算法中,循环条件及比较条件的区别 ●数组元素下标一定从0开始 ●函数定义头部和函数声明语句完全一样!!!函数定义时,参数表的括号后面 不能有分号!当数组作为函数参数时,数组名后面的方括号一定不能省掉!!! ●函数调用时,实参和形成在类型和个数上要完全一致!如果是指针变量做函 数的形参,则在调用时实参一定传递的是地址(可以是普通变量的地址,如F(&x);可以是指向普通变量的指针,如int *p; p=&x; F(p); 或者是数组名int a[N]; sort(a,N);或者是指向数组的指针,如int *p, a[N]; p=a; sort(p,N); ●用string类处理字符串 #include string s; ●可以用cin输入(不接收空格);也可以用getline(cin,s),接收空格; getline(cin,s,’#’),以特定字符作为输入结束的标志。 ●l=s.length(); l=s.size(); for(i=0;i 四、部分算法实现参考代码 ●判断一个数是否为素数 #include #include using namespace std; void main () { int n,i; cout<<"Enter a positive integer :" ; cin>> n ; for ( i=2; i<=sqrt((double)n);i++) { if(n%i==0) break; } if(i<=sqrt((double)n)) cout<<“不是素数“< else cout<<“是素数“< } ●求n之内所有质数之和 #include #include using namespace std; void main () { int n,i=3,j,sum=2; cout<<"请输入质数求和的范围:"< cin>>n; cout< for(;i<=n;i++) { for(j=2;j<=sqrt(double(i));j++) { if(i%j==0) break; } if(j>sqrt(double(i))) { cout<<'+'< sum=sum+i; } } cout<<"="< } ●求100以内所有奇数之和 #include using namespace std; void main() { int k,s=0; for(k=1;k<=100;k++) { if(k%2==0) continue; s=s+k; } cout<<“s=”< } ●求回文 #include using namespace std; void main( ) { int n,m,num=0,r; cout <<"Enter the number:"; cin >>n; m=n; while (n!=0) { r=n%10; //输出数字左移1位 num=num*10+r; // 求逆序数 n/=10; /*从原始数据中去掉已经反序输出的数位,为获 取下一个反序输出数字做准备*/ } if(num==m) cout <<"整数"< else cout <<"整数"< } ●利用辗转相除法(阿基里德算法)求最大公约数和最小公倍数#include using namespace std; void main( ) { int p, q, r,a,b; // 变量定义,p,q,r,a,b // 提示用户由键盘输入两个正整数 cout<< "Please input two integer numbers:"< cin>>p>>q; a=p; b=q; //保留原来p,q的值,分别放在a,b中 //保证p为大数,q为小数 if(p { r=p; p=q; q=r; }//交换p,q // 计算p 除q 的余数r r=p%q; // 只要r 不等于0, 重复进行下列计算 while(r!=0) { p=q; q=r; r=p%q; } //辗转法 cout <<"两个正整数的最大公因数是"< cout <<"两个正整数的最小公倍数是"< } “数据---各位数字”的获取、重组及转存 已知int a=1234,写出计算其个、十、百、千位的表达式。 解:a%10, a/10%10, a/100%10,a/1000%10或a/1000 ●将键盘输入的整数反序输出 #include using namespace std; void main( ) { int n,num; cout <<"Enter the number:"; cin >>n; cout <<"The number in reverse order is: "; do { num = n % 10; cout << num; n /= 10; } while (n!=0); cout < } ●求一个整数的反序数 #include using namespace std; void main( ) { int n,num=0; cout <<"Enter the number:"; cin >>n; while (n!=0) { r=n%10; //输出数字左移1位 num=num*10+r; // 求逆序数 n/=10; /*从原始数据中去掉已经反序输出的数位,为获 取下一个反序输出数字做准备*/ } cout <<"The number in reverse order is: "< } ●十进制转换为八进制 #include #include using namespace std; void main( ) { int a,j; //a为十进制整数,j为a除以8的余数 double i=0.0; //用于记录得到的余数是第几位,最低位为第0位 double b=0.0; //b为转换后的八进制整数 cout<<"请输入一个十进制整数:"; cin>>a; do { j=a%8; //转换成那种进制就除以对应进制的基数 b=b+j*pow(10.0,i); /*最先得到的余数是转换后的八进制数的最低位,乘以位权后存放到b中*/ a=a/8; // a除8的商,为下一次“除基数取余”做准备 i=i+1; }while(a>0); // 循环,直到商为0为止 cout< cout.precision(0); cout<<"转换成八进制数是:"< } ●八进制转换为十进制 #include #include using namespace std; void main( ) { int a,j; //a为八进制整数,j为a除以10的余数 double i=0.0; //用于记录得到的余数是第几位,最低位为第0位 double b=0.0; //b为转换后的十进制整数 cout<<"请输入一个八进制整数:"; cin>>a; do { j=a%10; //取八进制数的各个位上的数字,然后用位权法进行转换 以位权后存放到b中*/ a=a/10; // 取八进制数下一位上的数字(从右往左取) i=i+1; }while(a>0); // 循环,直到商为0为止 cout< cout.precision(0); cout<<"转换成十进制数是:"< **************************************************************************************** **************************************************************************************** ●一维数组求平均值 #include using namespace std; void main( ) { const int N=10; int scores[N]; int n,i,total=0; // n为数组实际长度 float avg=0.0; cout<<“请输入数组长度:”; cin>>n; // 输入数组实际长度 for(i=0;i cin>>scores[i]; for(i=0;i total=total+scores[i]; avg=float(total)/n; //计算平均成绩 cout<<“Average:”< } ●求一维数组中的最大值及其位置 #include using namespace std; void main( ) { const int N=10; int a[N]; //声明数组 int n,i,j,high; cout<<“请输入数组实际长度:”; cin>>n; for(i=0;i high=a[0]; //默认第一个元素为最大值 j=0; //记录最大元素的下标 for(i=1;i { if(a[i]>high) { high=a[i]; //记录最大值 j=i; //记录最大元素的下标 } } cout<<“最大元素为第”< } ●数组的反序(逆序)输出 法一:普通数组 #include #include using namespace std; void main() { const int N=10; int a[N],i,j,n,temp; cout<<"请输入数组的实际长度:"< cin>>n; cout<<"请输入数组元素:"< for(i=0;i cin>>a[i]; for(i=0,j=n-1;i { temp=a[i]; a[i]=a[j]; a[j]=temp; //实现反序存储 } cout<<"反序之后的数组元素为:"< for(i=0;i cout< } ●法二:指针方法 #include #include using namespace std; void main() { const int N=10; int a[N],i,j,n,temp, *p; cout<<"请输入数组的实际长度:"< cin>>n; cout<<"请输入数组元素:"< for(p=a;p>*p; p=a; for(i=0,j=n-1;i { temp=*(p+i); *(p+i)=*(p+j); *(p+j)=temp; //实现反序存储 } cout<<"反序之后的数组元素为:"< for(p=a;p cout< } ●方法三:子函数实现 #include using namespace std; void invert(int *p, int n) { int i,j,temp; for(i=0,j=n-1;i { temp=*(p+i); *(p+i)=*(p+j); *(p+j)=temp; } } void main() { int a[10],i,*p; cout<<"Input ten interger:"< for(i=0;i<10;i++) cin>>a[i]; p=&a[0]; // p=a; 指针指向数组 invert(p,10); //函数调用方式1,用指向数组的指针for(i=0;i<10;i++) cout< } void main( ) { int a[10],i; cout<<"Input ten interger:"< for(i=0;i<10;i++) cin>>a[i]; invert(a,10); //函数调用方式2,用数组名 for(i=0;i<10;i++) cout< } 插入算法 ●法一:普通数组 #include #include using namespace std; void main() { const int N=10; int a[N+1],p,x,i; cout<<“输入a 数组:”< while(x>a[p]&&p a[i+1]=a[i]; //将a[p]~a[n-1]后移 a[p]=x; //x 插入正确位置 for(i=0;i<=n;i++) cout< ● 法二:指针 #include const int N=10; int a[N+1],p,x, *t ; cout<<“输入a 数组:”< cout<<“输入待插入的数x :”< while (x>*(t+p)&&p *(t+p)=x; // ① for(t=a;t cin>>*t; } 折半查找 ● 方法一:数组方法 #include int a[10],i, top=0,bot=9,mid, x; cout<<"Please input ten numbers(from small to big):"< for (t=a+N-1; t>=a+p; t--) *(t+1)=*t; // ② t=a+p; //将指针t 指向由p 记录的插入位置 *t=x; // ② for(i=0;i<10;i++) cin>>a[i]; cout<<"Please input the number to search:"< { mid=(bot+top)/2; if(x==a[mid]) break; //结束最近的封闭循环体 else if(x>a[mid]) top=mid+1; else bot=mid-1; } if(top<=bot) cout< else cout<<"No this number."; } 方法二:指针 #include using namespace std; void main(void) { const int N =10; int a[N],x,top=0,bot=N-1,mid,*p; //输入一个从小到大序列的8个数据 for(p=a;p>*p; //输入要查找的数 cin>>x; p=a; while(top<=bot) { mid=(top+bot)/2; if(*(p+mid)==x) break; else if(x>*(p+mid)) top=mid+1; else bot=mid-1; } if(top<=bot) cout<<"pos is:"< else cout<<"This number is not in this array "; } 选择排序 ●方法一:数组方法 #include using namespace std; void main( ) { const int N=20; int a[N]; int i,j,t,n; cout<<“Input n:”; cin>>n; cout<<“Input numbers:”< for(i=0;i cin>>a[i]; //输入数组元素 for(i=0;i for(j=i+1; j if(a[i]>a[j]) { t=a[i]; a[i]=a[j]; a[j]=t; } //排序cout<<“The sorted numbers is:”< for(i=0;i { cout.width(5); cout< } //输出 } ●方法二:指针 p=a; for(i=0;i for(j=i+1; j if(*(p+i)>*(p+j) { t=*(p+i); *(p+i)= *(p+j); *(p+j)=t; } //排序 冒泡排序 ●方法一:数组方法 #include using namespace std; void main( ) { const int N=20; int a[N]; int i,j,t,n; cout<<“Input n:”; cin>>n; cout<<"Input numbers:"< for(i=0; i cin>>a[i]; //输入数组元素 for(i=0; i for(j=0; j if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } cout<<"The sorted numbers is:"< for(i=0; i { cout.width(5); cout< } cout< } ●方法二:指针 p=a; for(i=0; i for(j=0; j if(*(p+j)> *(p+j+1)) { t=*(p+j); *(p+j)= *(p+j+1); *(p+j+1)=t; } ●由随机数产生器产生一维数组的元素,求最大值及其所在数组中的位置,求 最小值及其所在数组中的位置,并把最大最小值进行交换。 #include #include #include using namespace std; void main() { const int N=20; int a[N],n,i,j,k,t,max,min; cout<<"请输入n值:"< cin>>n; srand(time(NULL)); for(i=0;i { a[i]=1+rand()%(200-1+1); } cout<<"产生的随机数为:"< for(i=0;i cout<<" "< min=a[0]; for(i=1;i { if(a[i] { min=a[i]; j=i; } } cout< cout<<"最小数为:"< for(i=1;i { if(a[i]>max) { max=a[i]; k=i; } } cout<<"最大数为:"< cout<<"最大、最小值交换后的结果为:"< for(i=0;i cout<<" "< } 定义有10个整型元素的一维数组,数组元素由随机数产生器生成,并将数组中所有元素循环右移m位。 #include #include #include #include using namespace std; void main() { const int N=10; int i,m,k,t=0; int a[N]; cout<<"随机产生数组的十个元素(1~100):"< srand(time(NULL)); //初始化随机数产生器 for(i=0;i { a[i]=1+rand( )%(100-1+1); //产生指定范围的随机数 } for(i=0;i cout< cout< cin>>m; k=m%N; while(k--) { t=a[N-1]; for(i=N-1; i>0; i--) a[0]=t; } cout<<"数组循环右移"< for(i=0;i cout< } 求一维数组的平均值并且把小于平均值的那些元素删掉。#include using namespace std; void main() { const int N=20; int a[N]; int i,j,n; double ave=0,sum=0; cout<<"input the n:"; cin>>n; for(i=0;i { cin>>a[i]; if(a[i]==0) break; } for(i=0;i { cout< }