#C1216. 2024CSPJ初赛模拟题(七)

2024CSPJ初赛模拟题(七)

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1.现有一张分辨率为 2048 * 512 像素的 16 位真彩色图像。请问要存储这张图像， 需要多大 的存储空间？（ ）。 {{ select(1) }}

  • 2MB
  • 4MB
  • 6MB
  • 8MB

2.已知 A=B=true，C=false，以下逻辑表达式恒为假的是（ ）。 {{ select(2) }}

  • (A∨┐B)∧B∧┐C
  • A∨B∧┐C∨(A∨┐B)
  • A∧C∨B∧C
  • A∨(┐B∧C)

3.二进制数 110.01 对应的十进制数是（ ）。 {{ select(3) }}

  • 6.75
  • 6.5
  • 6.25
  • 5.25

4.二进制转格雷码规则：将二进制右移一位后与原二进制异或,则二进制数 110011 对应的格雷码（）。 {{ select(4) }}

  • 101000
  • 101010
  • 010101
  • 110101

5.以下哪个排序算法的平均时间复杂度不是 O(n^2)（ ）。 {{ select(5) }}

  • 选择排序
  • 冒泡排序
  • 插入排序
  • 归并排序

6.前缀表达式 -*ab*c+de 的中缀表达式为（ ），其中+、-、*为运算符。 {{ select(6) }}

  • a*b-c*(d+e)
  • a*b-(d+e)*c
  • (d+e)*a-a*b
  • c*(d+e)-a*b

7.对于入栈顺序为 1，2，3，4，5 的序列，下列（ ）不是合法的出栈序列。 {{ select(7) }}

  • 1,2,3,4,5
  • 2,3,4,1,5
  • 5,3,4,2,1
  • 1,2,5,4,3

8.下列有关于栈与队列的说法错误的是（ ）。 {{ select(8) }}

  • 队列具有先进先出的特点，也被称为 FIFO 表
  • 栈和队列都是线性表，所以只能采用顺序存储
  • 入栈序列和出栈序列可能不同
  • 当队列发生假溢出时，可以使用循环队列

9.已知二叉树的中根遍历为 BDAGECF，后根遍历为 DBGEFCA，则该二叉树的叶子结点有多少 个（ ）。 {{ select(9) }}

  • 2
  • 3
  • 4
  • 5

10.包含数字 1 的三位自然数有（ ）个。 {{ select(10) }}

  • 268
  • 260
  • 252
  • 244

11.有如下递归函数，调用 solve（10，3）的返回值为（ ）。

int solve(int n,int m)
	if (n == 1) return 1;
	else return (f(n - 1, m) + m - 1) % n + 1;

{{ select(11) }}

  • 4
  • 5
  • 6
  • 7

12.从 10 个人中选 4 个人参加歌唱比赛，其中甲乙至少有一人被选上有（ ）种情况。 {{ select(12) }}

  • 285
  • 140
  • 210
  • 196

13.高度为 h 的均衡的二叉树是指：如果去掉叶结点及相应树枝，它应该是高度为 h-1 的满 二叉树，已知树根的深度为 1，如果某均衡的二叉树有 1050 个结点，则该树的高度为（ ）。 {{ select(13) }}

  • 9
  • 10
  • 11
  • 12

14.具有 4 个顶点的无向完全图，其生成树有（ ）个。 {{ select(14) }}

  • 10
  • 12
  • 14
  • 16

15.由 0，1，2，3，4 组成没有重复数字的三位数，其中百位数字小于个位数字的共有( )个。 {{ select(15) }}

  • 60
  • 48
  • 30
  • 18

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √ , 错误填×; 除 特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

