CSP-S 初赛最后的复习

2020CSP-S 模拟赛1

3、一个圆形水池中等概率随机分布着四只鸭子，那么存在一条直径，使得鸭子全在直径一侧的概率是（）。

A．\(\frac 1{16}\) B．\(\frac 1{8}\) C．\(\frac 1{4}\) D．\(\frac 1{2}\)

answer：D，四条半径，将 \(360^{\circ}\) 等概率分成四份，问是否有一份大于 \(\frac 12\)，考虑期望情况：

第一条半径占用区间 \(0^{\circ}\)，可行区间变成 \(360^{\circ}\)。

第二条半径占用区间 \(90^{\circ}\)，可行区间变成 \(270^{\circ}\)。

第三条半径占用区间 \(\frac 13\cdot 90^{\circ}+\frac 23\cdot 135^{\circ}=120^{\circ}\)，可行区间变成 \(240^{\circ}\)。

所以答案是 \(\frac{270}{360}\cdot \frac{240}{360}=\frac 12\)。

5、建堆算法可以用递推式表示：把建堆过程想成先对左子树建堆 \(T(\frac n2)\)，再对右子树建堆 \(T(\frac n2)\)，最后对根下溯 \(O(\log n)\)，可得：

\[T(n) = 2T(\frac n2) + O(\log n)
\]

求 \(T(n)\) 时间复杂度（）。

A．\(O(n^2)\) B．\(O(n\log n)\) C．\(O(n)\) D． \(O(1)\)

answer：C，主定理不适用。设 \(x=\log n\)，\(ans=\sum_{i=0}^{x}2^i(x-i)=O(n)\)，重点：根据建堆这个东西推测。

6、设完全图 \(G\) 有 \(n\) 个结点，\(m\) 条边，则当（）时，\(G\) 中存在欧拉回路。

A．\(m\) 为奇数 B．\(m\) 为偶数 C．\(n\) 为奇数 D．\(n\) 为偶数

answer：C，\(n\) 为奇数时每条边的度数都是偶数。

2020CSP-S 模拟赛2

1、下列CCF主办的赛事活动，名称翻译不正确的是？（）

A．CNCC（中国计算机大会）

B．NOIP(全国青少年信息学奥林匹克竞赛)

C．CTSC（国际信息学奥林匹克中国队选拔赛）

D．CSP-S（计算机非专业组别能力认证-提高级）

answer：B，联赛而非竞赛。

7、设哈希表长为 \(7\)，哈希函数是 \(H(key)=key%11\)，表中已有数据的关键字为 \(15\)，\(38\)，\(61\)，\(84\) 共四个，现要将关键字为 \(49\) 的结点加到表中，用线性探测法解决冲突，则放入的位置是( )

A．\(1\) B．\(3\) C．\(5\) D．\(8\)

answer：A。\(15\) 占用 \(4\)，\(38\) 占用 \(5\)，\(61\) 占用 \(6\)，\(84\) 本应占用 \(7\)，但是表长不够，线性探测塞到 \(0\)。\(49\) 和 \(38\) 冲突，探测 \(4\) 次到 \(1\)。

14、Internet 实现了分布在世界各地的各类网络的互联，其最基础和核心的协议是（）。

A、HTTP B、HTML C、TCP/IP D、FTP

answer：C，记住就好了。

2020CSP-S 模拟赛3

6、在微机系统中，最基本的输入输出模块BIOS存放在（）中。

A、RAM B、ROM C、硬盘 D、寄存器

answer：B。

RAM：随机存储器（Random Access Memory），可读可写，关机丢数据。

ROM：ROM表示只读存储器（Read Only Memory），永久不变，关机不丢，存有 BIOS。

寄存器：CPU 单位。Cache：CPU 和读写过渡。

14、关于有权值的无向图最小生成树，以下说法正确的是（）。

A、一个图的最小生成树是唯一的。

B、一个图的最小生成树不一定唯一，但任意两个的最小生成树的第 \(K\) 大的边大小相同。

C、一个图的最小生成树中不一定包含该图中权值最小的边。

D、一个图的最小生成树中一定不包含该图中权值最大的边。

answer：B。这是基本性质把，排除法也可以做。

17、else 改为 if(a%2!=0) 结果不变。（）

if(a%2==0) a=a/2+d;

else a=a/2+d+1;

answer：T，a 已经被改过了。

2020CSP-S 模拟赛4

1、以下说明不正确的是（）。

A．冯诺伊曼被誉为“电子计算机之父”。

B．图灵的“图灵机”是第一台可编程的电子计算机。

C．香农是现代信息论的著名创始人，信息论及数字通信时代的奠基人。

D．西蒙是人工智能中影响最大的符号主义学派的创始人和代表人物。

answer：B。背。图灵机是理论模型。

2、以下四项中（）项与别的选项最不相同。

A．\(P∧﹁ Q\)

