#C1215. CSP-J 初赛模拟题4

CSP-J 初赛模拟题4

一、单项选择题

（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

【第 1 题】

参加 NOI 比赛，以下不能带入考场的是（ ）。 {{ select(1) }}

  • 钢笔
  • U 盘
  • 适量的衣服
  • 铅笔

【第 2 题】

6 个顶点的连通图的最小生成树，其边数为（ ）。

{{ select(2) }}

  • 8
  • 7
  • 6
  • 5

【第 3 题】

某算法的计算时间表示为递推关系式 T(n)=T(n−1)+n（n 为正整数）及 T(0)=1，则该算法的时间复杂度为（ ）。

{{ select(3) }}

  • O(logn)O(logn)
  • O(nlogn)O(nlogn)
  • O(n)O(n)
  • O(n2)O(n^2)

【第 4 题】

在关系数据库中，存放在数据库中的数据的逻辑结构以（ ）为主。 {{ select(4) }}

  • ⼆维表
  • ⼆叉树
  • 哈希表
  • 邻接表

【第 5 题】

2024 年 8 月 5 日是星期一（这一天同学们都在参加CSP暑期初赛冲刺集训营地），那么 2024 年 9 月 21 日（考试日期）是（ ）。

{{ select(5) }}

  • 星期日
  • 星期三
  • 星期六
  • 星期一

【第 6 题】

关于分治算法，下列说法中错误的是？（ ）。 {{ select(6) }}

  • 分治算法的核⼼思想是分⽽治之，把问题转化为多个规模更⼩的⼦问题再求解
  • 分治算法可以不使⽤递归实现
  • 归并排序算法的时间复杂度是 O(logn)，其中n表示问题的规模
  • ⼆分法、快速排序等算法都是使⽤分治思想的典型算法

【第 7 题】

有规格尺⼨相同的 5 种颜⾊的⽪球各 15 个混装在箱⼦⾥，从中⾄少取出（ ）个，才能保证取出的球中有三个颜⾊相同的球? {{ select(7) }}

  • 8
  • 9
  • 10
  • 11

【第 8 题】

由 3 个 a、5 个 b 和 2 个 c 构成的字符串中，包含⼦串 "abc" 的共有（ ）个。 {{ select(8) }}

  • 840
  • 780
  • 600
  • 260

【第 9 题】

向一个栈顶指针为 hs 的链式栈中插入一个指针 s 指向的结点时，应执行（ ）。 {{ select(9) }}

  • hs->next = s;
  • s->next = hs->next; hs->next = s;
  • s->next = hs; hs = hs->next;
  • s->next = hs; hs = s;

【第 10 题】

设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做（ ）次比较。

{{ select(10) }}

  • 2n-1
  • 2n
  • n
  • logn

【第 11 题】

一家四口人，至少两个人生日属于同一月份的概率是（ ）（假定每个人生日属于每个月份的概率相同且不同人之间相互独立）。 {{ select(11) }}

  • 4196\frac{41}{96}
  • 112\frac{1}{12}
  • 1144\frac{1}{144}
  • 34\frac{3}{4}

【第 12 题】

黑猫老师站在坐标 (0,0) 处，面朝 x 轴正方向。第一轮，他向前走 1 单位距离，然后右转；第二轮，他向前走 2 单位距离，然后右转；第三轮，他向前走 3 单位距离，然后右转……他一直这么走下去。请问第 2017 轮后，他的坐标是：（ ）

image

{{ select(12) }}

  • (1008,1009)
  • (1009,1008)
  • (-1009,1008)
  • (1008,-1009)

【第 13 题】

如图所示，共有 13 个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由 1 变 0，或由 0 变 1）。现在要使得所有的格子中的数字都变为 0，至少需要（ ）次操作。

image

{{ select(13) }}

  • 2
  • 3
  • 4
  • 5

【第 14 题】

阅读程序写结果：

