CSP-J 2023 试题

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

1. 在C++中，下面哪个关键字用于声明一个变量，其值不能被修改？ {{ select(1) }}

• unsigned
• const
• static
• mutable

2. 八进制数 $12345678_8$ 和 $07654321_8$ 的和为？ {{ select(2) }}

• $22222222_8$
• $21111111_8$
• $22111111_8$
• $22222211_8$

3. 阅读下述代码，请问如何修改 data.value 的值？

union Data {
    int num;
    float value;
    char symbol;
};
union Data data;

{{ select(3) }}

• data.value = 3.14;
• value.data = 3.14;
• data->value = 3.14;
• value->data = 3.14;

4. 假设有一个链表的节点定义如下：

struct Node {
    int data;
    Node* next;
};

现在有一个指向链表头部的指针 Node* head。如果想要在链表中插入一个新的节点，其成员 data 的值为42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？ {{ select(4) }}

• Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
• Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
• Node* newNode = new Node; newNode->data = 42; head->next = newNode;
• Node* newNode = new Node; newNode->data = 42; newNode->next = head;

5. 根节点的高度为1，一棵拥有2023个节点的三叉树高度至少为？ {{ select(5) }}

• 6
• 7
• 8
• 9

6. 小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息。则小明一共有多少种选择时间段的方案？ {{ select(6) }}

• 31
• 18
• 21
• 33

7. 以下关于高精度运算的说法错误的是？ {{ select(7) }}

• 高精度计算主要是用来处理大整数或需要保留多位小数的运算。
• 大整数除以小整数的处理步骤可以是：将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。
• 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。
• 高精度加法运算的关键在于逐位相加并处理进位。

8. 后缀表达式 "623+-382/+*23+" 对应的中缀表达式是？ {{ select(8) }}

• $((6-(2+3))\times(3+8\div2))^2+3$
• $6-2+3\times3+8\div2^2+3$
• $(6-(2+3))\times((3+8\div2)^2)+3$
• $6-((2+3)\times(3+8\div2))^2+3$

9. 数 $101010_2$ 和 $166_8$ 的和为？ {{ select(9) }}

• $10110000_2$
• $236_8$
• $158_{10}$
• $A0_{16}$

10. 假设有一组字符 {a,b,c,d,e,f}，对应的频率分别为 5%、9%、12%、13%、16%、45%。请问以下哪个选项是字符 a,b,c,d,e,f 分别对应的一组哈夫曼编码？ {{ select(10) }}

• 1111, 1110, 101, 100, 110, 0
• 1010, 1001, 1000, 011, 010, 00
• 000, 001, 010, 011, 10, 11
• 1010, 1011, 110, 111, 00, 01

11. 给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么？ {{ select(11) }}

• EDBFGCA
• EDBGCFA
• DEBGFCA
• DBEGFCA

12. 考虑一个有向无环图，该图包含4条有向边：(1,2),(1,3),(2,4)和(3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序？ {{ select(12) }}

• 4,2,3,1
• 1,2,3,4
• 1,2,4,3
• 2,1,3,4

13. 在计算机中，以下哪个选项描述的数据存储容量最小？ {{ select(13) }}

• 字节(byte)
• 比特(bit)
• 字(word)
• 千字节(kilobyte)

14. 一个班级有10个男生和12个女生。如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能的组合？ {{ select(14) }}

• 1420
• 1770
• 1540
• 2200

15. 以下哪个不是操作系统？ {{ select(15) }}

• Linux
• Windows
• Android
• HTML

二、阅读程序（共3大题，判断题每题2分，选择题每题3分，共40分）

程序1

double f(double a, double b, double c){
    double s = (a + b + c) / 2;
    return sqrt(s * (s - a) * (s - b) * (s - c));
}

判断题 16. 当输入为"2 2 2"时，输出为"1.7321"。 {{ select(16) }}

• 正确
• 错误

17. 将第7行中的(s - b)*(s - c)改为(s - c)*(s - b)不会影响程序运行的结果。 {{ select(17) }}

• 正确
• 错误

18. 程序总是输出四位小数。 {{ select(18) }}

• 正确
• 错误

选择题 19. 当输入为"3 4 5"时，输出为？ {{ select(19) }}

• 6.0000
• 12.0000
• 24.0000
• 30.0000

20. 当输入为"5 12 13"时，输出为？ {{ select(20) }}

• 24.0000
• 30.0000
• 60.0000
• 120.0000

程序2

int f(string x, string y){
    int m = x.size(), n = y.size();
    vector<vector<int>> v(m+1, vector<int>(n+1, 0));
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(x[i-1] == y[j-1])
                v[i][j] = v[i-1][j-1] + 1;
            else
                v[i][j] = max(v[i-1][j], v[i][j-1]);
        }
    }
    return v[m][n];
}

