cspj4

ID: 27050

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

BlueArc

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

在一个 $2000 \times 2000$ 的网格图上进行 BFS，需要记录每个格子到起点的最短步数。起点到任意格子的最短步数不超过 3998。已知：
- bool 类型占 1 字节；
- short 类型占 2 字节，取值范围至少为 $[-32768,32767]$ ；
- int 类型占 4 字节；
- $1\text{ MB}=1024\times1024\text{ B}$ 。
若内存限制为 16 MB，下列存储方案中，在能够正确记录最短步数并判断某个格子是否未访问的前提下，最节省空间的是（）。{{ select(1) }}

  int dist[2000][2000];
  bool vis[2000][2000];

  int dist[2000][2000]; // 用 -1 表示未访问

  short dist[2000][2000]; // 用 -1 表示未访问

```
  bool vis[2000][2000];
```

某程序用整数 mask 的二进制位表示若干状态是否已经出现。若第 k 位为 1，表示状态 k 已出现；第 k 位为 0，表示状态 k 未出现。下列代码原本想判断第 k 位是否为 0：
```
if (mask & (1 << k) == 0) {
    cout << "NO";
} else {
    cout << "YES";
}
```
已知 mask = 10, k = 2，即 mask 的二进制表示为 1010。下列说法正确的是（）。{{ select(2) }}

第 2 位为 0，程序输出 NO，代码写法正确
第 2 位为 0，但程序输出 YES，因为 & 的优先级高于 ==
第 2 位为 0，但程序输出 YES，因为 == 的优先级高于 &
第 2 位为 1，程序输出 YES，代码写法正确

一个 $3 \times 4$ 的二维数组 a，行、列下标均从 0 开始。现在按如下规则依次填入 1 到 12：
- 按照 $i+j$ 从小到大的顺序扫描所有位置 $(i,j)$ ；
- 若 $i+j$ 为偶数，则在这一条斜线上按行号 $i$ 从大到小填入；
- 若 $i+j$ 为奇数，则在这一条斜线上按行号 $i$ 从小到大填入。
填完后，再按 C++ 中二维数组的行优先顺序映射到一维数组 b，即：
```
b[i * 4 + j] = a[i][j];
```
则 b[5] 和 a[2][1] 的值分别是（）。{{ select(3) }}

5，8
5，9
6，9
7，8

有若干个只含数字的字符串：
```
"12", "121", "9", "34", "3"
```
现在要把这些字符串重新排列后首尾相接，使得到的新字符串尽可能小。字符串的排列顺序是（）。{{ select(4) }}

"12"，"121"，"3"，"34"，"9"
"121"，"12"，"3"，"34"，"9"
"121"，"12"，"34"，"3"，"9"
"3"，"34"，"9"，"121"，"12"

运行以下 C++ 代码片段，输出结果是（）。

set<int> s;
int a[6] = {7, 3, 5, 3, 7, 1};
for (int i = 0; i < 6; i++) {
    s.insert(a[i] % 5);
}
for (int x : s) {
    cout << x;
}
```{{ select(5) }}

0123
1235
7351
0137

一个带头结点 0 的双向循环链表初始状态如下：
```
0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 0
```
定义操作 move(x, y)：将当前链表中的结点 x 从原位置摘下，再插入到结点 y 的后面。依次执行：
```
 move(2, 4)
 move(5, 1)
 move(3, 2)
