上機考試及題集完全版----用于合并

1、本學(xué)期程序設(shè)計基礎(chǔ)課程實行上機考核，現(xiàn)將考核有關(guān)事項通知如下：（1） 考核時間：本學(xué)期最后一次上機時間為機試。（2） 考核內(nèi)容：主要是算法設(shè)計與實現(xiàn)?？碱}來自本學(xué)期布置的作業(yè)、例題及一些補充的題目。（3） 考試形式：機試前進入機房時，每人隨機抽取一道題（同一個組的同學(xué)保證不抽到同一題），然后上機編程，調(diào)試通過后報告監(jiān)考人員審核，審核通過后將源程序拷貝到監(jiān)考人員U盤上，然后可以離開機房。源程序文件明必須是“學(xué)號姓名.cpp”，如“2012216827王梓丞.cpp”。（4） 考試要求：機試時考試規(guī)則同課堂考試一致，不允許帶書、紙張等。不能攜帶任何可用計算機處理的軟件或數(shù)據(jù)(不允許任何私人攜帶的U

2、盤、磁盤或計算器) ，不能攜帶任何類型的通訊工具，包括無線電接收器、移動電話。（5） 考試成績：本次機試成績將在程序設(shè)計基礎(chǔ)課程成績中占25%的比重。（6） 其它有關(guān)事項由主考教師和監(jiān)考人員負責(zé)處理。附：考試題集1. 學(xué)校曾經(jīng)組織一次“程序設(shè)計大獎賽”，規(guī)定本學(xué)期“程序設(shè)計”課程的成績可以因為在大獎賽上獲獎而加5分，總分不超過100分。編程序，輸入某同學(xué)的考試成績，回答是否在競賽中獲獎，計算并輸出該某同學(xué)的程序設(shè)計課成績 。#include"stdio.h"void main()int mark;char win;printf("please input mark

3、:");scanf("%d",&mark);getchar();printf("你是否在大獎賽上獲獎(Y/N)");win=getchar();if(win='y'|win='Y')mark=mark+5;if(mark>100)mark=100;printf("your mark is %dn",mark);2. 編寫一個程序，用戶輸入年份及月份兩個數(shù)據(jù)，程序輸出該月份的天數(shù)。（提示：對2月要考慮是否閏年，閏年年份要么能被4整除且不能被100整除，要么能被400整除，除此之外都

4、不是閏年）。#include"stdio.h"void main()int yy,mm,days;printf("please input year:");scanf("%d",&yy);printf("please input month(1-12):");scanf("%d",&mm);switch(mm)case 1:days=31;break;case 2:if(yy%4=0&&yy%100!=0)|yy%400=0)days=29;elsedays=28

5、; break;case 3:days=31;break;case 4:days=30;break;case 5:days=31;break;case 6:days=30;break;case 7:days=31;break;case 8:days=31;break;case 9:days=30;break;case 10:days=31;break;case 11:days=30;break;case 12:days=31;break;printf("this month has %d days!n",days);3. 求一元二次方程ax2+bx+c=0的根。（要考慮a、

6、b、c三個系數(shù)不同的取值） #include"stdio.h"#include"math.h"void main()float a,b,c,delta;printf("please input a、b、c : ");scanf("%f%f%f",&a,&b,&c);if(a!=0)delta=b*b-4*a*c;if(delta>0)printf("X1=%f,X2=%fn",(-b+sqrt(delta)/(2*a),(-b-sqrt(delta)/(2*a);e

