CSP-J 初赛模拟卷 07

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

1. 八位八进制数 $(12345670)_8$ 和 $(07654321)_8$ 的和为 ( )

{{ select(1) }}

• $(22222221)_8$
• $(21111111)_8$
• $(22111111)_8$
• $(22222211)_8$

2. 哈夫曼编码中，下列哪个说法是错误的？( )

{{ select(2) }}

• 哈夫曼编码是一种前缀编码
• 哈夫曼编码可以实现无损压缩
• 哈夫曼编码的编码长度是固定的
• 哈夫曼编码是根据字符出现的频率来构建的

3. 在递归算法中，下列哪个操作可能导致栈溢出 ( )

{{ select(3) }}

• 过深的递归调用
• 过多的全局变量
• 大量的内存分配
• 频繁的 IO 操作

4. 一个袋子里有红、黄、蓝三种颜色的球各十个，取出多少个球才能保证取到的至少有 5 个颜色相同的球 ( )

{{ select(4) }}

• 10
• 11
• 12
• 13

5. 将 5 个整数数字 -2、-1、1、2、3 划分为若干个集合，要求每个集合内的数字之和均大于 0，则存在 ( ) 种划分方法。(空集合的情况不考虑)

{{ select(5) }}

• 7
• 5
• 6
• 8

6. 假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为 ( )

{{ select(6) }}

• ABCDEFGHIJ
• ABDEGHJCFI
• ABDEGJHCFI
• ABDEGHJFIC

7. 高度为 n 的均衡的二叉树是指：如果去掉最后一层叶结点及相应的树枝，它应该是高度为 n-1 的满二叉树。在这里，树高等于结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有 2381 个结点，则该树的树高为 ( )

{{ select(7) }}

• 10
• 11
• 12
• 13

8. 数字 $(4961)_{12}$ 在( )进制下是回文数字。回文数字即为正着读反着读都一样的数字。

{{ select(8) }}

• 7
• 8
• 9
• 10

9. vector 所不具备的特性是( )

{{ select(9) }}

• 所需内存大小等于存储元素个数乘以对应数据类型内存空间
• 随机访问任一元素
• 不必事先估计存储空间
• 可在 O(1) 时间内计算存储元素个数

10. 假定 int a=2，b=5，c=7; 以下关系表达式中，运算结果和其他项不相同的是( )

{{ select(10) }}

• b >= a*a
• (b > a) == (c > b)
• b % a > c % a
• a + b >= c

11. 下列说法正确的是( )

{{ select(11) }}

• C++ 是一种解释性语言
• 编译通常指将高级语言源代码转译为汇编代码的过程。
• 结构体类型的成员变量不可以包含string数组。
• 多维数组的数组名也是一个指针类型的常量。

12. 在单链表中删除数据元素为"AAAABB"的节点，保证包含"AAAABB"，单链表的头结点是 head，指针域为 next，数据域为 value 需要使用指令( )

{{ select(12) }}

• node *p = head;
  while (p->value != "AAAABB")    p = p->next;
  p = p->next->next;
  

• node *p = head;
  while (p->next->value != "AAAABB")    p = p->next;
  p = p->next->next;
  

• node *p = head;
  while (p->value != "AAAABB")    p = p->next;
  p->next = p->next->next;
  

• node *p = head;
  while (p->next->value != "AAAABB")    p = p->next;
  p->next = p->next->next;
  

13. 将数字 1，2，3，4，5 的全排列按字典序排序，则排列 3，1，2，4，5 排在第 ( ) 位。

{{ select(13) }}

• 48
• 49
• 50
• 51

14. 32位整数 -10 的反码为( )

{{ select(14) }}

• 1000 0000 0000 0000 0000 0000 0000 1010
• 0000 0000 0000 0000 0000 0000 0000 1010
• 0111 1111 1111 1111 1111 1111 1111 0101
• 1111 1111 1111 1111 1111 1111 1111 0101

15. 将满二叉树按后序遍历从 1 开始编号，若编号 15 的节点存在父节点，则编号 15 的节点的父节点编号为 ( )

{{ select(15) }}

• 16
• 30
• 31
• 树的高度未知，无法确认

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

阅读程序第一题（12分）

01 #include <iostream>
02 using namespace std;
03 const int N = 100010;
04 int n, x;
05 int L[N], R[N], a[N];
06 int main() {
07     cin >> n;
08     for (int i = 1; i <= n; ++i) {
09         cin >> x;
10         a[x] = i;
11     }
12     for (int i = 1; i <= n; ++i) {
13         R[i] = i + 1;
14         L[i] = i - 1;
15     }
16     for (int i = 1; i <= n; ++i) {
17         L[R[a[i]]] = L[a[i]];
18         R[L[a[i]]] = R[a[i]];
19     }
20     for (int i = 1; i <= n; ++i) {
21         cout << R[i] << " ";
22     }
23     cout << endl;
24     return 0;
25 }

