珅泽教育CSP-J第一轮模拟考第二十八套

本卷共 43 题，满分 100 分。

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

第 1 题

以下哪个贡献属于艾伦·图灵？（ ）

{{ select(1) }}

• 发明计算机
• 发明编程语言
• 提出图灵测试
• 发明互联网

第 2 题

一张分辨率为 $2000\times1000$ 像素的 16 位真彩色图像，约需要多大的存储空间？（ ）

{{ select(2) }}

• 4 KB
• 4 MB
• 8 KB
• 8 MB

第 3 题

-100 的 8 位二进制补码形式是（ ）。

{{ select(3) }}

• 1000 1100
• 1001 1011
• 1110 0100
• 1001 1100

第 4 题

设 A、B、C、D 分别代表四进制下互不相同的四个数字。若 $CDBA+DCCD=AAAB$，则 $CDB+DBA$ 的十进制结果是（ ）。

{{ select(4) }}

• 55
• 53
• 52
• 51

第 5 题

以下不能用来交换整数 a 和 b 的值的是（ ）。

{{ select(5) }}

• tmp=a; a=b; b=tmp;
• a=a+b; b=a-b; a=a-b;
• a=a^b; b=a^b; a=a^b;
• a=a-b; b=a+b; a=a+b;

第 6 题

下列哪个循环语句可以确保循环体至少执行一次？（ ）

{{ select(6) }}

• while
• do-while
• for
• if

第 7 题

下面代码的输出是（ ）。

#include <iostream>
#include <string>
using namespace std;
int main() {
    string str = "Hello,World!";
    string sub = str.substr(2, 5);
    for (int i = 0; i < sub.length(); i++) {
        cout << sub[i];
    }
    return 0;
}

{{ select(7) }}

• llo,W
• ello,
• ello
• 编译错误

第 8 题

下面程序的输出是（ ）。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a[] = {100, 200, 300, 400, 500};
    int *p = a;
    int pos = -1;
    while (p <= &a[3]) {
        printf("%d ", a[++pos]);
        p += 2;
    }
    return 0;
}

{{ select(8) }}

• 100 300
• 100 200
• 100 200 300 400
• 300 400

第 9 题

有如下递归函数，调用 solve(6,7) 的结果为（ ）。

long long solve(long long a, long long b) {
    if (b == 0) return 1;
    if (b == 1) return a;
    if (b % 2 == 0)
        return solve(a, b / 2) * solve(a, b / 2);
    return a * solve(a, b / 2) * solve(a, b / 2);
}

{{ select(9) }}

• 46656
• 117649
• 279936
• 326592

第 10 题

用冒泡排序将序列 3,5,2,11,7,8,9,4 升序排列，需要执行（ ）次交换。

{{ select(10) }}

• 9
• 10
• 11
• 12

第 11 题

元素 R1、R2、R3、R4、R5 的入栈顺序为 R3、R1、R4、R2、R5。若第一个出栈的是 R4，则最后一个出栈的不可能是（ ）。

{{ select(11) }}

• R1
• R2
• R3
• R5

第 12 题

用权值 {3,4,6,12,15,17,33,49,60} 构建哈夫曼树（每次合并时较小权值为左孩子，左边编码为 0），哈夫曼编码 1001 对应的结点权值为（ ）。

{{ select(12) }}

• 33
• 25
• 13
• 7

第 13 题

深度优先搜索使用的数据结构是（ ）。

{{ select(13) }}

• 队列
• 栈
• 链表
• 集合

第 14 题

五个不同元素 $a_i(i=1,2,3,4,5)$ 排成一排，规定 $a_1$ 不排第一、$a_2$ 不排第二，共有多少种排法？

{{ select(14) }}

• 64
• 72
• 78
• 84

第 15 题

有一个 $n$ 行 $m$ 列的网格，每格权值为非负整数 a[i][j]。从右上角 $(1,m)$ 走到左下角 $(n,1)$，只能向左或向下，求最小路径权值和的递推式是（ ）。

{{ select(15) }}

• f(i,j)=min(f(i-1,j),f(i,j-1))+a[i][j]
• f(i,j)=max(f(i-1,j),f(i,j-1))+a[i][j]
• f(i,j)=min(f(i-1,j),f(i,j+1))+a[i][j]
• f(i,j)=max(f(i-1,j),f(i,j+1))+a[i][j]

二、阅读程序（判断题请选择“正确”或“错误”，共 18 题、40 分）

阅读程序（1）

输入的 num[i] 均为正整数。

#include <iostream>
using namespace std;

int num[10000];

