CSP-J 初赛十连测总结【单项选择】

Su777 · 2024-09-15 21:02:37 · 个人记录

基于梦熊联盟「信息学奥赛 CSP 满分之路」编写。

试题编码格式：【J1-A1】代表第一套，单选第一题。

单项选择

\color{Red}\bold{仔细审题，题面读两遍再选。}

计算机编程语言

机器语言：0 和 1。

汇编语言：跟机器语言基本上一对一。

高级语言：有面向对象和面向过程的。

面向对象语言：Python，C++，Java，C#，Ruby，JavaScript，Java，Swift，Objective-C，PHP。

面向过程语言：C，Fortran，Pascal，Basic。

网络基础概念

【J3-A9】。
【J6-A5】。
【J10-A2】按照分布的拓扑结构，计算机网络类型可分为星形、环形、总线型。
\color{Red}\bold{找个文章速通一下。}

网络的七层结构：

层级	常用协议
（7）应用层	邮件协议S(imple)M(ail)T(ransfer)P(rotocol)，网络请求协议HTTP(S)，通过网址获取服务器地址D(omian)N(ame)S(ervice)，远程登录协议S(ecure)S(ocket)H(shell)，文件传输协议F(ile)T(ranster)P(rotocol)，TELNET，邮件协议P(ost)O(ffice)P(rotocol)(version)3
（6）表示层	同应用层
（5）会话层	同应用层
（4）传输层	TCP，UDP
（3）网络层	IPv4，IPv6
（2）数据链路层
（1）物理层	局域网LAN，城域网MAN，广域网WAN，互联网/外网Internet，内网Intranet

TCP/IP 是因特网的最基本的协议。

互联网是全球各地科学家共同研究的成果，不是哪国人发明的。

HTTP(S)是网络协议，但是 HTML 不是网络协议。HTML 是一种页面标记语言。

二叉树

【J1-A13】二叉树的 2 度节点个数加一，等于二叉树的 0 度节点个数。节点的度就是它的儿子个数。
【J3-A13】满二叉树的节点数=2^{高度}-1。如果根节点高度为 0，那么 2 的次方数要加一。

排列组合

捆绑法，插空法，隔板法，正难则反，A_n^m,C_n^m 的值不要算错。

【J3-A14】运用捆绑法+插空法，或者正难则反。注意要仔细一点，慢一点，很容易多 1 或者少 1。
【J6-A14】看清题目要求，要选几个。
【J7-A14】看清题意。
【J8-A14】正难则反。

字符串

【J3-A15】考察字串个数，注意空串的情况。

排序算法

审题！看清楚问的是时间复杂度还是空间复杂度，是否稳定还是是否基于排序。

排序算法主要考察平均、最好、最差时间复杂度，空间复杂度，是否基于比较，是否稳定。

【J4-A6】考察排序算法是否基于比较。

![排序算法总结](https://cdn.luogu.com.cn/upload/image_hosting/ktw8oget.png)

不稳定的排序算法：选择、希尔、快速、堆。

不基于比较的算法：计数、桶、基数。

基于比较的算法中，数组元素值比较的次数与初始排列次序无关的是选择排序。

小学奥数

【J6-A6】最倒霉原理（抽屉原理）要加一。算出答案后试着按题意操作一下，看看能不能保证满足要求。
【J8-A13】同上。

ACSII 码常识（重点！）

【J7-A1】考察 4 的 ASCII 码的二进制表示。

'\t' == 9;
'\n' == 10;
'\r' == 13;
' ' == 32 == 0x20 == 0b 010 0000;
'0' == 48 == 0x30 == 0b 011 0000;
'A' == 65 == 0x41 == 0b 100 0001;
'a' == 97 == 0x61 == 0b 110 0001;
'a' - 'A' == 32;

格雷码

【J7-A10】格雷码不是一种可靠性编码。

格雷码是一个二进制数系，而且按照位来分，比如说：3 位格雷码序列，由 8 个三位二进制数组成，可以有前导零。

任意两个相邻的代码只有一位二进制数不同。

序列当中的第一个数和最后一个树只有一位二进制数不同。

格雷码是一种可靠性编码。

格雷码\color{Red}\bold{不是}一种可靠性编码。

算法思想

【J8-A8】分治算法复杂度为 O(n\log n)，倍增法时间复杂度为 O(\log n)。

常识

【J8-A3】在关系数据库中，存放数据库中的数据的逻辑结构以二维表为主。
- SQL 查询语言
- MySQL 免费数据库
- Oracle 商业化数据库
- SQL Server 商业化数据库
【J9-A10】在 U 盘上发现病毒后，较为彻底的清除方法是格式化 U 盘。
【J10-A2】树和图都是数据结构。

哈夫曼树

模拟的时候耐心一点。

【J10-A9】哈夫曼树的构造用到贪心的算法思想。

CSP-J 初赛十连测 总结【单项选择】