#include<iostream>
using namespace std;
int main()
{
    int t[256];
    string s;
    int i;
    cin >> s;
    for (i = 0; i < 256; i++)
        t[i] = 0;
    for (i = 0; i < s.length(); i++)
        t[s[i]]++;
    for (i = 0; i < s.length(); i++)
        if (t[s[i]] == 1)
        {
            cout << s[i] << endl;
            return 0;
        }
    cout << "no" << endl;
    return 0;
}

输入：xyzxyw

输出：（ ）。

{{ select(14) }}

  • z
  • w
  • zw
  • x

【第 15 题】

阅读程序写结果：

#include<iostream>
using namespace std;
int g(int m, int n, int x)
{
    int ans = 0;
    int i;
    if (n == 1)
        return 1;
    for (i = x; i <= m / n; i++)
        ans += g(m - i, n - 1, i);
    return ans;
}
int main()
{
    int t, m, n;
    cin >> m >> n;
    cout << g(m, n, 0) << endl;
    return 0;
}

输入：7 3

输出：（ ）。

{{ select(15) }}

  • 7
  • 12
  • 9
  • 8

二、阅读程序

（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

阅读程序（一）

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int SIZE = 25;
4. int n, k, a[SIZE];
5. int cnt = 0;
6. long long ans;
7. bool isPrime(int n) {
8.      cnt++;
9.      // cout << cnt << endl;
10.     if (n <= 1)
11.         return false;
12.     for (int i = 2; i * i <= n; ++i)
13.         if (0 == n % i)
14.             return false;
15.     return true;
16. }
17. void dfs(int m, int sum, int x) {
18.     if (m == k) {
19.         if (isPrime(sum)) {
20.             ans++;
21.         }
22.         return;
23.     }
24.     for (int i = x; i < n; ++i)
25.         dfs(m + 1, sum + a[i], i + 1);
26.     return;
27. }
28. int main() {
29.     cin >> n >> k;
30.     for (int i = 0; i < n; ++i)
31.         cin >> a[i];
32.     dfs(0, 0, 0);
33.     cout << ans << endl;
34.     return 0;
35. }

假设输入的所有数都为不超过 1000 的正整数，完成下面的判断题和单选题：

判断题

  1. 将第 12 ⾏中的 i*i<=n 改为 i<=sqrt(n)，程序的运⾏结果不会改变。 {{ select(16) }}
  • 正确
  • 错误
  1. 将第 25 ⾏中的 sum+a[i] 改为 sum+=a[i]，程序的运⾏结果不会改变。 {{ select(17) }}
  • 正确
  • 错误
  1. 若输⼊ k 值⽐ n ⼤，则程序会死循环，⽆输出。 {{ select(18) }}
  • 正确
  • 错误

单选题

  1. 若输⼊ k 的值为 6，且输⼊ n>=k，a 数组的元素均为相等的正整数,则输出为（ ）。 {{ select(19) }}
  • 0
  • 2
  • 4
  • 8
  1. 若输⼊ 12 8，则 isPrime 被调⽤的次数为（ ）。 {{ select(20) }}
  • 4
  • 66
  • 132
  • 495

阅读程序（二）

1. #include <cstdio>
2. #include <cstring>
3. using namespace std;
4. char s[101];
5. int n, cnt[26];
6. int main() {
7. 	  scanf("%s", s);
8.	  n = strlen(s);
9.	  for (int i = 0; i < n; i++) {
10.		 if (s[i] >= 'A' && s[i] <= 'Z')
11.			 cnt[s[i]-'A']++;
12.		 if (s[i] >= 'a' && s[i] <= 'z')
13.			 cnt[s[i]-'a']++;
14.		 if (s[i] >= '0' && s[i] <= '9')
15.			 cnt[s[i]-'0']++;
16.	  }
17.	  int p = 0;
18.	  for (int i = 1; i < 26; i++)
19.		 if (cnt[i] > cnt[p])
20.			 p = i;
21.	  printf("%d\n", p);
22.	  return 0;
23. }

