#CSP003. 入门级CSP-J第3套初赛模拟试题

入门级CSP-J第3套初赛模拟试题

一、单项选择题（共15题，每题2分，共计30分）

  1. 在网络上,若某台电脑的设备及数据可由其他电脑共享,这台电脑称为( )。 {{ select(1) }}
  • 个人计算机
  • 副机
  • 服务器
  • 主机
  1. 下列不同数制表示的数中,最大的一个数是()。 {{ select(2) }}
  • 十进制数220.1
  • 二进制数11011011.1
  • 八进制数334.1
  • 十六进制数DC.1
  1. 字母在计算机中是以编码形式表示的,通用的编码是ASCII码,字母"A"的ASCII码是65,字母"E"的ASCII码是( )。 {{ select(3) }}
  • 05
  • 52
  • 69
  • 68
  1. 连接到internet上的每台计算机都必须有1个( )地址,该地址共含( )个字节。前面若干个字节表示( );后面若干字节表示( )。为了避免使用数字,人们经常用字母替代,这些名字称为( )。 {{ select(4) }}
  • IP、四、网络地址、计算机地址、网
  • 网络、四、IP地址、网内计算机地址、域名
  • 网络、不超过十、网页、网址、网名
  • IP、四、网络地址、网内计算机地址、域名
  1. 在TCP/IP协议中,TCP和IP分别提供什么服务( )。 {{ select(5) }}
  • 传输层、网络层
  • 链路层、网络层
  • 传输层、会话层
  • 物理层、链路层
  1. 一棵树T有2个度数为2的结点、有1个度数为3的结点、有3个度数为4的结点,那么树T有()个树叶。 {{ select(6) }}
  • 14
  • 6
  • 18
  • 7
  1. 在一个图中,所有顶点的度数之和等于所有边数的( )倍。 {{ select(7) }}
  • 1/2
  • 1
  • 2
  • 4
  1. 下列IP地址中正确的是()。 {{ select(8) }}
  • 202.300.12.4
  • 192.168.0.3
  • 100:128:35:91
  • 111-102-35-21
  1. 设有100个顶点,利用二分法查找时,最大比较次数是()。 {{ select(9) }}
  • 50
  • 10
  • 25
  • 7
  1. 一棵二叉树的中序遍历序列为:DCBAECHF,后序遍历序列为:CDBEHFCA,则前序遍历的序列是()。 {{ select(10) }}
  • ABCDFGHE
  • ABDGCEFH
  • ACBGDHEF
  • ACEFHBGD
  1. 下面合法的电子邮件地址是()。 {{ select(11) }}
  1. Internet给我们提供了资源共享、浏览、检索信息和远程登录等多种服务,下面几个选项中用于远程登录的是()。 {{ select(12) }}
  • Telnet
  • E_mail
  • TCP/IP
  • WWW
  1. 在数据结构中,链表是( )。 {{ select(13) }}
  • 顺序存储的线性表结构
  • 非顺序存储的线性表结构
  • 非顺序存储的非线性表结构
  • 顺序存储的非线性表结构
  1. C++程序运行时,是在哪种存储器中进行的?( )。 {{ select(14) }}
  • 硬盘
  • RAM
  • ROM
  • CACHE
  1. 当 A>=B && B>=C 的取值为真时,表达式 A>C || B==C 的值( )。 {{ select(15) }}
  • 为真
  • 无法判定结果的真假
  • 也有可能为假
  • 只有当A、B、C都相等时才为真

二、阅读程序（共计40分；标注分值的按标注计，未标注判断题每题1.5分，选择题每题4分）

（一）

#include<iostream>
#include<cstdio>
using namespace std;
int i,j,n;
int x[101],y[101];
int main()
{
    cin>>n;
    for(i=1;i<=n;i++) cin>>x[i];
    for(i=1;i<=n-1;i++)
        for(j=i+1;j<=n;j++)
            if(x[i]>x[j])
                y[j]++;
            else if(x[i]<x[j])
                y[i]++;
    for(i=1;i<=n;i++)
        printf("%5d_",y[i]);
    cout<<endl;
    return 0;
}

判断题 16. (1分)把第13行与第15行互换位置,结果不会改变。() {{ select(16) }}

  • 正确
  • 错误
  1. (1分)第14行把if(x[i]<x[j])删掉效果一样。() {{ select(17) }}
  • 正确
  • 错误
  1. 第11行把i+1改成1,数组y每个元素的值增加1倍。() {{ select(18) }}
  • 正确
  • 错误
  1. 数组y[i]中存的是x[i]在数列中从大到小的次序。() {{ select(19) }}
  • 正确
  • 错误

选择题 20. 此程序的时间复杂度是( )。 {{ select(20) }}

  • O(log2n)
  • O(n log2n)
  • O(n^2)
  • O(n)
  1. 此程序如果n输入4,然后输入2 4 1 3,输出结果是()。 {{ select(21) }}
  • 1 2 3 4
  • 2 0 3 1
  • 4 3 2 1
  • 1 3 0 2

（二）