```
执行完所有操作后，从头结点 0 的后继开始，沿 next 指针依次遍历得到的序列是（）。{{ select(6) }}

1, 3, 4, 2, 5
1, 5, 4, 2, 3
1, 5, 2, 3, 4
1, 4, 5, 2, 3

在一个双向循环链表中，区间 [L, R] 表示从结点 L 开始沿 next 指针走到结点 R 的一段连续结点。设：
```
a = L->pre
b = R->next
c = p->next
```
其中结点 p 不在区间 [L, R] 中，且 p 不是 a。现在要将整个区间 [L, R] 从原位置摘下，并插入到结点 p 的后面。以下指针关系正确的是（）。{{ select(7) }}

  a->next = b;
  b->pre = a;
  p->next = L;
  L->pre = p;
  R->next = c;
  c->pre = R;

  a->next = R;
  b->pre = L;
  p->next = L;
  L->pre = p;
  R->next = c;
  c->pre = R;

  a->next = b;
  b->pre = a;
  p->next = R;
  R->pre = p;
  L->next = c;
  c->pre = L;

  a->next = b;
  b->pre = a;
  L->pre = c;
  R->next = p;
  p->next = L;
  c->pre = R;

将关键字 5, 2, 8, 1, 4, 3, 6, 9 依次插入一棵初始为空的二叉搜索树中，则该树的中序遍历和后序遍历分别是（）。{{ select(8) }}

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

一个小根堆用数组表示为：
```
1, 3, 5, 7, 9, 6, 8
```
删除堆顶元素后，将最后一个元素放到堆顶，并向下调整。调整完成后的堆数组是（）。{{ select(9) }}

3, 5, 6, 7, 9, 8
5, 3, 6, 7, 9, 8
3, 8, 5, 7, 9, 6
3, 7, 5, 8, 9, 6

无向图的边为：
```
(1,2), (1,4), (2,3), (2,5), (4,5), (5,6)
```
从顶点 1 开始进行 BFS，每次优先访问编号较小的未访问邻点，则顶点的访问顺序是（）。{{ select(10) }}

1, 2, 3, 4, 5, 6
1, 4, 2, 5, 3, 6
1, 2, 4, 5, 3, 6
1, 2, 4, 3, 5, 6

有 5 个任务，依赖关系如下：

任务 3 必须在任务 1 和任务 2 完成后才能开始

任务 4 必须在任务 2 完成后才能开始；

任务 5 必须在任务 3 和任务 4 完成后才能开始。

下列说法一定正确的是（ ）。
```{{ select(11) }}

任务 1 一定比任务 2 先完成
任务 2 一定比任务 5 先完成
任务 4 一定比任务 3 先完成
任务 5 可以最先完成

有面值为 1、4、6 的硬币，每种数量不限。若要凑出金额 8，采用“每次选择不超过剩余金额的最大面值”的贪心策略，下列说法正确的是（）。{{ select(12) }}

贪心得到 2 枚硬币，且一定最优
贪心得到 3 枚硬币，且一定最优
贪心得到 3 枚硬币，但不是最优
无法凑出金额 8

已知非负整数 a、b 满足 a+b=a^b，则下列说法正确的是（）。{{ select(13) }}

a & b = 0
a | b = a + b - 1
a ^ b = a + b + 1
a + b = 2(a | b) + 1

在一条直线上有 n 个同学，他们的位置从小到大依次为 x1<x2<x3<...<xn。现在要选一个集合点 t，使所有同学到集合点的总路程尽量短。定义
$f(t)=\sum_{i=1}^n |x_i-t|$
则下列说法正确的是（）。{{ select(14) }}

f(t) 在平均数处一定取得最小值
f(t) 在最大值处一定取得最小值
当 n 为偶数时，f(t) 的最小值在中间两个数之间的任意整数处都能取得
f(t) 只可能在唯一一个整数处取得最小值

长度为 9 的 01 串中，恰好有 4 个 1，且任意两个 1 之间至少有一个 0。这样的字符串共有（）个。{{ select(15) }}

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填对，错误填错；除特殊说明外，判断题1.5分，选择题3分，共计40分）

(1)

#include <bits/stdc++.h>
using namespace std;
int ones(int x) {
    int cnt = 0;
    while (x) {
        cnt++;
        x &= x - 1;
    }
    return cnt;
}
int rot(int x, int k, int p) {
    int mask = (1 << p) - 1;
    k %= p;
    return ((x << k) | (x >> (p - k))) & mask;
}
int main() {
    int p, q;
    cin >> p >> q;
    int n = 1 << p;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = i ^ (i >> 1);
    }
    int s = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        int x = rot(a[i], q, p);
        if (ones(x ^ a[i]) == 2) {
            cnt++;
            s ^= x;
        }
    }
    cout << a[q] << " " << rot(a[q], q, p) << endl;
    cout << cnt << " " << s << endl;
    return 0;
}

判断题：数组 a 中第 i 项的值为 i 与 i/2 按位异或的结果。（）{{ select(16) }}

判断题：函数 rot(x, k, p) 的作用是把 x 的二进制表示整体左移 k 位，超出部分直接丢弃。（）{{ select(17) }}

判断题：函数 ones(x) 的循环次数等于 x 的二进制表示中 $1$ 的个数。（）{{ select(18) }}

若输入为：
```
3 1
```
程序第一行输出为（）。{{ select(19) }}

1 2
1 4
3 6
2 4

若输入为：
```
3 1
```
程序第二行输出为（）。{{ select(20) }}

4 0
4 7
6 7
8 7

当输入为 p q，且 $1\le q<p$ 时，该程序的时间复杂度最接近（）。{{ select(21) }}

