第三套

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

1. 以下关于 CCF 组织举办的竞赛说法不正确的是。{{ select(1) }}

• CSP 认证每年举办一次，分“入门组”和“提高组”，分两轮进行。
• NOIP 竞赛有悠久的历史，最早于 1996 年开始举办。
• NOI 竞赛始于 1983 年，该竞赛不仅可以现场参加，还可以通过网上报名参加同步赛。
• 各省的省队选拔独立进行，分两轮，初中选手只拥有 E 类名额。

2. 以下关于个人计算机操作系统的说法正确的是。{{ select(2) }}

• Bill Gates，他创办的 Microsoft 公司开发了 Linux 系列系统。
• Steve Jobs，他的苹果公司开发了 IOS 系统。
• 目前 Linux 和 Windows 系统都是开源的，网上都能搜索并下载。
• 除了以上提到的所有操作系统，还有 DOS，Unix 等系统。Windows 使用最广。

3. 十进制表达式 (3×512+7×64+4×8+3)+1 的结果以二进制形式表示为。{{ select(3) }}

• 1011110010
• 11111100100
• 111110100011
• 11111101101

4. 计算机能直接执行的指令包括两部分，他们是。{{ select(4) }}

• 源操作数与目标操作数
• 操作码与操作数
• ASCII 码与汉字代码
• 数字与字符

5. 以下程序段：

for (i = 1; i <= n; i++) a[i] = i;
for (i = 2; i <= n; i++)
    if(i == a[i]) {
	 	for (j = 1; j * i <= n; j++)
		    a[j * i] = a[j * i] / i * (i - 1);
	}

的作用是求出 $1$ 至 $n$ 的所有{{ select(5) }}。

• 质数
• 整数的最大因数
• 整数的因数个数
• 整数的 $ϕ(i)$

6. 关于 BIOS 下面说法正确的是{{ select(6) }}。

• BIOS 一般由操作系统厂商来开发完成。
• BIOS 里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。
• BIOS 是计算机基本输入输出系统软件的简称。
• BIOS 能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

7. 命题 $P→Q$ 可读做 $P$ 蕴含 $Q$， 其中 $P$、$Q$ 是两个独立的命题。只有当命题 $P$ 成立而命题 $Q$ 不成立时，命题 $P→Q$ 的值为 false，其它情况均为 true。与命题 $P→Q$ 等价的逻辑关系式是。{{ select(7) }}

• $﹁ P∧ Q$
• $P∧ Q$
• $﹁ (P∨ Q)$
• $﹁P∨ Q$

8. 现在有一个集合，里面包含了字符串 zlymAKIOItxdy（不含引号）的所有字符，则请问该集合的所有非空真子集的个数为。{{ select(8) }}

• $4095$
• $4096$
• $4094$
• $2046$

9. 对于完全背包问题（给出 $n$ 种物品和一个容积为 $m$ 的背包，每种物品有无限个，单个大小为 $v_i$，价值为 $w_i$，要求选择适当的物品放入背包，满足大小不超过容积且价值最大），设 $f_i$ 表示用去 $i$ 的空间能获得的最大价值，倒序枚举 $i$ 为使用的空间，正序枚举 $j$ 为物品编号，则可写出动态转移方程。{{ select(9) }}

• f[i] = max(f[i], f[i - w[j]] + v[j])
• f[i] = max(f[i], f[i - v[j]] + w[j])
• f[i] = min(f[i], f[i - w[j]] + v[j])
• f[i] = min(f[i], f[i - v[j]] + w[j])

10. 小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第 $1$ 个航班 准点的概率是 $0.9$，第 $2$ 个航班准点的概率为 $0.8$, 第 $3$ 个航班准点的概率为 $0.9$。如果存在第 $i$ 个（$i=1,2$）航班晚点，第 $i+1$ 个航班准点，则小明将赶不上第 $i+1$ 个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此次旅行成功的概率是。{{ select(10) }}

• $0.5$
• $0.648$
• $0.72$
• $0.74$