7、lseif(delta=0)printf("X1=X2=%fn",-b/(2*a);elseprintf("X1=%f+%fi,X2=%f-%fin",-b/(2*a),sqrt(-delta)/(2+a),-b/(2*a),sqrt(-delta)/(2+a);elseif(b!=0)printf("X=%fn",-c/b);elseif(c=0)printf("0=0!n");elseprintf("%f=0n",c);4. 學(xué)校曾經(jīng)組織一次“程序設(shè)計大獎賽”，規(guī)定本學(xué)期“程序設(shè)計”課程的成

8、績可以根據(jù)大獎賽的成績適度加分。加分規(guī)則是：參賽者加5分，三等獎加15分，二等獎加20分，一等獎加30分，總分不超過100分。編程序，輸入某同學(xué)的考試成績，回答在競賽中獲獎等級，計算并輸出該某同學(xué)的程序設(shè)計課成績 。#include"stdio.h"void main()int mark,win;printf("please input your mark: ");scanf("%d",&mark);printf("請選擇你參加大獎賽的情況：n");printf("(0:未參加,1:參賽,2:三等

9、獎,3:二等獎,4:一等獎):n");scanf("%d",&win);switch(win)case 0:break;case 1:mark=mark+5;break;case 2:mark=mark+15;break;case 3:mark=mark+20;break;case 4:mark=mark+30;if(mark>100)mark=100;printf("你最終的成績是: %dn",mark);5. 高速公路每公里的收費標準按不同種類汽車如下: 小汽車（ car ） 0.50 元 卡車（ truck ） 1.00 元

10、 大客車（ bus ） 1.50 元編程序，為某高速公路收費站計算各種車輛的收費額。#include"stdio.h"void main()enumcar,truck,bussort;int i;float km,price;printf("please choose (1:car,2:truck,3:bus): ");scanf("%d",&i);switch(i)case 1:sort=car;break;case 2:sort=truck;break;case 3:sort=bus;printf("請輸入所走路

11、程: ");scanf("%f",&km);switch(sort)case car:price=0.50;break;case truck:price=1.00;break;case bus:price=1.50;printf("cost=%fn",price*km);6. 設(shè)計一個模擬單步計算器的程序，設(shè)該計算器只能作加、減、乘、除運算。用戶輸入形如 m#n的算式，其中m、n為運算數(shù)，#為運算符。（需考慮運算符不合法，及除數(shù)為0的情況）#include"stdio.h"void main()float m,n,s

12、;char w;printf("please input m、w、n: ");scanf("%f%c%f",&m,&w,&n);switch(w)case '+':s=m+n;break;case '-':s=m-n;break;case '*':s=m*m;break;case '/':s=m/n;break;default :printf("error!n");if(w='/'&&n=0)printf("

13、;除數(shù)為0，無意義!n");elseprintf("%fn",s);7. 編寫程序，輸入一個4位自然數(shù)n，判斷n是否是降序數(shù)。降序數(shù)是指對于n=d1d2dk有： d1d2dk#include"stdio.h"void main()int n,a,b,c,d;printf("請輸入一個四位數(shù):");scanf("%d",&n);a=n/1000;b=(n%1000)/100;c=(n%100)/10;d=n%10;if(a>=b&&b>=c&&c>=

14、d)printf("%d是一個降序數(shù)n",n);elseprintf("%d不是一個降序數(shù)n",n);8. 編寫程序，輸入一個5位自然數(shù)n，判斷n是否對稱數(shù)。對稱數(shù)是指正序和反序讀都相等的整數(shù)，如96769為對稱數(shù)。9. 編寫程序，判斷給定的3位數(shù)是否為Armstrong數(shù)。Armstrong數(shù)是指其值等于它每位數(shù)字立方和的數(shù)，如153就是一個Armstrong數(shù)。10. 編寫程序，輸入一個整數(shù)，判斷它能否被3、5、7整數(shù)，并輸出如下信息。（1） 能同時被3、5、7整數(shù)。（2） 能同時被兩個數(shù)整數(shù)，并指明是被哪兩個數(shù)整除。（3） 能被一個數(shù)整數(shù)，并指明這

15、是哪個數(shù)。（4） 不能被所有3個數(shù)整除。11. 郵局寄包裹的費用是根據(jù)包裹的重量來收取的。一個重量為2kg或低于2kg的包裹收取3.25元。高于2kg的包裹，超出部分每千克收取1.05元，超出部分不足1kg按1kg計算。因此如果發(fā)件人發(fā)送重達5.63kg的包裹，就需要繳納7.45元。編寫程序，輸入包裹的重量，計算并輸出發(fā)件人須繳納的費用。#include"stdio.h"void main()float m,n,price;printf("請輸入包裹的重量:");scanf("%f",&m);n=m-2.0;if(m<=

16、2.0)price=3.25;elseif(n>(int)n)n=(int)n+1;price=1.05*n+3.25;printf("需繳納費用%.2f元n",price);12. 一個臨時照顧孩子的人的收費標準是：18:00到21:30間每小時2元，21:30到午夜間每小時4元，18:00以前和午夜以后不照顧孩子。編寫程序，輸入開始時間和結(jié)束時間，計算并輸出某一個雇工的薪酬。程序應(yīng)檢查無效的開始和結(jié)束時間。#include"stdio.h"void main()int s,f,a,b;printf("請分別輸入開始時的時s、分f(18

17、<=s<24): ");scanf("%d%d",&s,&f);printf("請分別輸入結(jié)束時的時a、分b(s<=b<=24): ");scanf("%d%d",&a,&b);if(s<18|s>=24|f>60|(a*60+b)<(s*60+f)|a>24|b>60)printf("error!n");if(s*60+f)<(21.5*60)&&(a*60+b)<(21.5*60)p

18、rintf("該雇工可以賺取%.2f元n",(a*60.0+b)-(s*60.0+f)*2.0/60);if(s*60+f)<(21.5*60)&&(a*60+b)>=(21.5*60)printf("該雇工可以賺取%.2f元n",(21.5*60)-(s*60.0+f)*2.0/60)+(a*60.0+b)-(21.5*60)*4.0/60);if(s*60+f)>=(21.5*60)printf("該雇工可以賺取%.2f元n",(a*60.0+b)-(s*60.0+f)*4.0/60);13. 編

19、寫程序，按下述公式求自然對數(shù)底e的近似值。#include"stdio.h"#define eps 1e-6void main()int n=1;float e,r=1.0;for(e=1.0;r>=eps;e=e+r)r=r/n;n+;printf("e=%fn",e);14. 編寫程序，統(tǒng)計以100為結(jié)束符的整數(shù)輸入流中-1、0、1的出現(xiàn)次數(shù)并將其輸出。#include"stdio.h"#define n 100void main()int i=0,j=0,k=0,m;printf("please input th

20、e integer: ");scanf("%d",&m);while(m!=n)switch(m)case -1:i=i+1;break;case 0:j=j+1;break;case 1:k=k+1;printf("please input the integer: ");scanf("%d",&m);printf("number of -1: %dn",i);printf("number of 0: %dn",j);printf("number of 1:

21、 %dn",k);15. 編寫程序，打印“99乘法表”1 12 2 43 3 6 94 4 8 12 165 5 10 15 20 256 6 12 18 24 30 367 7 14 21 28 35 42 498 8 16 24 32 40 48 56 649 9 18 27 36 45 54 63 72 81* 1 2 3 4 5 6 7 8 9#include"stdio.h"void main()int i,j,k;for(i=1;i<=9;i+)printf("%3d",i);for(j=1;j<=i;j+)printf

22、("%3d",i*j);printf("n");printf(" *");for(k=1;k<=9;k+)printf("%3d",k);printf("n");16. 編寫程序，打印200以內(nèi)的素數(shù)，要求每行輸出10個數(shù)。#include "stdio.h"void main()int i,j,k;bool flag;for(i=2,k=0;i<=200;i+)flag=true;for(j=2;j<=i/2;j+)if(i%j=0)flag=false;

23、if(flag)if(k%10=0)printf("n");k+;printf("%5d",i);printf("n");17. 編寫程序，輸出如下序列的前50項，此序列的第一項為0；第二項為1；以后的奇數(shù)項為其前兩項之和；偶數(shù)項為其前兩項之差。要求每行輸出10個數(shù)。#include"stdio.h"void main()int i,a=0,b=1,c,m=-1;printf("%7d%7d",a,b);for(i=3;i<=50;i+)m=-m;c=b+m*a;printf("

24、%7d",c);if(i%10=0)printf("n");a=b;b=c;printf("n");18. 編寫程序，輸入正整數(shù)N，計算r1!+r2!+rn!并輸出。其中N=r1r2rn。#include"stdio.h"void main()int N,S,P,r,i;S=0;printf("please input N: ");scanf("%d",&N);while(N!=0)r=N%10;N=N/10;P=1;for(i=1;i<=r;i+)P=P*i;S=S+P

