#B. [NOI蓝图杯] 八月月赛-全真模拟赛初赛

A B C D E F G H I J
    Type: Objective

[NOI蓝图杯] 八月月赛-全真模拟赛初赛

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

单项选择

1), NOI官网的域名是() {{ select(1) }}

  • www.noi.cn
  • www.ccf.org.cn
  • www.noi.com
  • www.noip.cn

2), 以下关于编程语言说法正确的是() {{ select(2) }}

  • C++比 Python高级,所以C++是高级语言,而Python不是
  • PHP是世界上最好的编译型语言
  • 只有机器语言才可以被计算机直接执行
  • 可以选择使用C语言参加 CSP-J/S 2022

3), 《九章算术》是中国古代的数学专著,其内包含很多好用的算法和数学知识。例如:”可半者半之,可半者,副置分母子之数,以少减多,更相减损,求其等也。以等数约之“就解决了一类常见的数学问题,这类问题现在常用( )来解决。{{ select(3) }}

  • 辗转相除法
  • 中国剩余定理
  • 分治法
  • 二分法

4), 6个小朋友站在一排,其中A和B必须相邻,C和D必须不相邻,则有( )种不同排列方法? {{ select(4) }}

  • 36
  • 72
  • 144
  • 120

5), 新学期将至, 高新OI社区准备花费4万8千元的经费用于采购新电脑,现有4种电脑可供选择,每种电脑的价格均为4000元,为了满足同学们的需要,每种电脑都至少要采购2台,且必须把经费全部花光,请问共有多少种不同的采购方案? () {{ select(5) }}

  • 165
  • 220
  • 56
  • 35

6), 以下关于数据结构的说法正确的是() {{ select(6) }}

  • 使用链表存储数据,可以随机访问任一元素
  • 对于一个栈,现有两个数据x和y,只要x比y先入栈,那么y就一定比x先出栈
  • 对于一个队列,现有两个数据x和y,只要x比y先入队,那么x就一定比y先出队
  • 二叉树是线性数据结构

7), 求8位二进制补码00100110对应的十进制数() {{ select(7) }}

  • -89
  • 90
  • 89
  • 38
  1. 有9台完全相同的空调需要打包销售,要求将这9台空调分成3组,每组至少一台空调。 例如,可以将9台空调分为2+4+3,也就是一组有2台空调,另一组有4台空调,还有一组有3台空调。要注意,无需考虑分成的组的顺序,也就是说2+4+3和4+2+3是同一个的分组方案。请问有多少种分组方案() {{ select(8) }}
  • 6
  • 7
  • 28
  • 36

9), 根据以下代码推断f(1)的值为()

int f(int x)
{
	if(x>100) return x-100;
	else if(x>50) return f(x+50);
	else return f(x+10)+f(x+20);
}

{{ select(9) }}

  • 48
  • 103
  • 53
  • 63

10), 以下关于树的说法正确的是() {{ select(10) }}

  • 约定独根树的高度为1,那么高度为6的二叉树最多有63个节点
  • 二叉树就是每个节点都有恰好两个子节点的有根树
  • 无向无环图被称为树
  • 除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树,被称为完全二叉树

11), 对于前缀表达式 / + * 7 + 4 6 2 8,下面的后缀表达式的值与其不相等的是() {{ select(11) }}

  • 9 1 - 10 * 1 + 9 /
  • 9 10 3 - * 7 /
  • 2 5 + 9 * 7 /
  • 15 3 / 9 * 3 /

12), 某算法的计算时间表示为递推关系式T(n)=T(n/2) +n/2 (n为正整数)及T(0) =1,则该算法的时间复杂度为() {{ select(12) }}

  • O(logn)
  • O(nlogn)
  • O(n)
  • O(n^2)

13), 一棵二叉搜索树的后序遍历为1 3 5 4 2,求出它的前序遍历() {{ select(13) }}

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

14), 在下面的有向图中,从点a出发做BFS (广度优先搜索),以下哪个不可能是BFS序(BFS过程中遍历到点的顺序) () img {{ select(14) }}

  • a b d c e f
  • a d b f c e
  • a b d c f e
  • a d b c f e

15), 古人洞悉天机,创立了划分时间的“三元九运”体系:以一百八十年作为一个正元,每一正元分为上元、中元、下元;每元六十年,再分为三个运,每运为二十年,即上元是一运、二运、三运,中元是四运、五运、六运,下元是七运、八运、九运。从而构成了完整的三元和九运体系。已知2022年处于八运, 问1922年处于哪个元运之中() {{ select(15) }}

  • 上元, 二运
  • 上元, 三运
  • 中元, 四运
  • 下元, 八运

阅读程序

#include <cstdio>

#define base 2
#define Y 1799

using namespace std;

int d_y[3010], d_m[13];
int sum_y[3010], sum_m[13];

int check (int i)	
{
	return !(i % 400) || i% 100 && !(i % 4);
}