01 #include <iostream> 
02 using namespace std;
03 int n;
04 int a[1000];
05 int z(int x) 
06 {
07     int ret = 0;
08     for (; x; x >>= 1) ret++;
09     return ret; 
10 }
11 int y(int x) 
12 {
13     return x|(x-1); 
14 }
15 int main() 
16 {
17     cin >> n;
18     for (int i = 0; i < n; ++i) cin >> a[i];
19     for (int i = 0; i < n; ++i)
20        cout << y(a[i]) - z(a[i]) << ' ';
21     cout << endl;
22     return 0;
23 }
  1. 输出的结果不可能为负数（ ）。 {{ select(16) }}
  • 正确
  • 错误
  1. 输入的a[i]必须全为非负整数，否则程序将陷入死循环（ ）。 {{ select(17) }}
  • 正确
  • 错误
  1. 当输入为 1 512002 时，输出为 512000（ ）。 {{ select(18) }}
  • 正确
  • 错误
  1. 将第 13 行的(x-1)改为(x+1)，输入的 a[i]全为偶数时，结果不变（）。 {{ select(19) }}
  • 正确
  • 错误
  1. 当输入 2 65536 2147483647 时，输出为（）。 {{ select(20) }}
  • 65520 32
  • 65520 -32
  • 131054 2147483616
  • 131054 -2147483616
01 #include <iostream> 
02 #include <queue>
03 #include <vector>
04 using namespace std; 
05
06 int n, e, d[10005];
07 vector<int> vec[10005];
08 int k = 1, ans[10005]; 
09
10 void topological() 
11 {
12  queue<int> q;
13  for (int i = 1; i <= n; i++)
14    if (d[i] == 0)
15      q.push(i);
16  while (!q.empty()) 
17  {
18    int cur = q.front();
19    ans[k++] = cur;
20     if (k == n + 1) 
21    {
22     for (int i = 1; i < k; i++)
23        cout << ans[i] << " ";
24      return ; 
25    }
26    q.pop();
27    for (int i = 0; i < vec[cur].size(); i++) 
28    {
29      int t = vec[cur][i];
30      d[t]--;
31     if (d[t] == 0)
32       q.push(t); 
33    }
34  }
35  cout << -1; 
36 }
37
38 int main() 
39 {
40  cin >> n >> e;
41  for (int i = 1; i <= e; i++) 
42  {
43    int x, y;
44    cin >> x >> y;
45    d[y]++;
46    vec[x].push_back(y); 
47  }
48  topological();
49  return 0; 
50 }

假设输入的 n，e，x，y 均是不超过 10000 以内的正整数，完成下面的判断题和单选题：

21、对于输入的任意的 x1,y1和 x2,y2 交换输入顺序会影响结果。( ) {{ select(21) }}

  • 正确
  • 错误

22、第 24 行的 return 语句去掉也不影响结果。( ) {{ select(22) }}

  • 正确
  • 错误

23、第 46 行 vec[x].push_back(y)可以修改为 vec[x] = y，不影响结果。( ) {{ select(23) }}

  • 正确
  • 错误

24、该代码的时间复杂度为（ ）。 {{ select(24) }}

  • O(n)
  • O(elogn)
  • O(n+e)
  • O(ne)

25、若输入

6 8
1 2
1 4
2 6
3 2
3 6
5 1
5 6
5 2

则输出为( )。 {{ select(25) }}

  • 3 5 1 2 4 6
  • 5 1 4 3 2 6
  • 2 4 6 1 3 5
  • 3 5 1 4 2 6

26、以下哪种输入情况会输出-1（ ）。 {{ select(26) }}

  • 4 6 1 2 1 3 2 3 4 1 4 2 4 3
  • 4 6 1 2 1 3 1 4 2 3 4 2 4 3
  • 4 6 1 2 1 3 1 4 3 2 3 4 4 2
  • 4 6 1 2 1 3 2 3 3 4 4 1 4 2
01 #include <iostream> 
02 using namespace std;
03 int q[500005], head, tail;
04 int sum[500005], n, m, k, mx = -2147483648u;
05 int main() 
06 {
07     cin >> n >> m;
08     for (int i = 1; i <= n; ++i) 
09     {
10         cin >> k;
11         sum[i] = sum[i - 1] + k; 
12     }
13     q[tail] = 0;
14     tail++;
15     for (int i = 1; i <= n; ++i) 
16     {
17          while (head < tail && i - q[head] > m) 
18         {
19               head++; 
20         }
21         mx = max(mx, sum[i] - sum[q[head]]);
22        while (head < tail && sum[i] <= sum[q[tail - 1]]) 
23        {
24            tail--; 
25        }
26        q[tail] = i;
27        tail++; 
28     }
29     cout << mx;
30     return 0; 
31 }