假设输入的字符串长度不超过 100，完成下面的判断题和单选题。

判断题

  1. 输入的字符串只能由小写字母或大写字母组成。 {{ select(21) }}
  • 正确
  • 错误
  1. 将第 9 行的 i<n 改成 i<=n，程序运行时可能会发生错误。 {{ select(22) }}
  • 正确
  • 错误
  1. 将第 12 行 s[i] >='a' && s[i] <='z'改成s[i] >='a'，程序可能发生运行时错误。 {{ select(23) }}
  • 正确
  • 错误
  1. 若输入的字符串全部由数字字符组成，则输出的整数必然小于 10。 {{ select(24) }}
  • 正确
  • 错误

单选题

  1. 若输入为 ABCDcbaAcDbC，输出为（ ）。 {{ select(25) }}
  • 0
  • 1
  • 2
  • 3
  1. 若输入为 a2B3233CCDC，输出为（ ）。 {{ select(26) }}
  • 0
  • 1
  • 2
  • 3

阅读程序（三）

1. #include <iostream>
2. using namespace std;
3. int a[101], n, cnt;
4. int main() {
5.	  cin >> n;
6.	  for (int i = 1; i <= n; i ++) {
7.		  cin >> a[i];
8.		  int j = i;
9.		  while (j > 1 && a[j] < a[j/2]) {
10.			  cnt++;
11.			  int t = a[j];
12.			  a[j] = a[j/2];
12.			  a[j/2] = t;
13.			  j /= 2;
14.		  }
15.	   }
16.	   cout << cnt << endl;
17.	   return 0;
18. }

假设输入的 n 是正整数，a[i] 都是在 [1,n] 范围内的整数，完成下面的判断题和单选题。

判断题

  1. 循环结束时，a[1] 保存的是输入的 n 个数中的最小值。

    {{ select(27) }}

  • 正确
  • 错误
  1. 循环结束时，a[1]～a[n] 按升序排序 (a[1]≤a[2]≤…≤a[n])。 {{ select(28) }}
  • 正确
  • 错误
  1. 当 n 为 10 时，无论输入的 a[1]～a[n] 值为多少，输出的 cnt 不会大于 19。 {{ select(29) }}
  • 正确
  • 错误
  1. 当 n 为 100 时，无论输入的 a[1]～a[n] 值为多少，输出的 cnt 不会大于 450。 {{ select(30) }}
  • 正确
  • 错误

单选题

  1. 当输入的 n 为 5，a[1]～a[5] 依次为 3,5,2,4,1 时，输出的结果为（ ）。 {{ select(31) }}
  • 1
  • 2
  • 3
  • 4
  1. 当输入的 n 为 5，a[1]～a[5] 依次为 2,3,1,4,5 时，输出的结果为（ ）。 {{ select(32) }}
  • 1
  • 2
  • 3
  • 4

三、完善程序

（单选题，每小题 3 分，共计 30 分）

完善程序(一)

（区间素数个数）给定两个正整数 l 和 r，求区间 [l,r] 内素数的个数。如下代码是⼀个经典的计算过程，请将程序补充完整。 输⼊格式： 第 1 ⾏有两个整数，分别代表询问次数 n 和给定区间的右端点最⼤值 m。接下来 n ⾏，每⾏两个整数 l 和 r，代表⼀次查询。 输出格式： 对于每次查询输出⼀⾏，若 l，r∈[1,m]，则输出区间内素数的个数，否则输出 "Crossing the line"。 输⼊样例：

2 5
1 3
1 6

输出样例：