11. 以下关于 CSP 非专业级认证与 NOIP 竞赛关系的说法最恰当的是。{{ select(11) }}

• 完全无关
• 组织者相同
• 举办目标相同
• 从属关系，CSP 从属于 NOIP

12. 关于信息学竞赛涉及算法，以下说法不正确的是。{{ select(12) }}

• 搜索分为深度优先和广度优先两种，特点是代码难度低，但都很费时
• 模拟是一种最基本的算法，就是按照题目要求做。广义的模拟还包含其他算法
• 贪心算法类似于“鼠目寸光”，该算法前提是满足“部分最优组成全局最优”
• 动态规划包含了很多类型和优化，动态转移方程是该算法的核心

13. 如图，小圆圈表示网络的结点，结点之间的连线表示它们有网线相联，连线标注的数字表示该段网线单位时间内可以通过的最大信息量，现从结点 B 向结点 A 传递信息，信息可以分开沿不同的路线同时传递，则单位时间内传递的最大信息量为。{{ select(13) }}

• $19$
• $20$
• $24$
• $25$

14. 分辨率为 $1600x900$、$16$ 位色的位图，存储图像信息所需的空间为。{{ select(14) }}

• 2812.5KB
• 4218.75KB
• 4320KB
• 2880KB

15. 情境：一位妈妈生了 $n$ 胞胎，这 $n$ 个孩子长得非常相似，让人无法辨认。一天晚上，妈妈要给这 $n$ 个孩子洗澡。妈妈每次从孩子中抓出一个洗澡，洗完后又把他放回孩子之中，如此重复 $n$ 次。问题：若 $n=10$，则在所有的可能中，恰好只有三个孩子没有洗澡的可能性约为{{ select(15) }}

• $14\%$
• $36\%$
• $31\%$
• $17\%$

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

1	#include<cstdio>
2	#define MAX_N 20
3	#define ll long long
4	using namespace std;
5	int n;
6	long long f[MAX_N][MAX_N];
7	int main()
8	{
9	    scanf("%d",&n);
10	    for(int i=0;i<=n;i++)
11	    {
12	        f[0][i]=1;
13	    }
14	    for(int i=1;i<=n;i++)
15	    {
16	        for(int j=i;j<=n;j++)
17	        {
18	            if(i==j)f[i][j]=f[i-1][j];
19	            else f[i][j]=f[i][j-1]+f[i-1][j];
20	        }
21	    }
22	    cout<<f[n][n]<<endl;
23	    return 0;
24	}

判断题

16. 如果第 $3$ 行的代码缺失，程序会出现编译错误。{{ select(16) }}

• √
• ×

17. 本程序中 $f$ 数组内被改变过的元素的值与 $n$ 无关，即对于不同的 $n$，$f$ 数组中不为 $0$ 的元素值都对应相同。{{ select(17) }}

• √
• ×

18. 若 $n=10$，对于任何 $0\le i\le n$，$f[0][i]=1$。{{ select(18) }}

• √
• ×

19. 若 $n=10$，对于任何 $0\le i\le n$，$f[1][i]=1$。{{ select(19) }}

• √
• ×

选择题

20. （5 分）本程序没有使用的基本算法是{{ select(20) }}

• 模拟
• 递推
• 递归
• 动态规划

21. 对于输入 $6$，本程序输出{{ select(21) }}

• $5$
• $14$
• $42$
• $132$

1	#include<iostream>
2	#include<algorithm>
3	using namespace std;
4	long int n,k,sum[100001],num=1,f[100001];
5	struct ren
6	{
7	   long int ks,js;  
8	};
9	ren z[100001];  
10	int cmp(ren a,ren b)  
11	{  
12	    return a.ks>b.ks;  
13	}  
14	int main()  
15	{  
16	    long int i,j;   
17	    cin>>n>>k;  
18	    for(i=1;i<=k;i++)  
19	    {  
20	        cin>>z[i].ks>>z[i].js;    
21	        sum[z[i].ks]++;  
22	    }  
23	    sort(z+1,z+k+1,cmp);  
24	    for(i=n;i>=1;i--)   
25	    {  
26	        if(sum[i]==0)  
27	        f[i]=f[i+1]+1;  
28	        else for(j=1;j<=sum[i];j++)  
29	        {  
30	            if(f[i+z[num].js]>f[i])  
31	            f[i]=f[i+z[num].js];  
32	            num++;  
33	        }  
34	    }  
35	    cout<<f[1]<<endl;
36	}

