CCF认证CSP-J入门组模拟测试题第二套
三、完善程序题
第一题 菲波拉契数列
菲波拉契数列为1,1,2,3,5,8,13,21,…,其元素产生的规则是前两个数为1,从第三个数开始每个数等于它前面两个数之和。已知任意一个正整数可以表示为若干个互不相同的菲波拉契数之和。例如:36=21+13+2。
下面的程序是由键盘输人一个正整数n,输出组成n的互不相同的菲波拉契数。算法说明:
(1)寻找小于等于n的最大菲波拉契数a,并以a作为组成n的一个数
(2)若n≠a,则以n-a作为n的新值,重复步骤(1)。若a=n,则结束。
#include<iostream>
#include<cstdio>
using namespace std;
int n;
bool first;
int find(int n)
{
int a,b,c;
a=l;b=l;
do
{
c=a+b;
__①__
}while (b<n);
if(__②__)
return b;
else
__③__
}
void p(int n)
{
int a;
a=find(n);
if(first)
{
printf("%4d",a);
first=false;
}
else
(__④__)
if(a<n) (__⑤__);
}
int main()
{
cin>>n;
first=true;
printf("%5d=",n);
p(n);
cout<<endl;
return 0;
}程序分析：此程序是一个求解斐波那契数列的程序，程序的大致流程如下：
- 首先定义了一个整型变量n，表示要求解的斐波那契数列的项数。
- 定义了一个函数find，用来找到小于等于n的最大斐波那契数。起始时，定义三个变量a、b、c，a和b都初始化为1。然后进入一个循环，在循环中计算c=a+b，然后更新a和b的值，将b赋值给a，c赋值给b。直到b的值大于等于n，循环终止。最后判断b是否等于n，如果等于n，则返回b，否则返回a。
- 定义了一个递归函数p，用来打印出所有的斐波那契数。首先调用find函数找到小于等于n的最大斐波那契数，并将其赋值给变量a。如果是第一个斐波那契数，将a打印出来，并将first标记为false。如果不是第一个斐波那契数，将"+"和a打印出来。然后判断a是否小于n，如果是，则递归调用p函数，将n-a作为参数传入。
- 程序的主函数中，读入n的值。
- 调用函数p，并将n作为参数传入。
- 打印出结果。
单选题
①处应该填
A. a=c;b=a;
B. a=b;b=c;
C. a==c;b==a;
D. a==b;b==c;
答案：B
答案分析：此处根据程序分析应该是答案B
②处应该填
A. b==n
B. b<n
C. a==n
D. a<n
答案：A
答案分析：此处根据程序分析来是答案A
③处应该填
A. return c
B. return b
C. return a+b
D. return a
答案：D
答案分析：此处根据程序分析来是答案D
④处应该填
A. printf("%4d",a)
B. printf("+%4d",a)
C. printf("%4d",b)
D. printf("+%4d",b)
答案：B
答案分析：此处根据程序分析来是答案B，不是第一个数要加上加号
⑤处应该填
A. p(a)
B. p(b)
C. p(n-a)
D. p(n-b)
答案：C
答案分析：此处根据程序分析来是答案C
第二题 高速公路费用
现在政府计划在某个区域的城市之间建立高速公路,以使得其中任意两个城市之间都有直接或间接的高速公路相连。费用为每千米为一个单位价格,求最小费用。
输人:n(n<=100,表示城市数目)。接下来n行,每行两个数 xi,yi,表示第i个城市的坐标。(单位:千米)。输出:最小费用(保留2位小数)。
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=101;
struct tcity
{
float x,y;
};
tcity c[maxn];
float d[maxn][maxn],a,minf;
int p[maxn],n,i,j,k;
int main()
{
cin>>n;
for(i=1;i<=n;i++)
cin>>c[i].x>>c[i].y;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d[i][j]=(__①__)
p[1]=0;
for(i=2;i<=n;i++)(__②__)
for(i=1;i<=n-1;i++)
{
minf=1E10;
for(j=1;j<=n;j++)
{
if(__③__)
{
minf=d[p[j]][j];
(__④__)
}
}
a=a+d[p[k]][k];
p[k]=0;
for(j=1;j<=n;j++)
if(__⑤__) p[j]=k;
}
printf("%0.2f",a);
return 0;
}程序分析：此程序是一个求解旅行商问题（Traveling Salesman Problem，简称TSP）的算法。
- 首先，定义了一个结构体tcity，表示城市的坐标信息。然后定义了一个二维数组d来存储城市之间的距离。
- 接下来，通过输入获取城市个数n，并依次输入每个城市的坐标。
- 然后，使用嵌套循环计算每两个城市之间的距离，并存储到二维数组d中。
- 接下来，初始化了一个一维数组p，表示城市的访问顺序，初始时将第一个城市设置为已访问，并将其余城市设置为未访问。。
- 接下来，进行n-1次迭代的贪心选择，每次选择距离最短的未访问城市，更新访问顺序和总距离。
- 最后，输出最小总距离a。
单选题
①处应该填
A. sqrt((c[i].x-c[i]·y)*(c[¡].x-c[i].y)+(c[j].x-c[j].y)*(c[j].x-c[j].y));
B. sqrt((c[i].x-c[j].x)*(c[j].x-c[i].x)+(c[i].y-c[j].y)*(c[j]·y-c[i].y));
C. sqrt((c[i].x-c[j].x)*(c[i].x-c[j].x)+(c[i],y-c[j].y)*(c[i].y-c[j].y));
D. sqrt((c[i].x-c[i].y)*(c[j].x-c[j].y)+(c[i].x-c[i].y)*(c[j].x-c[j].y));
答案：C
答案分析：此处要填的是两点之间的直线距离如何计算，答案C
②处应该填
A. p[i]=1;
B. p[i]=0;
C. p[n-i]=0;
D. p[n-i]=1;
答案：D
答案分析：此处p[i]可以理解为第i点到起点1的最短距离
③处应该填
A. p[j]==0 && d[p[j]][j]<minf
B. p[j]!=0 && d[p[j]][j]<minf
C. p[j]==0 || d[p[j]][j]<minf
D. p[j]!=0 || d[p[j]][j]<minf
答案：B
答案分析：此处是查找没有加入最小费用几何的点到最小费用集合里点的距离最小值的点
④处应该填
A. k=minf
B. k=0
C. k=i
D. k=j
答案：D
答案分析：此处是记录当前最小点位
⑤处应该填
A. d[p[j]][j]>d[k][j]
B. d[p[j]][j]<d[k][j]
C. d[p[i]][j]>d[k][j]
D. d[p[i]][j]<d[k][j]
答案：D
答案分析：此处是找到集合外的点与刚加入的点是否有更优的值，如果有更新最优点位