B．\((P ∧ Q)\to P\)

C．\(P \to(P ∨ Q）\)

D．\(﹁(P ∨ Q)∨﹁(﹁P ∧ ﹁Q)\)

answer：A，一下是为真条件：

A：\(P=1,Q=0\)。

B：\(\forall\)。

C：\(\forall\)。

D：\(\forall\)。

3、在计算机的四个发展阶段中，以下哪个是第二个阶段：（）。

A．晶体管时代

B．电子管时代

C．小规模集成电路时代

D．大规模和超大规模集成电路时代

answer：A，第一个阶段（第1代）：电子管数字机（1946-1958年）。第二个阶段（第2代）：晶体管数字机（1958-1964年）。第三个阶段（第3代）：集成电路数字机（1964-1970年）。第四个阶段（第4代）：大规模集成电路机（1970年至今）。

4、真正能唯一标识出一台计算机网络中一台计算机的地址是（）。

A．地址掩码

B．ip地址

C．域名地址

D．MAC地址

answer：D，背！

9、以下关于渐进记号的性质是正确的有：（）

A．\(f(n) =\Theta(g(n)),g(n) =\Theta(h(n)) ⇒f(n) =Θ(h(n))\)

B．\(f(n) =O(g(n)),g(n) =O(h(n)) ⇒h(n) =O(f(n))\)

C．\(O(f(n))+O(g(n)) = O(min{f(n),g(n)})\)

D．\(f(n) = O(g(n)) ⇔g(n) = O(f(n))\)

answer：A。

渐近紧确界记号：\(\Theta\)。

渐近上界记号：\(O\)。

渐近下界记号：\(\Omega\)。

非渐近紧确上界：\(o\)。

非渐近紧确下界：\(\omega\)。

14、一个游戏：连续抛掷硬币，直到最近三次硬币抛掷结果是“正反反”或者“反反正”。如果是前者，Alice赢，如果是后者Bob赢，问Alice对Bob的胜率（）。

A. \(1:1\) B. \(1:3\) C. \(3:2\) D. \(3:1\)

answer：D，拿“正反反”和“反反正”建 AC 自动机，在这上面跑 Alice \(\frac 34\)，Bob \(\frac 14\)。

初赛强化训练3

3、以下几种存储器的访问速度第二快的是（）

A、Cache B、ROM

C、RAM D、金士顿DT100G3（32GB）

answer：C，Cache\(>\)RAM\(>\)ROM。

2020CSP-S 模拟赛8

1、在下列几种存储器中，访问速度最慢的是（）。

A、ROM B、cache C、RAM D、寄存器

answer：A，寄存器\(>\)Cache\(>\)RAM\(>\)ROM。

2、在等腰直角三角形 \(ABC\) 中，过直角顶点 \(C\) 在 \(∠ACB\) 内部任作一射线 \(CM\)，与线段 \(AB\) 交于点 \(M\)，求 \(AM<AC\) 的概率。（）

A、\(\frac 1{\sqrt 2}\) B、\(\frac 12\) C、\(\frac {\sqrt 2}3\) D、\(\frac 34\)

answer：D 注意射线概率要看角度！！

12、下列关于排序的算法，不正确的是（）。

A.不存在这样一个基于排序码比较的算法：它只通过不超过 \(9\) 次排序码的比较，就可以对任何 \(6\) 个排序码互异的数据对象实现排序。

B.如果输入序列已经排好序，快速排序算法将比归并排序更快。

C.希尔排序的最后一趟就是插入排序。

D.任何基于排序码比较的算法，对 \(n\) 个数据对象进行排序时，最坏情况下的时间复杂度不会低于 \(O(n\log n)\)。

answer：B，背！

14、下列有关说法不正确的是（）。

A. 区块链的本质是一个去中心化的数据库，它将为人类社会带来巨大的变革。

B. 谷歌人工智能新应用Duplex已经通过了图灵测试。

C. G网络作为第五代移动通信网络，其峰值理论传输速度可达每秒数十GB。

D. 艾德文·卡特姆和帕特·汉拉汉凭借在3D计算机图形学领域的创新获得了2020年的图灵奖。

answer：B，背（考场上出来就没了！

17、若 \(13\) 行 i>=0 改成 i>0，不影响程序结果。

1 #include<iostream>

2 using namespace std;

3 int main(){

4	int n;

5	cin>>n;

6	string s="1";

7	int t;

8	do{

9		int i=s.length()-1;

10		while(s[i]=='1'){

11			s[i]='0';i--;

12		}

13		if(i>=0)s[i]='1';

14		else s='1'+s;

15		t=0;

16		for(int i=0;i<s.length();i++){

17			t=t*10+s[i]-'0';

18		}

19	}while(t%n);

20	cout<< s<<endl;

21	return 0;

22 }

answer：T，因为 \(i\not= 0\)。

祝我 CSP-S2020 初赛 \(rp++\)！

巴特西