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

本卷共 43 题，满分 100 分。

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

第 1 题

以下语言在计算机中能够直接被识别和执行的是（ ）。

{{ select(1) }}

• 编译型语言
• 机器语言
• 解释型语言
• 高级语言

第 2 题

若十进制数为 $135.5$，则其八进制数为（ ）。

{{ select(2) }}

• 207.25
• 207.4
• 217.25
• 217.4

第 3 题

由 5 个“0”和 3 个“1”组成的 8 位二进制补码，能表示的最小整数是（ ）。

{{ select(3) }}

• -125
• -126
• -3
• -32

第 4 题

以下选项中，仅当 $x$ 的绝对值在 2 至 7 范围内时，表达式值为“真”的是（ ）。

{{ select(4) }}

• (x>=-7)&&(x<=-2)||(x>=2)&&(x<=7)
• (x>=2)&&(x<=7)&&(x>=-7)&&(x<=-2)
• (x>=-7)||(x<=-2)||(x>=2)||(x<=7)
• (x>=2)&&(x<=7)||(x>=-2)&&(x<=-7)

第 5 题

当输入字符 D 时，以下 switch 语句会输出什么？

char rank;
scanf("%c", &rank);
switch (rank){
    case 'A': printf("A"); break;
    case 'B': printf("B");
    case 'C': printf("C"); break;
    case 'D': printf("D");
    case 'E': printf("E");
    default: printf("error!");
}

{{ select(5) }}

• DEerror!
• D
• DE
• Derror!

第 6 题

当输入 7 时，以下代码输出的 Odd 和 Even 各是多少个？

int t;
scanf("%d", &t);
for (int i = 0; i < t + 1; i++){
    printf(i & 1 ? "Odd" : "Even");
}

{{ select(6) }}

• 4 个、4 个
• 4 个、3 个
• 3 个、5 个
• 5 个、3 个

第 7 题

考虑如下递归算法，则调用 func(3, 2) 得到的返回结果为（ ）。

int func(int n, int x){
    if (n <= 0) return 1;
    else if (n == 1) return 2 * x;
    else return 2 * x * func(n - 1, x)
              - 2 * (n - 1) * func(n - 2, x);
}

{{ select(7) }}

• 14
• 16
• 40
• 48

第 8 题

下列四种排序算法，不具备稳定性的是（ ）。

{{ select(8) }}

• 冒泡排序
• 插入排序
• 计数排序
• 选择排序

第 9 题

以下哪个结构可以用来存储图（ ）。

{{ select(9) }}

• 栈
• 哈希表
• 邻接表
• 队列

第 10 题

无向图的边为 A0-A1、A1-A3、A0-A3、A0-A2、A2-A4。以 A0 为起点进行深度优先遍历时，遍历顺序不可能是（ ）。

{{ select(10) }}

• A0, A1, A3, A2, A4
• A0, A3, A1, A2, A4
• A0, A1, A2, A3, A4
• A0, A2, A4, A3, A1

第 11 题

给定一棵二叉树，其前序遍历序列为 [1, 2, 4, 5, 3, 6, 7]，中序遍历序列为 [4, 2, 5, 1, 6, 3, 7]，则后序遍历序列为（ ）。

{{ select(11) }}

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

第 12 题

借助栈将中缀表达式 a+b*c+(d*e+f)*g 转化为后缀表达式，当读入 f 时，符号栈里从底向上依次是（ ）。

{{ select(12) }}