22. 本程序使用了贪心算法。{{ select(22) }}

• √
• ×

23. 第 23 行 sort 排序后 z 数组中的元素按 js 元素降序排序。{{ select(23) }}

• √
• ×

24. 以下是对于本代码的一段输入，则对应的输出是 $3$

15 6
1 2
1 6
4 11
8 5
8 1
11 5

{{ select(24) }}

• √
• ×

25. 本代码的 $24$ 行换成 for (i = 1; i <= n; ++i)，可能会引发“数组越界”错误{{ select(25) }}

• √
• ×

选择题

26. 第 $10$ 至 $12$ 行程序定义了一个 cmp 函数以用于 sort 的比较。我们可以用含有以下的一个选项的程序段来定义适用于该结构体类型的小于运算。这个选项是{{ select(26) }}

• this
• operator
• iterator
• it

27. 本程序的时间复杂度是{{ select(27) }}

• $O(n)$
• $O(k)$
• $O(n·\text{log}n)$
• $O(nk)$

//注释：本程序使用一种树形数据结构，实现了将读入的数据按照“左子树<=根<=右子树”的方法建树，并输出树的深度及后序遍历。
1	#include<iostream>
2	using namespace std;
3	struct node
4	{
5	    int data,left,right;
6	};
7	node tree[300010];
8	int n1;
9	int ans;
10	int NNN(int x)
11	{
12	    n++;
13	    tree[n].data=x;
14	    tree[n].left=tree[n].right=0;
15	    return n;
16	}
17	void insert(int x,int& idx)
18	{
19		if(!idx)
20		{
21	        idx=NNN(x);
22	        return ;
23    	}
24      if(x<tree[idx].data)
25          insert(x,tree[idx].left);
26      else    
27          insert(x,tree[idx].right);
28	}
29	void dfs(int idx,int deep)
30	{
31		if(!idx)
32	    {
33	        ans=max(ans,deep);
34          return ;
35      }
36	    dfs(tree[idx].left,deep+1);
37	    dfs(tree[idx].right,deep+1);
38	}
39	void printhx(int idx)
40	{
41	    if(idx)
42	    {
43          printhx(tree[idx].left);
44          printhx(tree[idx].right);
45          cout<<tree[idx].data<<endl;
46      }
47	}
48	int main(){
49      cin>>n1;
50		for(int i=1;i<=n1;i++)
51		{
52      	int x;
53      	cin>>x;
54      	int id=1;
55      	if(i==1)
56         	    NNN(x);
57      	else
58     	        insert(x,id);
59  	}
60  	dfs(1,0);
61  	cout<<"deep="<<ans<<endl;
62  	printhx(1);
63  	return 0;
64	}

判断题

28. 在本程序中，第 $7$ 行的数组必须开到数据范围的结点数的 $4$ 倍以上{{ select(28) }}

• √
• ×

29. 存放树的节点时运用了指针思想 {{ select(29) }}

• √
• ×

30. 程序第 $10$ 至 $16$ 行的 NNN 函数作用是给树增加一个空节点 {{ select(30) }}

• √
• ×

31. 将程序第 $36$ 行和 $37$ 行交换，不会对程序产生影响 {{ select(31) }}

• √
• ×

选择题

32. （5 分）一种树形结构是指 {{ select(32) }}

• 权值线段树
• 树状数组
• 斐波那契堆
• 二叉搜索树

33. 以下是一个对于本程序的输入，则与之对应的输出是

8
1 4 3 9 10 35 2 7