$O(p)$
$O(2^p)$
$O(p2^p)$
$O(2^{2p})$

(2)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n + 1);
    for (int i = 1; i <= n; i++) {
        string t;
        cin >> t;
        g[i] = " " + t;
    }
    vector<vector<int>> s(n + 1, vector<int>(m + 1, 0));
    vector<vector<int>> diag(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int v = g[i][j] - '0';
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v;
            diag[i][j] = diag[i - 1][j - 1] + v;
        }
    }
    int q;
    cin >> q;
    int ok = 0, best = -1;
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
        int d = diag[x2][y2] - diag[x1 - 1][y1 - 1];
        if (sum == d) ok++;
        best = max(best, sum - d);
    }
    cout << ok << " " << best << endl;
    return 0;
}

判断题：s[i][j] 表示从 (1,1) 到 (i,j) 的矩形区域中所有数字之和。（）{{ select(22) }}

判断题：diag[i][j] 表示从 (i,j) 开始向右下方走到边界所经过数字之和。（）{{ select(23) }}

判断题：对某次查询，若 sum == d，说明该查询矩形中所有的 $1$ 都在它的主对角线上。（）{{ select(24) }}

若输入为：

程序输出为（）。{{ select(25) }}

1 2
2 2
0 3
2 3

使用第 25 题的输入，四次查询中第几次会使 ok 增加？（）{{ select(26) }}

第 $1$ 次
第 $2$ 次
第 $3$ 次
没有一次

设网格大小为 $n\times m$ ，查询次数为 $q$ ，该程序的时间复杂度最接近（）。{{ select(27) }}

$O(nm+q)$
$O(nmq)$
$O(q\log(nm))$
$O(n+m+q)$

(3)

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int x, step;
};
int main() {
    int n, a, b;
    cin >> n >> a >> b;
    vector<int> dis(n + 1, -1);
    queue<Node> q;
    dis[a] = 0;
    q.push({a, 0});
    while (!q.empty()) {
        Node cur = q.front();
        q.pop();
        int x = cur.x;
        int y1 = x * 2;
        int y2 = x - 1;
        int y3 = n - x + 1;
        int nxt[3] = {y1, y2, y3};
        for (int i = 0; i < 3; i++) {
            int y = nxt[i];
            if (1 <= y && y <= n && dis[y] == -1) {
                dis[y] = cur.step + 1;
                q.push({y, cur.step + 1});
            }
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (dis[i] != -1 && dis[i] <= dis[b]) cnt++;
    }
    cout << dis[b] << endl;
    cout << cnt << endl;
    return 0;
}

判断题：该程序使用广度优先搜索求从 a 到每个可达位置的最少操作次数。（）{{ select(28) }}

判断题：一次操作可以把当前位置 x 变为 2x、x-1 或 n-x+1，但变换后的数必须仍在 $[1,n]$ 范围内。（）{{ select(29) }}

判断题：变量 cnt 统计的是所有可以从 a 到达的位置个数。（）{{ select(30) }}

若输入为：
```
10 3 9
```
程序第一行输出为（）。{{ select(31) }}

若输入为：
```
10 3 9
```
程序第二行输出为（）。{{ select(32) }}

若把程序中的
```
int nxt[3] = {y1, y2, y3};
```
改为
```
int nxt[3] = {y3, y2, y1};
```
并仍输入：
```
10 3 9
```
则程序第一行输出会变为（）。{{ select(33) }}

1
2
3
不变，仍为原来的值

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

(1)（第 $k$ 个可用编号）

某系统中的编号为正整数 $1,2,3,\ldots$ 。现在有 $n$ 个编号已经被占用，这些编号互不相同，并按从小到大的顺序给出。请找出第 $k$ 个没有被占用的正整数编号。例如，已被占用的编号为 $2,3,7$ ，没有被占用的编号依次为 $1,4,5,6,8,\ldots$ ，第 $4$ 个没有被占用的编号是 $6$ 。保证 $1 \le n \le 10^5$ ， $1 \le k \le 10^9$ ，所有被占用编号不超过 $10^9$ 。请补全程序。

#include <bits/stdc++.h>
using namespace std;
long long countFree(const vector<long long>& used, long long x) {
    long long blocked = __(34)__;
    return __(35)__;
}
long long solve(const vector<long long>& used, long long k) {
    long long l = 1;
    long long r = k + (long long)used.size();
    long long ans = -1;
    while (__(36)__) {
        long long mid = l + (r - l) / 2;
        if (__(37)__) {
            ans = mid;
            r = mid - 1;
        } else {
            l = __(38)__;
        }
    }
    return ans;
}
int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> used(n);
    for (int i = 0; i < n; i++) cin >> used[i];
    cout << solve(used, k) << endl;
    return 0;
}