25、;printf("r1!+r2!+rn!=%dn",S);19. 完數(shù)問題：若有一數(shù)，其值等于它的因子之和，則該數(shù)稱為完數(shù)。例如，6的因子為1、2、3，而6=1+2+3，故6是完數(shù)。編程輸出1000之內(nèi)的所有完數(shù)及其因子。#include"stdio.h"void main()int i,j,k,s;for(i=2;i<=1000;i+)s=0;for(j=1;j<i;j+)if(i%j=0)s=s+j;if(s=i)printf("%3d its factors are ",i);for(k=1;k<i;k+)if

26、(i%k=0)printf("%4d",k);printf("n");20. 把一張1元鈔票換成1分、2分和5分的硬幣，每種至少有1枚，問有多少種換法？#include"stdio.h"void main()int i,j,k,count=0;for(i=1;i<=100/1;i+)for(j=1;j<=100/2;j+)for(k=1;k<=100/5;k+)if(i+2*j+5*k=100)count+;printf("%dn",count);21. 斐波那契（Fibonacci）數(shù)列問題：F

27、ibonacci數(shù)列遞歸定義為：x0=0,x1=1,xi+1=xi+xi-1, i=2,3,即從第二項開始，數(shù)列中的每一個元素等于前面兩個元素之和。編程輸出前20項Fibonacci數(shù)。（提示可以用遞歸或迭代兩種方式編程）#include"stdio.h"void main()int r=0,s=1,m,i;for(i=1;i<=20;i+)m=r+s;printf("%8d",m);r=s;s=m;22. 公雞5元1只，母雞3元1只，小雞1元3只，花了100元錢買100只雞，問公雞、母雞、小雞各多少只？#include"stdio.h&

28、quot;void main()int g,m,x;for(g=1;g<100/5;g+)for(m=1;m<100/3;m+)for(x=3;x<100*3;x=x+3)if(g+m+x=100&&(5*g+3*m+x/3)=100)printf("g=%d m=%d x=%dn",g,m,x);23. 編寫程序，用循環(huán)語句控制打印如圖所示的字符圖形。 A B C D E F G H IB C D E F G H I AC D E F G H I A BD E F G H I A B CE F G H I A B C DD E F G H

29、 I A B CC D E F G H I A BB C D E F G H I AA B C D E F G H I#include"stdio.h"void main()char x,y;for(x='A'x<='E'x+)for(y=x;y<='I'y+)printf("%2c",y);for(y='A'y<x;y+)printf("%2c",y);printf("n");for(x='D'x>='

30、A'x-)for(y=x;y<='I'y+)printf("%2c",y);for(y='A'y<=x-1;y+)printf("%2c",y);printf("n");24. 編寫程序，打印如下圖所示的圖形 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 5 6 5 4 3 2 1 1 2 3 4 5 6 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 1 2 3 4 5 6

31、 7 8 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 0 9 8 7 6 5 4 3 2 1#include"stdio.h"void main()int i,j,k,l;for(i=1;i<=10;i+)for(j=1;j<=10-i;j+)printf(" ");for(k=1;k<=i;k+)if(k=10)printf("%2d",0);elseprintf("%2d",k);for(l=i-1;l>=1;l-)printf("%2d"

32、,l);printf("n");25. 驗證哥德巴赫猜想：任意一個大偶數(shù)都可以分解為兩個素數(shù)之和。用戶輸入一個大于6的偶數(shù)，程序計算并輸出分解結(jié)果。#include"stdio.h"bool prime(int n)int j;for(j=2;j<=n/2;j+)if(n%j=0)return false;return true;void main()int i,n;printf("請輸入一個大于6的偶數(shù): ");scanf("%d",&n);for(i=2;i<n;i+)if(prime(i)