{{ select(33) }}

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

（Qjl 的比赛）Qjl 是一名神犇，他最近出了一场盛大的 AK赛。比赛共含有 $n(1\le n\le 100000)$ 题，由于是 AK 赛，任何人做了任何一道题都能保证 AC。但是 Qjl 身为神犇，要摆神犇的架子，具体做法是对于不同的题，赋予不同的满分，这样会让 AK 者的分数变得好看。

不过，他的比赛中不断会出现出锅的情况，也就是题目满分应该被调整。他会不断调整一些题目的满分，使之更合理。现在 Qjl 需要你编写程序，帮他满足两种操作，如果你写出了代码，你有可能会获得 $2147483648\%32768$ 分的额外满分！

他首先给你两个正整数 $n,m$，表示题目数与操作数；然后他会给你 $n$ 个正整数，表示这些题目初始的满分。接下来他会不断给你发 $m$ 条操作指令：

1 x y k：表示将题号 $i∈[x,y]$ 的题目的满分都加上 $k$；

2 x y：表示询问题号 $i∈[x,y]$ 的所有题目的 AK 分（即总分和）。请你编写程序，以享受 AK 的快感。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct point
{
	int lft,rgt,num,lzy;
} a[400401];
int b[100001],n,m,i,x,y,z,t;
void build(int p,int l,int r)
{
	a[p].lft=l;
	a[p].rgt=r;
	if (l==r)
	{
		a[p].num=b[l];
		return;
	}
	build(①,l,(l+r)/2);
	build(②,(l+r)/2+1,r);
	a[p].num=a[p*2].num+a[p*2+1].num;
}
void down(int p)
{
	if (③)
	{
		a[p*2].num+=a[p].lzy*(a[p*2].rgt-a[p*2].lft+1);
		a[p*2+1].num+=a[p].lzy*(a[p*2+1].rgt-a[p*2+1].lft+1);
		a[p*2].lzy+=a[p].lzy;
		a[p*2+1].lzy+=a[p].lzy;
		④;
	}
}
void add2(int nd,int st,int ed,int x)
{
	if (st<=a[nd].lft && ed>=a[nd].rgt)
	{
		a[nd].num+=⑤;
		a[nd].lzy+=x;
		return;
	}
	down(nd);
	if (st<=(a[nd].lft+a[nd].rgt)/2) add2(nd*2,st,ed,x);
	if (ed>=(a[nd].lft+a[nd].rgt)/2+1) add2(nd*2+1,st,ed,x);
	a[nd].num=a[nd*2].num+a[nd*2+1].num;
}
int Find(int nd,int l,int r)
{
	if (⑥) return ⑦;
	down(nd);
	int bb=0;
	if (l<=(a[nd].lft+a[nd].rgt)/2) bb+=Find(nd*2,l,r);
	if (r>=(a[nd].lft+a[nd].rgt)/2+1) bb+=Find(nd*2+1,l,r);
	return bb;
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for (i=1;i<=n;i++)
	{
		scanf("%lld",&b[i]);
	}
	build(1,1,n);
	for (i=1;i<=m;i++)
	{
		scanf("%lld",&t);
		if (t==1)
		{
			scanf("%lld%lld%lld",&x,&y,&z);
			add2(1,x,y,z);
		}
		else
		{
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",Find(1,x,y));
		}
	}
}

34. 填入 ① 和 ② 的代码分别是。{{ select(34) }}

• p * 2;p * 2 + 1
• p * 2 + 1;p * 2
• p + 1;p + 2
• p + 2;p + 1

35. 填入 ③ 处的代码是。{{ select(35) }}

• a[p].num == 0
• a[p].num != 0
• a[p].lay == 0
• a[p].lzy != 0

36. 填入 ④ 处的代码是。{{ select(36) }}

• a[p].num = 0
• a[p].lzy = 0
• a[p].num = a[p].lzy=0
• down(p * 2); down(p * 2 + 1);

37. 填入 ⑤ 处的代码是。{{ select(37) }}

