CSP-J模拟试题

您的姓名：
一、单项选择题(共15题，每题2分，共计30分；每题有且仅有一个正确选项)
1.以下关于CSP-J/S的描述错误的是()
2.在8位二进制补码中，10110110表示的是十进制下的()
3. 2019年10月14日是星期一，1978年10月14日是()
4. 图G是一棵n节点的树，G上有()条边
5. 由五个不同的节点构成的树有()种
6. 有一个长为6的A序列：{3,20,4,6,1}，现通过进行交换其中相邻两个数字的操作进行排序，要将A序列排成从小到大的递增序列最少要进行多少次交换操作()
7.某算法计算时间表示为递推关系式： T(N)=N+T(N/2) ,则该算法时间复杂度为( )。
8.一棵6节点二叉树的中序遍历为DBAGECF,先序遍历为ABDCEGF，后序遍历为()
9.一张有9个节点的无向图最多有()条边
10.下列不属于面向对象程序设计语言的是( )
11.G是一张有n个点m条边的连通图，必须删去()条边才能将其变成一棵n节点的树
12.字符串”abcab”本质不同的子串个数(),不考虑空串
13.十进制小数13.375对应的二进制数是()：
14.若某算法的计算时间表示为递推关系：

则该算法的复杂度为()
15. 一家三口人，恰好仅有两个人生日在同一天的概率是() 【假设每年都是365天】
二、阅读程序写结果(共18小题，每小题2分，最后两题4分，共计40分)
第一题
#include<iostream>
using namespace std;
int a,b,c;
int main()
{
    cin>>a>>b>>c;
    int t=b;
    b=a,a=t;
    c=a;
    cout<<a<<" "<<b<<" "<<c;
}
16. 若输入3 9 1，则输出9 3 3
17. 若输入12300400000 3 7，将一定能输出3 12300400000 3
18.该程序中，头文件#include<iostream>可以改成#include<cstdio>
19.若输入3 6 9，输出()
20.若将c=a改成c=t,则若输入3 6 9，输出()
21.若将c=a改成c=b,则若输入3 6 9，输出()
第二题
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int w[35000],d[35000],dp[35000];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
       scanf("%d%d",&w[i],&d[i]);
    for(int i=1;i<=n;i++)
      {
          for(int j=m;j>=w[i];j--)
             {
                   dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
             }
       }
    printf("%d\n",dp[m]);
    return 0;
}
22. 上述代码中，双重循环里循环变量j的枚举顺序改为从w[i]到m，输出结果一定不变
23. 上述代码中，双重循环中变量i的枚举顺序改为从n到1，输出结果一定不变
24. 当输入为：
4 6
1 4
2 6
3 12
2 7
输出为()
25.若输入数据中，1<=n<=30000,1<=m<=30000,1<=w[i]<=30000,1<=d[i]<=30000,则所求答案一定没有溢出()
26.若输入数据中，1<=n<=30000,1<=m<=30000,1<=w[i]<=30000,1<=d[i]<=1000000000,则所求答案一定没有溢出()
27.上述代码的时间复杂度为()
第三题
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 500+10
using namespace std;
int a[N],n;
int main()
{
   cin>>n;
   for(int i=1;i<=n;i++)   cin>>a[i];
   for(int i=1;i<n;i++)
     {
        int tmp=i;
        for(int j=i+1;j<=n;j++)
             if(a[j]<a[tmp])  tmp=j;
       swap(a[i],a[tmp]);
       }
   for(int i=1;i<=n;i++)    cout<<a[i]<<" ";
   cout<<endl;
   return 0;
}
28. 上述代码实现了对一个长度为n的序列进行排序()
29. 我们将上述算法称为()
30.上述代码的时间复杂度为()
31. 若输入数据为：
5
3 2 1 5 4
则if(a[j]<a[tmp])这句话中的条件会成立多少次(即后面的tmp=j会被执行多少次) ()
32.去掉头文件#include<cstdio>后程序仍能正常编译运行()
33. 去掉using namespace std;后程序仍能正常编译运行()
五、完善程序(每题15分，共计30分)
1. 请完善下面的程序，使用BFS统计一张边权都为1的图中，从给定起点到所有点的距离：
#include<algorithm>
#include<cstdio>
#include<vector>
#define N 200020
using namespace std;
int n,m;
vector<int>G[N];
int q[N],hd,tl;
int dis[N];
void BFS(___（1）_____)
{
   hd=1,tl=0;
   for(int i=1;i<=n;i++)dis[i]=-1;
   q[++tl]=st,dis[st]=0;
   while(____(2)_____)
    {
       int u=q[hd++];
       for(int i=0;i<G[u].size();i++)
         {
            int v=G[u][i];
            if(____(3)____)continue;
            dis[v]=dis[u]+1;
            q[++tl]=v;
         }
    }
}
int main()
{
   scanf("%d%d",&n,&m);
   for(int i=1;i<=m;i++)
     {
         int x,y;
         scanf("%d%d",&x,&y);
         G[x].push_back(y);
         ______(4)________;
      }
   int st;
   scanf("%d",&st);
   BFS(st);
   for(_____(5)_____)   printf("%d ",dis[i]);
}
34.上述程序___(1)___中应该填写()
35.上述程序___(2)___中应该填写()
36.上述程序___(3)___中应该填写()
37. 上述程序___(4)___中应该填写()
38. 上述程序___5___中应该填写()
2.(拓扑排序)给出一张n节点m条边的有向图，求出该图的一个拓扑排序，若无拓扑排序输出-1
输入：
第一行两个正整数 n,m 表示点数和边数。
接下来 m 行，每行三个正整数 x,y表示节点 x->y之间有一条边。
输出：
一个拓扑序：按拓扑序输出点的编号。若拓扑序不唯一，输出任意一个均可。若无拓扑序，输出 -1.
#include<algorithm>
#include<cstdio>
#include<vector>
#define N 200020
using namespace std;
int n,m;
vector<int>G[N];
int q[N],hd,tl;
int du[N];
int ans[N],tot;
void topo()
{
   hd=1,tl=0;
   for(int i=1;i<=n;i++)   if(___(1)____)   q[++tl]=i;
   while(hd<=tl)
    {
       int u=q[hd++];
       ans[++tot]=u;
       for(int i=0;____(2)____;i++)
         {
            int v=G[u][i];
            du[v]--;
            if(!du[v])____(3)____;
         }
     }
    if(tot!=n)  puts("-1");
    else
      {
            for(int i=1;i<=n;i++)
                 printf("%d ",ans[i]);
       }
}
int main()
{
   scanf("%d%d",&n,&m);
   for(int i=1;i<=m;i++)
     {
        int x,y;
        scanf("%d%d",&x,&y);
        _____(4)___________;
        _____(5)___________;
     }
    topo();
}
39. 上述程序___1___中应该填写()
40. 上述程序___2___中应该填写()
41. 上述程序___3___中应该填写()
42. 上述程序___4___中应该填写()
43. 上述程序___5___中应该填写()
更多问卷 复制此问卷