#ACSP1014. cspj-模拟题14

cspj-模拟题14

一、单项选择题

  1. 表达式 (int) ceil(3.7) 的结果为 ({{ select(1) }})。
  • 4.0
  • 4
  • 3.0
  • 3
  1. 在C++中定义如下数组 double a[10][100] (double为双精度浮点数类型)，存储容量约为 ({{ select(2) }})。
  • 2MB
  • 4KB
  • 8KB
  • 16KB
  1. 设一个有序的单链表有n个结点，现要求插入一个新节点后使得单链表依然保持有序，则该操作的时间复杂度为 ({{ select(3) }})。
  • A. O(logn)
  • B. O(1)
  • C. O(n^2)
  • D. O(n)
  1. 徐老师曾经是一位调酒师，有强迫症的他希望调出水和酒精比例恰好为x：y的酒精饮料，但是徐老师的调酒技术十分的笨拙，他每次只能进行如下的操作：1) 向杯子里加满水或者酒精 2) 将杯子里的液体倒出一半。比如如果要调出水：酒精为5：3的饮料，那么徐老师可以进行如下的操作：
  1. 加满水，目前为1:0
  2. 倒出一半液体，加满酒精，目前为1：1
  3. 倒出一半液体，加满酒精，目前为1：3
  4. 倒出一半液体，加满水，目前为5：3
    下列选项中永远无法调制出来的比例为 ({{ select(4) }})。
  • 9:7
  • 21:11
  • 5:7
  • 3:29
  1. 使用1×2和2×1大小的多米诺骨牌填满2×8的方格的方案数为({{ select(5) }})。
  • 31
  • 32
  • 33
  • 34
  1. 在算法竞赛中，我们经常遇到一些求解最优性的问题，比如经典的跳石头问题：比赛在一条笔直的河道中进行，有n块岩石，现在可以移走m块岩石，使得相邻两块石头之间的距离尽可能长，请问进行了m次移动后相邻两块岩石之间距离最小值最大为多少? 对于这一类问题我们发现如果对于一个距离k，我们容易判断是否存在一种移走石头的方案能够使得其合法，我们就将一个最优性问题转换为了存在性问题。这样对于求解这道题，我们为了得到较低的时间复杂度，我们可以考虑使用的算法是 ({{ select(6) }})。
  • 递推法
  • 递归法
  • 二分法
  • 倍增法
  1. C++中表达式 13 << 2 + 1 的值是多少? ({{ select(7) }})。
  • 104
  • 53
  • 4
  • 1
  1. 设无向图G中边的集合E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为 ({{ select(8) }})。
  • aedfcb
  • acfebd
  • aebcfd
  • aedfbc
  1. ( n×(n+2)×(n+4)n \times (n+2) \times (n+4) ) 一定是 ({{ select(9) }}) 的倍数。
  • 2
  • 3
  • 5
  • 7
  1. 从一个3元素的集合中允许重复地有序选取5个元素有多少种不同的方式? ({{ select(10) }})。
  • 81
  • 243
  • 27
  • 9
  1. 设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到的序列为 ({{ select(11) }})。
  • BADC
  • BCDA
  • CDAB
  • CBDA
  1. 已知一棵二叉树一共有2022个节点，根节点高度为1，则二叉树的高度至少为({{ select(12) }})。
  • 10
  • 11
  • 12
  • 1011
  1. 某双向链表a的列表存储形式如下，其中每组数据中第一个元素是数据，第二个元素是前驱指针，第三个元素是后继指针，链表的头指针为head，则当前链表的前3个元素之和为 ({{ select(13) }})。
    int a[] = {{3,4,3},{6,-1,4},{2,4,3},{1,0,-1},{4,1,0}};
int head = 1;
  • 10
  • 11
  • 12
  • 13
  1. 有一堆石子，初始有2018颗。小白和小蓝轮流取石子，每次最少取1颗石子，最多取5颗石子，取走最后一颗石子的一方获胜。小白先取石子，那么他第一次应该取走 ({{ select(14) }}) 颗石子，才能保证必胜。
  • 2
  • 3
  • 4
  • 5
  1. 下图中将ABCD四个区域用至多四种颜色染色，使得相邻区域颜色不同的方案数是({{ select(15) }})。
  • 48
  • 4
  • 12
  • 24

二、阅读程序

第一小题

当容器中的元素按照递增的顺序存储时，lower_bound函数返回容器中第一个大于等于目标值的位置，upper_bound函数返回容器中第一个大于目标值的位置。若容器中的元素都比目标值小则返回最后一个元素的下一个位置。

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

int n, k;
vector<int> a;

int main() {
    cin >> n;
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    cin >> k;
    cout << a[lower_bound(a.begin(), a.end(), k) - a.begin()] << endl;
    return 0;
}

保证k小于 max{ai}−1max\{a_i\}-1。

16.上述代码可以求出序列a中大于k的数中的最小的数。 ({{ select(16) }})

  • T
  • F

17.将a.push_back(x); 改为 a[i] = x;，程序输出结果一定不变。 ({{ select(17) }})

  • T
  • F

18.若将sort(a.begin(), a.end());删去程序有可能会运行出错。 ({{ select(18) }})

  • T
  • F

19.此程序的时间复杂度为 O(logn)。 ({{ select(19) }})

  • T
  • F

20.若输入为

5
1 2 3 4 5
2

则输出为 ({{ select(20) }})。

  • 2
  • 3
  • 4
  • 5

21.若将

cout << a[lower_bound(a.begin(), a.end(), k) - a.begin()] << endl;

改为

cout << a[upper_bound(a.begin(), a.end(), k) - a.begin()] << endl;

则输出为 ({{ select(21) }})。

  • 2
  • 4
  • 7
  • 8

第二小题

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

int a[1005], d[1005];

int find(int l, int r, int key) {
    while (l < r) {
        int m = (l + r) / 2;
        if (a[m] > key) r = m;
        else l = m + 1;
    }
    return r;
}

int main() {
    int n, len = 1;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    d[1] = a[1];
    for (int i = 2; i <= n; i++) {
        if (a[i] >= d[len]) {
            len++;
            d[len] = a[i];
        } else {
            int j = find(1, len + 1, a[i]);
            d[j] = a[i];
        }
    }
    cout << len << endl;
    return 0;
}

22.若a[i]大于数组d中的所有元素，则第22行find()函数的返回值为len+1。 ({{ select(22) }})

  • T
  • F

23.将第10行代码“return r;”改为“return l;”，不影响程序的运行结果。 ({{ select(23) }})

  • T
  • F

24.该程序的时间复杂度为 ({{ select(24) }})。

  • O(log2n)
  • O(n)
  • O(nlog2n)
  • O(n^2)

25.输入:

20
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

输出: ({{ select(25) }})

  • 5
  • 6
  • 7
  • 8

第三小题

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

const int maxn = 500010;
string str;
int pos[maxn];