判断题 21. f函数的返回值小于等于min(n,m)。 {{ select(21) }}

• 正确
• 错误

22. f函数的返回值等于两个输入字符串的最长公共子串的长度。 {{ select(22) }}

• 正确
• 错误

23. 当输入两个完全相同的字符串时，g函数的返回值总是true。 {{ select(23) }}

• 正确
• 错误

选择题 24. 将第19行中的v[m][n]替换为v[n][m]，那么该程序？ {{ select(24) }}

• 行为不变
• 只会改变输出
• 一定非正常退出
• 可能非正常退出

25. 当输入为"csp-j p-jcs"时，输出为？ {{ select(25) }}

• 0
• 1
• T
• F

26. 当输入为"csppsc spsccp"时，输出为？ {{ select(26) }}

• T
• F
• 0
• 1

程序3

int solve1(int n){ return n * n; }

int solve2(int n){
    int sum = 0;
    for(int i = 1; i <= sqrt(n); i++){
        if(n % i == 0){
            if(n / i == i)
                sum += i * i;
            else
                sum += i * i + (n / i) * (n / i);
        }
    }
    return sum;
}

判断题 27. 如果输入的n为正整数，solve2函数的作用是计算n所有的因子的平方和。 {{ select(27) }}

• 正确
• 错误

28. 第13–14行的作用是避免n的平方根因子进入第16行而被计算两次。 {{ select(28) }}

• 正确
• 错误

29. 如果输入的n为质数，solve2(n)的返回值为$n^2+1$。 {{ select(29) }}

• 正确
• 错误

选择题 30. 如果输入的n为质数p的平方，那么solve2(n)的返回值为？ {{ select(30) }}

• $p^2+p+1$
• $n^2+n+1$
• $n^2+1$
• $p^4+2p^2+1$

31. 当输入为正整数时，第一项减去第二项的差值一定？ {{ select(31) }}

• 大于等于0
• 大于等于0且不一定大于0
• 小于0
• 小于等于0且不一定小于0

32. 当输入为"5"时，输出为？ {{ select(32) }}

• 651625
• 650729
• 651676
• 652625

三、完善程序（每题3分，共30分）

程序1（寻找被移除的元素）

int find_missing(vector<int>& nums){
    int left = 0, right = nums.size() - 1;
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] == mid + 1){
            // 2
        } else {
            // 3
        }
    }
    return // 4
}

33. 1处应填？ {{ select(33) }}

• 1
• nums[0]
• right
• left

34. 2处应填？ {{ select(34) }}

• left = mid + 1
• right = mid – 1
• right = mid
• left = mid

35. 3处应填？ {{ select(35) }}

• left = mid + 1
• right = mid – 1
• right = mid
• left = mid

36. 4处应填？ {{ select(36) }}

• left + nums[0]
• right + nums[0]
• mid + nums[0]
• right + 1

37. 5处应填？ {{ select(37) }}

• nums[0] + n
• nums[0] + n - 1
• nums[0] + n + 1
• nums[n-1]

程序2（编辑距离）

int edit_dist_dp(string str1, string str2){
    int m = str1.length(), n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for(int i = 0; i <= m; i++){
        for(int j = 0; j <= n; j++){
            if(i == 0) dp[i][j] = // 1
            else if(j == 0) dp[i][j] = // 2
            else if(// 3) dp[i][j] = // 4
            else dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], // 5)
        }
    }
    return dp[m][n];
}

38. 1处应填？ {{ select(38) }}

• j
• i
• m
• n

39. 2处应填？ {{ select(39) }}

• j
• i
• m
• n

40. 3处应填？ {{ select(40) }}

• str1[i-1] == str2[j-1]
• str1[i] == str2[j]
• str1[i-1] != str2[j-1]
• str1[i] != str2[j]

41. 4处应填？ {{ select(41) }}

• dp[i-1][j-1] + 1
• dp[i-1][j-1]
• dp[i-1][j]
• dp[i][j-1]

42. 5处应填？ {{ select(42) }}

• dp[i][j] + 1
• dp[i-1][j-1] + 1
• dp[i-1][j-1]
• dp[i][j]