CSPJ2019初赛

ID: 2835

Type: Objective

Tried: 1

Accepted: 0

Difficulty: 10

Uploaded By:

hantina

若有定义：int a=7； float x=2.5，y=4.7；则表达式x+a%3*(int)(x+y)%2的值是:( ){{ select(1) }}

A. 0.000000
B. 2.750000
C. 2.500000
D. 3.500000

下列属于图像文件格式的有（）{{ select(2) }}

A. WMV
B. MPEG
C. JPEG
D. AVI

二进制数11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑或运算的结果是（）{{ select(3) }}

A. 11 1111 1111 1101
B. 11 1111 1111 1101
C. 10 1111 1111 1111
D. 11 1111 1111 1111

编译器的功能是（）{{ select(4) }}

A. 将源程序重新组合
B. 将一种语言(通常是高级语言)翻译成另一种语言(通常是低级语言)
C. 将低级语言翻译成高级语言
D. 将一种编程语言翻译成自然语言

设变量x为float型且已赋值，则以下语句中能将x中的数值保留到小数点后两位，并将第三位四舍五入的是（）{{ select(5) }}

A. x=(x*100+0.5)/100.0;
B. x=(int)(x*100+0.5)/100.0;
C. x=(x/100+0.5)*100.0;
D. x=x*100+0.5/100.0;

由数字1，1，2，4，8，8所组成的不同的4位数的个数是（）{{ select(6) }}

A. 104
B. 102
C. 98
D. 100

排序的算法很多，若按排序的稳定性和不稳定性分类，则( )是不稳定排序。{{ select(7) }}

A. 冒泡排序
B. 直接插入排序
C. 快速排序
D. 归并排序

G是一个非连通无向图(没有重边和自环)，共有28条边，则该图至少有( )个顶点。{{ select(8) }}

A. 10
B. 9
C. 11
D. 8

一些数字可以颠倒过来看，例如0、1、8颠倒过来看还是本身，6颠倒过来是9，9颠倒过来看还是6，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901。假设某个城市的车牌只有5位数字，每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的5位数能被3整除？( ){{ select(9) }}

A. 40
B. 25
C. 30
D. 20

一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？( ){{ select(10) }}

A. 23
B. 21
C. 20
D. 22

设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？( ){{ select(11) }}

A. n^2
B. nlogn
C. 2n
D. 2n−1

以下哪个结构可以用来存储图？（）{{ select(12) }}

A. 栈
B. 二叉树
C. 队列
D. 邻接矩阵

以下哪些算法不属于贪心算法（）。{{ select(13) }}

A. Dijkstra算法
B. Floyd算法
C. Prim算法
D. Kruskal算法

有一个等比数列，共有奇数项，其中第一项和最后一项分别是2和118098，中间一项是486，请问一下哪个数是可能的公比？（）。{{ select(14) }}

A. 5
B. 3
C. 4
D. 2

有正实数构成的数字三角形排列形式如图所示。第一行的数为 a(1,1) ，第二行 a(2,1) ，a(2,2) ，第 n 行的数为 a(n,1) ，a(n,2) ，…，a(n,n) 。从 a(1,1) 开始，每一行的数 a(i,j) 只有两条边可以分别通向下一行的两个数 a(i+1,j) 和a(i+1,j+1)。用动态规划算法找出一条从 a(1,1) 向下通道 a(n,1)，a(n,2)，…，a(n,n) 中某个数的路径，使得该路径上的数之和最大。令 C[i][j] 是从 a(1,1) 到 a(i,j) 的路径上的数的最大和，并且 C[i][0]=C[0][j]=0 ，则C[i][j]=( ){{ select(15) }}

A. max(C[i-1][j-1], C[i-1][j])+a(i,j)
B. C[i-1][j-1]+C[i-1][j]
C. max(C[i-1][j-1], C[i-1][j])+1
D. max(C[i][j-1], C[i-1][j])+a(i,j)

二、阅读程序

(1)

#include <cstdio>
using namespace std;
int n;
int a[100];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

第16行输出ans时，ans的值一定大于i。（）{{ select(16) }}

A. 正确
B. 错误

程序输出的ans小于等于n。（）{{ select(17) }}

A. 正确
B. 错误

若将第12行的 < 改为 !=，程序输出的结果不会改变。（）{{ select(18) }}

A. 正确
B. 错误

当程序执行到第16行时，若 ans−i>2 ,则a[i+1] ≤ a[i] 。（）{{ select(19) }}

A. 正确
B. 错误

若输入的a数组是一个严格单调递增的数列, 此程序的时间复杂度（）{{ select(20) }}

A. O(logn)
B. O(n^2)
C. O(nlogn)
D. O(n)

最坏情况下，此程序的时间复杂度是( )。{{ select(21) }}

A. O(n^2)
B. O(logn)
C. O(n)
D. O(nlogn)

(2)

#include <iostream>
using namespace std;

const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];

int getRoot(int v) {
    if (fa[v] == v) return v;
    return getRoot(fa[v]);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
        cnt[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, x, y;
        cin >> a >> b;
        x = getRoot(a);
        y = getRoot(b);
        ans += cnt[x] * cnt[y];
        fa[x] = y;
        cnt[y] += cnt[x];
    }
    cout << ans << endl;
    return 0;
}

输入的a和b值应在[0, n-1]的范围内。( ){{ select(22) }}

A. 正确
B. 错误

第16行改成fa[i] = 0；，不影响程序运行结果。( ){{ select(23) }}

A. 正确
B. 错误

若输入的 a 和 b 值均在 [0,n−1] 的范围内，则对于任意 0≤i<n 都有 0≤fa[i]<n ( ){{ select(24) }}

A. 正确
B. 错误

若输入的 a 和 b 值均在 [0,n−1] 的范围内，则对于任意 0≤i<n 都有 1≤cnt[i]≤n ( ){{ select(25) }}

A. 正确
B. 错误

当 n 等于 50 时，若 a,b 的值都在 [0,49] 的范围内，且在第 25 行时 x 总是不等于 y ,那么输出为()。{{ select(26) }}

A. 1276
B. 1176
C. 1225
D. 1250

此程序的时间复杂度是()。{{ select(27) }}

A. O(n)
B. O(logn)
C. O(n^2)
D. O(nlogn)

(3)

#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];

int main() {
    cin >> s >> t;
    int slen = s.length(), tlen = t.length();

    for (int i = 0, j = 0; i < slen; ++i) {
        if (j < tlen && s[i] == t[j]) ++j;
        pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列
    }

    for (int  i = slen - 1 , j = tlen - 1; i >= 0; --i) {
        if(j >= 0 && s[i] == t [j]) --j;
        suf[i]= j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列
    }

    suf[slen] = tlen -1;
    int ans = 0;
    for (int i = 0, j = 0, tmp = 0; i <= slen; ++i){
        while(j <= slen && tmp >= suf[j] + 1) ++j;
        ans = max(ans, j - i - 1);
        tmp = pre[i];
    }
    cout << ans << endl;
    return 0;
}
/*
提示： t[0..pre[i] -1]是 s[0..i]的子序列；
t[suf[i]+1..tlen-1]是 s[i..slen-1]的子序列。
*/

程序输出时，suf 数组满足：对任意 0≤i<slen , suf[i]≤suf[i+1] 。（）{{ select(28) }}

A. 正确
B. 错误

当 t 是 s 的子序列时，输出一定不为 0 。（）{{ select(29) }}

A. 正确
B. 错误

程序运行到第 23 行时，j-i-1 一定不小于 0 。（）{{ select(30) }}

A. 正确
B. 错误

当 t 是 s 的子序列时，pre 数组和 suf 数组满足：对任意 0≤i<slen,pre[i]>suf[i+1]+1 。（）{{ select(31) }}

A. 正确
B. 错误

若 tlen=10 ,输出为 0 ,则 slen 最小为（）{{ select(32) }}

A. 10
B. 12
C. 0
D. 1

若 tlen=10 ,输出为 2 ,则 slen 最小为（）。{{ select(33) }}

A. 0
B. 10
C. 12
D. 1

三、完善程序

(1)（匠人的自我修养）

#include<cstdio>
using namespace std;
const int maxn = 1001;

int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn], bonus[maxn];
int points;
bool find(){
    int target = -1;
    for (int i = 1; i <= n; ++i)
        if(① && ②){
            target = i;
            break;
    }
    if(target == -1)
        return false;
    unlock[target] = -1;
    ③
    for (int i = 0; i < cnt[target]; ++i)
        ④
    return true;
}

int main(){
    scanf("%d%d", &n, &points);
    for (int i = 1; i <= n; ++i){
        cnt[i] = 0;
        scanf("%d%d", &threshold[i], &bonus[i]);
    }
    for (int i = 1; i <= n; ++i){
        int m;
        scanf("%d", &m);
        ⑤
        for (int j = 0; j < m; ++j){
            int fa;
            scanf("%d", &fa);
            child[fa][cnt[fa]] = i;
            ++cnt[fa];
        }
    }

    int ans = 0;
    while(find())
        ++ans;

    printf("%d\n", ans);
    return 0;
}

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

A. unlock[i] <= 0
B. unlock[i] >= 0
C. unlock[i] == 0
D. unlock[i] == -1

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

A. threshold[i] > points
B. threshold[i] >= points
C. points > threshold[i]
D. points >= threshold[i]

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

A. target = -1
B. --cnt[target]
C. bonus[target] = 0
D. points += bonus[target]

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

A. cnt[child[target][i]] -= 1
B. cnt[child[target][i]] = 0
C. unlock[child[target][i]] -= 1
D. unlock[child[target][i]] = 0

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

A. unlock[i] = cnt[i]
B. unlock[i] = m
C. unlock[i] = 0
D. unlock[i] = -1

(2)（取石子）

#include <cstdio>
#include<algorithm>
using namespace std;
const int maxn = 64;
int n, m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win;
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &a[i], &b[i]);
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j)
            if (a[i] > a[j]){
                swap(a[i], a[j]);
                swap(b[i], b[j]);
            }
    status = ①;
    trans = 0;
    for(int i = 1, j = 0; i <= m; ++i){
        while (j < n && ②){
            ③;
            ++j;
        }
        win = ④;
        ⑤;
    }

    puts(win ? "Win" : "Loss");

    return 0;
}

①处应填( ){{ select(39) }}

A. 0
B. ~0ull
C. ~0ull^1
D. 1

②处应填( ){{ select(40) }}

A. a[j] < i
B. a[j] == i
C. a[j] != i
D. a[j] > 1

③处应填( ){{ select(41) }}

A. trans |= 1ull << (b[j] - 1)
B. status |= 1ull << (b[j] - 1)
C. status += 1ull << (b[j] - 1)
D. trans += 1ull << (b[j] - 1)

④处应填( ){{ select(42) }}

A. ~status | trans
B. status & trans
C. status | trans
D. ~status & trans

⑤处应填( ){{ select(43) }}

A. trans = status | trans ^ win
B. status = trans >> 1 ^ win
C. trans = status ^ trans | win
D. status = status << 1 ^ win

#CSPJ2019CS. CSPJ2019初赛

Status

Development

Support

About

#CSPJ2019CS. CSPJ2019初赛

CSPJ2019初赛

Status

Development

Support

About

Don't have an account?

SIGN IN