long long solve(int m, int n) {
    long long ans = 0;
    pos[0] = 0, pos[m + 1] = n + 1;
    for (int i = 1; i <= m; i++) {
        int left = pos[i] - pos[i - 1] - 1;
        int right = pos[i + 1] - pos[i] - 1;
        if (left >= 2) {
            ans += left - 1;
        }
        if (right >= 2) {
            ans += right - 1;
        }
        if (left > 0 && right > 0) {
            ans += (long long)left * right;
        }
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    cin >> str;
    int m = 0;
    for (int i = 0; i < n; i++) {
        if (str[i] == 'G') {
            pos[++m] = i + 1;
        }
    }
    long long ans = solve(m, n);
    m = 0;
    for (int i = 0; i < n; i++) {
        if (str[i] == 'H') {
            pos[++m] = i + 1;
        }
    }
    ans += solve(m, n);
    cout << ans << endl;
    return 0;
}

26.第31行和第38行中pos数组内分别记录了每个字母G和H的索引位置(经过+1处理后的结果)。 ({{ select(26) }})

  • T
  • F

27.删除第8行代码后，程序输出不会改变。 ({{ select(27) }})

  • T
  • F

28.程序的含义是求解字符串str中长度大于等于3的子串中，有且仅有一个字母与其他字母不同的子串个数。 ({{ select(28) }})

  • T
  • F

29.若输入

5
GHGHG

则输出为 ({{ select(29) }})。

  • 1
  • 2
  • 3
  • 4

20.选出下面说法正确的是 ({{ select(30) }})。

  • 第9行代码是枚举满足条件的子串中的中间字母位置。
  • 第10, 11行代码中left和right是指枚举的字母位置左右两边相同字母的个数。
  • 第13行代码中left-1是指：以pos[i]作为子串的右端点且该子串满足条件的个数。
  • 第19行代码中long long可以删除，程序输出总是不会改变。

三、完善程序

第一小题

(链表去重) 输入一个长度为n的不下降序列，将其保存到单向链表之中，并去掉其中的重复元素。例如，输入序列“1,2,2,3,3”，首先构建链表“1->2->2->3->3”，然后从头到尾遍历链表，删除重复的2和3，最后输出结果1,2,3。

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

int a[100][2]; // 用数组a模拟链表
// a[i][0]表示元素值, a[i][1]表示next指针
int head; // head为链表头指针
int tot; // tot为链表元素插入的位置

void add(int t) { // 在链表尾插入元素t
    if (head == -1) {
        a[tot][0] = t; a[tot][1] = 1;
        head = tot; tot++;
    } else {
        int x = head;
        while (a[x][1] != -1) x = a[x][1];
        a[tot][0] = t; a[tot][1] = -1;
        a[x][1] = tot; tot++;
    }
}

void del() { // 去掉重复元素
    if (head == -1) return;
    int x = head, nextx = a[x][1];
    while (a[x][1] != -1) {
        if (a[x][0] == a[nextx][0]) {
            a[x][1] = a[nextx][1];
        } else {
            x = a[x][1];
        }
    }
}

int main() {
    int n, t;
    cin >> n;
    head = -1; tot = 0;
    for (int i = 0; i < n; i++) {
        cin >> t;
        add(t);
    }
    del();
    int x = head;
    while (x != -1) {
        cout << a[x][0] << ' ';
        x = a[x][1];
    }
    return 0;
}

31.第1处应填: ({{ select(31) }})

  • 0
  • -1
  • head+1
  • tot

32.第2处应填: ({{ select(32) }})

  • a[tot][0] = x
  • a[tot][1] = x
  • a[x][0] = tot
  • a[x][1] = tot

33.第3处应填: ({{ select(33) }})

  • a[x][0] = a[nextx][0]
  • a[nextx][0] = a[x][0]
  • a[x][1] = a[nextx][1]
  • a[nextx][1] = a[x][1]

34.第4处应填: ({{ select(34) }})

  • x = a[x][1]
  • x = a[nextx][1]
  • nextx = a[x][1]
  • nextx = a[nextx][1]

35.第5处应填: ({{ select(35) }}) A. x = a[x][0] B. x = a[x][1] C. x++ D. x += a[x][1]

第二小题

(数位操作) 你有两个正整数n和x，你需要对x进行若干次操作使得x在十进制下的数位长度大于n。每一次操作，你可以选择x在十进制下任何一位中出现过的数y(0≤y<10)，将x变为x*y。请问最少的操作次数为多少？输入仅一行，两个正整数n，x，输出仅一行，表示最少的操作次数(不满足条件输出-1)。

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

#define ll long long

struct node {
    ll val, stp;
};

ll n, x; // n表示目标位数, x表示初始值
queue<node> q; // 定义队列, 用/BFS
map<ll, bool> vis; // 定义哈希表, 记录某个值是否已被访问过

ll calcBit(ll x) {
    int t = 0;
    while (x) {
        ++t; // 位数计数器加1
        x /= 10; // 去掉最后一位
    }
    return t;
}

int main() {
    cin >> n >> x; // 读取输入的目标位数n和初始值x
    q.push({x, 0}); // 初始化队列
    ll ans = 1000; // 初始化答案为一个较大的数

    while (!q.empty()) {
        node s = q.front(); // 取出队列的第一个节点
        q.pop(); // 弹出该节点
        ll res = s.val; // 当前值

        if (calcBit(res) >= n) { // 如果当前值的位数大于等于目标位数
            ans = min(ans, s.stp); // 更新最小步数
            break; // 跳出循环
        }

        while (res) { // 提取当前值的每一位
            ll t = res % 10; // 取当前值的最后一位
            res /= 10; // 去掉最后一位

            if (!vis[s.val * t] && calcBit(s.val * t) <= n) { // 如果新值未被访问过且其位数小于等于目标位数
                vis[s.val * t] = true; // 标记为已访问
                q.push({s.val * t, s.stp + 1}); // 将新值加入队列
            }
        }
    }

    if (ans == 1000) cout << -1 << endl; // 如果最小步数仍然是初始值，表示未找到结果，输出-1
    else cout << ans << endl; // 输出最小步数
    return 0;
}

36.第1处应填写 ({{ select(36) }})

  • q.push({x, 0});
  • q.push({x, 1});
  • q.push(x, 0);
  • q.push(x, 1);

37.第2处应填写 ({{ select(37) }})

  • 1
  • 5
  • 10
  • 1000

38.第3处应填写 ({{ select(38) }})

  • calcBit(res) > n
  • calcBit(res) >= n
  • calcBit(res) < n
  • calcBit(res) <= n

39.第4处应填写 ({{ select(39) }})

  • vis[s.val * t]
  • !vis[s.val]
  • !vis[s.val * t]
  • vis[s.val]

40.第5处应填写 ({{ select(40) }})

  • vis[s.val * t] = true, q.push({s.val * t, s.stp + 1});
  • vis[s.val * t] = true, q.push({t, s.stp + 1});
  • vis[s.val * t] = false, q.push({s.val * t, s.stp + 1});
  • vis[s.val * t] = false, q.push({t, s.stp + 1});
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 蜀ICP备2022008388号-1
  3. Worker 0, 109ms
  4. Powered by Hydro v4.19.1 Community