33、&&prime(n-i)printf("%d %d %d",n,i,n-i);printf("n");break;printf("n");26. 編寫一個程序解決愛因斯坦臺階問題：有人走以臺階，若以每步走2級則最后剩1級；若每步走3級則最后剩2級；若以每步走4級則最后剩3級；若以每步走5級則最后剩4級；若以每步走6級則最后剩5級；若以每步走7級則最后剛好不剩。問臺階共有幾級？#include"stdio.h"void main()int i;for(i=7;i<1000;i=i+7)if(i%

34、2=1&&i%3=2&&i%4=3&&i%5=4&&i%6=5)printf("臺階有%d階n",i);break;27. 編寫程序，輸出所有小于100的可以被11整除的自然數(shù)，以及這些數(shù)之和。#include"stdio.h"void main()int i,s;for(i=11,s=0;i<=100;i+)if(i%11=0)printf("%3d",i);s=s+i;printf("這些數(shù)之和為: %dn",s);28. 一輛汽車裝滿油料可

35、以行駛300km。從存放有n車油料的油庫出發(fā)，通過在途中建立加油站的方法，它可以行駛 千米。編寫程序，給定L以計算n。#include"stdio.h"#include"math.h"void main()float L,s,p;int n;printf("please input L: ");scanf("%f",&L);p=L/300;for(n=1,s=0;p>s;n+)s=s+1.0/(2*n-1);printf("%dn",n-1);29. 編寫函數(shù)，判定它的4個整型參數(shù)

36、中是否有兩個數(shù)的值相等。主函數(shù)讀入4個數(shù)，調(diào)用該函數(shù)，輸出判定結(jié)果。#include"stdio.h"int a,b,c,d;int f(int a,int b,int c,int d)if(a=b|a=c|a=d|b=c|b=d|c=d)printf("有兩個數(shù)的值相等n");elseprintf("沒有兩個數(shù)的值相等n");return 0;void main()printf("請輸入4個整數(shù): ");scanf("%d%d%d%d",&a,&b,&c,&d)

37、;f(a,b,c,d);30. 編寫以一個函數(shù)reverse(int n)，求任意4位整數(shù)的逆序數(shù)。如n=2637時，函數(shù)返回值是7362。主函數(shù)讀入一個整數(shù)，判斷其合法性，調(diào)用函數(shù)得到結(jié)果輸出。#include"stdio.h"int reverse(int n)int a,b,c,d;a=n/1000;b=(n%1000)/100;c=(n%100)/10;d=n%10;return d*1000+c*100+b*10+a;void main()int m;printf("請輸入一個四位數(shù):");scanf("%d",&m

38、);if(m>9999|m<1000)printf("數(shù)據(jù)不合法!n");elseprintf("該整數(shù)的逆序數(shù)為:%dn",reverse(m);31. 編寫程序，輸入m、n的值計算并輸出 要求編寫一函數(shù)f(int num)求正整數(shù)num的階乘。#include"stdio.h"double f(int num)double s;int i;for(i=num,s=1;i>=1;i-)s=s*i;return s;void main()int m,n;printf("please input m、n (m

39、>=n): ");scanf("%d%d",&m,&n);if(m<n)printf("error! m 應(yīng)該大于 n !n");elseprintf("%.0fn",f(m)/(f(m-n)*f(n);32. 下面是一個有效的計算xn的方法。初始化：answer=1; power=x; m=n;當(dāng)m!=0時，重復(fù)計算：若m是奇數(shù)，則令 answer=answer*power; m=m-1;否則，令 power=power*power； m=m/2;重復(fù)計算至m=0結(jié)果為answer編寫函數(shù)pow

40、er(float x, int n)實現(xiàn)上述算法，主函數(shù)讀入x和n，調(diào)用函數(shù)得到返回值輸出。#include"stdio.h"float power(float x, int n)int m=n;float power=x,answer=1;while(m!=0)if(m%2!=0)answer=answer*power;m=m-1;elsepower=power*power;m=m/2;return answer;void main()float x;int n;printf("please input x,n: ");scanf("%f%d

41、",&x,&n);printf("%.2fn",power(x,n);33. 編寫函數(shù)，以兩個正整數(shù)位參數(shù)，如果這兩個數(shù)是友好的，返回true，否則返回false。如果這兩個整數(shù)的約數(shù)之和（除了它本身之外）等于對方，就稱這對數(shù)是友好的。例如，1184和12101184的約數(shù)之和為1+2+4+8+16+32+74+148+296+592=12101210的約束之和為1+5+10+11+22+55+110+121+242+605=1184#include"stdio.h"bool prime(int m,int n)int i,j,

