一、单项选择题(每题 2 分,共 30 分)

1. 十进制数 $2024$ 的八进制表示是( )。

{{ select(1) }}

• $3749$
• $3750$
• $3751$
• $3752$

2. 以下关于计算机协会竞赛的描述正确的是( )。

{{ select(2) }}

• NOI 国家集训队每年产生 $4$ 名选手代表中国参加 IOI
• CSP-J/CSP-S 是 $2018$ 年开始举办的
• USACO 晋级白金的选手可以直接参加 NOIP
• ACSL 和 NOIP 都是 CCF 旗下的程序设计赛事

3. 以下哪个可以用作 C++ 程序中的变量名?( )

{{ select(3) }}

• public
• loops
• new
• delete

4. 以下哪个数据结构不属于线性结构?( )

{{ select(4) }}

• 栈
• 数组
• 树
• 链表

5. 以下哪个属于 STL 函数?( )

{{ select(5) }}

• main
• sort
• freopen
• scanf

6. 小明用递归的方法写了一个斐波那契数列的程序,在这里递归函数经常用到的数据结构是( )。

{{ select(6) }}

• 树
• 栈
• 链表
• 队列

7. 堆排序程序运行的时间复杂度是( )。

{{ select(7) }}

• $O(logn)$
• $O(n)$
• $O(n^2)$
• $O(n \log n)$

8. 在下列排序算法中,( )是稳定的排序算法。

{{ select(8) }}

• 归并排序
• 快速排序
• 选择排序
• 拓扑排序

9. 一台 $32$ 位操作系统的计算机运行 C++,下面哪个说法是正确的?( )

{{ select(9) }}

• C++ 语言中的一个 int 类型的变量占 $8$ 字节
• C++ 语言中的一个指针类型的变量占 $4$ 字节
• C++ 语言中的一个 bool 类型的变量占 $2$ 字节
• C++ 语言中的一个 double 类型的变量占 $4$ 字节

10. 设全集 $I=\{a,b,c,d,e,f,g,h\}$ ,集合 $B\cup A=\{a,b,c,d,e,f\}$, $C\cap A=\{c,d,e\}$, $\sim B\cap A=\{a,d\}$ 那么集合 $C\cap B\cap A$ 为( )。

{{ select(10) }}

• $\{c,e\}$
• $\{d,e\}$
• $\{e\}$
• $\{c,d,e\}$

11. 在不大于 $19004$ 的正整数中,与 $19004$ 互质的正整数有( )个。

{{ select(11) }}

• $9500$
• $9498$
• $9497$
• $9499$

12. 假设 P=true,Q=false,R=true,S=true,逻辑运算表达式 $P \land Q \lor R \land S$ 的值是( )。

{{ select(12) }}

• true
• false
• null
• NIL

13. 对于二叉树 T,已知其前序遍历序列为 $1243576$ ,中序遍历序列为 $4215736$ ,则其后序遍历序列为( )。

{{ select(13) }}

• $4$ $2$ $5$ $7$ $6$ $3$ $1$
• $4$ $2$ $7$ $5$ $6$ $3$ $1$
• $4$ $2$ $7$ $5$ $3$ $6$ $1$
• $4$ $7$ $2$ $3$ $5$ $6$ $1$

14. 一个口袋内装有大小相同的 $7$ 个白球和 $2$ 个黑球,从口袋中取出 $3$ 个球,使其中不含黑球,有多少种取法?( )

{{ select(14) }}

• $32$
• $35$
• $24$
• $56$

15. 在下图中,从顶点( )出发存在一条路径可以遍历图中的每条边一次,而且仅遍历一次。

{{ select(15) }}

• B点
• A点
• E点
• C点

二、阅读程序

(程序输入不超过数组或字符串定义的范围;判断题正确填 $\surd$ ,错误填 $x$ ;除特殊说明外,判断题每题 $1.5$ 分,选择题每题 $3$ 分,共计 $40$ 分) (1)

#include<bits/stdc++.h>

using namespace std;

int a[100005];