void init()
{
	for(int i=Y+1; i<=3000; i++)
	{
		d_y[i] = 365 + check(i);
		sum_y[i] = sum_y[i-1] + d_y[i];
	}
	for(int i=1; i<=12 ; i++)
	{
		if((i<8 && i&1) || (i>7 && !(i&1))) 
		{
			d_m[i] = 31;
		}
		else if(i == 2) 
		{
			d_m[i] = 28;
		}
		else 
		{
			d_m[i] = 30;
		}
		sum_m[i] = sum_m[i-1] + d_m[i];
	}
}


int main()
{
	init();
	int y, m, d, ans;
	scanf("%d%d%d", &y, &m, &d);
	ans = sum_y[y-1] + sum_m[m] - d_m[m] + d + base;
	if(check(y) && m > 2)
	{
		ans++;
	}
	printf("%d\n", ans % 7);
	return 0;
}

程序满足输入y>=1800y>=1800, m, d均合法。

判断题

16), 将Y与base分别替换为1795和4时,对程序输出没有影响() {{ select(16) }}

  • true
  • false

17), 当y=4000y=4000时,程序仍能输出正确结果() {{ select(17) }}

  • true
  • false

18), 将第16 行的(i<8 && i & 1) ||(i> 7 &&!(i & 1))改成(i <= 8 && i & 1) ||(i>=7 && !(i & 1)),对答案没有影响() {{ select(18) }}

  • true
  • false

19), 将Y与base分别替换为1798和3时,对程序输出没有影响() {{ select(19) }}

  • true
  • false

选择题

20), 输入为1801 1 4时,程序输出为() {{ select(20) }}

  • 7
  • 4
  • 0
  • 1

21), 输入为2019 3 1时,程序输出为() {{ select(21) }}

  • 3
  • 4
  • 5
  • 6
#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n, m, a[N],b[N],c[N],d[N];

int main()
{
	scanf("%d", &n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
	}
	for(int i=1;i<=n;i++)		//第12行 
	{
		a[i]=i+1,b[i]=i-1;
	}
	sort(c+1, c+n+1);			//第14行 
	for(int i=1,x;i<=n; i++)
	{
		scanf("%d", &x);
		if(d[x]) continue;			//第18行 
		d[x]=1;
		a[b[x]]=a[x];				//第20行 
		b[a[x]]=b[x];				//第21行 
		if(b[x]) 
		{
			printf("%d ",c[b[x]]);
		}
		if(a[x]!=n+1) 
		{
			printf("%d",c[a[x]]);
		}
		printf("\n");
	}
	printf("END");
	return 0;
}

输入的n是小于等于10510^5的正整数, c[i]是小于等于n的互不相同的正整数, x是小于等于n的正整数。 以下题目均认为输入符合上述条件。

判断题

22), 该程序有可能会发生数组越界。() {{ select(22) }}

  • true
  • false

23), 在执行完第14行后的任何时刻,对于任意0到n+1之间(包括0与n+1)的i,均有a[i]严格大于b[i]。() {{ select(23) }}

  • true
  • false

24), 该程序不会输出任何空行。() {{ select(24) }}

  • true
  • false

选择题

25), 该程序的时间复杂度是() {{ select(25) }}

  • O(nlogn)O(nlogn)
  • O(n)O(n)
  • O(n2)O(n^2)
  • O(logn)O(logn)

26), 假设输入的数据为5 2 3 1 5 4 4 2 1 4 3,则在输出结果中,数字3出现的次数为() {{ select(26) }}

  • 2次
  • 3次
  • 4次
  • 5次

27), 以下哪种修改方式不会使输出发生变化() {{ select(27) }}

  • 删去第18行
  • 将第12行改为 for(int i=2; i<=n-1; i++)
  • 将第20行与21行交换
  • 删去第14行
#include<cstdio>
#include<iostream>
using namespace std;
int n,m, a[50][50], c[50][50];
int main()
{
	scanf ("%d%d", &n, &m);
	for(int i=0;i<=n;i++)		//第7行 
	{
		a[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			a[i][j]=a[i-1][j]+j*a[i-1][j-1];
		}
	}
	for(int i=0;i<=n;i++)
	{
		c[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			c[i][j]=c[i-1][j]+c[i-1][j-1];
		}
	}
	int ans=0;
	for(int k=1;k<=n-m; k++)
	{
		ans+=a[n][k]*c[n-k-1] [n-k-m];
	}
	printf("%d\n", ans);
	return 0;
}

判断题

28), 若输入n=7,m=0,则此程序会发生数组越界() {{ select(28) }}

  • true
  • false

29), 假设输入n=10,m=5,若把第7行的i=0改成i=1,则同样输入的输出结果不变() {{ select(29) }}

  • true
  • false

30), 当n=9,0<m<=n时, m越大,输出结果越小() {{ select(30) }}

  • true
  • false

选择题

31), 输入n=4,m=2,输出为() {{ select(31) }}

  • 4
  • 16
  • 20
  • 24

