2019信息学奥赛CSP-J 入门组试卷+答案+解析!!

网友投稿 2019-10-30 14:31

2019CCF非专业级别软件能力认证第一轮

(CSP-J)入门级C++语言试题A卷

(B卷与A卷仅顺序不同)

https://cdn.china-scratch.com/timg/191101/14313A1A-0.jpg

解析:答案A。

中国国家顶级域名即是.cn,.cn域名由国家管理。cn也是中国的缩写。

https://cdn.china-scratch.com/timg/191101/1431361T3-1.jpg

解析:答案D。

与运算是两者有一个0结果就是0,两者都是1才是1。

11 1011 1001 0111

01 0110 1110 1011

——————————&

01 0010 1000 0011

https://cdn.china-scratch.com/timg/191101/14313BK1-2.jpg

解析:答案C。

1字节 = 8位。32除以8等于4,所以选C。

https://cdn.china-scratch.com/timg/191101/14313Ia0-3.jpg

解析:答案A。

上述程序其实是计算出s减去c个1后等于多少,也就是a-c等于多少。所以选A。

https://cdn.china-scratch.com/timg/191101/14313KI0-4.jpg

解析:答案A。

二分查找的次数为logN。计算得出https://cdn.china-scratch.com/timg/191101/14313L632-5.jpg 所以选A。

https://cdn.china-scratch.com/timg/191101/14313H922-6.jpg

解析:答案D。

链表和数组不同的是他不能随机访问,只能“随藤摸瓜”的找。

https://cdn.china-scratch.com/timg/191101/14313II9-7.jpg

解析:答案C。

数据比较小,可以用列举法来做。如果袋子中最大8个球的情况有1种,最大7个球有1种,最大6个球有2种,最大5个球有3种,最大4个球有5种,最大3个球有4种,最大2个球有2种。一共18种。

https://cdn.china-scratch.com/timg/191101/14313JH9-8.jpg

解析:答案C。

先将其补充成完全二叉树,此时树的结点总数是15,所以答案选C。

https://cdn.china-scratch.com/timg/191101/14313V449-9.jpg

解析:答案B。

素数是能能被自己和1整除的数。从100开始推算,100不是素数,99也不是.... 97只能被1和自己整除,所以选B。

https://cdn.china-scratch.com/timg/191101/14313VK0-10.jpg

解析:答案C.

用短除法可以算出29。

https://cdn.china-scratch.com/timg/191101/14313Q946-11.jpg

解析:答案C。

性价比最高的是方案二,那么在周五、周六和周日这三天用方案二,跑了15公里,1800千卡。

还剩6公里,在周一到周二跑完,消耗600千卡。那么一总消耗2400千卡。

https://cdn.china-scratch.com/timg/191101/14313UZ0-12.jpg

解析:答案A。

鸽笼原理。因为求最少的可能性,那么我们可以构造一个尽量花色不一样的情况。

红、黄、蓝、绿、红、黄、蓝、绿、红、黄、蓝、绿。已有12张牌,剩下不管拿到什么颜色都会构成四种颜色相同。所以选A。

https://cdn.china-scratch.com/timg/191101/14313SG4-13.jpg

解析:答案C。

显然中间一位数字只能为1和0,接着去列举其他四位即可。

https://cdn.china-scratch.com/timg/191101/14313Sb4-14.jpg

解析:答案B。

通过后序遍历不难看出根结点是A,那么左子树结点为DBGEHJ,右子树为CIF。因为求的是前序遍历,那么选项中如果右子树出现在了左子树前面,即可排除。再根据后序遍历的序列构建整个二叉树即可得出B。

https://cdn.china-scratch.com/timg/191101/1431394921-15.jpg

解析:答案A。

图灵奖(Turing Award),全称“A.M. 图灵奖(A.M Turing Award)”,由于ACM于1966年设立,专门奖励那些对计算机事业作出重要贡献的个人。