int g(int a) {
    int ans = 0, m = 0;
    while(a){
        if((a & 1) == 0)
            ans |= 1 << m;
        m++;
        a >>= 1;
    }
    return ans;
}

int main() {
    int n, res = 0;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> num[i];
    for(int i = 0; i < n; i++) num[i] = g(num[i]);
    for(int i = 0; i < 31; i++) {
        int k = 0;
        for (int j = 0; j < n; j++) {
            if ((num[j] >> i) & 1 == 1) k++;
        }
        res += k * (n - k);
    }
    cout << res;
    return 0;
}

第 16 题

若把程序第 23 行移到第 22 行循环之外，程序结果不变。（ ）

{{ select(16) }}

• 正确
• 错误

第 17 题

程序第 23 至 26 行中，k 计算的是数组 num 中倒数第 i 位（i=0 表示个位）为 1 的元素数量。（ ）

{{ select(17) }}

• 正确
• 错误

第 18 题

程序执行完第 21 行后，数组内的元素都会变小。（ ）

{{ select(18) }}

• 正确
• 错误

第 19 题

当输入的 n=100 时，输出的最大值为 $50\times50\times31$。（ ）

{{ select(19) }}

• 正确
• 错误

第 20 题

若输入如下，输出是（ ）。

4
8 6 4 3

{{ select(20) }}

• 14
• 12
• 10
• 0

第 21 题

若输入如下，输出是（ ）。

16
1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535

{{ select(21) }}

• 680
• 0
• 637
• 706

二、阅读程序（判断题请选择“正确”或“错误”，共 18 题、40 分）

阅读程序（2）

输入满足 $2\le n\le13$。原卷第 24 题的“第 1010 行”是排版重叠，实际指程序第 10 行。

#include <bits/stdc++.h>
using namespace std;
int n, a[15], c[15];
void dfs(int x) {
    if (x == n + 1) {
        for (int i = 1; i <= n; i++) printf("%d ", a[i]);
        printf("\n");
        return;
    }
    for (int i = x; i >= 1; i--) {
        c[x]++;
        dfs(x + 1);
        if (i > 1) swap(a[i], a[i - 1]);
    }
    for (int i = 1; i < x; i++) swap(a[i], a[i + 1]);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) a[i] = i;
    dfs(1);
    printf("%d", c[n]);
    return 0;
}

第 22 题

程序输出的每一行都不相同。（ ）

{{ select(22) }}

• 正确
• 错误

第 23 题

程序输出的最后一行，其数字一定等于 $n!$。（ ）

{{ select(23) }}

• 正确
• 错误

第 24 题

若把程序第 10 行中的 i >= 1 改为 i > 1，程序一定只输出一行。（ ）

{{ select(24) }}

• 正确
• 错误

第 25 题

输入 4 时，输出的第 8 行是（ ）。

{{ select(25) }}

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

第 26 题

输入 5 时，输出的第 115 行是（ ）。

{{ select(26) }}

• 5 3 2 4 1
• 5 3 4 2 1
• 5 4 2 3 1
• 5 2 4 3 1

第 27 题

输入 6 时，输出的第 365 行是（ ）。

{{ select(27) }}

• 2 6 1 3 4 5
• 3 4 6 1 2 5
• 3 1 6 5 2 4
• 2 1 4 3 5 6

二、阅读程序（判断题请选择“正确”或“错误”，共 18 题、40 分）

阅读程序（3）

