CSP-JS 2022第一轮认证已于9月18日结束,考完当天下午老师整理试卷并分享了估分链接,结果不算理想,当然官方的成绩还没正式公布,最终结果还未知。
一、单项选择题(共 15 题,每题 2 分,共计 30 分;每题有且仅有一个正确选项) 1.以下哪种功能没有涉及C++语言的面向对象特性支持:( )。 A. C++中调用 printf 函数 B. C++中调用用户定义的类成员函数 C. C++中构造一个 class 或 struct D. C++中构造来源于同一基类的多个派生类
答案:A 解析:printf 是格式化输出,是C语言中的输出方式,不涉及到面向对象。
2. 有 6 个元素,按照 6、5、4、3、2、1 的顺序进入栈 S,请问下列哪个出栈序列是非法的 ( )。 A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6
答案:C 解析:3出4出,然后栈顶是5,不能6出
3.运行以下代码片段的行为是( )。
cpp
int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;
A. 将x的值赋为201 B. 将y的值赋为101 C. 将q指向x的地址 D. 将p指向y的地址
答案:D 解析:将q赋值给p以后,表示指针变量p和指针变量q中都存储的是变量y的地址。所以p和a都指向了y的地址。
4.链表和数组的区别包括( )。 A. 数组不能排序,链表可以 B. 链表比数组能存储更多的信息 C. 数组大小固定,链表大小可动态调整 D. 以上均正确
答案:C 解析:数组一经定义后,在内存中就会分配出固定的空间存放内存中的数据,链表的大小取决于链表中结点的个数,可以动态调整。所以选C
5. 对假设栈S和队列Q的初始状态为空。存在 e1~e6 六个互不相同的数据,每个数据按照 进栈S、出栈S、进队列Q、出队列Q的顺序操作,不同数据间的操作可能会交错。已知栈S中依次有数据 e1、e2、e3、e4、e5和e6进栈,队列Q依次有数据e2、e4、e3、e6、e5和e1出队列。则栈S的容量至少是( )个数据。 A. 2 B. 3 C. 4 D. 6
答案:B 解析:首先栈的顺序是先进后出 然后队列的顺序是先进先出 核心点:每一个结点的操作都是进栈,出栈,进队列,出队列。 根据队列来看,e2是第一个出队的,表明此时e2是第一个入队,也就是说在e2入队之前栈中存储的数据为el,e2。然后e2出栈,栈中保存元素为cl,然后队列第二个出队数据是e4,e4入队之前栈中数据有el,e3,e4。然后e4,e3依次出栈进入队列出队,然后队列下一个出队的元素e6,e6入队前栈中数据有el,e5,e6。 所以根据分析来看,栈的容量至少为3。
6.对表达式a+(b-c)*d的前缀表达式为( ),其中+、-、*是运算符。 A. *+a-bcd B. +a*-bcd C. abc-d*+ D. abc-+d
答案:B 解析:前缀表达式 方法一:按照运算顺序,符号前移,操作数后移。 方法二:按照表达式画出树后可以求出前序遍历,即为前缀表达式。
7. 假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%, 15%, 30%, 16%, 29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码,字母d的编码长度为 ( )位。 A. 1 B. 2 C. 2或3 D. 3
答案:B 解析:先构造哈夫曼树,然后可以发现d在哈夫曼树的第2层。编码长度为2。
8. 一棵有 n 个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第1个位 置。若存储在数组第9个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子 结点的位置分别是( )。 A. 8、18 B. 10、18 C. 8、19 D. 10、19
答案:C 解析:根据二叉树的顺序存储来看
9. 考虑由N个顶点构成的有向连通图,采用邻接矩阵的数据结构表示时,该矩阵中至少存在( )个非零元素。 A. N-1 B. N C. N+1 D. N2
答案:B 解析:题目中说的是有向连通图,口个顶点最少存在n条边。所以存在n个非0元素。
10.以下对数据结构的表述不恰当的一项为:( )。 A. 图的深度优先遍历算法常使用的数据结构为栈。 B. 栈的访问原则为后进先出,队列的访问原则是先进先出。 C. 队列常常被用于广度优先搜索算法。 D. 栈与队列存在本质不同,无法用栈实现队列。
答案:D 解析:栈与队列存在本质相同,他们都是操作受限的线性表。
11.以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果(其中,next 域为结 点的直接后继,prev域为结点的直接前驱):( )。 A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next; B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next; C. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s; D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;
答案:D 解析:双向循环链表中,每个节点都存在一个pre指针域和nex!指针域。pre指针域存储前驱结点的地址,next指针域存储后继结点的地址。
12.以下排序算法的常见实现中,哪个选项的说法是错误的:( )。 A. 冒泡排序算法是稳定的 B. 简单选择排序是稳定的 C. 简单插入排序是稳定的 D. 归并排序算法是稳定的
答案:B 解析:不稳定排序有:选择,希尔,快速,堆排序
13.八进制数32.1对应的十进制数是( )。 A. 24.125 B. 24.250 C. 26.125 D. 26.250
答案:C 解析:3*8+2=26 / 1/8=0.125
14.一个字符串中任意个连续的字符组成的子序列称为该字符串的子串,则字符串abcab有( )个内容互不相同的子串。 A. 12 B. 13 C. 14 D. 15
答案:B 解析:长度为0的子串:空串 长度为1的子串:abc 长度为2的子串:ab bc ca 长度为3的子串:abc bca cab 长度为4的子串:abca bcab 长度为S的子串:abcab 一共是13个。
15.以下对递归方法的描述中,正确的是:( ) A. 递归是允许使用多组参数调用函数的编程技术 B. 递归是通过调用自身来求解问题的编程技术 C. 递归是面向对象和数据而不是功能和逻辑的编程语言模型 D. 递归是将用某种高级语言转换为机器代码的编程技术
答案:B 解析:递归就是西数自己调用自己
二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√,错误填×;除特 殊说明外,判断题 1.5 分,选择题 3 分,共计 40 分)
cpp
01 #include <iostream>
02
03 using namespace std;
04
05 int main()
06 {
07 unsigned short x, y;
08 cin>>x>>y;
09 x = (x | x << 2) &
10 x = (x | x << 1) &
11 y = (y | y << 2) &
12 y = (y | y << 1) &
13 unsigned short z =
14 cout << z << endl;
15 return 0;
16 }
假设输入的 x、y 均是不超过 15 的自然数,完成下面的判断题和单选题:
16. 删去第7行与第13行的unsigned,程序行为不变。( )
答案:V 解析:因为输入的x和y都是不超过15 的自然数,15表示为二进制是 1111, short类型的变量是2个字节,16位,其中最高位是符号位,剩下15位存放数据,足够放的下运算的结果。所以加不加unsigned(无符号)没有影响。所以本题正确。
17. 将第7行与第13行的short均改为char,程序行为不变。( )
答案:x 解析:如果改成char类型,因为y在整个程序中左移了4位,那么最高位的值有可能是1,导致最后的结果存不到char类型的变量中,最后结果就会出错,所以本题错误。
18. 程序总是输出一个整数“0”。( )
答案:x 解析:第4题和第s题带入模拟后能够判断输出不是0,所以本题错误。
19. 当输入为“2 2”时,输出为“10”。( )
答案:x 解析:输入是22之后,模拟带入运算答案是12,所以本题错误。
20. 当输入为“2 2”时,输出为“59”。( )
答案:x 解析:输入是22之后,模拟带入运算答案是12,所以本题错误。
21. 当输入为“13 8”时,输出为( )。 A. “0” B. “209” C. “197” D. “226”
答案:B 解析:经过模拟运算,计算出答案是209。
cpp
01 #include <algorithm>
02 #include <iostream>
03 #include <limits>
04
05 using namespace std;
06
07 const int MAXN = 105;
08 const int MAXK = 105;
09
10 int h[MAXN][MAXK];
11
12 int f(int n, int m)
13 {
14 if (m == 1) return n;
15 if (n == 0) return 0;
16
17 int ret = numeric_limits::max();
18 for (int i = 1; i <= n; i++)
19 ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
20 return ret;
21 }
22
23 int g(int n, int m)
24 {
25 for (int i = 1; i <=n; i++)
26 h[i][1] = i;
27 for (int j = 1; j <= m; j++)
28 h[0][j] = 0;
29
30 for (int i = 1; i <= n; i++)
31 for ( j = 2; j <= m; j++) {
32 h[i][j] = numeric_limits<int>::max();
33 for (int k = 1; k <= i; k++)
34 h[i][j] = min(
35 h[i][j],
36 max(h[i -k][j], h[k - 1][j - 1] + 1);
37 }
38 }
39
40 return h[n][m];
41 }
42
43 int main()
44 {
45 int n, m;
46 cin >> n >> m;
47 cout << f(n, m) << endl << g(n, m) << endl;
48 return 0;
49 }
假设输入的 n、m 均是不超过 100 的正整数,完成下面的判断题和单选题:
22.当输入为“7 3”时,第 19 行用来取最小值的 min 函数执行了 449 次。( )
答案:x 解析:执行了448次。两个参数,可以画一个表进行模拟。额外标记每一次运算需要的次数。
每个表格里面存放了当前的值,(里面表示运行min的次数。发现n–7,m-=3的时候min运行了448次。
23.输出的两行整数总是相同的。( )
答案:V 解析:模拟过后发现两个西数的目的相同,做的是同样的运算。所以本题正确。
24.当m为1时,输出的第一行总为n。( )
答案:V 解析:当m的值是1的时候,递归出口在第14行 if(m == 1) return n;所以本题正确
25.算法g(n,m)最为准确的时间复杂度分析结果为( )。 A. 0(n3/2m) B. 0(nm) C. 0(n2m) D. 0(nm2)
答案:C 解析:关注第30行、第31行、第33行,这3行循环的次数分别是n,m,n,所以时间复杂度可以估计为0(m*n2)。所以答案选C。
26.当输入为“20 2”时,输出的第一行为( )。 A. “4” B. “5” C. “6” D. “20”
答案:C 解析:因为两个函数结果相同,带入到,或者g西数中模拟可得6,所以选择C选项。
27.(4 分)当输入为“100 100”时,输出的第一行为() A. “6” B. “7” C. “8” D. “9”
答案:B 解析:因为两个函数结果相同,带入到f或者g西数中模拟可得了,所以选择B选项
cpp
01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09 int l = 0, r = n;
10 while (l <= r) {
11 int mid = (l + r) / 2;
12 if (mid * mid <= n) l = mid + 1;
13 else r = mid - 1;
14 }
15 return l - 1;
16 }
17
18 double solve2(double x) 19 {
20 if (x == 0) return x;
21 for (int i = 0; i < k; i++)
22 x = (x + n / x) / 2;
23 return x;
24 }
25
26 int main()
27 {
28 cin >> n >> k;
29 double ans = solve2(solve1());
30 cout << ans << ' ' << (ans * ans == n) << endl;
31 return 0;
32 }
假设int为32位有符号整数类型,输入的n是不超过47000的自然数、k是不超过int表示范围的自然数,完成下面的判断题和单选题:
经过模拟,我们可以发现本题主要运算的就是n的平方根,当k在增大的时候,运算出的答案就越接近n的平方根。
28.该算法最准确的时间复杂度分析结果为𝑂𝑂(log𝑛𝑛+𝑘𝑘)。( )
答案:V 解析:sovlel西数是一个二分的西数,时间复杂度是O(logn) solve2西数是一个循环k次的西数,时间复杂度是O(k) 因为solve1函数和solve2函数都仅仅调用了一次,所以整个算法的时间复杂度是0(k十logr)。所以本题正确。
29.当输入为“9801 1”时,输出的第一个数为“99”。( )
答案:V 解析:输入的是9801,1 相当于计算的是sqrt(9801)=99,所以输出的ans是99。,所以本题正确。
30.对于任意输入的n,随着所输入k的增大,输出的第二个数会变成“1”。( )
答案:× 解析:只要不能开平方根,就是0,所以本题错误。
31.该程序有存在缺陷。当输入的 n 过大时,第 12 行的乘法有可能溢出,因此应当将 mid强制转换为64位整数再计算。( )
答案:x 解析:n是不超过47000的自然数,mid是二分后的值,mid*mid是不会超过in范围的,所以本题错误。
32.当输入为“2 1”时,输出的第一个数最接近( )。 A. 1 B. 1.414 C. 1.5
答案:C 解析:带入模拟,可得1.5
33.当输入为“3 10”时,输出的第一个数最接近( )。 A. 1.7 B. 1.732 C. 1.75
答案:B 解析:输入的3和10,发现经过了多次运算后,会逐步接近于3的平方根,也就是1.732
34.当输入为“256 11”时,输出的第一个数( )。 A. 等于16 B. 接近但小于16 C. 接近但大于 16 D. 前三种情况都有可能
答案:A 解析:因为256的平方根就是16,无论k是多少,答案都是16.
三、完善程序(单选题,每小题 3 分,共计 30 分)
(1)(枚举因数)从小到大打印正整数 n 的所有正因数。 试补全枚举程序。
35. (1)处应填( ) A. n%i == 0 B. n%i == 1 C. n%(i-1) == 0 D. n%(i-1) == 1
答案:A 解析:需要将所有口的因子放入vector中。所以判断i是不是因数的方式为if(n%i==0)
36. (2)处应填( ) A. n / fac[k] B. fac[k] C. fac[k]-1 D. n / (fac[k]-1)
答案:B 解析:输出了所有小于sqrt(n)的因子
37. (3)处应填( ) A. (i-1)*(i-1)==n B. (i-1)*i==n C. i*i==n D. i*(i-1)==n
答案:C 解析:如果口是一个完全平方数,则会出现i*i==n的情况,此时i只需要输出一个即可。
38. (4)处应填( ) A. n-i B. n-i+1 C. i-1 D. I
答案:D 解析:当i*i==n时,输出一个i(这里原题面为大写I)
39. (5)处应填( ) A. n / fac[k] B. fac[k] C. fac[k]-1 D. n / (fac[k]-1)
答案:A 解析:输出所有大于sort(n)的因子,因为因数成对出现,所以可以直接用口除以其中一个约数等于另外一个约数。也就是n/fac[k]
(2)(洪水填充)现有用字符标记像素颜色的8×8图像。颜色填充的操作描述如下:给定起始像素的位置和待填充的颜色,将起始像素和所有可达的像素(可达的定义:经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色 都与起始像素颜色相同),替换为给定的颜色。 试补全程序。
40. (1)处应填( ) A. image[r][c] == prev_color B. image[r][c] != prev_color C. image[r][c] == new_color D. image[r][c] != new_color
答案:A 解析:判断(0)是否不越界且合法。坐标在范围内,颜色等于起点坐标颜色,颜色还没被巷换过条件2的表达为image[r][c]==pre_color
41. (2)处应填( ) A. image[cur.r+1][cur.c] = new_color B. image[cur.r][cur.c] = new_color C. image[cur.r][cur.c+1] = new_color D. image[cur.r][cur.c] = prev_color
答案:B 解析:将起点的颜色替换为新颜色 image[cur.c][cur.c]=new color
42. (3)处应填( ) A. Point(pt.r, pt.c) B. Point(pt.r, pt.c+1) C. Point(pt.r+1, pt.c) D. Point(pt.r+1, pt.c+1)
答案:C 解析:经过方向为上、下、左、右 (r-1,c)、 (r+1,c)、 (r, c-1)、 (r,c+1) 缺了往下方向的。即Point(pt.r+1,pt.c)
43. (4)处应填( ) A. prev_color = image[p.r][p.c] B. new_color = image[p.r][p.c] C. image[p.r][p.c] = prev_color D. image[p.r][p.c] = new_color
答案:D 解析:将符合条件的邻接位置的颜色替换为新颜色 image[p.r][p.c]=new_color
44. (5)处应填( ) A. queue.push(p) B. queue.push(pt) C. queue.push(cur) D. queue.push(Point(ROWS,COLS))
答案:A 解析:下一个位置入队