二、阅读程序

  1. 程序大意:对于字符串中的第i位,如果i是n的约数,并且第i个字符比'a'(97)要大,就减少'a'(97)-'A'(65)。

    #include#includeusing namespace std;char st[100];int main() {  scanf("%s", st);int n = strlen(st); // 计算字符串的长度for (int i = 1; i <= n; ++i) { // 对字符串中的第i个字符进行循环枚举if (n % i == 0) { // 判断i是否是n的约数char c = st[i - 1]; // 取出字符串中的第i个字符if (c >= 'a') // 判断字符是否大于97st[i - 1] = c - 'a' + 'A'; // 将字符减少32}}printf("%s", st); // 输出字符串return 0;}

    1)考察程序的输入输出。

          程序中没有对字符串中的字符范围进行任何要求。

    2)考察表达式运算,除法和取模。

           如果i = 0,那么在n对i进行取模运算时就会报错,因为除以0了。

    3)考察约数判断,注意不是素数判定。

           判断素数的时候通常用这种方式进行加速,是因为sqrt(n)之后的约数与之前的约数是一一对应的,这也就说明了sqrt(n)之后还有约数。

           如果将循环范围缩小了,就不会处理后面的约数,导致答案不一样。

    4)考察数据类型,字符型的存储与表示。

           大写字母的ASCII码都要小于'a'(97),所以不会对字符串进行修改。

    5)考察数学,约数数量计算。

           将要计算的数分解质因数,每个质因数的出现次数加1,再乘起来就是约数个数。

           最多时每个约数的位置都可以修改,18有6个约数。

    6)考察数学,约数数量计算。

           10000 = 2^5 * 5^5,一共有(5 + 1) * (5 + 1) = 36个约数。

           不会求约数个数的同学可以暴力算一下其他几个数的约数个数,用排除法也能得到这个答案。

  2. 程序大意:有ab两组元素,两组元素之间可以两两配对(0可以任意次配对)。

    初始时所有元素都和另一组的0配对,每次考察a组的第x个元素和b组的第y个元素,如果这两个元素之前的配对交叉了,则把它们之前的配对元素都重新配对到0,并将这两个元素配对。

    最后求有多少个元素和0配对。

    https://cdn.china-scratch.com/timg/191101/1431393442-16.jpg

    #includeusing namespace std;int n, m;int a[100], b[100];
    int main() {  scanf("%d%d", &n, &m); // n个数与m次操作for (int i = 1; i <= n; ++i) // 初始时所有数都跟0配对a[i] = b[i] = 0;  for (int i = 1; i <= m; ++i) {int x, y;    scanf("%d%d", &x, &y);    if (a[x] < y && b[y] < x) { // 对于想要配对的数,判断原先的一对配对是否交叉      if (a[x] > 0) // 将原先的配对元素重新和0配对b[a[x]] = 0;if (b[y] > 0)        a[b[y]] = 0;      a[x] = y; // 当前两个元素建立新的配对a[y] = x;}}int ans = 0;  for (int i = 1; i <= n; ++i) { // 统计和0配对的元素数量if (a[i] == 0)++ans;if (b[i] == 0)++ans;}printf("%dn", ans);return 0;}

    1)考察对程序含义的理解。

          m > 0时一定会有一个配对,所以和0配对的元素的数量一定小于2n。

    2)考察对程序含义的理解,反例设计。

          统计是按照元素编号的顺序进行的,如果有一个x < y的配对,那么统计完b中的第x个元素时ans会变成奇数。

    3)考察对程序含义的理解,反例设计。

           如果ab中的第i个元素进行配对,则a[i]和b[i]同时>0。

    4)考察对程序含义的理解,反例设计。

           x总是小于y不代表x之前没有别的配对,如果x之前有别的配对,则照样会执行清理。

             可以依次对(1, 1)和(1, 2)进行配对,则第二次操作时会对1的配对进行清理。

    5)考察对程序含义的理解。

          x和y两两不同时,每次都会成功进行配对,m次会产生m对配对,所以和0配对的元素数量为2n - 2m。

    6)考察对程序含义的理解。

           x各不相同,y每次相等,那么x和y配对时每次都会清理掉之前的配对,最终只会产生一组配对,所以和0配对的元素数量为2n - 2。

  3. 程序大意:将一个元素序列根据a值构造成一棵二叉树,每次在序列中选择a值最小且最靠前的元素作为根,根之前的序列构建左子树,根之后的序列构建右子树。

    最后求出每个节点的深度乘以b值的和。

    #includeusing namespace std;const int maxn = 10000;int n;int a[maxn];int b[maxn];int f(int l, int r, int depth) { // 计算序列中l到r这几个元素构成的根深度为depth的子树的权值if (l > r) // 判断空子树return 0;int min = maxn, mink;for (int i = l; i <= r; ++i) { // 查找a值最小的最靠左的元素if (min > a[i]) {min = a[i]; // 记录最小值mink = i; // 记录位置}}int lres = f(l, mink - 1, depth + 1); // 计算左子树int rres = f(mink + 1, r, depth + 1); // 计算右子树return lres + rres + depth * b[mink]; // 当前子树的权值为左右子树权值与根权值的和}int main() {cin >> n;for (int i = 0; i < n; ++i) // 读入每个元素的a值cin >> a[i];for (int i = 0; i < n; ++i) // 读入每个元素的b值cin >> b[i];cout << f(0, n - 1, 1) << endl; // 构建子树并计算权值return 0;}

    1)考察循环遍历数组,也可以直接进行反例设计。

          重复的a值不影响查找最小元素,所以不会出错。

    2)考察对程序含义的理解。

           所有元素的b值为0,则权重也全部为0,总权重就是0。

           可以根据程序观察一下,所有的计算都会和b值进行相乘,没有常数,也可以猜到结果为0。

    3)考察数据结构二叉树,节点分层时的特性,最劣极端情况。

          每个子树中的每个节点都会进行一次比较,最坏情况下二叉树有n层(每次只划分出一个子树),所以比较次数为100 + 99 + ... + 1 = 5050,与5000最接近。

    4)考察数据结构二叉树,节点分层时的特性,最优极端情况。

          最少情况下二叉树有log层,100个节点约为7层,每一层的总节点数估算为n,则比较次数大约为700次,与600最接近。

    5)综合考察对程序含义的理解、二叉树的结构与数学计算。

          为了让输出最大,则需要让b值大的元素深度尽可能的大,一条链可以达成这个要求,则权值为1^2 + 2^2 + ... + 10^2 = 385。

    6)综合考察对程序含义的理解、二叉树的结构与数学计算。

           每个元素的b值均为1,则计算的是元素的深度和,所以需要让二叉树的深度尽可能小。

           那么第一层可以有1个节点,第二层可以有2个,第三层可以有4个,以此类推。权值为1 * 1 + 2 * 2 + 4 * 3 + 8 * 4 + ... + 32 * 6 + 37 * 7 = 580,注意最后一层节点数不满。