42、k,s1=0,s2=0;for(i=1;i<=m/2;i+)if(m%i=0)s1=s1+i;for(j=1;j<=n/2;j+)if(n%j=0)s2=s2+j;if(s1=n&&s2=m)return true;return false;void main()int m,n;printf("請輸入兩個正整數(shù):n");scanf("%d%d",&m,&n);if(prime(m,n)printf("這兩個數(shù)是友好的!n");elseprintf("這兩個數(shù)不是友好的!n"

43、;);34. 編寫程序計算調(diào)和級數(shù)的前N項和。要求結(jié)果是一個準確的分數(shù)A/B形式。 #include"stdio.h"int i,j,n,s1,s2,s,k,min;void main()printf("please input n : ");scanf("%d",&n);s1=1;for(i=1;i<=n;i+)s1=s1*i;s=0;for(j=1;j<=n;j+)s2=s1/j;s=s+s2;printf("%d/%dn",s,s1);min=s;k=2;while(k<=min/2

44、)if(s1%k=0&&s%k=0)s=s/k;s1=s1/k;min=s;k=2;elsek+;printf("化簡后的值為:Hn=%d/%dn",s,s1);35. 編寫程序，輸入n個整數(shù)，用“主元排序”法，將其升序排序（從小到大）輸出。#include"stdio.h"#define n 4void main()int i,j,k,r,an;printf("請輸入一組整數(shù):n");for(i=0;i<n;i+)printf("a%d=",i);scanf("%d",&

45、amp;(ai);for(i=0;i<n-1;i+)j=i;for(k=i+1;k<n;k+)if(aj>ak)j=k;r=ai;ai=aj;aj=r;printf("排序后的數(shù)組為:n");for(i=0;i<n;i+)printf("a%d=%d ",i,ai);printf("n");36. 編寫一個程序，輸入全班同學(xué)某門課考試成績，計算平均成績并統(tǒng)計大于等于平均成績的人數(shù)。（提示：批量數(shù)據(jù)通常不事先規(guī)定輸入的數(shù)據(jù)數(shù)量，而是以一個特殊的標志作為輸入結(jié)束。程序根據(jù)結(jié)束標志統(tǒng)計人數(shù)）#include"

46、;stdio.h"void main()int mark,num,count=1,a1000,i=1,j,m=0;float p;printf("please input mark （1000為結(jié)束標志）: ");scanf("%d",&mark);num=mark;a0=mark;while(mark!=1000)printf("please input mark: ");scanf("%d",&mark);if(mark!=1000)num=num+mark;ai=mark;count

47、+;i+;p=(float)num/count;for(j=0;j<=i;j+)if(aj>=p)m+;printf("全班的平均分是:%.3fn",p);printf("大于等于平均成績的人數(shù)為:%dn",m);37. 打印楊輝三角形的前10行 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 #include"stdio.h"#define n 10#define wideword 6void main()int i,j,an,bn;for(i=0;i<n;i+)for(j=

48、1;j<i;j+)aj=bj+bj-1;ai=1;for(j=0;j<=i;j+)bj=aj;for(j=0;j<=30-i*(wideword/2);j+)printf("%C",' ');for(j=0;j<=i;j+)printf("%6d",aj);printf("n");38. 編寫程序，輸入n個整數(shù)，用“冒泡排序”法，將其升序排序（從小到大）輸出。#include"stdio.h"#define n 4bool flag;int r,i,an;void main(

49、)printf("請輸入一組整數(shù)：");for(i=0;i<n;i+)scanf("%d",&ai);flag=true;while(flag)flag=false;for(i=0;i<n-1;i+)if(ai>ai+1)r=ai;ai=ai+1;ai+1=r;flag=true;for(i=0;i<n;i+)printf("a%d=%d ",i,ai);printf("n");39. 編寫程序，輸入n個整數(shù)，用“逐步增加遞增子序列”法（或稱插入排序），將其升序排序（從小到大）輸出。

