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

ID: 4710

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

椰子

标签>

初赛模拟试题

CSP-J

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

关于机器翻译，下列选项中正确的是（）。 {{ select(1) }}

常见的翻译软件只有金山词霸、金山快译两种
机器翻译的英文全称是Machine Translation，简称MT
百度和谷歌不具有在线翻译功能
机器翻译是利用计算机把一种自然语言转变成另一种机器语言

以补码存储的8位有符号整数10100011的十进制表示为（）。 {{ select(2) }}

关于网络协议，下面说法中正确的是（）。 {{ select(3) }}

Internet网络协议采用TCP/IP协议
我们所说的TCP/IP协议就是指传输控制协议
www浏览器使用的应用协议是IPX/SPX
没有网络协议，网络也能实现可靠地传输数据

以下程序执行完毕后，输出的值为（）。

int f(int n)
{
    if(n==2 || n==1)
        return 1;
    else
        return f(n-1)+f(n-2);
}
cout<<f(9);

下列关键字序列中，哪一项是堆（）。 {{ select(5) }}

16,72,31,23,94,53
94,23,31,72,16,53
16,53,23,94,31,72
16,23,53,31,94,72

对n个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多（）。 {{ select(6) }}

从小到大排列好的
从大到小排列好的
元素无序
元素基本有序

n为一个两位数，它的数码之和为a，当n分别乘以3、5、7、9以后得到4个乘积，如果每一个积的数码之和都为a，那么这样的两位数n有（）个。 {{ select(7) }}

二叉树第10层的结点数的最大数目为（）。 {{ select(8) }}

10
100
512
1024

100以内最大的素数是（）。 {{ select(9) }}

15张卡片，每张卡片上写有3个不同的汉字，任意2张上的汉字不完全相同；任意6张中，一定有2张，它们上面有共同的汉字。这15张卡片上最多有多少个不同的汉字？（） {{ select(10) }}

仅由数字1,2,3组成的七位数中，相邻数字均不相同的七位数的个数是（）。 {{ select(11) }}

有甲、乙、丙、丁四支球队参加的足球循环赛，每两队都要赛一场，胜得3分，负者得0分，踢平则两队各得1分。现在甲、乙、丙分别得了7分、1分和6分，已知甲和乙踢平，那么丁得（）分。 {{ select(12) }}

若一组记录的排序码为(46,79,56,38,40,84)，利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。 {{ select(13) }}

38,40,46,56,79,84
40,38,46,79,56,84
40,38,46,56,79,84
40,38,46,84,56,79

一棵6节点二叉树的中序遍历为ABDGECF，先序遍历为DBACECF，后序遍历为（）。 {{ select(14) }}

DGBEFAC
ABGEFCD
GBEACFD
ABCDEFC

下面哪种图不一定是树（）。 {{ select(15) }}

无回路的连通图
有n个结点，n-1条边的连通图
每对结点间都有通路的图
连通但删去任意一条边则不连通的图

二、阅读程序（共计40分；判断题每题1.5分，选择题每题3分）

（一）前缀和区间查询

#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
int a[N], s[N];
int main()
{
    int n, m;
    cin >> n >> m;
    memset(s, 0, sizeof(s));
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = a[i] + s[i-1];
    }
    int l, r;
    while(cin >> l >> r)
    {
        cout << s[r] - s[l-1] << endl;
    }
    return 0;
}

判断题 16. 输出只能是正整数。（） {{ select(16) }}

正确
错误

将第03行的2e5改为2e10输出结果不变。（） {{ select(17) }}

正确
错误

将第09行删除，程序运行结果不会改变。（） {{ select(18) }}

正确
错误

只要输入int类型的数据，输出结果就一定正确。（） {{ select(19) }}

正确
错误

选择题 20. 若输入为5 3 1 2 3 4 5 2 4，则输出的结果为（）。 {{ select(20) }}

本题中下列哪一项的数据范围偏小（）。 {{ select(21) }}

a[N]
s[N]
m
以上都不对

（二）求第n个素数

#include<cstdio>
bool pd(long long n)
{
    if(n == 1)
        return false;
    for(long long i = 2; i < n; i++)
        if(n % i == 0) return false;
    return true;
}
int main()
{
    long long n, i, c = 0;
    int INF = 1 << 30;
    scanf("%d", &n);
    for(i = 2; i <= INF; i++)
    {
        if(pd(i))
        {
            c++;
            if(c == n)
            {
                printf("%d", i);
                return 0;
            }
        }
    }
    printf("\n over");
    return 0;
}

判断题 22. 将第13行修改为INF = 1 << 40，输出结果一定不变。（） {{ select(22) }}

正确
错误

将第23行修改为break或continue，相同输入下输出结果一定相同。（） {{ select(23) }}

正确
错误

