已知:inti=8,j=10,m,n;m=++i;n=j++;问语句执行后m=【1】,n=
第1题
【说明】
所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。
应用贪婪法求解该问题。程序先计算由各点构成的所有边的长度(作为边的权值),按长度大小对各边进行排序后,按贪婪准则从排序后的各边中选择边组成回路的边,贪婪准则使得边的选择按各边长度从小到大选择。
函数中使用的预定义符号如下:
define M 100
typedef struct{/*x为两端点p1、p2之间的距离,p1、p2所组成边的长度*/
float x;
int p1, p2;
}tdr;
typedef struct{/*p1、p2为和端点相联系的两个端点,n为端点的度*/
int n, P1, p2;
}tr;
typedef struct{/*给出两点坐标*/
float x,y;
}tpd;
typedef int tl[M];
int n=10;
【函数】
float distance(tpd a,tpd b);/*计算端点a、b之间的距离*/
void sortArr(tdr a[M], int m);
/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表,m为边的条数*/
int isCircuit(tr[M], int i, int j);
/*判断边(i, j)选入端点关系表r[M]后,是否形成回路,若形成回路返回0*/
void selected(tr r[M], int i, int j);/*边(i,j)选入端点关系表r*/
void course(tr r[M], tl 1[M]);/*从端点关系表r中得出回路轨迹表*/
void exchange(tdr a[M], int m, int b);
/*调整表排序表,b表示是否可调,即是否有边长度相同的边存在*/
void travling(tpd pd[M], int n, float dist, t1 locus[M])
/*dist记录总路程*/
{
tdr dr[M];/*距离关系表*/
tr r[M];;/*端点关系表*/
int i, j, k, h, m;/*h表示选入端点关系表中的边数*/
int b;/*标识是否有长度相等的边*/
k=0;
/*计算距离关系表中各边的长度*/
for(i=1;i<n;i++){
for(j=i+1;j<=n;j++){
k++;
dr[k].x=(1);
dr[k].p1=i;
dr[k].p2=j;
}
}
m=k;
sortArr(dr,m);/*按距离大小从小到大排序形成排序表*/
do{
b=1;
dist=0;
k=h=0;
do{
k++;
i=dr[k].p1;
j=dr[k].p2;
if((r[i].n<=1)&&(r[j].n<=1)){/*度数不能大于2*/
if((2)){
/*若边(i,j)加入r后形成回路,则不能加入*/
(3);
h++;
dist+=dr[k].x;
}else if((4)){
/*最后一边选入r成回路,则该边必须加入且得到解*/
selected(r,i,j);
h++;
&n
第2题
【说明】
所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。
应用贪婪法求解该问题。程序先计算由各点构成的所有边的长度(作为边的权值),按长度大小对各边进行排序后,按贪婪准则从排序后的各边中选择边组成回路的边,贪婪准则使得边的选择按各边长度从小到大选择。
函数中使用的预定义符号如下:
define M 100
typedef struct{/*x为两端点p1、p2之间的距离,p1、p2所组成边的长度*/
float x;
int p1, p2;
}tdr;
typedef struct{/*p1、p2为和端点相联系的两个端点,n为端点的度*/
int n, P1, p2;
}tr;
typedef struct{/*给出两点坐标*/
float x,y;
}tpd;
typedef int tl[M];
int n=10;
【函数】
float distance(tpd a,tpd b);/*计算端点a、b之间的距离*/
void sortArr(tdr a[M], int m);
/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表,m为边的条数*/
int isCircuit(tr[M], int i, int j);
/*判断边(i, j)选入端点关系表r[M]后,是否形成回路,若形成回路返回0*/
void selected(tr r[M], int i, int j);/*边(i,j)选入端点关系表r*/
void course(tr r[M], tl 1[M]);/*从端点关系表r中得出回路轨迹表*/
void exchange(tdr a[M], int m, int b);
/*调整表排序表,b表示是否可调,即是否有边长度相同的边存在*/
void travling(tpd pd[M], int n, float dist, t1 locus[M])
/*dist记录总路程*/
{
tdr dr[M];/*距离关系表*/
tr r[M];;/*端点关系表*/
int i, j, k, h, m;/*h表示选入端点关系表中的边数*/
int b;/*标识是否有长度相等的边*/
k=0;
/*计算距离关系表中各边的长度*/
for(i=1;i<n;i++){
for(j=i+1;j<=n;j++){
k++;
dr[k].x=(1);
dr[k].p1=i;
dr[k].p2=j;
}
}
m=k;
sortArr(dr,m);/*按距离大小从小到大排序形成排序表*/
do{
b=1;
dist=0;
k=h=0;
do{
k++;
i=dr[k].p1;
j=dr[k].p2;
if((r[i].n<=1)&&(r[j].n<=1)){/*度数不能大于2*/
if((2)){
/*若边(i,j)加入r后形成回路,则不能加入*/
(3);
h++;
dist+=dr[k].x;
}else if((4)){
/*最后一边选入r成回路,则该边必须加入且得到解*/
selected(r,i,j);
h++;
&n
第3题
[说明]
所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。
应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(作为边的权值),按长度大小对各边进行排序后,按贪婪准则从排序后的各边中选择组成回路的边,贪婪准则使得边的选择按各边长度从小到大选择。
函数中使用的预定义符号如下:
define M 100
typedef struct{/*x为两端点p1、p2之间的距离,p1、p2所组成边的长度*/
float x;
int p1,p2;
}tdr;
typedef struct{/*p1、p2为和端点相联系的两个端点,n为端点的度*/
int n,p1,p2;
}tr;
typedef struct{/*给出两点坐标*/
float x,y;
}tpd;
typedef int tl[M];
int n=10;
[函数]
float distance(tpd a,tpd b);/*计算端点a、b之间的距离*/
void sortArr(tdr a[M],int m);
/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表,m为边的条数*/
int isCircuit(tr r[M],int i,int j);
/*判断边(i,j)选入端点关系表r[M]后,是否形成回路,若形成回路返回0*/
void selected(tr r[M],int i,int j);/*边(i,j)选入端点关系表r*/
void course(tr r [M],tl l[M]);/*从端点关系表r中得出回路轨迹表*/
void exchange(tdr a[M],int m,int b);
/*调整表排序表,b表示是否可调,即是否有长度相同的边存在*/
void travling(tpd pd [M],int n,float dist,tl locus[M])
/*dist记录总路程*/
{
tdr dr[M];/*距离关系表*/
tr r[M];/*端点关系表*/
int i,j,k,h,m;/*h表示选入端点关系表中的边数*/
int b;/*标识是否有长度相等的边*/
k=0;
/*计算距离关系表中各边的长度*/
for(i=1;i<n; i++){
for(j=i+1;J<=n;j++){
k++;
dr[k].x=(1);
dr[k].pl=i;
dr[k].p2=j;
}
}
m=k;
sortArr(dr,m);/*按距离大小从小到大排序形成排序表*/
do{
b=1;
dist=0;
k=h=0:
do{
k++;
i=dr[k].p1;
j=dr[k].p2;
if((r(i].n<=1)&&(r[j].n<=1)){/*度数不能大于2*/
if (2) {
/*若边(i,j)加入r后形成回路,则不能加入*/
(3);
h++;
dist+=dr[k].x;
}else if (4) {
/*最后一边选入r成回路,则该边必须加入且得到解*/
selected(r,i,j);
h++:
dist+=dr[k].x;
}
}
}while((k !=n) && (h !=n));
if(h==n){/*最后一边选入构成回路,完成输出结果*/
course(r,locus);
}else(/*找不到解,调整dr,交换表中边长相同的边在表中的顺序,并将b置0*/
(5);
}
}while(!b);
}
(1)
第4题
阅读以下说明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。
【说明】
已知两个整数数组A和B中分别存放了长度为m和n的两个非递减有序序列,函数Adjustment(A,B,m,n)的功能是合并两个非递减序列,并将序列的前m个整数存入A中,其余元素依序存入B中。
合并过程如下:从数组A的第一个元素开始处理。用数组B的最小元素B[0]与数组A的当前元素比较,若A的元素较小,则继续考查A的下一个元素;否则,先将A的最大元素暂存入temp,然后移动A中的元素挪出空闲单元并将B[0]插入数组A,最后将暂存在temp中的数据插入数组B的适当位置(保持B的有序性)。如此重复,直到A中所有元素都不大于B中所有元素为止。
【C函数】
void Adjustment(int A[],int B[],int m,int n)
{ /*数组A有m个元素,数组B有n个元素*/
inti,k,temp;
for(i=0;i<m;i++)
{
if(A[i]<=B[0]) continue,
temp= (1) ;/*将A中的最大元素备份至temp*/
/*从后往前依次考查A的元素,移动A的元素并将来自B的最小元素插入A中*/
for(k= m-1; (2) ;k--)
A[k]=A[k-1];
A[i]=(3) ;
/*将备份在temp的数据插入数组B的适当位置*/
for(k=1; (4) &&k<n;k++)
B[k_1]=B[k];
B[k-1]= (5) ;
}
}
第5题
请考生编写函数mmm(STUa[],STU*s)实现程序的要求,最后调用函数readwritedat()把结果输出到文件out.dat中。
例如:
KS01 87 60 88
KS09 97 59 99
KS11 67 67 60
则调用该函数后,输出
the top:KS01,87, 60, 88
include <stdio.h>
include <string.h>
define N 10
void readwritedat ();
typedef struct ss{
char num[10];
int s1, s2, s3;
}STU;
mmm(STU a[],STU *s)
{
}
main ( )
{
STU a[N]={
{ "01", 81, 93, 92},
{ "02", 89, 65, 91},
{ "03", 66, 55, 73},
{ "04", 87, 91, 99},
{ "05", 77, 65, 91},
{ "06", 90, 55, 73},
{ "07", 79, 65, 91},
{ "08", 61, 55, 73},
{ "09", 80, 93, 92},
{ "10", 71, 65, 91}
}m;
int i;
for (i=0; i<N; i++ )
printf ("No=%s Mark=%d\n",a[i] .num, a[i] .s1,a[i] .s2,a[i].s3);
mmm (a, &m);
printf("the highest: %s,%d\n",m.num,m.s1+m.s2+m.s3);
readwritedat ( );
}
void readwritedat ( )
{
FILE *rf, *wf;
STU a[N] ,m;
int i;
rf=fopen ( "in. dat", "r" );
wf=fopen ( "out. dar", "w" );
for (i=0; i<10; i++)
fscanf (rf, "%s%d%d%d", a [i] .hum, &a[i] .s1, &a[i] .s2, &a [i] .s3);
mmm(a, &m);
fprintf(wf,"the top: %s,%d,%d,%d\n",m.num,m.s1,m.s2,m.s3);
fclose (rf);
fclose (wf);
}
第6题
已知求一组数据连续若干数和的最大值采用分治方法得到O(nlogn)的时间复杂度,请完成下面分治法求解的代码: /************************************************************************/ /* 分治法 最大和子数组有三种情况: 1)A[1...mid] 2)A[mid+1...N] 3)A[i..mid..j] /************************************************************************/ //find max crossing left and right int Find_Max_Crossing_Subarray(int arr[], int low, int mid, int high) { const int infinite = -9999; int left_sum = infinite; int right_sum = infinite; int max_left = -1, max_right = -1; int sum = 0; //from mid to left; for (int i = mid; i >= low; i --) { sum += arr[i]; if (sum > left_sum) { left_sum = sum; max_left = i; } } sum = 0; //from mid to right for (int j = mid + 1; j <= high; j ++) { sum +="arr[j];" if (sum> right_sum) { right_sum = sum; max_right = j; } } return (left_sum + right_sum); } int Find_Maximum_Subarray(int arr[], int low, int high) { if (high == low) //only one element; return arr[low]; else { int mid = (low + high)/2; int leftSum = Find_Maximum_Subarray(arr, low, mid); int rightSum = Find_Maximum_Subarray(arr, mid+1, high); int crossSum = Find_Max_Crossing_Subarray(arr, low, mid, high); ——————————完成这里的代码—————————————————— } } 注意为了尽量减少答案的多样性,本次编程代码请通过>而不是 <符号进行数据的比较。按照leftsum,rightsum,crosssum的顺序进行比较。>
第7题
已知求一组数据连续若干数和的最大值采用分治方法得到O(nlogn)的时间复杂度,请完成下面分治法求解的代码: /************************************************************************/ /* 分治法 最大和子数组有三种情况: 1)A[1...mid] 2)A[mid+1...N] 3)A[i..mid..j] /************************************************************************/ //find max crossing left and right int Find_Max_Crossing_Subarray(int arr[], int low, int mid, int high) { const int infinite = -9999; int left_sum = infinite; int right_sum = infinite; int max_left = -1, max_right = -1; int sum = 0; //from mid to left; for (int i = mid; i >= low; i --) { sum += arr[i]; if (sum > left_sum) { left_sum = sum; max_left = i; } } sum = 0; //from mid to right for (int j = mid + 1; j <= high; j ++) { sum +="arr[j];" if (sum> right_sum) { right_sum = sum; max_right = j; } } return (left_sum + right_sum); } int Find_Maximum_Subarray(int arr[], int low, int high) { if (high == low) //only one element; return arr[low]; else { int mid = (low + high)/2; int leftSum = Find_Maximum_Subarray(arr, low, mid); int rightSum = Find_Maximum_Subarray(arr, mid+1, high); int crossSum = Find_Max_Crossing_Subarray(arr, low, mid, high); ——————————完成这里的代码—————————————————— } } 注意为了尽量减少答案的多样性,本次编程代码请通过>而不是<符号进行数据的比较。按照leftsum,rightsum,crosssum的顺序进行比较。>
第8题
例如:5591是素数,则该数满足条件,计算平均值pjz1,且个数cnt=cnt+1。
9812是非素数,则该数不满足条件,计算平均值pjz2。
注意:部分源程序已给出。
程序中已定义数组:a[300],b[300],已定义变量:cnt,pjz1,pjz2。
请勿改动主函数main()、读函数readDat()和写函数writeDat()的内容。
试题程序:
include<stdio. h>
int a[300], cnt=0;
double pjz1=0.0, pjz2=0.0;
int isP(int m)
{
int i;
for (i=2; i<m; i++)
if(m%i==0) return 0;
return 1;
}
void jsValue()
{
}
main ( )
{
int i;
readDat ();
jsValue();
writeDat ();
printf ("cnt=%d\n满足条件的平均值pjz1=%7.21f\n不满足条件的平均值
pjz2=%7.21f\n", cnt, pjz1, pjz2);
}
readDat ( )
{
FILE *fp;
int i;
fp=fopen("in82.dat","r");
for (i=0; i<300; i++)
fscanf (fp, "%d, ", &a [i]);
fclose (fp);
}
writeDat ()
{
FILE *fp;
int i;
fp=fopen("out82.dat","w");
fprintf(fp,"%d\n%7.21f\n%7.21f\n",cnt,pjz1,pjz2);
fclose(fp);
}
第9题
例如:5591是素数,则该数满足条件,计算平均值pjz1,且个数cnt=cnt+1。
9812是非素数,则该数不满足条件,计算平均值pjz2。
注意:部分源程序已给出。
程序中已定义数组:a[300],b[300],已定义变量:cnt,pjz1,pjz2。
请勿改动主函数main()、读函数readDat()和写函数writeDat()的内容。
试题程序;
include<stdio.h>
int a[300], cnt=0;
double pjz1=0.0,pjz2=0.0;
int isP(int m)
{
int i;
for(i=2;i<m;i++)
if(m%i==0) return 0;
return 1;
}
void jsValue()
{
main()
{
int i;
readDat();
jsValue();
writeDat();
printf("cnt=%d\n满足条件的平均值pjz1=%7.2lf\n不满足条件的平均值
pjz2=%7.2lf\n",cnt,pjz1,pjz2);
}
readDat()
{
FILE *fp;
int i;
fp=fopen( "in82.dat","r");
for(i=0;i<300;i++)
fscanf(fp,"%d,",&a[i]);
fclose(fp);
}
writeDat()
{
FILE *fp;
int i;
fp=fopen("out82.dat","w");
fprintf(fp,"%d\n%7.2lf\n%7.2lf\n",cnt ,pjz1,piz2);
fclose(fp);
}
第10题
例如:5591是素数,则该数满足条件,存入数组b中,且个数cnt=cnt+1。
9812是非素数,则该数不满足条件,忽略。
注意:部分源程序已给出。
程序中已定义数组:a[300],b[300],已定义变量:cnt。
请勿改动主函数main()、读函数readDat()和写函数writeDat()的内容。
试题程序:
include<stdio.h>
int a[300],b[300],cnt=0;
int isP(int m)
{
int i;
for(i=2;i<m;i++)
if(m%i==0) return 0;
return 1;
}
jsValue()
{
}
main()
{
int i;
readDat();
jsValue();
writeDat();
printf("cnt=%d\n",cnt);
for(i=0;i<cnt;i++)
printf("b[%d]=%d\n",i,b[i]);
}
readDat ( )
{
FILE *fp;
int i;
fp= fopen ( "IN58. DAT", "r" );
for (i=0; i<300; i++)
fscanf(fp,"%d,",&a[i])
fclose (fp);
}
writeDat ( )
{
FILE *fp;
int i;
fp=fopen ( "OUT58. DAT", "w" );
fprintf(fp,"%d\n",cnt);
for (i=0; i<cnt; i++)
fprintf (fp, "%d\n", b[i]
fclose(fp);
}
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!