50、#include"stdio.h"#define n 7int i,j,k,r,an;void main()printf("請輸入一組整數(shù):");for(i=0;i<n;i+)scanf("%d",&ai);for(i=1;i<n;i+)j=i-1;while(aj>ai&&j>=0)j=j-1;r=ai;for(k=i;k>j+1;k-)ak=ak-1;aj+1=r;for(i=0;i<n;i+)printf("a%d=%d ",i,ai);printf

51、("n");40. 編程實現(xiàn)二分查找算法。設(shè)數(shù)組以按升序排序，“對半檢索”亦稱“兩分法檢索”。在檢索過程中用到三個變量：lower : 記錄檢索區(qū)間下界，初值是0 ；upper : 記錄檢索區(qū)間上界，初值是n-1 ；j: 標記當(dāng)前檢索位置。檢索思想令j=(lower+upper)/2n key=aj: 找到，位置為；函數(shù)search返回j n key<aj: key在alower與aj之間 檢索區(qū)間縮小一半,upper=j-1 n key>aj: key在aj與aupper之間， 檢索區(qū)間縮小一半,lower=j+1重復(fù)上述過程。重復(fù)的終止條件為 upper-l

52、ower < 0 ，表示未找到，返回 -1 。 要求編寫一函數(shù)int half_search( int n, int a, int key) 其中n為數(shù)組長度、a為一維數(shù)組、key為要查找的關(guān)鍵字，若找到key，函數(shù)返回對應(yīng)的數(shù)組下標，未找到返回-1。主函數(shù)讀入一數(shù)組，先調(diào)用排序函數(shù)sort(int a, int n)（排序算法任選)對數(shù)組排序，然后調(diào)用搜索函數(shù)，輸出搜索結(jié)果。#include"stdio.h"int sort(int a, int n)int i,j,k,r;for(i=0;i<n-1;i+)j=i;for(k=i+1;k<n;k+)if

53、(aj>ak)j=k;r=ai;ai=aj;aj=r;return 0;int half_search( int n, int a, int key)int lower,upper,j;lower=0;upper=n-1;while(upper-lower>=0)j=(upper+lower)/2;if(key=aj)return j;elseif(key>aj)lower=j+1;elseupper=j-1;return -1;void main()int n,a100,key,m,i;printf("請輸入數(shù)組長度n 、關(guān)鍵字key :n");scan

54、f("%d%d",&n,&key);printf("請輸入一維數(shù)組a%dn",n);for(i=0;i<n;i+)printf("a%d=",i);scanf("%d",&ai);sort(a,n);m=half_search(n,a,key);printf("對應(yīng)的數(shù)組下標為:%dn",m);41. 編寫函數(shù)，對給定的數(shù)組組成的序列排序輸出，并輸出每個數(shù)組元素在排序之前的序號。設(shè)函數(shù)為 sortofup(int a, int b, int n) 其中a中存放要排序

55、的數(shù)組元素，b存放其排序前的序號，n為數(shù)組長度。主函數(shù)讀入數(shù)組a，并給數(shù)組元素置序號（為簡單起序號從0至n-1）。調(diào)用函數(shù)結(jié)束后，分別輸出數(shù)組a、b個元素值。#include"stdio.h"sortofup(int a, int b, int n)int i,j,k,r,c100;for(i=0;i<n;i+)ci=ai;for(i=0;i<n-1;i+)j=i;for(k=i+1;k<n;k+)if(aj>ak)j=k;r=ai;ai=aj;aj=r;for(i=0;i<n;i+)for(j=0;j<n;j+)if(ai=cj)bi=

56、j;return 0;void main()int a100,b100,i,n;printf("請輸入數(shù)組長度n:n");scanf("%d",&n);printf("請輸入數(shù)組a%d:n",n);for(i=0;i<n;i+)printf("a%d=",i);scanf("%d",&ai);sortofup(a,b,n);printf("排序后a%d為:n",n);for(i=0;i<n;i+)printf("%d ",ai);printf("n");printf("每個數(shù)組元素在排序之前的序號為:n