#include<iostream>
#include<cstdio>
using namespace std;
int n,i,x;
int d[11];
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        d[x]=d[x]+1;
    }
    d[0]=0;
    for(i=1;i<=10;i++)
        d[i]=d[i-1]+d[i];
    for(i=1;i<=10;i++)
        if(d[i]!=d[i-1])
            printf("%3d:%4d_",i,d[i-1]+1);
    return 0;
}

判断题 22. (1分)输入的 x 值应在[0,n-1]的范围内。() {{ select(22) }}

  • 正确
  • 错误
  1. (1分)把第12行改成"d[x]++",不影响程序运行结果。() {{ select(23) }}
  • 正确
  • 错误
  1. 对任意在[1,9]之间的数i,都有d[i-1]<d[i]<d[i+1]。() {{ select(24) }}
  • 正确
  • 错误
  1. 把第18行改成"if(d[i]>d[i-1])",程序运行的结果会发生改变。() {{ select(25) }}
  • 正确
  • 错误

选择题 26. 输入 n=10 后,接着输入:1 3 4 3 5 2 4 3 5 2后,程序输出结果为( )。 {{ select(26) }}

  • 1:1 2:2 3:3 4:2 5:3
  • 1:1 2:2 3:4 4:7 5:9
  • 1:0 2:1 3:2 4:1 5:2
  • 1:1 2:2 3:3 4:4 5:5
  1. 把程序第19行改成"printf("%3d",i);"后,输入 n=10 后,接着输入:1 3 4 1 5 4 4 3 5 1后,程序输出结果为()。 {{ select(27) }}
  • 12345
  • 3232
  • 4343
  • 1345

（三）

#include<iostream>
#include<cstdio>
using namespace std;
int j,i,m;
int a[10];
int main()
{
    for(i=2;i<=6;i++) a[i]=i+1;
    do
    {
        m=2;
        for(i=3;i<=6;i++)
            if(a[m]>a[i]) m=i;
        a[m]=a[m]+m;
        m=1;
        for(i=2;i<=5;i++)
            for(j=i+1;j<=6;j++)
                if(a[i]<a[j]) m=0;
    }while(m==0);
    printf("%d",a[2]);
    return 0;
}

判断题 28. 程序结束时,a[2]的值一定是数组a中的最大值。() {{ select(28) }}

  • 正确
  • 错误
  1. 第21行 "m==0" 成立时,数组 a[i](2 ≤i ≤6) 从大到小排序。() {{ select(29) }}
  • 正确
  • 错误
  1. 程序输出时,a数组满足:对任意的 2≤i<6 ,有a[i]>a[i+1]。() {{ select(30) }}
  • 正确
  • 错误
  1. 删除第16行代码"m=1"程序结果会发生改变。() {{ select(31) }}
  • 正确
  • 错误

选择题 32. 程序的输出结果为()。 {{ select(32) }}

  • 58
  • 59
  • 61
  • 60
  1. 此程序的时间复杂度是()。 {{ select(33) }}
  • O(n^3)
  • O(n log n)
  • O(n^2)
  • O(n)

三、完善程序（单选题，每小题3分，共计30分）

（一）菲波拉契数列拆分

菲波拉契数列为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=1;b=1;
    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;
    printf("%5d=",n);
    first=true;
    p(n);
    cout<<endl;
    return 0;
}
  1. ①处应填()。 {{ select(34) }}
  • a=c;b=a
  • a=b;b=c
  • ac;ba
  • ab;bc
  1. ②处应填()。 {{ select(35) }}
  • b==n
  • b<n
  • a==n
  • a<n
  1. ③处应填()。 {{ select(36) }}
  • return c
  • return b
  • return a+b
  • return a
  1. ④处应填()。 {{ select(37) }}
  • printf("%4d",a)
  • printf("+%4d",a)
  • printf("%4d",b)
  • printf("+%4d",b)
  1. ⑤处应填()。 {{ select(38) }}
  • p(a)
  • p(b)
  • p(n-a)
  • p(n-b)

（二）最小生成树（Prim算法）

现在政府计划在某个区域的城市之间建立高速公路,以使得其中任意两个城市之间都有直接或间接的高速公路相连。费用为每千米为一个单位价格,求最小费用。 输入: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("%.2f",a);
    return 0;
}
  1. ①处应填()。 {{ select(39) }}
  • sqrt((c[i].x-c[i].y)(c[i].x-c[i].y)+(c[j].x-c[j].y)(c[j].x-c[i].y));
  • 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));
  • 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));
  • 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));
  1. ②处应填()。 {{ select(40) }}
  • p[i]=1;
  • p[i]=0;
  • p[n-i]=0;
  • p[n-i]=1;
  1. ③处应填()。 {{ select(41) }}
  • p[j]==0 && d[p[j]][j]<minf
  • p[j]!=0 && d[p[j]][j]<minf
  • p[j]==0 || d[p[j]][j]<minf
  • p[j]!=0 || d[p[j]][j]<minf
  1. ④处应填()。 {{ select(42) }}
  • k= minf;
  • k=0;
  • k=i;
  • k=j;
  1. ⑤处应填()。 {{ select(43) }}
  • d[p[j]][j]>d[k][j]
  • d[p[j]][j]<d[k][j]
  • d[p[i]][j]>d[k][j]
  • d[p[i]][j]<d[k][j]
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  6.  粤公网安备44195502000195号
  11. 粤ICP备2026000218号