输入保证 $a>0$。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
long long k[N];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &k[i]);
    }
    sort(k, k + n);
    while (m--) {
        long long a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);
        if (c <= 0) {
            printf("NO\n");
            continue;
        }
        int pos1 = lower_bound(k, k + n, b) - k;
        int pos2 = pos1;
        if (pos1 != 0) {
            pos2 = pos1 - 1;
        }
        if (pos1 != n && (b - k[pos1]) * (b - k[pos1]) < 4 * a * c) {
            printf("YES\n%lld\n", k[pos1]);
        } else if (pos2 != n && (b - k[pos2]) * (b - k[pos2]) < 4 * a * c) {
            printf("YES\n%lld\n", k[pos2]);
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

第 28 题

删除第 13 行 sort(k,k+n) 后，程序运行结果不变。（ ）

{{ select(28) }}

• 正确
• 错误

第 29 题

把第 17 行 if(c<=0) 中的 <= 攆为 <，程序运行结果不变。（ ）

{{ select(29) }}

• 正确
• 错误

第 30 题

把第 21 行的 lower_bound(k,k+n,b)-k 改为 upper_bound(k,k+n,b)-k-1，程序运行结果不变。（ ）

{{ select(30) }}

• 正确
• 错误

第 31 题

输入如下，输出结果是（ ）。

1 2
1
1 -1 2
1 -1 3

{{ select(31) }}

• YES\n1\nYES\n1
• NO\nNO
• YES\n2\nYES\n2
• NO\nYES\n1

第 32 题

输入如下，输出结果是（ ）。

1 1
100000000
100000000 100000000 100000000

{{ select(32) }}

• YES\n100000000
• NO
• YES\n1
• YES\n10

第 33 题

该算法的时间复杂度是（ ）。

{{ select(33) }}

• $O((m+n)\log n)$
• $O(m\log n)$
• $O(n\log n)$
• $O(mn)$

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

完善程序（1）：重排为 2 的幂

对于输入的正整数重新排列，判断是否存在一个没有前导零的重排结果是 2 的幂。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
bool flag;
vector<int> vis;
string nums;
bool checkPower(int n) {
    return (n & (n - 1)) == ___(1)___;
}
void dfs(int x, int ans) {
    if (___(2)___) {
        flag = checkPower(ans);
        return;
    }
    for (int i = 0; i < nums.length(); i++) {
        if ((ans == 0 && nums[i] == '0') || vis[i] || (i > 0 && !vis[i - 1] && ___(3)___)) {
            continue;
        }
        vis[i] = 1;
        dfs(x + 1, ___(4)___);
        if (flag) return;
        vis[i] = 0;
    }
}
int main() {
    cin >> nums;
    ___(5)___;
    vis.resize(nums.length());
    dfs(0, 0);
    cout << (flag ? "yes" : "no");
    return 0;
}

第 34 题

①处应填（ ）。

{{ select(34) }}

• 0
• -1
• n
• n-1

第 35 题

②处应填（ ）。

{{ select(35) }}

• ans == nums.length()+1
• x == nums.size()+1
• ans == nums.length()
• x == nums.size()

第 36 题

③处应填（ ）。

{{ select(36) }}

• nums[i] == nums[i+1]
• nums[i] == nums[i-1]
• nums[i-1] == nums[i+1]
• nums[i] == nums[x-1]

第 37 题

④处应填（ ）。

{{ select(37) }}

• ans*10+nums[i]
• ans*10+nums[i]-'0'
• (nums[i]-'0')*10+ans
• ans*10+nums[i-1]-'0'

第 38 题

⑤处应填（ ）。

{{ select(38) }}

• sort(nums,nums+nums.length())
• sort(nums.begin()+1,nums.end())
• sort(nums.begin(),nums.begin()+nums.length())
• sort(nums+1,nums+nums.length()+1)

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

完善程序（2）：进制转换

将 $p$ 进制数 $n$ 转换为 $q$ 进制，$p,q\in[2,36]$，用大写字母 A 至 Z 表示 10 至 35。

#include <bits/stdc++.h>
using namespace std;
int p, q, a[1005], len = 1;
string n;
int main() {
    cin >> p >> n >> q;
    for (int i = 0; i < n.size(); i++) {
        for (int j = 0; j < len; j++) ___(1)___;
        if (n[i] >= '0' && n[i] <= '9') a[0] += n[i] - '0';
        else a[0] += n[i] - 'A' + 10;
        for (int j = 0; j < len; j++) {
            ___(2)___;
            ___(3)___;
        }
        while (___(4)___) {
            ___(5)___;
            a[len] %= q;
            len++;
        }
    }
    for (int i = len - 1; i >= 0; i--)
        if (a[i] < 10) cout << char(a[i] + '0');
        else cout << char(a[i] + 'A' - 10);
    return 0;
}

第 39 题

①处应填（ ）。

{{ select(39) }}

• a[j] *= p
• a[j] *= q
• a[j] *= pow(p,i)
• a[j] *= pow(q,i)

第 40 题

②处应填（ ）。

{{ select(40) }}

• a[j] += a[j-1]/q
• a[j+1] += a[j]/q
• if(j) a[j] += a[j-1]/q
• if(j) a[j+1] += a[j]/q

第 41 题

③处应填（ ）。

{{ select(41) }}

• if(j) a[j-1] /= q
• if(j) a[j-1] %= q
• if(j) a[j] %= q
• a[j] %= q

第 42 题

④处应填（ ）。

{{ select(42) }}

• a[len]
• a[len]/q
• a[len-1]
• a[len-1]/q

第 43 题

⑤处应填（ ）。

{{ select(43) }}

• a[len] += a[len-1]%q
• a[len] += a[len-1]/q
• a[len+1] += a[len]%q
• a[len+1] += a[len]/q