CSP-J初赛模拟题

（C++语言 满分：100分 考试时间：120分钟）

一、单项选择题（共 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分）

#include <iostream>
using namespace std;
const int N = 100010;
int n, x;
int L[N], R[N], a[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        a[x] = i;
    }
    for (int i = 1; i <= n; ++i) {
        R[i] = i + 1;
        L[i] = i - 1;
    }
    for (int i = 1; i <= n; ++i) {
        L[R[a[i]]] = L[a[i]];
        R[L[a[i]]] = R[a[i]];
    }
    for (int i = 1; i <= n; ++i) {
        cout << R[i] << " ";
    }
    cout << endl;
    return 0;
}

1$\le$ n $\le$ 100000 ,1$\le$ x $\le$ 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分）

#include<iostream>
using namespace std;
const int maxn = 110;
int a[maxn],ans=0;
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    while(true) {
        bool flag = true;
        for(int i = 1; i < n; i++) {
            if(a[0] != a[i])
                flag = false;
        }
        if(flag) break;         
        for(int i = 0; i < n; i++){
            a[i] = a[i] / 2;
        }
        int temp = a[n - 1];
        for(int i = n - 1; i > 0; i--)
            a[i] += a[i - 1];
        a[0] += temp;
        for(int i = 0; i < n; i++){
            if(a[i] & 1 != 0){
                a[i]++;
                ans++;
            }
        } 
    }
    cout << ans << endl;
    return 0;
}

限定题目数据 1$\le$ n $\le$ 100 ,1$\le$ a[i] $\le$ 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

阅读程序第三题

#include<iostream>
#include<cstring>
using namespace std;
int indexof(char str1[],char str2[]){
    int flag = -1;
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    for(int i = 0;i < len1; i++){
        int pos = i;
        for(int j = 0;j < len2; j++){
            if(pos >= len1) break;
            if( str1[pos++] != str2[j]){
                break;
            }else{
                if(j == len2-1)
                    flag = i;
            }
        }
    }
    return flag;
} 
char str1[1005];
char str2[1005];
int main(){
    cin >> str1 >> str2;
    cout << indexof(str1,str2) << endl;
    return 0;
}

判断题

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$次询问，每次计算并输出$max$(i%a + i%b) (l $\le$i$\le$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();
        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