2
Crossing the line

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
bool is_prime[MAXN];
int sum[MAXN];
void get_sum(int m) {
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i = 2;①; ++i) {
        if (is_prime[i]) {
            for (②; j <= m; j += i)
                ③
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (is_prime[i])
            ④;
        else
            sum[i] = sum[i - 1];
    }
}
int main() {
    int n, m, l, r;
    cin >> n >> m;
    get_sum(m);
    while (n--) {
        cin >> l >> r;
        if (l >= 1 && r <= m)
            cout << ⑤ << endl;
        else
            cout << "Crossing the line" << endl;
    }
    return 0;
}
  1. ① 处应填（ ）。 {{ select(33) }}
  • i<=m
  • i*i<=m
  • i<=n
  • i*i<=n
  1. ② 处应填（ ）。 {{ select(34) }}
  • int j=1
  • int j=2
  • int j=i
  • int j=i*i
  1. ③ 处应填（ ）。 {{ select(35) }}
  • is_prime[j] = true
  • is_prime[i] = true
  • is_prime[j] = false
  • is_prime[i] = false
  1. ④ 处应填（ ）。 {{ select(36) }}
  • sum[i]++
  • sum[i]+=sum[i-1]
  • sum[i]=sum[i-1]
  • sum[i]=sum[i-1]+1
  1. ⑤ 处应填（ ）。 {{ select(37) }}
  • sum[r+1]-sum[l]
  • sum[r+1]-sum[l-1]
  • sum[r]-sum[l-1]
  • sum[r]-sum[l]

完善程序(二)

（合唱队形）NN位同学站成一排，音乐老师要请其中的(N−K)(N-K)位同学出列，使得剩下的KK位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K1, 2, …, K，他们的身高分别为T1,T2,…,TKT_1, T_2, …, T_K，则他们的身高满足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)T_1 < T_2 < … < T_i , T_i > T_{i+1} > … > T_K (1≤i≤K)。

你的任务是，已知所有NN位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入的第一行是一个整数N（2≤N≤100）N（2 ≤ N ≤ 100），表示同学的总数。第二行有nn个整数，用空格分隔，第ii个整数Ti（130≤Ti≤230）T_i（130 ≤ T_i ≤ 230）是第ii位同学的身高（厘米）。

输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

样例

8
186 186 150 200 160 130 197 220

4

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2024;
int n, ans = 0;
int h[MAXN], f[MAXN], g[MAXN];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &h[i]);
    for (int i = 1; i <= n; i++) {
        ①;
        for (int j = 1; j < i; j++)
            if ( ② )
                f[i] = max(f[i], f[j] + 1);
    }
    for (int i = n; i; i--) {
        g[i] = 1;
        for (int j = n; ③; j--)
            if (h[j] < h[i])
                ④;
    }
    for (int i = 1; i <= n; i++)
        ⑤;
    printf("%d\n", n - ans);
    return 0;
}
  1. ① 处应填（ ）。 {{ select(38) }}
  • f[i] = 1
  • f[i] = 0
  • gf[i] = 1
  • g[i] = 0
  1. ② 处应填（ ）。 {{ select(39) }}
  • h[j]<=h
  • h[j]<h[i]
  • h[j]>=h[i]
  • h[j]>h[i]
  1. ③ 处应填（ ）。 {{ select(40) }}
  • j>=i
  • j>=0
  • j>i
  • j>0
  1. ④ 处应填（ ）。 {{ select(41) }}
  • g[i]=max(f[i],f[j]+1)
  • g[i]=max(f[i],g[j]+1)
  • g[i]=max(g[i],f[j]+1)
  • g[i]=max(g[i],g[j]+1)
  1. ⑤ 处应填（ ）。 {{ select(42) }}
  • ans=max(ans,f[i]+g[i]-1)
  • ans=max(f[i],g[i]-1)
  • ans=max(ans,f[i]+g[i])
  • ans=max(g[i],f[i]-1)

Statistics

Related

In following contests:

CSP-J 真题+模拟题

  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. Copyright：
  3. 沪ICP备2023029987号-1
  4. Worker 0, 23ms
  5. Powered by Hydro v4.10.6 Community