#YHCSP9999. YHCSP9999

YHCSP9999

选择题

  1. （2分）十进制数114的相反数的8位二进制补码是：{{ select(1) }}
  • 10001110
  • 10001101
  • 01110010
  • 01110011
  1. （2分）以下哪个网站不是Online Judge（在线程序判题系统）?Online Judge可以查看算法题目，提交自己编写的程序，然后可以获得评测机反馈的结果。{{ select(2) }}
  • Luogu
  • Gitee
  • LeetCode
  • Codeforces
  1. （2分）小A用字母A表示1，B表示2，以此类推，用26表示Z。对于27以上的数字，可以用两位或者更长的字符串来对应，例如AA对应27，AB对应28，AZ对应52，AAA对应703 ……那么BYT对应的数字是什么? {{ select(3) }}
  • 2018
  • 2020
  • 2022
  • 2024
  1. （2分）UIM拍摄了一张照片，其分辨率是4096×2160，每一个像素都是24位真彩色。在没有压缩的情况下，这张图片占用空间接近以下哪个值? {{ select(4) }}
  • 8MB
  • 25MB
  • 200MB
  • 200KB
  1. （2分）在一个长度为n的数组中找到第k大的数字，平均的算法时间复杂度最低的是: {{ select(5) }}
  • O(n)
  • O(nk)
  • O(nlogn)
  • O(n^2)
  1. （2分）对于“树”这种数据结构，正确的有: ①一个有n个顶点、n - 1条边的图是树 ②一个树中的两个顶点之间有且只有一条简单路径 ③树中一定存在度数不大于1的顶点 ④树可能存在环 {{ select(6) }}
  • ①②④
  • ①②③
  • ②③
  • ①②
  1. （2分）博艾中学进行了一次信息学会考测试，其优、良、及格、不及格的试卷数量分别为10,13,14,15张。现在这些卷子混在一起，要将这些卷子按照等级分为4叠。分卷子的方法是，每次将一叠有不同等级答卷的卷子分为两堆，使得这两堆中没有相同等级的卷子，然后可以再分，直到分为4叠。要分完这些卷子，至少需要多少次“分卷子”的操作?将一堆数量为nn的卷子分成两堆，就会产生nn次分卷子的操作。{{ select(7) }}
  • 84
  • 93
  • 78
  • 85
  1. （2分）一个二叉树的前序遍历是HGBDAFEC，中序遍历是BGHFAEDC，同时采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1，若某结点的下标为ii，则其左孩子位于下标2ii处、右孩子位于下标2ii + 1处），则该数组的最大下标至少为（ ）{{ select(8) }}
  • 7
  • 13
  • 15
  • 12
  1. （2分）在C++语言中，如果a = 1;b = 0;c = 1;那么以下表达式中为1的是: {{ select(9) }}
  • a&&b||b&&c
  • a + b>c||b
  • !(c&&(!a||b))
  • a + b + c
  1. （2分）在一个初始长度为nn的链表中连续进行kk次操作，每次操作是读入两个数字aiai和bibi，在链表中找到元素为aiai的结点（假设一定可以找到），然后将bibi这个元素插入到这个结点前面。在最理想的情况下，链表访问的结点数量最少可能是多少（不算将要插入的结点）? {{ select(10) }}
  • n次
  • k次
  • nk次
  • n + k次
  1. （2分）A班有5名风纪委员，B班有4名风纪委员，C班有3名风纪委员。现在需要从这些同学中选取6名风纪委员巡逻，如果只关注各班派出的风纪委员人数，有几种不同的方案? {{ select(11) }}
  • 9
  • 12
  • 15
  • 18
  1. （2分）以下哪种排序算法的时间复杂度是O(n^2)? {{ select(12) }}
  • 计数排序
  • 插入排序
  • 希尔排序
  • 归并排序
  1. （2分）已知rand()可以生成一个0到32767的随机整数，如果希望得到一个范围在[a,b)的随机整数，a和b是不超过100的正整数且a < b，那么可行的表达式是什么? {{ select(13) }}
  • (rand()%(b - a)) + a
  • (rand()%(b - a + 1)) + a
  • (rand()%(b - a)) + a + 1
  • (rand()%(b - a + 1)) + a + 1
  1. （2分）一个7个顶点的完全图需要至少删掉多少条边才能变为森林? {{ select(14) }}
  • 16
  • 21
  • 15
  • 6
  1. （2分）2020年8月，第（ ）届全国青少年信息学奥林匹克竞赛在（ ）举行? {{ select(15) }}
  • 26，广州
  • 26，长沙
  • 37，广州
  • 37，长沙

第16题

#include<iostream>
using namespace std;
#define MAXN 20
int gu[MAXN][MAXN];
int luo(int n, int m) {
    if(n <= 1 || m < 2)
        return 1;
    if(gu[n][m] != -1)
        return gu[n][m];
    int ans = 0;
    for(int i = 0; i < m; i += 2)
        ans += luo(n - 1, i);
    gu[n][m] = ans;
    return ans;
}
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < MAXN; i++)
        for(int j = 0; j < MAXN; j++)
            gu[i][j] = -1;
    cout << luo(n, m);
    return 0;
}