三、完善程序

  1. 程序思路:考察分治算法,通过递归的方式来对矩阵进行填充。

    从0作为元开始,每次将当前的矩阵划分成四个子矩阵,对应了一次变换,并根据变化规则分别得到四个子矩阵的元。

    子矩阵用递归的方式进行填充,直到不再变换。

    #includeusing namespace std;int n;const int max_size = 1 << 10;
    int res[max_size][max_size]; // 01矩阵
    void recursive(int x, int y, int n, int t) { // 填充左上角为(x, y)的n阶子矩阵,且元为tif (n == 0) { // 0阶矩阵只有一个数res[x][y] = t; // 等于元,不再变换return;}int step = 1 << (n - 1); // 分成的子矩阵之间的距离recursive(x, y, n - 1, t); // 左上角的子矩阵,元不变recursive(x, y + step, n - 1, t); // 右上角的子矩阵,元不变recursive(x + step, y, n - 1, t); // 左下角哦的子矩阵,元不变recursive(x + step, y + step, n - 1, !t); // 右下角的子矩阵,元取反}
    int main() {scanf("%d", &n);recursive(0, 0, n, 0); // 初始时要填充左上角为(0, 0)的n阶子矩阵,初始时元为0int size = 1 << n; // n阶矩阵的宽度为2^nfor (int i = 0; i < size; ++i) {for (int j = 0; j < size; ++j)printf("%d", res[i][j]);puts("");}return 0;}

    下面讲解一下对于不能完全看懂程序的同学该如何选择。

    1)如果填写一个常数,那整个矩阵就是常数矩阵了。

          而且这个t在函数中传递下来就只有这里可以直接使用,其他地方都是参数。

           所以除了t也没别的选择。

    2)分成四个子矩阵,看不懂程序的根据另外两行都能猜出来。

          另外两行中可以发现,x和y分别有加与不加两种可能,组合起来正好四种可能,所以肯定没减号。

    3)同上。

    4)通过函数中的参数命名可以猜出肯定是n了。

           然后测一下n = 1就可以确定第二个参数填0。

    5)测一下n = 1就知道肯定是1 << n。

  2. 程序思路:就是计数排序,和桶排序的原理有些相似。

    核心思想是,先统计每个值x出现的次数,再计算出小于等于每个值x的元素数量t,这个数量t决定了排序时值为x的元素应该从第t大开始逐个往前排,这样就完成了单关键字排序。

    双关键字排序时,要先排第二关键字,让元素都是根据第二关键字有序的。然后根据第一关键字重新排序时,首先可以保证结果是第一关键字有序的,同时对于第一关键字相同的元素,它们已经按照第二关键字排好序了,所以最后的结果是双关键字排序。

    #include#includeusing namespace std;const int maxn = 10000000;const int maxs = 10000;
    int n;unsigned a[maxn], b[maxn], res[maxn], ord[maxn];unsigned cnt[maxs + 1];
    int main() {scanf("%d", &n);for (int i = 0; i < n; ++i)scanf("%d%d", &a[i], &b[i]);memset(cnt, 0 , sizeof(cnt)); // 清0统计数组for (int i = 0; i < n; ++i)++cnt[b[i]]; // 先对第二关键字排序,统计每个b值的数量for (int i = 0; i < maxs; ++i)cnt[i + 1] += cnt[i]; // 累计小于等于每个b值的元素数量for (int i = 0; i < n; ++i)ord[--cnt[b[i]]] = i; // 根据第i个元素的b值,按照计算出的数量开始右后往前排列memset(cnt, 0 , sizeof(cnt));for (int i = 0; i < maxs; ++i)++cnt[a[i]]; // 接下来对第一关键字排序,统计每个a值的数量for (int i = 0; i < maxs; ++i)cnt[i + 1] += cnt[i]; // 累计小于等于每个a值的元素数量for (int i = n - 1; i >= 0; --i) // 因为排序中值相同的元素是从后往前放的,此时元素已经按b值排好序了,所以要从后往前来放元素才能保证a值相同的元素b值是由小到大的res[--cnt[a[ord[i]]]] = ord[i]; // 之前排好序的元素编号在ord中,要按照第二关键字排序来放for (int i = 0; i < n; ++i)printf("%d %dn", a[res[i]], b[res[i]]); // 双关键字排序的结果在res中return 0;}

    下面讲解一下对于不能完全看懂程序的同学该如何选择。

    1)先排第二关键字,肯定要选只有b[i]的选项。

    2)按照第二关键字排序,答案肯定跟b[i]相关。

           每个元素有ab两个值,ord中只能记录元素编号,所以肯定是保存i。

    3)现在根据第一关键字排序,答案应该是跟a[i]有关。

           有个与a[i]和b[i]同时有关的选项明显越界了,肯定不可能。

    4) ord里面存的是元素编号,肯定不能跟a[i]配合使用,而是要跟a[ord[i]]配合使用。

         同时这是根据第一关键字排序,应该是与a有关。

    5)res和ord里面存的都是元素编号,肯定不能嵌套使用。

           答案要按照排序输出,肯定与res或者ord有关。

    https://cdn.china-scratch.com/timg/191101/143139DO-17.jpg

总体来说,题目还是出的挺好的,考察的知识点也比较全面,注重考察原理。对于无法将知识点理解透彻的同学,也要学会根据上下文的线索来推导的能力,可以在选择题的考试中争取更多的分数

--end--

声明:本文章由网友投稿作为教育分享用途,如有侵权原作者可通过邮件及时和我们联系删除:freemanzk@qq.com