(34) 处应填（）{{ select(34) }}

lower_bound(used.begin(), used.end(), x) - used.begin()
upper_bound(used.begin(), used.end(), x) - used.begin()
used.end() - lower_bound(used.begin(), used.end(), x)
used.size() - x

(35) 处应填（）{{ select(35) }}

blocked - x
x + blocked
x - blocked
used[x] - blocked

(36) 处应填（）{{ select(36) }}

l <= r
l < r
l >= r
ans == -1

(37) 处应填（）{{ select(37) }}

countFree(used, mid) <= k
countFree(used, l) >= k
mid >= k
countFree(used, mid) >= k

(38) 处应填（）{{ select(38) }}

mid - 1
mid + 1
r + 1
l - 1

(2)（逃离蔓延的火焰）

给定一个 $n$ 行 $m$ 列的地图，其中：

# 表示墙，不能通过；
. 表示空地；
S 表示起点；
T 表示终点；
F 表示初始着火点。每一分钟，火焰会先向上下左右四个方向蔓延一格，不能穿过墙。人随后也可以向上下左右四个方向移动一格，不能走到墙上，也不能走到已经着火或同一时刻即将着火的格子。请输出从 S 到 T 的最少时间。若无法到达，输出 -1。保证 $1 \le n,m \le 1000$ ，地图中恰好有一个 S 和一个 T，可能有多个 F。请补全程序。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, m;
vector<string> grid;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool out(int x, int y) {
    return x < 0 || x >= n || y < 0 || y >= m;
}
int solve() {
    vector<vector<int>> fire(n, vector<int>(m, INF));
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    int sx = -1, sy = -1, tx = -1, ty = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'F') {
                fire[i][j] = 0;
                __(39)__;
            } else if (grid[i][j] == 'S') {
                sx = i;
                sy = j;
            } else if (grid[i][j] == 'T') {
                tx = i;
                ty = j;
            }
        }
    }
    while (__(40)__) {
        auto cur = q.front();
        q.pop();
        int x = cur.first, y = cur.second;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (out(nx, ny) || grid[nx][ny] == '#') continue;
            if (fire[nx][ny] != INF) continue;
            fire[nx][ny] = fire[x][y] + 1;
            q.push({nx, ny});
        }
    }
    queue<pair<int, int>> p;
    dist[sx][sy] = 0;
    p.push({sx, sy});
    while (!p.empty()) {
        auto cur = p.front();
        p.pop();
        int x = cur.first, y = cur.second;
        if (x == tx && y == ty) return dist[x][y];
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            int nd = dist[x][y] + 1;
            if (out(nx, ny) || grid[nx][ny] == '#') continue;
            if (dist[nx][ny] != -1) continue;
            if (__(41)__) continue;
            dist[nx][ny] = __(42)__;
            __(43)__;
        }
    }
    return -1;
}
int main() {
    cin >> n >> m;
    grid.resize(n);
    for (int i = 0; i < n; i++) cin >> grid[i];
    cout << solve() << endl;
    return 0;
}

(39) 处应填（）{{ select(39) }}

q.pop()
q.push({i, j})
p.push({i, j})
fire[i][j] = INF

(40) 处应填（）{{ select(40) }}

q.empty()
!q.empty()
p.empty()
fire[sx][sy] == INF

(41) 处应填（）{{ select(41) }}

nd > fire[nx][ny]
nd >= fire[nx][ny]
dist[x][y] >= fire[x][y]
grid[nx][ny] == 'T'

(42) 处应填（）{{ select(42) }}

dist[x][y]
fire[nx][ny]
nd
dist[nx][ny] + 1

(43) 处应填（）{{ select(43) }}

q.push({nx, ny})
p.pop()
p.push({sx, sy})
p.push({nx, ny})

#cspj4. cspj4

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

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填对，错误填错；除特殊说明外，判断题1.5分，选择题3分，共计40分）

(1)

(2)

(3)

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

(1)（第 $k$ 个可用编号）

(2)（逃离蔓延的火焰）

状态

开发

支持

关于

#cspj4. cspj4

cspj4

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

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填对，错误填错；除特殊说明外，判断题1.5分，选择题3分，共计40分）

(1)

(2)

(3)

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

(1)（第 kkk 个可用编号）

(2)（逃离蔓延的火焰）

状态

开发

支持

关于

登录

(1)（第 $k$ 个可用编号）