保证 1<=n<=5*10^5

27.该算法最准确的时间复杂度分析结果为 O(n^2)。 () {{ select(27) }}

  • 正确
  • 错误

28.当输入的 k 均为负数时，输出为输入的最大值。 () {{ select(28) }}

  • 正确
  • 错误

29.当输入的 n 等于 m 时，输出为 n 个数的和。 () {{ select(29) }}

  • 正确
  • 错误

30.当输入为 6 4 1 -3 5 1 -2 3 时，输出为（）。 {{ select(30) }}

  • 6
  • 7
  • 11
  • 13

31.当输入的 n=100，m=50，k 为从 1 开始每次增加 2 的奇数时，输出为()。 {{ select(31) }}

  • 15000
  • 15050
  • 7500
  • 7550

32.当输入均为 n 时，输出为（）。 {{ select(32) }}

  • n
  • 2*n
  • n^2
  • 2^n

三、完善程序（单选题，每小题 3 分，共计 30 分）

  1. (等比数列)第一行输入一个正整数 n,第二行输入 n 个整数,判断这些数是否构成等比数 列。

试补全程序。

#include<bits/stdc++.h> 
using namespace std;
int main()
{
	int n, q, pre, now, i; cin >> n;
		①
		②
		pre = now;
    for (i = 3; i <= n; i++) {
        cin >> now; 

	if (③)
		break;
	q = now / pre;
		④ 
}
    if(⑤)
    	cout << "Yes"; 
    else
    	cout << "No"; 	
    return 0;
}

33.①处应填( )。 {{ select(33) }}

  • cin >> pre;
  • cin >> pre >> now;
  • cin >> now;
  • cin >> now >> pre;

34.②处应填( )。 {{ select(34) }}

  • q = 1;
  • q = now / pre;
  • q = 0;
  • q = pre / now;

35.③处应填( )。 {{ select(35) }}

  • now != pre*q
  • now == pre*q
  • now < pre
  • now > pre

36.④处应填( )。 {{ select(36) }}

  • now = pre;
  • now = q;
  • pre = q;
  • pre = now;

37.⑤处应填( )。 {{ select(37) }}

  • n
  • i > n
  • i < n
  • i <= n
  1. (三分查找) 三分查找是一种查找算法，用于在有序序列中查找特定元素。该算法从序列 中选择一个中心点，将序列分成三个部分，并检查目标值是否在其中一个部分中。如果目标 值在部分中，则查找结束。如果目标值不在部分中，则继续在剩余的两个部分中进行查找。 直到找到目标值，或者查找范围为空。 试补全程序
#include<iostream>
using namespace std;
int a[100000005];
int search(int left, int right, int x) {
	if (①) return -1;
	else if (left + 1 == right || left == right) {
		if (a[left] == x) return left; 
    else if (a[right] == x) return right;
		else return ②;
		 
	}
	int l = (right - left + 1) / 3;
	int lbound = left + l, rbound = right - l;
	if (a[lbound] == x) return lbound;
	else if (x < a[lbound]) return ③;
	else if (a[rbound] == x) return rbound;
    else if (x < a[rbound]) return search(lbound + 1, rbound - 1, x); 
    else return ④;
}

int main() {

    int n, targe;
    cin >> n >> targe;
    for (int i = 1; i <= n; i++) cin >> a[i]; 
    cout << ⑤;
	return 0; 
}

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

  • left >= right
  • left > right
  • right >= left
  • right > left

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

  • -1
  • 0
  • left - 1
  • left + 1

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

  • search(1, lbound, x)
  • search(left, lbound - 1, x)
  • search(left, n, x)
  • search(left, lbound - l, x)

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

  • search(rbound, n, x)
  • search(1, right, x)
  • search(rbound + l, right, x)
  • search(rbound + 1, right, x)

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

  • search(0, n - 1, targe)
  • search(0, n - 1, 0)
  • search(1, n, targe)
  • search(1, n, 0)
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 41ms
  4. Powered by Hydro v4.17.4 Community