bool judge(int x)
{
    int i=2;
    if(x==0 || x==1)
        return false;
    while( i <= floor(sqrt(x)) && (x%i != 0) )
        i++;
    if(i > floor(sqrt(x)))
        return true;
    return false;
}

int inverted(int n)
{
    int sum;
    sum = 0;
    while(n > 0)
    {
        sum = sum*10 + n%10;
        n /= 10;
    }
    return sum;
}

int main()
{
    int m,n,k;
    bool flag;
    k = 0;
    flag = false;
    cin >> m >> n;
    for(int i=m; i<=n; i++)
        if( judge(i) && judge(inverted(i)) )
        {
            k++;
            a[k] = i;
            flag = true;
        }
    if(flag)
    {
        for(int i=1; i<k; i++)
            cout << a[i] << ",";
        cout << a[k] << endl;
    }
    else
        cout<< "No" << endl;
    return 0;
}

(1) 将第 $6$ 行中的 i=2 改为 i=1 ,程序的运行结果不会改变。 ( )

{{ select(16) }}

• 正确
• 错误

(2) 将第 $9$ 行中的 x%i != 0 去掉,程序的运行结果不会改变。 ( )

{{ select(17) }}

• 正确
• 错误

(3) 将第 $18$ 行删除,程序的运行结果不会改变。 ( )

{{ select(18) }}

• 正确
• 错误

(4) 将第 $31$ 行删除,程序的运行结果不会改变。 ( )

{{ select(19) }}

• 正确
• 错误

(5) 若输入数据为 $1949$ $2024$ ,则输出为( )。

{{ select(20) }}

• $1949$,$1987$
• $1949$,$1979$
• $1951$,$1979$
• $1951$,$1987$

(6) 若输出为 NO ,则输入可能为( )。

{{ select(21) }}

• $168$ $180$
• $785$ $792$
• $999$ $1020$
• $2024$ $2050$

(2)

#include<bits/stdc++.h>

using namespace std;

int main()
{
    string s;
    int len,pos,i,j,sum;
    sum = 0;
    getline(cin,s);
    len = s.size();
    s[len] = ' ';
    for(i=0; i<=len; i++)
    {
        if(s[i] != ' ')
            sum++;
        else
        {
            pos = i;
            for(j=1; j<=sum; j++)
                cout << s[--pos];
            sum = 0;
            if(i != len)
                cout<<" ";
        }
    }
    cout<<endl;
    return 0;
}

(1) 将第 $7$ 行删除,程序的运行结果不会改变。 ( )

{{ select(22) }}

• 正确
• 错误

(2) 将第 $9$ 行中的 s.size() 改为 s.length() ,程序的运行结果不会改变。( )

{{ select(23) }}

• 正确
• 错误

(3) 将第 $10$ 行 s[len] = ' ' 改为 s[len] = 32 ,程序的运行结果不会改变。( )

{{ select(24) }}

• 正确
• 错误

(4) 将第 $20$ 行删除,程序的运行结果不会改变。 ( )

{{ select(25) }}

• 正确
• 错误

(5) 若输入CCF CSP,则输出为( )。

{{ select(26) }}

• FCC PSC
• CCF CSP
• PSC FCC
• FCC CSP

(6) 将第 $19$ 行中的 --pos 改为 pos--,输入CCF CSP,则输出为( )。

{{ select(27) }}

• PS FC
• CF SP
• FC PS
• CC SC

(3)

#include<bits/stdc++.h>
#define N 1000010

using namespace std;

int x, tot, a[N];

void calculate(int n, int step)
{
    int ans;
    ans = 1;
    for(int i=1; i<=step-1; i++)
        ans *= a[i];
    if(ans > x)
        return;
    if(ans == x)
    {
        tot++;
        return;
    }
    for(int i=a[step-1]; i<=x; i++)
        if(n%i == 0)
        {
            n /= i;
            a[step] = i;
            calculate(n, step+1);
            n *= i;
        }
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        tot = 0;
        cin >> x;
        a[0] = 2;
        calculate(x, 1);
        cout << tot << endl;
    }
    return 0;
}

(1) 若将第 $2$ 行替换为 const int N=1000010 ;程序的运行结果不会改变。( )

{{ select(28) }}

• 正确
• 错误

(2) 若将第 $8$ 行删除,程序的运行结果不会改变。 ( )

{{ select(29) }}

• 正确
• 错误

(3) 若将第 $15$ 行中的 tot++ 替换为 ++tot ,程序的运行结果不会改变。 ( )

{{ select(30) }}

• 正确
• 错误

(4) 将第 $21$ 行和第 $22$ 行交换,程序的运行结果不会改变。 ( )

{{ select(31) }}

• 正确
• 错误

(5) 本程序中的算法用到了( )的思想。

{{ select(32) }}

• 贪心
• 搜索回溯
• 二分
• 动态规划

(6) 若输入 $2$ $24$ $36$ ,那么输出结果是( )。

{{ select(33) }}

• $7$ $9$
• $7$ $8$
• $8$ $9$
• $8$ $8$

(7) ($4$ 分)若输入 $2$ $96$ $2024$ ,那么输出结果是( )。

{{ select(34) }}

• $18$ $20$
• $18$ $21$
• $19$ $20$
• $19$ $21$

三、完善程序

单项选择题,每题 $3$ 分,共 $30$ 分。

(1)给定两个正整数 $l$ 和 $r$ ,求区间 $[1,r]$ 内素数的个数。如下代码是一个经典的计算过程,请将程序补充完整。

输入格式: 第 $1$ 行有两个整数,分别代表询问次数 $n$ 和给定区间的右端点最大值 $m$ 。接下来 $n$ 行,每行两个整数 $l$ 和 $r$ ,代表一次查询。

输出格式: 对于每次查询输出一行,若 $l,r\in[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(35) }}

• i <= m
• i * i <= m
• i <= n
• i * i <= n

(2) ② 处应填( )

{{ select(36) }}

• int j=1
• int j=2
• int j=i
• int j=i * i

(3) ③ 处应填( )

{{ select(37) }}

• is_prime[j] = true
• is_prime[i] = true
• is_prime[j] = false
• is_prime[i] = false

(4) ④ 处应填( )

{{ select(38) }}

• sum[i]++
• sum[i] += sum[i-1]
• sum[i] = sum[i-1]
• sum[i] = sum[i-1] +1

(5) ⑤ 处应填( )

{{ select(39) }}

• sum[r+1] - sum[l]
• sum[r+1] - sum[l-1]
• sum[r] - sum[l-1]
• sum[r] - sum[l]

(2) $N$ 位同学站成一排,音乐老师要请其中的 $(N-K)$ 位同学出列,使得剩下的 $K$ 位同学排成合唱队形。合唱队形是指这样的一种队形:设 $K$ 位同学从左到右依次编号为 $1,2,\ldots,K$ ,他们的身高分别为 $T_1,T_2,\ldots,T_K$ ,则他们的身高满足 $T_1<\cdots<T_i>T_{i+1}>\cdots>T_K$（$1\leqslant i\leqslant K$）。你的任务是,已知所有 $N$ 位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。

输入格式:

输入的第 $1$ 行是一个整数 $N$ ,表示同学的总数。第 $2$ 行有 $N$ 个整数,用空格分隔,第 $i$ 个整数 $T_i$ 是第 $i$ 位同学的身高(厘米)。

输出格式:

输出包括一行,这一行只包含一个整数,就是最少需要几位同学出列。数据范围: $2\leqslant N\leqslant 100$ , $130\leqslant T_i\leqslant 230$。

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(40) }}

• f[i] = 1
• f[i] = 0
• g[i] = 1
• g[i] = 0

(2) ② 处应填( )

{{ select(41) }}

• h[j] <= h[i]
• h[j] < h[i]
• h[j] >= h[i]
• h[j] > h[i]

(3) ③ 处应填( )

{{ select(42) }}

• j >= i
• j >= 0
• j > i
• j > 0

(4) ④ 处应填( )

{{ select(43) }}

• 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)

(5) ⑤ 处应填( )

{{ select(44) }}

• 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)