将第23行修改为break，相同输入下变量c的值和未修改前一定相同。（） {{ select(24) }}

正确
错误

将第23行修改为break，相同输入下输出结果一定相同。（） {{ select(25) }}

正确
错误

选择题 26. 当输入为8时，输出为（）。 {{ select(26) }}

17
19\n over
19
23\n over

将第06行的i < n修改为（）后功能不变且效率更高。 {{ select(27) }}

i*i <= n
i < n/2
i < n/3
i < n/4

（三）最长不上升子序列与最长上升子序列

#include<bits/stdc++.h>
using namespace std;
int s[100001], a[100001], n, ans1, ans2;
int main()
{
    while(scanf("%d", &a[++n]) != EOF);
    n--;
    for(int i = n; i >= 1; i--){
        s[i] = 1;
        for(int j = i+1; j <= n; j++){
            if(a[j] <= a[i]){
                s[i] = max(s[i], s[j]+1);
            }
        }
        ans1 = max(ans1, s[i]);
    }
    for(int i = 1; i <= n; i++){
        s[i] = 1;
        for(int j = 1; j <= i; j++){
            if(a[j] < a[i]){
                s[i] = max(s[i], s[j]+1);
            }
        }
        ans2 = max(ans2, s[i]);
    }
    printf("%d %d", ans1, ans2);
    return 0;
}

判断题 28. 若输入序列单调递增，则ans1的值为1。（） {{ select(28) }}

正确
错误

若输入序列单调递减，则ans2的值为1。（） {{ select(29) }}

正确
错误

ans1的值越大，ans2的值将会越小。（） {{ select(30) }}

正确
错误

输入的数值不能为负数。（） {{ select(31) }}

正确
错误

选择题 32. 若输入389 207 155 300 299 170 158 65，输出的第一个数为（）。 {{ select(32) }}

若输入0 -1 0 -1，则输出为（）。 {{ select(33) }}

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

（一）SPFA 最短路

给定一个有n个顶点（1~n编号）、m条边的有向图（部分边权可能为负，保证无负环），计算从1号点到其他所有点的最短路。

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
const int inf = 0x3f3f3f3f;
int h[N], e[N], ne[N], cnt, w[N];
int dis[N];
bool st[N];
int n, m;
void add(int a, int b, int c){
    e[cnt] = b;
    w[cnt] = c;
    ne[cnt] = h[a];
    h[a] = cnt++;
}
void spfa()
{
    memset(dis, inf, sizeof(dis));
    dis[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = ① ; ② ; i = ne[i]){
            int j = e[i];
            if(dis[j] > dis[t] + w[i])
            {
                ③ ;
                if(!st[j])
                {
                    ④ ;
                    st[j] = true;
                }
            }
        }
    }
}
int main(){
    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof h);
    while(m--){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        ⑤ ;
    }
    spfa();
    for(int i = 2; i <= n; ++i)
        printf("%d\n", dis[i]);
    return 0;
}

①处应填（）。 {{ select(34) }}

1
-1
h[t]
t

②处应填（）。 {{ select(35) }}

i = 0
i > 0
i != -1
i > -1

③处应填（）。 {{ select(36) }}

dis[j] = dis[t] + w[t]
dis[j] = abs(dis[t] + w[i])
dis[j] = dis[t] + w[i]
dis[j] = dis[i] + w[i]

④处应填（）。 {{ select(37) }}

q.push(j)
q.push(i)
q.push(st[j])
q.push(1)

⑤处应填（）。 {{ select(38) }}

spfa()
add()
add(a,b,c)
spfa

（二）货币系统（完全背包）

两个货币系统等价当且仅当它们能表示的非负整数集合完全相同。给定原货币系统，求与之等价且面额种数最少的货币系统的面额种数。

#include<bits/stdc++.h>
using namespace std;
int a[105], f[25005];
int main()
{
    int T, n;
    scanf("%d", &T);
    while(①){
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        sort(a, a + n);
        int x = ② ;
        memset(f, 0xcf, sizeof(f));
        f[0] = ③ ;
        for(int i = 0; i < n; i++){
            for(int j = a[i]; j <= x; j++)
                f[j] = max(f[j], ④);
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            if(⑤)
                res++;
        }
        printf("%d\n", res);
    }
    return 0;
}

①处应填（）。 {{ select(39) }}

②处应填（）。 {{ select(40) }}

a[0]
a[n-1]
a[1]
a[n]

③处应填（）。 {{ select(41) }}

-1
0
1
n

④处应填（）。 {{ select(42) }}

f[j+a[i]]+1
f[a[i]]+1
f[j-a[i]]
f[j-a[i]]+1

⑤处应填（）。 {{ select(43) }}

f[a[i]] == 1
f[a[i]] == 0
f[a[i]] > 1
f[a[i]] > 2

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