• a[nd].rgt - a[nd].lft + 1
• a[nd].rgt - a[nd].lft
• x * (a[nd].rgt - a[nd].lft + 1)
• x * (a[nd].rgt - a[nd].lft)

38. 填入 ⑥ 和 ⑦ 处的代码分别是。{{ select(38) }}

• l <= a[nd].lft && a[nd].rgt <= r；a[nd].num
• l <= a[nd].lft && a[nd].rgt <= r；a[nd].num * (l - r + 1)
• a[nd].lft <= l && r <= a[nd].rgt；a[nd].num * (l - r + 1)
• a[nd].lft <= l && r <= a[nd].rgt；a[nd].num

（奶牛也感染）每头奶牛都不想成为被新型病毒感染的奶牛。被所有奶牛接触的奶牛就是一头被感染的奶牛。因为奶牛喜欢偷偷摸摸地行动，所有接触是单向的，所有奶牛都与自己接触。奶牛之间的接触是可以传递的 —— 如果 $A$ 接触过 $B$，$B$ 接触过 $C$，那么 $A$ 也接触过 $C$。牛栏里共有 $N$ 头奶牛，给定一些奶牛之间的接触关系，请你算出有多少头奶牛不幸被感染。

输入的第一行是两个用空格分开的整数 $N$ 和 $M$。接下来 $M$ 行每行两个用空格分开的整数 $A$ 和 $B$，表示 $A$ 接触过 $B$。输出被感染的奶牛的数量。

#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int v,next;
} p[50001];
int front[10001],M;
void Add(int u,int v)
{
	++M;
	p[M].v=v;
	    ①    ;
	front[u]=M;
}
int dfn[10001],low[10001],N,s;
stack<int> zhan;
int which[10001];
int Out[10001],id,large[10001];
int n,m;
int dfs(int x)
{
	++N;
	dfn[x]=low[x]=N;
	zhan.push(x);
	for (int i=front[x];i;i=p[i].next)
	{
		if (    ②    )
		{
			dfs(p[i].v);
			    ③    
		}
		else
		 low[x]=min(low[x],dfn[p[i].v]);
	}
	if (dfn[x]==low[x])
	{
		++s;
		int S=0;
		int v;
		do
		{
			v=zhan.top();
			zhan.pop();
			    ④    
			++S;
		} while (x!=v);
		Large[s]=S;
	}
}
int main()
{
	int i,j;
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		Add(x,y);
	}
	for (i=1;i<=n;++i) 
	    if (dfn[i]==0) dfs(i);
	for (i=1;i<=n;++i)
	    for (j=front[i];j;j=p[j].next)
	        if (which[p[j].v]!=which[i]) ⑤;
	for (i=1;i<=s;++i)
	    if (Out[i]==0) {
	 	 	if (id!=0)
	 	 	{
	 		 	printf("%d\n",0);
	 		 	return 0;
	 	 	}
	 	 	id=i;
	  	}
	printf("%d\n",large[id]);
	return 0;
}

39. ① 处填入的代码是。{{ select(39) }}

• p[M].next = u
• p[M].next = v
• p[M].next = front[u]
• p[M].next = front[v]

40. ② 处填入的代码是。{{ select(40) }}

• !dfn[p[i].v]
• dfn[p[i].v]
• low[p[i].v]
• !low[p[i].v]

41. ③ 处填入的代码是。{{ select(41) }}

• dfn[x] = min(dfn[x], dfn[p[i].v]);
• dfn[x] = max(dfn[x], low[p[i].v]);
• low[x] = max(low[x], dfn[p[i].v]);
• low[x] = min(low[x], low[p[i].v]);

42. ④ 处填入的代码是。{{ select(42) }}

• ++s;
• which[v] = s;
• x = zhan.top(), zhan.pop();
• zhan.push(x + v);

43. ⑤ 处填入的代码是。{{ select(43) }}

• ++Out[which[i]]
• ++which[Out[i]
• ++Out[Out[i]]
• ++which[which[i]]