CSP-J 2025初赛模拟卷 9

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

第 1 题 两个十六进制数 (1ACF)16 和 (0451)16 做加法的结果是（ ）。
{{ select(1) }}

• (1F25)16
• (7975)10
• (17455)8
• (1111100100)2

第 2 题 一个“无符号长整型变量”占用（ ）字节。
{{ select(2) }}

• 32
• 4
• 16
• 8

第 3 题 判断字符串 s1 是否为回文串，如果是就输出“yes”，否则输出“no”。以下代码中，正确的实现是（ ）。

int main() {
    string s1, s2;
    cin >> s1;
    s2 = s1;
    reverse(s1.begin(), s1.end());
    if (s1 == s2) cout next = q; q->next = p->next;`  
-  `p->next = &c; q->next = p->next;`  
-  `(*p).next = q; (*q).next = &b;`  
-  `a.next = c; c.next = b;`  

**第 6 题** 以下哪个特性是数组和链表共有的？（ ）  
{{ select(6) }}  
-  动态分配  
-  元素之间的次序关系  
-  存储连续  
-  通过索引访问  

**第 7 题** 下面关于哈夫曼树的描述中，正确的是（ ）。  
{{ select(7) }}  
-  哈夫曼树一定是完全二叉树  
-  哈夫曼树一定是平衡二叉树  
-  哈夫曼树中权值最小的两个结点互为兄弟结点  
-  哈夫曼树中左子结点小于父结点，右子结点大于父结点  

**第 8 题** 已知一棵二叉树有 2025 个结点，则其中至多有（ ）个结点有 2 个子结点。  
{{ select(8) }}  
-  1010  
-  1011  
-  1012  
-  1013  

**第 9 题** 下面的说法中正确的是（ ）。  
{{ select(9) }}  
-  计算机网络按照拓扑结构分为星型、环型、总线型等  
-  互联网的基础是 OSI 七层协议而不是 TCP/IP 协议族  
-  现代计算机网络主要采用电路交换技术  
-  10.10.1.1 是 D 类 IP 地址  

**第 10 题** 下面关于图的说法中正确的是（ ）。  
{{ select(10) }}  
-  所有点数为奇数的连通图，一定可以一笔画成  
-  所有只有两个奇度点（其余均为偶度点）的连通图，一定可以一笔画成  
-  哈密顿图一定是欧拉图，而欧拉图未必是哈密顿图  
-  哈密顿图不一定是欧拉图，而欧拉图一定是哈密顿图  

**第 11 题** （ ）是一种选优搜索法，按选优条件向前搜索以达到目标。当搜索到某一步时，如果发现原先的选择并不优或者达不到目标，就后退一步重新选择。  
{{ select(11) }}  
-  二分算法  
-  动态规划  
-  回溯法  
-  贪心算法  

**第 12 题** 动态规划是将一个问题分解为一系列子问题后来求解，下面（ ）属于动态规划问题。  
{{ select(12) }}  
-  多重背包  
-  排队打水  
-  有序数组找数  
-  全排列  

**第 13 题** 设无向图 G 的邻接矩阵如下图所示，则 G 的顶点数和边数分别为（ ）。  

0 1 1 0 0
1 0 1 1 0
1 1 0 0 1
0 1 0 1 0
0 0 1 0 0

{{ select(13) }}  
-  4, 5  
-  5, 8  
-  4, 10  
-  5, 5  

**第 14 题** 某条道路从东到西有 8 个路灯，巡查员为了维护方便，在每根灯杆上都安装了开关，第 i 个开关能够切换前 i 个灯的状态（开或关），一开始灯全是开的。巡查员通过控制开关一共能得到（ ）种不同灯的开或者关的组合状态。  
{{ select(14) }}  
-  128  
-  256  
-  127  
-  255  

**第 15 题** 某四位正整数 abcd 满足如下条件（a, b, c, d 是非负整数）：abcd = 1^3 + 2^3 + ... + n^3，abcd = (1 + 2 + 3 + ... + n)^2，abcd = (ab + cd)^2，这样的正整数 abcd 共有（ ）个。  
{{ select(15) }}  
-  0  
-  1  
-  2  
-  3  

## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 V，错误填 ×）

### (1)
```cpp
#include 
using namespace std;
const int N = 100 + 5;
int n, c, x, y, len, l[N], r[N], cha[N];
char a[N];
int main() {
    scanf("%d%d%s", &n, &c, a + 1);
    len = n;
    for (int i = 1; i = l[i] + cha[i] && x 
using namespace std;
const int N = 2e5 + 5;
int n, ans, a[N], cnt[20];
int main() {
    scanf("%d", &n);
    for (int i = 1; i 
using namespace std;
const int N = 10005, M = 15;
char c[N];
int d, num[N], dp[N][M][2];
int dfs(int pos, int res, int sta) {
    if (pos == 0)
        return res == 0;
    if (dp[pos][res][sta] != -1)
        return dp[pos][res][sta];
    int ret = 0, maxx = 9;
    if (sta)
        maxx = num[pos];
    for (int i = 0; i 
using namespace std;
const int N = 2e5 + 5;
int n, pre[N], a[N], dp[N][3];
int main() {
    scanf("%d", &n);
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for (int i = 1; i 
using namespace std;
const int N = 3e5 + 5;
int n, k, a[N], p[N][11], ans[N][11];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        ①
    }
    for (int j = 1; j <= k; j++)
        for (int i = 1; i + j <= n; i++)
            p[i][j] = min(p[i][j - 1], a[i + j]);
    for (int j = 1; j <= k; j++)
        for (int i = 1; i + j <= n; i++)
            ②
    for (int i = 1; i <= n; i++)
        ans[i][0] = ③
    for (int j = 1; j <= k; j++) {
        for (int i = 1; i <= n; i++) {
            ans[i][j] = min(ans[i - 1][j] + a[i], ans[i][j - 1]);
            for (int h = 0; ④; h++)
                ans[i][j] = min(ans[i][j], ⑤);
        }
    }
    printf("%d\n", ans[n][k]);
    return 0;
}

38. ①处应填（ ）。
    {{ select(38) }}

• p[i][0] = i
• p[i][0] = a[i]
• p[i][i] = i
• p[i][i] = a[i]

39. ②处应填（ ）。
    {{ select(39) }}

• p[i][j] *= j
• p[i][j] *= (j + 1)
• p[i][j] *= i
• p[i][j] *= (i + 1)

40. ③处应填（ ）。
    {{ select(40) }}

• ans[i - 1][0] + a[i]
• ans[i - k][0] + p[i - k + 1][k]
• ans[i - 1][0] + a[i] * i
• ans[i - k][0] + p[i - k + 1][k] * k

41. ④处应填（ ）。
    {{ select(41) }}

• h < i && h < j
• h < i && h <= j
• h <= i && h < j
• h <= i && h <= j

42. ⑤处应填（ ）。
    {{ select(42) }}

• ans[i - h][j - h] + p[i - h][h]
• ans[i - h][j - h] + p[i - h][h] * h
• ans[i][j - h] + p[i][h]
• ans[i][j - h] + p[i - h][h]