32), 输入n=7,m=4,输出为() {{ select(32) }}

  • 77
  • 448
  • 497
  • 805

33), 下列哪个情况下的输出等于输入的n () {{ select(33) }}

  • m=n-1 且1<n<50
  • m=1 且 1<n<10
  • n=m-1 且1<m<50
  • n=m=1

完善程序

[特殊遍历]输入一个矩阵, 按照右上, 左下对角线的蛇形顺序遍历输出矩阵中的值, 例如, 给出的矩阵为:

1 2 3 4 5 6 7 8 9

则输出为: 1 2 4 7 5 3 6 8 9

img

#include <bits/stdc++.h>

using namespace std;

int mat[105][105];
int res[10005];

int main() 
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i= 0; i<n; i++) 
	{
		for(int j = 0; j < m; j ++)
		{
			scanf("%d", &mat[i][j]);
		}
	}
	int cnt = 0;
	for(int i=0; i < m + n - 1; i++)
	{
		int x, y;
		if(i%2==1)
		{
			if(i < m)
			{
				x = 0;
				y = i;
			}
			else 
			{
				①;
				y = m - 1;
			}
			while(x < n && y >= 0)
			{
				res[cnt++] = mat[x][y];
				②;
			}
		}
		else
		{
			if(i < n) 
			{
				x = i;
				y = 0;
			}
			else
			{
				x = n - 1;
				③; 
			}
			while(④)
			{
				res[cnt++] = mat[x][y];
				x--;
				y++;
			}
		}
	}
	for(int i = 0; ⑤; i ++)
	{
		printf("%d ", res[i]);
	}
	return 0;		
}

34), ①处应填() {{ select(34) }}

  • x=m - i + 1
  • x= n - i+ 1
  • x = i - m + 1
  • x =i - n + 1

35), ②处应填() {{ select(35) }}

  • x++, y--
  • x--, y ++
  • x++, y++
  • x--, y--

36), ③处应填() {{ select(36) }}

  • y= m- i+ 1
  • y= n- i+ 1
  • y= i- m + 1
  • y = i- n+ 1

37), ④处应填() {{ select(37) }}

  • x > 0 && y < m
  • x >= 0 && y < m
  • x < n && y > 0
  • x <= n && y > 0

38), ⑤处应填( ) {{ select(38) }}

  • i < cnt
  • i <= cnt
  • i >= cnt
  • i*i < cnt

(尺取法)尺取法通常是对数组保存一对下标,即所选取的区间的左右端点,然后根据实际情况不断地推进区间左右端点以得出答案。给定字符串s,与一个长度为5的数组aia_i。字符串仅包含A, B,C,D,E 五种大写字母,要求求出原字符串中有多少个子串满足字母A至少有a1a_1个,字母B至少有a2a_2个,……,字母E至少有a5a_5个。s的子串指从s中取出一段连续的字符串,例如ABC是DABCE的子串, ABC不是DADBC的子串,字符串本身可以是自己的子串。 以下程序使用尺取法求解,数据保证s的长度大于0且小于等于10510^5, 1≤a≤1051 \le a \le 10^5。试补全程序。

#include <bits/stdc++.h>

using namespace std;

string s;
long long ans;
int cnt [5];

bool check ()
{
	for(int i=0;i<5;i++)
	{
		if(①) return false;
	}
	return true;
}

int main()
{
	cin>>s;
	for(int i=0;i<5;i++)
	{
		cin>>cnt[i];
	}
	int n=s.size();
	for(int l=0, r=-1;l<n;l++)
	{
		while(②)
		{
			r++;
			③; 
		}
		if (check()) 
		{
			ans += ④; 
		}
		⑤; 
	}
	cout<<ans;
	return 0;
}

39), ①处填() {{ select(39) }}

  • cnt[i]>=0
  • cnt[i]<0
  • cnt[i]>0
  • cnt[i]<=0

40), ②处填() {{ select(40) }}

  • r+1<n&&!check()
  • r<n&&!check()
  • r+1<n&&check()
  • r<n&&check ()

41), ③处填() {{ select(41) }}

  • cnt[s[r]- 'A']++
  • cnt[s[r]- 'A']--
  • cnt[s[r-1]- 'A']++
  • cnt[s[r-1]- 'A']--

42), ④处填() {{ select(42) }}

  • n-r
  • n-r+1
  • r-l
  • n-l+1

43), ⑤处填() {{ select(43) }}

  • cnt[s[r]- 'A']++
  • cnt[s[r]- 'A']--
  • cnt[s[l]- 'A']++
  • cnt[s[l]- 'A']--

[NOI蓝图杯] 八月月赛-复现赛

Not Attended
Status
Done
Rule
Ledo
Problem
10
Start at
2023-8-8 0:00
End at
2023-9-1 4:00
Duration
580 hour(s)
Host
Partic.
28
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 18ms
  • Powered by Hydro v4.9.27 Community