数据范围：$1≤ n ≤ 10^5 ,1≤ x ≤ n$。

判断题

16. 将程序中 L 字符均替换为 R 字符,程序执行结果一定不变。( )

{{ select(16) }}

• 正确
• 错误

17. 若输入 $x$ 的值为 $1\sim n$ 的全排列，则输出数组也是 $1 \sim n$ 的全排列。( )

{{ select(17) }}

• 正确
• 错误

18. 若输入 x 的值不合法，均大于 n 且小于 N , 则程序输出为等差数列。( )

{{ select(18) }}

• 正确
• 错误

19. 存在合法输入使得输出值均为 n + 1。( )

{{ select(19) }}

• 正确
• 错误

单选题

20. 若程序输入为5 1 2 3 4 5，则程序输出为( )

{{ select(20) }}

• 2 3 4 5 6
• 3 4 5 6 6
• 0 0 0 0 0
• 6 6 6 6 6

21. 将第 17 行与 18 行代码互换位置，若程序输入为 5 1 2 3 4 5，则程序输出为( )

{{ select(21) }}

• 2 3 4 5 6
• 3 4 5 6 6
• 0 0 0 0 0
• 6 6 6 6 6

阅读程序第二题（12分）

01 #include<iostream>
02 using namespace std;
03 const int maxn = 110;
04 int a[maxn],ans=0;
05 int main() {
06     int n;
07     cin >> n;
08     for(int i = 0; i < n; i++) cin >> a[i];
09     while(true) {
10         bool flag = true;
11         for(int i = 1; i < n; i++) {
12             if(a[0] != a[i])
13                 flag = false;
14         }
15         if(flag) break;         
16         for(int i = 0; i < n; i++){
17             a[i] = a[i] / 2;
18         }
19         int temp = a[n - 1];
20         for(int i = n - 1; i > 0; i--)
21             a[i] += a[i - 1];
22         a[0] += temp;
23         for(int i = 0; i < n; i++){
24             if(a[i] & 1 != 0){
25                 a[i]++;
26                 ans++;
27             }
28         } 
29     }
30     cout << ans << endl;
31     return 0;
32 }

限定题目数据 $1≤ n ≤ 100 ,1≤ a_i ≤ 1000$。

22. 当且仅当输入 a 数组的值均为偶数或均相等时，程序输出值可能为 0。( )

{{ select(22) }}

• 正确
• 错误

23. 程序执行结束时，a 数组所有元素的和大于等于输入时 a 数组的和。( )

{{ select(23) }}

• 正确
• 错误

24. 将程序第 10 行 bool flag=true 搬运到第 9 行之前,对程序执行结果没有影响。( )

{{ select(24) }}

• 正确
• 错误

单选题

25. 当程序输入为 2 50 1000 时,程序输出为( )

{{ select(25) }}

• 0
• 2
• 4
• 1

26. 程序输出值一定小于等于( )

{{ select(26) }}

• $n$
• $n^2$
• $n!$
• 以上选项都不对

27. 当程序输入为 3 1 5 10 时，while 循环执行次数为( )

{{ select(27) }}

• 5
• 6
• 7
• 8

阅读程序第三题

01 #include<iostream>
02 #include<cstring>
03 using namespace std;
04 int indexof(char str1[],char str2[]){
05     int flag = -1;
06     int len1 = strlen(str1);
07     int len2 = strlen(str2);
08     for(int i = 0;i < len1; i++){
09         int pos = i;
10         for(int j = 0;j < len2; j++){
11             if(pos >= len1) break;
12             if( str1[pos++] != str2[j]){
13                 break;
14             }else{
15                 if(j == len2-1)
16                     flag = i;
17             }
18         }
19     }
20     return flag;
21 } 
22 char str1[1005];
23 char str2[1005];
24 int main(){
25     cin >> str1 >> str2;
26     cout << indexof(str1,str2) << endl;
27     return 0;
28 }

判断题

28. 如果 str2 的长度大于等于 str1 输出一定为 -1 ( )

{{ select(28) }}

• 正确
• 错误

29. 函数 indexof 的功能为返回在字符串 str1 中查找字符串 str2 第一次出现的位置,若 str1 不包含 str2 ,则返回 -1。( )

{{ select(29) }}

• 正确
• 错误

30. 程序输入到字符数组 str1 的字符中一定不含空格。( )

{{ select(30) }}

• 正确
• 错误

31. 当输入 str1 与 str2 的字符均包含字符 'a' 时，程序输出一定为非负数字。( )

{{ select(31) }}

• 正确
• 错误

单选题

32. 将程序中 pos++ 替换为( )，对程序执行没有任何影响

{{ select(32) }}

• ++pos
• pos
• pos+=1
• 以上都不对

33. 程序输入为 abcdeabcd cde 时,程序输出为( )。

{{ select(33) }}

• -1
• 1
• 2
• 7

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

1.(最大取余) 共 $q$ 次询问，每次计算并输出 $\text{max(i\%a + i\%b)}$，保证 $(l≤i≤r)$ $\max$ 表示计算最大值。例如当 $a=3, b=5,l=1,r=10;$ 则 $1 \% 3 + 1 \% 5 = 2，2 \% 3 + 2 \% 5 = 4 ，3 \% 3 + 3 \% 5 = 3， ... ，10 \% 3 + 10\% 5 = 1；$若其中的最大值为 $5$，则输出 $5$。输入保证不存在计算越界，完善如下程序。

#include <bits/stdc++.h>
using namespace std;
int a,b,q,l,r,t;
int gcd(int x,int y){ // 辗转相除法
    if(x % y == 0) return ①;
    return ②;
}

bool check() {
    int x = (l + 1 + ③) / t;
    int y = (r + 1) / t;
    return x <= y;
}
int calc(int x) {
    return x % a + x % b;
}
int main() {
    cin >> a >> b;
    t = ④;
    cin >> q;
    while(q--) {
        cin >> l >> r;
        int ans = 0;
        if(check()) {
            cout << a + b - 2 << endl;
            continue;
        }
        ans = ⑤;
        for(int i = r / a * a - 1; i >= l; i -= a)
            ans = max(ans,calc(i));
        for(int i = r / b * b - 1; i >= l; i -= b)
            ans = max(ans,calc(i));
        cout << ans << endl;
    }
    return 0;
}

34. ①处应填（ ）

{{ select(34) }}

• 0
• x
• y
• 1

35. ②处应填（ ）

{{ select(35) }}

• gcd(y,x % y)
• gcd(x % y,x)
• gcd(x % y,y)
• gcd(y % x,x)

36. ③处应填（ ）

{{ select(36) }}

• t - 1
• -1
• t
• r

37. ④处应填（ ）

{{ select(37) }}

• gcd(a,b)
• a*b/gcd(a,b)
• a*gcd(a,b)
• gcd(a*b,a/b)

38. ⑤处应填（ ）

{{ select(38) }}

• 0
• 1
• calc(r)
• calc(l)

2.题目描述: 给定一个 01 字符串 $s$ ,可以对字符串 $s$ 进行任意次如下两种类型的操作：

操作 1：将连续的一段字符 '1' 全都变成字符 '0' 进行一次该操作的花费为 $a$；

操作 2：将恰好一个字符 '0' 修改为字符 '1' 进行一次该操作的花费为 $b$。

你希望使用最小的总花费使字符串 $s$ 中的每个字符都变为 '0'。

求：使字符串 $s$ 中的每个字符都变为 '0' 所需的最小总花费？

例如给定字符串 01101110，操作 1 花费 $a=5$，操作 2 花费 $b=1$，最小花费应为 6。

(将第 4 个字符 0 先修改为 1，再将连续的 1 转换为 0。)

输入约定：输入保证不全为 0 或 1。

#include<bits/stdc++.h>
using namespace std;
long long t,g[100005];
int main(){
    cin >> t;
    while(t--){
        memset(g, 0 ,sizeof(g)); 
        int a,b;
        string s;
        cin >> a >> b >> s;
        long long gap = 0,nowg = 0,cnt = 0,tot = 0,len = s.size();
        s[len] = '0';
        for(int i = 0 ;i < ①;i++)
            if(s[i] == '1' && s[i + 1] == '0')    
                gap++; 
        if(s[len - 1] == '0') ②;
        for(int i = 0; i < len-1;i++){
            if(s[i] == '1' && s[i + 1] == '0')  nowg++;
            else if(nowg != 0 && s[i] == '0' && s[i + 1] != '1')    cnt++;
            else if(③){ 
                cnt++;
                g[nowg] = cnt;
                cnt = 0;
            }
        }
        if(④){ // 包含全部符合条件的情况
            cout << a << endl;
            continue;
        }
        for(int i = 1;i <= gap;i++){
            if(2 * a <= a + g[i] * b && i == 1)    tot += 2 * a;
            else if(2 * a <= a + g[i] * b && i != 1)    tot += a;
            else if(i != 1) tot += g[i] * b;
            else tot += ⑤;
        }
        cout << tot << endl;
    }
    return 0;
}

39. ①处应填写（ ）

{{ select(39) }}

• len
• len - 1
• a
• b

40. ②处应填写（ ）

{{ select(40) }}

• gap -= 1
• tot += b
• tot -= b
• g[nowg] -= 1

41. ③处应填写（ ）

{{ select(41) }}

• s[i] == '0'
• s[i] == '1'
• s[i + 1] == '0'
• s[i] == '0' && s[i + 1] == '1'

42. ④处应填写（ ）

{{ select(42) }}

• gap == 0
• cnt == 0
• cnt = len -2
• nowg = 0

43. ⑤处应填写（ ）

{{ select(43) }}

• a + g[i] * b
• g[i] * a
• a
• 2 * b