第16 - 1题（1.5分）

luo函数中，m的值不可能是奇数。（ ）{{ select(16) }}

  • A. 正确
  • B. 错误

第16 - 2题（1.5分）

若将第11行的 < 改为 <=，程序的输出结果可能会改变。（ ）{{ select(17) }}

  • A. 正确
  • B. 错误

第16 - 3题（1.5分）

若将第8,9,13行删除，程序的运行的结果不变 （ ）{{ select(18) }}

  • A. 正确
  • B. 错误

第16 - 4题（1.5分）

在添加合适的头文件后，将第19到21行替换为 memset(gu,255,sizeof(gu));可以起到相同的作用 （ ）{{ select(19) }}

  • A. 正确
  • B. 错误

第16 - 5题（3分）

若输入数据为4 8，则输出为（ ）。{{ select(20) }}

  • A. 7
  • B. 8
  • C. 15
  • D. 16

第16 - 6题（3分）

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

  • A. O(m2n)O(m^{2n})
  • B. O(nm!)O(nm!)
  • C. O(n2)O(n^2)
  • D. O(n2m)O(n^{2m})

17.（13分）

#include<bits/stdc++.h>
using namespace std;
int n, m;
int f[101][101];
int F[101][101];
int main() {
    scanf("%d%d", &n, &m); // n的值在1到100之间
    memset(f, -1, sizeof(f));
    for(int i = 1; i <= m; i++) {
        int u, v, w; // w的值在0到10000之间
        scanf("%d%d%d", &u, &v, &w);
        f[u][v] = f[v][u] = w;
    }
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(f[i][k] != -1 && f[k][j] != -1)
                    if(f[i][j] == -1||f[i][j]>f[k][j]+f[i][k])
                        f[i][j] = f[i][k] + f[k][j];
    int ans = 2147483647;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) {
            for(int x = 1; x <= n; x++)
                for(int y = 1; y <= n; y++)
                    F[x][y] = f[x][y];
            F[i][j] = F[j][i] = 0;
            for(int x = 1; x <= n; x++)
                for(int y = 1; y <= n; y++)
                    if(F[x][y]==-1||F[x][y]>F[x][i]+F[i][y])
                        F[x][y] = F[x][i] + F[i][y];
            for(int x = 1; x <= n; x++)
                for(int y = 1; y <= n; y++)
                    if(F[x][y]==-1||F[x][y]>F[x][j]+F[j][y])
                        F[x][y] = F[x][j] + F[j][y];
            int res = 0;
            for(int x = 1; x <= n; x++)
                for(int y = 1; y < x; y++)
                    res += F[x][y];
            ans = min(res, ans);
        }
    printf("%d\n", ans);
    return 0;
}

第17 - 1题（1.5分）

14到16行，将外层到内层的循环变量依次调整为i,j,k i,j,k，程序的运行的结果不变。（ ）{{ select(22) }}

  • A. 正确
  • B. 错误

第17 - 2题（1.5分）

这个程序的时间复杂度和m无关。（ ）{{ select(23) }}

  • A. 正确
  • B. 错误

第17 - 3题（1.5分）

20行的ans如果初始化为107时，可能无法得到正确结果。（ ）{{ select(24) }}

  • A. 正确
  • B. 错误

第17 - 4题（1.5分）

若将第27到30行的部分和31到34行的两个部分互换，程序的运行的结果不变。（ ）{{ select(25) }}

  • A. 正确
  • B. 错误

第17 - 5题（3分）

若输入数据为4 5/1 2 3/1 3 6/2 3 4/2 4 7/3 4 2 (其中“/”为换行符)，则输出为（ ）。{{ select(26) }}

  • A. 14
  • B. 18
  • C. 21
  • D. 28

第17 - 6题（3分）

这个程序使用了（ ）算法。{{ select(27) }}

  • A. Floyd
  • B. Dijkstra
  • C. Prim
  • D. Kruskal
  1. （14分）
#include<bits/stdc++.h>
#define MOD 19260817
#define MAXN 1005
long long A[MAXN][MAXN] = {0}, sum[MAXN][MAXN] = {0};
int n, m, q;
int main() {
    A[1][1] = A[1][0] = 1;
    for(int i = 2; i <= 1000; i++) {
        A[i][0] = 1;
        for(int j = 1; j <= i; j++)
            A[i][j] = (A[i - 1][j] + A[i - 1][j - 1]) % MOD;
    }
    for(int i = 1; i <= 1000; i++)
        for(int j = 1; j <= 1000; j++)
            sum[i][j] = (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + A[i][j] + MOD) % MOD;
    cin >> q;
    while(q--) {
        cin >> n >> m;
        cout << sum[n][m] << endl;
    }
    return 0;
}

第18 - 1题（1分）

当i≤j时，A[i][j]的值是0。（ ）{{ select(28) }}

  • A. 正确
  • B. 错误

第18 - 2题（2分）

当i>j时，A[i][j]的值相当于从i个不同元素中取出j个元素的排列数。（ ）{{ select(29) }}

  • A. 正确
  • B. 错误