• +(+
• +(*+
• ++(+
• ++(*+

第 13 题

12 个相同的小球放到 4 个不同的袋子里，袋子可以为空，一共有（ ）种放法。

{{ select(13) }}

• 220
• 286
• 455
• 560

第 14 题

从 1 至 9 中取出 7 个不同的数，要求它们的和是 36，共有（ ）种不同的取法。

{{ select(14) }}

• 1
• 2
• 3
• 4

第 15 题

甲、乙、丙、丁四位学员获得前四名且没有并列。甲说：“我是第 2 名，乙是第 3 名。”乙说：“丙是第 4 名，我是第 2 名。”丙说：“丁是第 2 名，我是第 3 名。”丁说：“我是第 1 名，乙是第 3 名。”已知每人都只说对了一半。丙是第（ ）名。

{{ select(15) }}

• 1
• 2
• 3
• 4

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

阅读程序（1）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll C1[35][35];
void init(){
    for(int i = 0; i <= 34; i++){
        C1[i][0] = 1;
        for(int j = 1; j <= i; j++){
            C1[i][j] = C1[i - 1][j] + C1[i - 1][j - 1];
        }
    }
}
ll CC(ll n, ll m){
    ll ans = 1;
    for(ll i = n; i > n - m; i--) ans = ans * i;
    for(ll i = m; i >= 1; i--) ans = ans / i;
    return ans;
}
int main(){
    init();
    ll n, m; scanf("%lld%lld", &n, &m);
    printf("%lld %lld", C1[n][m], CC(n, m));
    return 0;
}

第 16 题

第 16 行代码一定会导致原本结果中的小数被抹掉。（ ）

{{ select(16) }}

• 正确
• 错误

第 17 题

当 $0\le n<m$ 时，此时输出的两个数均为 0。（ ）

{{ select(17) }}

• 正确
• 错误

第 18 题

如果 n=50, m=49，输出的第二个数是 50。（ ）

{{ select(18) }}

• 正确
• 错误

第 19 题

组合数 $\binom{10000}{10}$ 的结果为偶数。（ ）

{{ select(19) }}

• 正确
• 错误

第 20 题

当 n=6, m=3 时，程序会输出（ ）。

{{ select(20) }}

• 10 10
• 15 15
• 15 20
• 20 20

第 21 题

二维数组 C1 中，$\sum_{i=1}^{10} C1[10][i]$ 的结果是（ ）。

{{ select(21) }}

• 511
• 1023
• 1024
• 2047

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

阅读程序（2）

提示：输入的 nums1 和 nums2 数组已按从小到大排序。

#include <bits/stdc++.h>
using namespace std;
vector<int> nums1, nums2;
int m, n, t;
int f(int k) {
    int index1 = 0, index2 = 0;
    while (true) {
        if (index1 == m) {
            return nums2[index2 + k - 1];
        }
        if (index2 == n) {
            return nums1[index1 + k - 1];
        }
        if (k == 1) {
            return min(nums1[index1], nums2[index2]);
        }
        int newIndex1 = min(index1 + k / 2 - 1, m - 1);
        int newIndex2 = min(index2 + k / 2 - 1, n - 1);
        int pivot1 = nums1[newIndex1];
        int pivot2 = nums2[newIndex2];
        if (pivot1 <= pivot2) {
            k -= newIndex1 - index1 + 1;
            index1 = newIndex1 + 1;
        }
        else {
            k -= newIndex2 - index2 + 1;
            index2 = newIndex2 + 1;
        }
    }
}
int main(){
    cin >> m >> n;
    for (int i = 0; i <= m - 1; i++){
        cin >> t;
        nums1.push_back(t);
    }
    for (int i = 0; i <= n - 1; i++){
        cin >> t;
        nums2.push_back(t);
    }
    int totalLength = nums1.size() + nums2.size();
    if (totalLength & 1) {
        cout << f((totalLength + 1) / 2);
    }
    else {
        cout << (f(totalLength / 2) + f(totalLength / 2 + 1)) / 2.0;
    }
    return 0;
}

第 22 题

程序的第 8、11 行分别改为 index1 == m - 1、index2 == n - 1 也不会出错。（ ）

{{ select(22) }}

• 正确
• 错误

第 23 题

程序第 21 行的等于号去掉，把 pivot1 <= pivot2 改为 pivot1 < pivot2，程序仍然正确。（ ）

{{ select(23) }}

• 正确
• 错误

第 24 题

程序输出的小数最多保留几位小数？

{{ select(24) }}

• 3
• 6
• 1
• 2

第 25 题

输入以下数据，最后输出的结果是（ ）。

4 9
1 3 4 9
1 2 3 4 5 6 7 8 9

{{ select(25) }}

• 3
• 4
• 5
• 6

第 26 题

以上程序完成了（ ）的任务。

{{ select(26) }}

• 找到两个数组合并后的第 $k-1$ 小的数字
• 找到两个数组合并后的第 $k$ 小的数字
• 找到两个数组合并后的中位数
• 找到两个数组合并后的众数

第 27 题

函数 f() 最坏情况下的时间复杂度为（ ）。

{{ select(27) }}

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

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

阅读程序（3）

输入满足：$1\le k\le n\le100$；$1\le a[i]\le n$ 且所有 a[i] 互不相同；各点坐标为 $[0,100]$ 内的整数，所有坐标互不相同（程序使用 double 存储）。

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-5;
double x[105], y[105], cx[105], cy[105];
int n, k, a[105], id[105];
vector<int> v[105];
double dis(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
bool solve(){
    bool flag = 0;
    for (int i = 1; i <= k; i++) v[i].clear();
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= k; j++){
            if (dis(x[i], y[i], cx[id[i]], cy[id[i]]) > dis(x[i], y[i], cx[j], cy[j]) + eps)
                id[i] = j;
        }
        v[id[i]].push_back(i);
    }
    for (int i = 1; i <= k; i++){
        double tx = cx[i], ty = cy[i];
        cx[i] = cy[i] = 0;
        for (int j = 0; j < v[i].size(); j++){
            cx[i] += x[v[i][j]];
            cy[i] += y[v[i][j]];
        }
        cx[i] /= v[i].size(); cy[i] /= v[i].size();
        if (abs(tx - cx[i]) > eps || abs(ty - cy[i]) > eps) flag = 1;
    }
    return flag;
}
double cal(){
    double ans = 0;
    for (int i = 1; i <= n; i++){
        ans += dis(x[i], y[i], cx[id[i]], cy[id[i]]);
    }
    return ans;
}
int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        id[i] = 1; // 第43行
    }
    for (int i = 1; i <= k; i++){
        cin >> a[i];
        cx[i] = x[a[i]]; cy[i] = y[a[i]];
    }
    while (solve());
    printf("%.2lf", cal());
    return 0;
}

第 28 题

如果 n=k，程序输出 0.00。（ ）

{{ select(28) }}

• 正确
• 错误

第 29 题

删去第 43 行的 id[i] = 1，程序的运行结果不会发生改变。（ ）

{{ select(29) }}

• 正确
• 错误

第 30 题

函数 solve() 的最坏时间复杂度最接近（ ）。

{{ select(30) }}

• $O(nk)$
• $O(n^2)$
• $O(k^2)$
• $O(nk\log k)$

第 31 题

如果输入如下，程序输出是（ ）。

2 1
0 0
1 1
1

{{ select(31) }}

• 0.70
• 1.00
• 1.41
• 2.00

第 32 题

输入的前七行如下（最后一行用于给出 3 个初始质心下标）。在合法填写最后一行时，程序输出的最大值是（ ）。

6 3
0 0
0 1
0 2
10 0
10 1
10 2

{{ select(32) }}

• 4.00
• 6.00
• 30.00
• 33.00

第 33 题

在题目给定的数据范围内，如果所有 y[i]=0，那么程序输出的最大值是（ ）。

{{ select(33) }}

• 2500.00
• 2550.00
• 5000.00
• 5050.00

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

完善程序（1）：删数问题

输入一个不超过 250 位的高精度正整数 $N$，删除其中任意 $k$ 个数字后，使剩余数字按原次序组成的非负整数最小，输出时不得含前导 0。

#include <iostream>
#include <cstring>
using namespace std;

string s;
int k, a[251];

int main(){
    cin >> s;
    cin >> k;
    int len = s.length();
    for (int i = 0; i < len; i++)
        ___(1)___;
    while (k--){
        for (int i = 0; i < len; i++){
            if (___(2)___){
                for (int j = i; j < len; j++)
                    ___(3)___;
                ___(4)___;
                break;
            }
        }
    }
    int i = 0, m = 0;
    while (a[i] == 0 && ___(5)___){
        m++;
        i++;
    }
    for (int i = m; i < len; i++)
        cout << a[i];
    return 0;
}

第 34 题

①处应填（ ）。

{{ select(34) }}

• a[i] = 0
• a[i] = s[i]
• a[i] = s[i] - '0'
• s[i] = s[i] - '0'

第 35 题

②处应填（ ）。

{{ select(35) }}

• a[i] < a[i + 1]
• a[i] > a[i + 1]
• a[i] <= a[i + 1]
• a[i] >= a[i + 1]

第 36 题

③处应填（ ）。

{{ select(36) }}

• a[j] = a[j + 1]
• a[j] = a[j - 1]
• a[j + 1] = a[j]
• a[j - 1] = a[j]

第 37 题

④处应填（ ）。

{{ select(37) }}

• i++
• i--
• len++
• len--

第 38 题

⑤处应填（ ）。

{{ select(38) }}

• m < len
• m < len - 1
• i < len
• i < len + 1

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

完善程序（2）：输出函数图中的所有环

一个有向图有 $n\le1000$ 个顶点，编号为 1 到 $n$，每个顶点的出度恰好为 1，用 nxt[i] 表示后继。输出所有环；先输出编号较小的顶点能够到达的环，每个环从环内编号最小的顶点开始输出。

#include <bits/stdc++.h>
using namespace std;
int n, fast, low, nt;
int nxt[1005];
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &nxt[i]);
    for (int i = 1; i <= n; i++){
        if (nxt[i]){
            low = fast = i;
            do{
                low = nxt[low];
                fast = nxt[nxt[fast]];
            }while (___(1)___);
            int minnode = fast;
            do{
                fast = nxt[fast];
                minnode = min(minnode, fast);
            }while (___(2)___);
            fast = minnode;
            while (___(3)___){
                nt = nxt[fast];
                printf("%d ", fast);
                nxt[fast] = ___(4)___;
                ___(5)___;
            }
            if (fast) printf("\n");
        }
    }
    return 0;
}

第 39 题

①处应该填（ ）。

{{ select(39) }}

• fast == low
• fast != low
• fast == nxt[fast]
• fast != nxt[fast]

第 40 题

②处应该填（ ）。

{{ select(40) }}

• fast == low
• fast != low
• fast == nxt[fast]
• fast != nxt[fast]

第 41 题

③处应该填（ ）。

{{ select(41) }}

• nxt[fast]
• nxt[nt]
• fast
• nt

第 42 题

④处应该填（ ）。

{{ select(42) }}

• 1
• low
• nt
• 0

第 43 题

⑤处应该填（ ）。

{{ select(43) }}

• fast = nxt[fast]
• nt = fast
• fast = nt
• fast = 0