#A. 初赛模拟题11

A
    Type: Objective

初赛模拟题11

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), 新学期将至,复旦大学算法协会准备花费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), 一棵二叉搜索树的后序遍历为13542,求出它的前序遍历() {{ 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']--

初赛模拟题11

Not Attended
Status
Done
Rule
OI
Problem
1
Start at
2024-9-1 14:00
End at
2024-9-1 15:00
Duration
1 hour(s)
Host
Partic.
12
  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