全国入门组 CSP-J 初赛模拟试题 (5)
一、单项选择题
（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
12) 用某种排序方法对线性表25 , 84,21,47,15,27,68,35,20进行排序，结点变化如下: (1)25,84, 21,47,15, 27, 68,35,28; (2)20,15, 21,25,47, 27, 68,35,84; (3)15,20, 21,25,35, 27, 47,68,84; (4)15,20, 21,25,27, 35, 47,68,84.那么，排序方法是（）
二、阅读程序
（程序输入不超过数组或字符串定义的范围;除特殊说明外，判断题1.5分，选择题4分，共计40分）
#include <iostream>
using namespace std;
void hanoi(int n,char a, char b,char c) {
if(n==1)
cout<<n<<" "<<a<<" "<<c<<endl;
else {
hanoi(n-1,a,c,b);
cout<<n<<" "<<a<<" "<<c<<endl;
hanoi(n-1,b,a,c);
}
}
int main() {
int n;
cin>>n;
hanoi(n,'A','B','C');
return 0;
}#include <cstdio>
#define N 1005
using namespace std;
int num[N];
int main() {
int a1=1,n,x;
scanf("%d", &n);
num[1] = 1;
for(int i=1; i<=n; ++i) {
x=0;
for(int j=1; j<=a1; ++j) {
num[j] = num[j] * 5 + x;
x = num[j] / 10;
num[j] %= 10;
}
if (x > 0) num[++a1] = x;
}
printf("0.");
for(int i=a1; i<n; ++i) {
putchar('0');
}
for(int i=a1; i>=1; i--) {
printf("%d", num[i]);
}
putchar('\n');
return 0;
}#include <iostream>
using namespace std;
int l,n,m,a[50005], ans;
bool check(int dis)
{
int count=0,last=0;
for(int i=1; i<=n; i++)
if(a[i]-last<dis)count++;
else last=a[i];
if(count>m)return 0;return 1;
}
int main()
{
ios::sync_with_stdio(0);
cin>>l>>n>>m;
for(int i=1; i<=n; i++)
cin>>a[i];
a[n+1]=l;
int fl=0,fr=l;
while(fl<=fr)
{
int mid=(fl+fr)/2;
if(check(mid))fl=mid+1, ans=mid;
else fr=mid-1;
}
cout<<ans ;
return 0;
}
三、完善程序
（单选题，每题3分，共计30分）
迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
#include<iostream>
using namespace std;
int main()
{
int edgs;
int points ;
int dis[10];
int flag[10];
int infinity=999999;
cin>>points>>edgs ;
int edg[10][10];
for (int i=1; i<=points; i++) // 初始化
{
for (int j=1; j<=points; j++)
{
if (i==j)
{
edg[1][j]=___(1)___;
}
else
{
edg[i][j]=___(2)___;
}
}
}
int point1 , point2 , quanzhi ;
for (i=1; i<=edgs; i++)
{
cin>>point1>>point2>>quanzhi ;
edg[point1][point2]= ___(3)___ ;
}
for (i=1; i<=points; i++)
{
dis[i]=edg[1][i];
}
for (i=1; i<=points; 1++)
{
flag[i]=0;
}
flag[1]=1;
int min,u;
for (i=1; i<=points-1; i++)
{//源点到源点不用比较，因次总的次数少一次
min=infinity;
for (int j=1; j<points; j++)
{
if (f1ag[j]==0&&dis[j]<min)
{//核心思想:依次比较出离源点最近的点
min=___(4)___;
u=j;
}
}
flag[u]=1;
for (int v=1; v<=points; v++)
{//找出离源点最近的点后更新dis里面的源点到各个点的值是否最小
if (edg[u][v]<infinity)
{
if (dis[v]>dis[u]+edg[u][v])
{
dis[V]=___(5)___;
}
}
}
}
for (i=1; i<=points; i++)
{
cout<<dis[i]<" ";
}
cout<<endl;
}
完全背包问题
容量为10的背包，有5种物品，每种物品数量无限，其重量分别为5, 4, 3, 2，1，其价值分别为1，2，3，4，5。
设计算法，实现背包内物品价值最大。代码如下(输出50)
容量为10的背包，有5种物品，每种物品数量无限，其重量分别为5, 4, 3, 2，1，其价值分别为1，2，3，4，5。
设计算法，实现背包内物品价值最大。代码如下(输出50)
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int total_weight = 10;
int w[6] = { 0,5,4,3,2,1};
int v[6] = { 0,1,2,3,4,5};
int dp[11]= { ___(1)___ };
for(int i=1; i<=___(2)___; i++)
for(int j=w[i]; j<=___(3)___; j++)
dp[j] =___(4)___;
cout <<___(5)___<< endl;
return 0;
}