第18 - 3题（2分）

sum[i][j]的值1<j≤i≤1000小于sum[i - 1][j - 1]的值。（ ）{{ select(30) }}

  • A. 正确
  • B. 错误

第18 - 4题（2分）

若将第12行改为A[i][j]=(A[i - 1][j]+A[i - 1][j - 1]+MOD)%MOD;，程序的运行的结果不变。（ ）{{ select(31) }}

  • A. 正确
  • B. 错误

第18 - 5题（4分）

A[i][j] (1≤i≤10,1≤j≤10) 的所有元素中，最大值是（ ）。{{ select(32) }}

  • A. 126
  • B. 276
  • C. 252
  • D. 210

第18 - 6题（3分）

若输入数据为1/5 3 (其中“/”为换行符)，则输出为（ ）。{{ select(33) }}

  • A. 10
  • B. 35
  • C. 50
  • D. 24
  1. （15分） （封禁xxs）现有n个xs（编号为1到n），每个xs都有一个关注者，第i个xs的关注者是ai。现在管理员要将其中的一些xs的账号封禁，但需要注意的是如果封禁了第i个人，那么为了不打草惊蛇，就不能封禁他的关注者ai。现在想知道最多可以封禁多少个xs。 输入第一行，一个整数表示答案。 第二行是n个1到n的整数表示ai。
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 300005
int n, ans = 0, a[MAXN], in[MAXN] = {0};
bool vis[MAXN] = {0};
void dfs(int cur, int w) {
    if(vis[cur])
        return;
    vis[cur] = true;
    if(w == 1) ans++;
    if((2))
        dfs(a[cur], (3));
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        in[a[i]]++;
    }
    for(int i = 1; i <= n; i++)
        if(!in[i]) (4);
    for(int i = 1; i <= n; i++)
        if((5)) dfs(i, 0);
    printf("%d\n", ans);
    return 0;
}

第19 - 1题（3分）

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

  • in[a[cur]]=0;
  • in[a[cur]]--;
  • in[cur]--;

第19 - 2题（3分）

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

  • in[a[cur]] != 0 || w == 1
  • in[a[cur]] == 0 || w == 0
  • in[a[cur]] != 0 || w == 0
  • in[a[cur]] == 0 || w == 1

第19 - 3题（3分）

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

  • 0
  • 1
  • w
  • 1 - w

第19 - 4题（3分）

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

  • dfs(i,1)
  • dfs(i,0)
  • dfs(a[i],1)
  • dfs(a[i],0)

第19 - 5题（3分）

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

  • !in[i]
  • in[i]
  • !vis[i]
  • vis[i]
  1. （15分） （烧作业）某课作业布置了N(3≤N≤100000)个题目，第i题对应的得分是ai。作业的总得分的计算方式为去掉作业中得分最小的一个题，剩下其它所有题目得分的平均值。但很不幸小A遇到了一场火灾，前K(1≤K≤N−2)个题目被烧了，无法记录得分。小A想知道，K是多少时，可以得到最高的作业得分？作业被烧了前K页，这时的得分是从第K + 1页到最后一页中，去除最小得分后取平均值。 输入第一行是整数N，第二行是n个不超过10000的非负整数表示ai。 输出一行，若干个整数表示答案。如果有多个K，请依次升序输出。
#include <cstdio>
#include <cmath>
#define min(a,b) (a<b?a:b)
#define MAXN 100002
using namespace std;
int n, k[MAXN], cnt = 0;
int s[MAXN], minScore, sum;
double maxAverage = 0, nowAverage;
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &s[i]);
    minScore = s[n];
    int sum;
    ①;
    for(int i = n - 1; i >= 2; i--) {
        minScore = min(minScore, s[i]);
        ②;
        nowAverage = ③;
        if(nowAverage > maxAverage) {
            ④;
            maxAverage = nowAverage;
        } else if(fabs(nowAverage - maxAverage) < 1e-6)
            ⑤;
    }
    for(int i = cnt; i >= 1; i--)
        printf("%d\n", k[i]);
    return 0;
}

第20 - 1题（3分）

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

  • sum=n
  • sum=s[1]
  • sum=s[n]
  • sum=0

第20 - 2题（3分）

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

  • sum=maxAverage*(n - i)
  • sum+=s[i]
  • sum+=s[n - i]
  • sum=s[i]+minScore

第20 - 3题（3分）

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

  • (double)(sum+minScore)/(n - i)
  • sum*1.0/(n - i)
  • (int)(sum - minScore)/(n - i)
  • (double)(sum - minScore)/(n - i)

第20 - 4题（3分）

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

  • k[++cnt]=i;
  • k[cnt++]=i - 1
  • cnt=1;k[cnt]=i - 1;
  • cnt=0;k[cnt]=i;

第20 - 5题（3分）

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

  • k[cnt++]=i;
  • k[++cnt]=i - 1;
  • k[cnt++]=n - i;
  • k[cnt]=i;
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. 浙ICP备2025154918号
  3. Worker 0, 154ms
  4. Powered by Hydro v4.19.1 Community