#5133. YCSP 2022 一轮模拟(初赛J组)
YCSP 2022 一轮模拟(初赛J组)
一、 单项选择题(共 15 题,每题 2 分,共计 30 分。每题有且仅有一个正确选项。)
- 一棵二叉树一共有19个节点,其叶子节点不可能有( )个 {{ select(1) }}
- 1
- 9
- 10
- 11
- 二叉树,已知其前序遍历是1 2 4 3 5 7 6(数字为结点的编号,以下同),后序遍历是4 2 7 5 6 3 1,则该二叉树的中序遍历不可能是( ) {{ select(2) }}
- 4 2 1 7 5 3 6
- 4 2 1 7 5 6 3
- 2 4 1 7 5 3 6
- 2 4 1 5 7 3 6
- 与十进制数 对应的8进制数是( ) {{ select(3) }}
- 21.5625
- 21.44
- 21.73
- 21.731
- 表达式的后缀表达式是( ) {{ select(4) }}
- abcd*+-
- abc+*d-
- abc*+d-
- -+*abcd
- 设一组初始记录关键字序列为,则以增量的一趟希尔排序结束后前4条记录关键字为( ) {{ select(5) }}
- 40,50,20,95
- 15,40,60,20
- 15,20,40,45
- 45,40,15,20
- 设某哈夫曼树中有个结点,则该哈夫曼树中有( )个叶子结点 {{ select(6) }}
- 99
- 100
- 101
- 102
- 十进制下的无限循环小数(不包括循环节内的数字均为或均为的平凡情况),在二进制下有可能是( )。 {{ select(7) }}
- 无限循环小数(不包括循环节内的数字均为0或均为9的平凡情况)
- 无限不循环小数
- 有限小数
- 整数
- 设分别代表三进制下的一位数字,若等式在三进制下成立,那么同样在三进制下,等式也成立 。 {{ select(8) }}
- YXZ
- ZXY
- XYZ
- XZY
- 通过分治算法解决输入大小为 N 的问题,以下方法中,( )的效率是最差的。 {{ select(9) }}
- 分成2个规模为N/3的子问题,并且完成其中的一个步骤需要的时间
- 分成2个规模为N/3的子问题,并且完成其中的一个步骤需要的时间
- 分成3个规模为N/2的子问题,并且完成其中的一个步骤需要的时间
- 分成3个规模为N/3的子问题,并且完成其中的一个步骤需要的时间
- 使用邻接表存储图,借助队列优化后,宽度优先搜索的时间复杂度和辅助空间复杂度为() {{ select(10) }}
- ,
- ,
- ,
- ,
- 一棵二叉树的前序遍历序列是,后序遍历序列是,则根结点的左子树的结点个数可能是( ) {{ select(11) }}
- 2
- 3
- 4
- 5
- 现有一只青蛙,初始时在 号荷叶上。当它某一时刻在 号荷叶上时,下一时刻将等概率地随机跳到 号荷叶之一上,直至跳到 号荷叶为止。当 时,平均一共 跳 次;当 时,平均一共跳 次。则当 时,平均一共跳( )次 {{ select(12) }}
- 3.5
- 37/12
- 47/12
- 1/4
- 完全二叉树的结点个数为,则它的叶结点个数为( ) {{ select(13) }}
- 设栈S的初始状态为空,元素依次入栈,以下出栈序列不可能出现的有( ) {{ select(14) }}
- a, b, c, e, d, f, g
- b, c, a, f, e, g, d
- a, e, c, b, d, f, g
- d, c, f, e, b, a, g
- 设全集,集合,,,那么集合为( ) {{ select(15) }}
- {c,e}
- {d,e}
- {e}
- {c,d,e}
二、 阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填 T,错误填F;除特殊说明外,判断题1.5分,选择题3分,共计40分)
1)
1. #include<iostream>
2. #include<cstring>
3. using namespace std;
4. int main(){
5. int i,n,jr,jw,jb;
6. char ch1;
7. char ch[22];
8. scanf("%d",&n);
9. scanf("%s",ch);
10. jr=0;
11. jw=n-1;
12. jb=n-1;
13. while(jr<=jw){
14. if(ch[jw]=='R'){
15. ch1=ch[jr];
16. ch[jr]=ch[jw];
17. ch[jw]=ch1;
18. jr++;
19. }else if(ch[jw]=='W'){
20. jw--;
21. }else{
22. ch1=ch[jw];
23. ch[jw]=ch[jb];
24. ch[jb]=ch1;
25. jw--;
26. jb--;
27. }
28. }
29. printf("%s\n",ch);
30. return 0;
31. }
判断题
- 对于一个输入,字符串中字母的排列顺序不影响输出 {{ select(16) }}
- 正确
- 错误
- 如果输入字符只有RWB三种,则最终输出的结果所有的R一定在最左边 {{ select(17) }}
- 正确
- 错误
- 将13行的jw换成jb,与原输出结果区别在于是W和B的位置交换了 {{ select(18) }}
- 正确
- 错误
- 如果输入不止RWB三种字符,则在结果中其他字符一定在最后 {{ select(19) }}
- 正确
- 错误
选择题
- 输入8 RWBBBERW,则输出为( ) {{ select(20) }}
- RRWWBBBE
- RRBBBEWW
- RRWWEBBB
- RREBBBWW
- (本题4分) 将 while 循环中所有的 jw 换成 jb,jb 换成 jw,则20题的输出为( ) {{ select(21) }}
- RRWWBBBE
- RRBBBEWW
- RRWWEBBB
- RREBBBWW
2)
1. #include<iostream>
2. #include<cstring>
3. using namespace std;
4. int main(){
5. int i,j,s,sp1;
6. int p;
7. int a[11];
8. sp1=1;
9. a[1]=2;
10. j=2;
11. while(sp1<10){
12. j++;
13. p=1;
14. for(i=2;i<=j-1;i++)
15. if(j%i==0)
16. p=0;
17. if(p){
18. sp1++;
19. a[sp1]=j;
20. }
21. }
22. j=2;
23. p=1;
24. while(p){
25. s=1;
26. for(i=1;i<=j;i++)
27. s*=a[i];
28. s++;
29. for(i=2;i<=s-1;i++)
30. if(s%i==0)
31. p=0;
32. j++;
33. }
34. cout<<s<<endl;
35. return 0;
36. }
判断题
- a数组中保存着前10个质数 {{ select(22) }}
- 正确
- 错误
- 将14行的 i<=j-1 修改成 i<j-1 ,答案不会发生改变 {{ select(23) }}
- 正确
- 错误
- 该程序24行的 while(p) 语句会执行六次 {{ select(24) }}
- 正确
- 错误
- 将26行的 i<=j 修改成 i<j ,答案会发生改变 {{ select(25) }}
- 正确
- 错误
选择题
- 最终的输出结果为( ) {{ select(26) }}
- 30031
- 2311
- 510511
- 211
- 如果将 s++ 改为 s+=17 ,则最终输出结果为( ) {{ select(27) }}
- 30047
- 2327
- 510527
- 227
3)
1. #include<iostream>
2. using namespace std;
3. int n;
4. int count(int n)
5. {
6. if (n==1) return 0;
7. else if (n%2==0)
8. return count(n/2)+1;
9. else
10. return count(n*3+1)+1;
11. }
12. int main()
13. {
14. cin>>n;
15. cout<<count(n);
16. return 0;
17. }
判断题
- 存在一个输入使得该程序不能终止 {{ select(28) }}
- 正确
- 错误
- 对于所有的如果有,那么 count(i) 的递归次数一定比 count(j) 的递归次数要少 {{ select(29) }}
- 正确
- 错误
选择题
- 如果输入为,函数调用次数为( ) {{ select(30) }}
- 1
- 2
- 3
- 4
- 如果输入为,函数调用次数为( ) {{ select(31) }}
- 9
- 11
- 13
- 15
- 如果输入为,输出为( ) {{ select(32) }}
- 44
- 45
- 46
- 47
- 如果将第7行改为 n%2==1 ,输入为14,输出为( ) {{ select(33) }}
- 4
- 8
- 12
- 16
三、完善程序(单选题,每小题3分,共计30分)
1)给定一个长度为的无序正整数序列,以及另一个数,接下来以类似快速排序的方法找到序列中第大的数(关于第大的数:例如序列中第大的数是)。
1. #include <stdlib.h>
2. #include <stdio.h>
3.
4. int a[1000001],n,ans = -1;
5.
6. void swap(int *a,int *b) {
7. int c;
8. c = *a;
9. *a = *b;
10. *b = c;
11. }
12. int FindKth(int left, int right, int n) {
13. int tmp,value,i,j;
14. if (left == right) return left;
15. tmp = rand()% (right - left) + left;
16. swap( &a[tmp], &a[left] );
17. value = ① ;
18. i = left;
19. j = right;
20. while (i < j) {
21.
22. while (i < j && ② ) j --;
23. if (i < j) {
24. a[i] = a[j];
25. i ++;
26. } else break;
27. while (i < j && ③ ) i ++;
28. if (i < j) {
29. a[j] = a[i];
30. j - -;
31. } else break;
32. }
33. a[i] = value;
34. if (i < n) return FindKth( ④ );
35. if (i > n) return FindKth( ⑤ );
36. return i;
37. }
38.
39. int main() {
40. int i;
41. int m = 1000000;
42. for (i = 1; i <= m; i ++) scanf("%d", &a[i]);
43. scanf("%d", &n);
44. ans = FindKth(1,m,n);
45. printf("%d\n", a[ans]);
46. return 0;
47. }
34.①处应填( ) {{ select(34) }}
- a[tmp]
- a[left]
- a[right]
- a[1]
35.②处应填( ) {{ select(35) }}
- a[j]<value
- a[j]>value
- a[i]<a[j]
- a[i]>a[j]
36.③处应填( ) {{ select(36) }}
- a[i]<value
- a[i]>value
- a[i]<a[j]
- a[i]>a[j]
37.④处应填( ) {{ select(37) }}
- left,i,n
- left,i-1,n
- i+1,right,n
- i,right,n
38.⑤处应填( ) {{ select(38) }}
- left,i,n
- left,i-1,n
- i+1,right,n
- i,right,n
- 有一些长度相等的等差数列(数列中每个数都为 的整数), 设长度均为,将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数,问原先,最大可能为多大?先读入一个数,再读入个数,代表打乱后的数。输出等差数列最大可能长度。
1. #include <stdio.h>
2. int hash[60];
3. int n, x, ans, maxnum;
4.
5. int work(int now) {
6. int first, second, delta, i;
7. int ok;
8. while ( ① && !hash[now])
9. ++now;
10. if (now > maxnum)
11. return 1;
12. first = now;
13. for (second = first; second <= maxnum; second++)
14. if (hash[second]) {
15. delta = ②;
16. if (first + delta * ③ > maxnum) break;
17. if (delta == 0)
18. ok = ( ④ );
19. else {
20. ok = 1;
21. for (i = 0; i < ans; i++)
22. ok = ok && (hash[first+delta*i]);
23. }
24. if (ok) {
25. for (i = 0; i < ans; i++)
26. hash[first+delta*i]--;
27. if (work(first))
28. return 1;
29. for (i = 0; i < ans; i++)
30. hash[first+delta*i]++;
31. }
32. }
33. return 0;
34. }
35.
36. int main() {
37.
38. int i;
39.
40. memset(hash, 0, sizeof(hash));
41. scanf("%d", &n);
42. maxnum = 0;
43. for (i = 0; i < n; i++) {
44. scanf("%d", &x);
45. hash[x]++;
46. if (x > maxnum)
47. maxnum = x;
48. }
49. for (ans = n; ans >= 1; ans--)
50. if ( n%ans==0 && ⑤) {
51. printf("%d\n", ans);
52. break;
53. }
54. return 0;
55. }
39.①处应填( ) {{ select(39) }}
- now<maxnum
- now<=maxnum
- now>=maxnum
- now>maxnum
40.②处应填( ) {{ select(40) }}
- first-second
- second+first
- second-first
- maxnum-second
41.③处应填( ) {{ select(41) }}
- ans-1
- ans
- ans+1
- max(first,ans)
42.④处应填( ) {{ select(42) }}
- hash[first]<ans
- hash[first]>=ans
- delta<ans
- delta>ans
43.⑤处应填( ) {{ select(43) }}
- work(0)
- work(ans)
- work(n)
- work(n-ans)
Related
In following contests: