CSP历届初赛知识点总结（1） » 老官童鞋gogo的博客

此文章只收纳了初赛/第一轮中需要背诵的内容，对于如何计算、解题方法少有涉及。

最后附有易错点整理。

计算机的基本构成

CPU高速缓存是用于减少处理器访问内存所需平均时间的部件。仅次于CPU寄存器。其容量远小于内存，但速度却可以接近处理器的频率。当处理器发出内存访问请求时，会先查看缓存内是否有请求数据。
硬盘是电脑的主要存储媒介之一。
高速缓存,称为高速缓冲存储器,是介于中央处理器CPU和主存储器之间的高速小容量存储器。
内存属于存储器，是冯诺依曼结构体系中构成计算机的五大部件（存储器、运算器、控制器、输入设备、输出设备）之一。
鼠标、U盘和摄像头都是外部设备，没有电脑也能启动。
输入设备有键盘，鼠标，摄像头，扫描仪，光笔，手写输入板，游戏杆，语音输入装置等。

输出设备有显示器、打印机、音响、绘图仪、影像输出系统、语音输出系统、磁记录设备等。
总线是计算机各种功能部件之间传送信息的公共通信干线。总线连接CPU、存储器、I/O设备。
随机存取存储器RAM(Random Access Memory)在计算期间被用作高速暂存记忆区，当计算机在运行时RAM是可得到的，当关闭计算机时信息将会丢失。ROM(Read Only Memory)断电后，不受影响。
全球两大个人电脑处理器厂商：Intel和AMD。奔腾、酷睿、赛扬都是Intel生产的处理器型号。性能：赛扬（低端）< 奔腾（中低端）< 酷睿（高端）。i3, i5, i7, i9都是酷睿的系列。目前市场上主流使用的型号为酷睿i5和酷睿i7。
在计算机内部用来传送、存贮、加工处理的数据或指令都是以二进制码形式进行的。
CPU的功能主要是解释计算机指令，控制程序以及处理计算机软件中的数据。
分辨率指单位面积中存储的信息量，是每英寸屏幕内有多少个像素点，分辨率的单位为PPI(Pixels Per Inch)，通常叫做像素每英寸，跟屏幕尺寸无关。
用户既可以通过WiFi方式也可以通过物理连接（有线通信）的方式连接到网络。
光盘、磁盘、固态硬盘都是存储设备。
存储器是许多存储单元的集合，按单元号顺序排列。在内存储器中每个存储单元都被赋予一个唯一的序号，称为地址，每个存储单元的地址是唯一且固定不变的，而存储在其中的信息是可以更换的。

操作系统的基本概念及其常见操作

Linux下的文件不需要扩展名。exe通常是windows系统可执行文件的拓展名；com是顶级域名，早期专属于商业组织注册；dll是windows系统中动态链接库的库函数的扩展名。
将回收站清空后，肉眼看不见文件了。但是对于操作系统来说，只是将这件文件占用的硬盘空间标记为“删除”，并且让肉眼不可见而已。只有等这块硬盘空间被别的文件占用时，原先的文件才被新数据所覆盖，此时原先的文件才无法再恢复。
Adobe Photoshop，简称“PS”，是由Adobe Systems开发和发行的图像处理软件，不是操作系统。
操作系统是一组主管并控制计算机操作、运用和运行硬件、软件资源和提供公共服务来组织用户交互的相互关联的系统软件程序。
编译器的作用是把源程序译成目标程序，数据库的作用是便于进行数据管理，主板的作用是实现硬件之间的连接。
程序中断是指在计算机执行程序的过程中，出现某些急需处理的异常情况或特殊请求，CPU暂时中止现行程序，而转去这些异常情况或特殊请求进行处理。
寻址空间一般指的是CPU对于内存寻址的能力，CPU最大能查找多大范围的地址叫做寻址能力，CPU的寻址能力以字节为单位，如32位寻址的CPU可以寻址2的32次方大小的地址也就是4G，这也是为什么32位的CPU最大能搭配4G内存的原因，再多的话CPU就找不到了。
CapsLock会切换大小写。
计算机中以二进制方式存储数据

计算机网络与Internet的基本概念

TCP/IP 模型见图，通信两端的同一层会传送相同的信息。 A 最符合该图的形式。
HTTP（Hypertext Transfer Protocol）- 超文本传输协议。
POP3（Post Office Protocol – Version 3）- 邮局协议版本 3。
Telnet 协议是 TCP/IP 协议中的一员，是 Internet 远程登陆服务的标准协议和主要方式。
无线局域网利用射频的技术，使用电磁波在空中进行通信连接。 Wi-Fi和蓝牙都属于无线通信，且仅能在有限范围内实现各种通信设备的互连，因此是无线局域网。
IPv6采用128位(16字节)地址来避免地址资源的枯竭。目前IPv4已经分配完毕。
通常在搜索引擎中“”（引号）内的内容指定搜索的专用名词，并且不可拆分；另有如《》代表书名号出现在搜索结果当中，书名号括起来的内容不会被拆分，或者表示搜索的内容含有书名号，intitle：指定查询标题中含有某些关键词，filetype：搜索特定格式文件等。
中国国家顶级域名即是.cn，.cn域名由国家工业和信息化部管理，.cn域名注册的管理机构为中国互联网信息中心（CNNIC）。国家代码顶级域名指示国家区域（如.cn代表中国，.us代表美国，.fr代表法国，.ch为瑞士等等）。
SMTP(Simple Mail Transfer Protocol)是一种提供可靠且有效的电子邮件传输的协议,是建立在FTP文件传输服务上的一种邮件服务，主要用于系统之间的邮件信息传递，并提供有关来信的通知。
UDP，用户数据报协议（User Datagram Protocol）,为应用程序提供了一种无需建立连接就可以发送封装的 IP 数据包的方法。
对等网络（Peer-to-peer networking）或对等计算（Peer-to-peer computing），网络的参与者共享他们所拥有的一部分硬件资源（处理能力、存储能力、网络连接能力、打印机等），这些共享资源通过网络提供服务和内容，能被其它对等节点（Peer）直接访问而无需经过中间实体。
FTP，文件传输协议（File Transfer Protocol）是用于在网络上进行文件传输的一套标准协议。
以太网是一种计算机局域网技术，以太网是目前应用最普遍的有线网技术。以太网的每个版本都有电缆的最大长度限制(即无须放大的长度),这个范围内的信号可以正常传播,超过这个范围信号将无法传播。
蓝牙、WiFi、GPRS都属于无线通信技术。
常用的电子邮件协议有SMTP、POP3、IMAP4。
广域网(WAN)是在一个广泛地理范围内所建立的计算机通信网，其范围可以超越城市和国家以至全球。此外还有局域网(LAN)和城域网(MAN)。

程序设计语言以及程序编译与运行

超链接的格式为： <a href="锚点" target="">热点</a> <a href="task1.html" target="mainFrame1">查看任务1</a>
时间复杂度指的是算法执行消耗的时间，空间复杂度指的是算法执行所占用的内存空间。
栈用于计算机临时数据的存储，在递归调用的过程中获得的数据都是临时数据，调用系统栈，递归结束时，计算机会输出最终答案并把临时数据清除。
C语言是面向过程的编译性语言，C++是面向对象的编译性语言，Java是面向对象的解释性语言，python是面向对象的解释性语言。

字节与字

byte是计算机存储的基本单位，bit是计算机存储的最小单位，一个字节由8个二进制位组成，1 byte(字节) = 8 bit(位)。
一般来说，若地址总线为 $n$ 位，则可寻址空间为 $2^n$ 字节。
字节（ Byte ）是计算机存储信息的基本单位。
$n$ 位色图中一个像素点占用 $n$ bit（位）空间。

进制的基本概念与进制转换

不同进制的符号表示：二进制 B (binary)、八进制 O (octal)、十进制 D (decimal)、十六进制 H (hexadecimal)。
十六进制中，用大写字母A－F表示10－15，记住，A表示10
链表不可以随机访问任意元素，只能按顺序从头节点开始访问。但是链表可以不必事物估计存储空间，插入删除不需要移动元素，且链表所需空间与线性表长度成正比。

NOI以及相关活动的历史

当然，想要获得更加全面的计算机简史、OI及相关活动的历史，点击这里：计算机及OI发展史

中国计算机学会于1984年创办全国青少年计算机程序设计竞赛(简称：NOI)，注意是“全国”，不是“中国”，是“竞赛”，不是“联赛”。
CCF NOIP复赛全国统一评测时使用的系统软件是NOI Linux。
CCF于2016年11月1日发布《CCF关于NOI系列赛事程序设计语言变更的公告》从2022年开始，NOIP竞赛也将不再支持Pascal语言。

其他

矢量图使用直线和曲线来描述图形，这些图形的元素是一些点、线、矩形、多边形、圆和弧线等，它们都是通过数学公式计算获得的。
HTML 是超文本标记语言，网页使用浏览器打开阅读。
TXT是文本格式。

JPEG格式是最常用的图像文件格式，后缀名为.jpg或.jpeg。

GIF的全称是Graphics Interchange Format，可译为图形交换格式。（动图）

PNG（Portable Network Graphics）是一种采用无损压缩算法的位图格式。（透明图）
计算机病毒是编制者在计算机程序中插入的破坏计算机功能或者数据的代码，能影响计算机使用，能自我复制的指令集合或者程序。
P2P指对等网络(peer-to-peer)，一种网络技术和网络拓扑结构。每台电脑都可以提供资源给其他电脑，透过P2P文件交换软件，可直接与其他网友交换电脑中的资料。
AVI、MOV、RMVB、MP4都是视频文件格式。
Adobe Acrobat是由Adobe公司所开发的电子文书处理软体集，可用于阅读、编辑、管理和共享PDF文件。
Microsoft(微软)是软件生产商。Intel、AMD、IBM都是CPU生产厂商。

图与哈希表

$n$ 个点的无向完全图边数为 $\frac{n(n-1)}{2}$。
满二叉树第 $n$ 层有 $2^{(n-1)}$ 个节点，前 $n$ 层共有 $2^n-1$ 个节点。
一棵 $n$ 个节点的树有 $n-1$ 条边。
图中任意两点都是连通的（可以不是直接连通，间接连通也可以，只要有路径连接就可以），那么图被称作连通图。

字符串处理

字符串可以看作字符数组，是一种特殊的线性表。
串的长度可以为零称之为空串，空串不包含任何字符， {‘\0’}才是空串。\0与NULL相同。

万人坑——易错点

折半搜索（二分搜索）时，根据题目判断要查找的元素是否一定存在，来确定最后一次判断是否需要，例如：

设有100个数据元素，采用折半搜索时，最大比较次数为( )。

答案：7

解析：根据二分查找原理，每次查找后剩余元素数量为查找前元素数量除2向下取整，100/2=50/2=25/2=12/2=6/2=3/2=1（6次），因为题目中没有保证查找数据一定存在，所以剩最后一个元素时也要进行查找，所以最大比较次数是7次。

一定看清楚了题目让你输出什么：

#include <iostream>
#include <string> 
using namespace std;

int main()
{
	string str;
	int i;
	int count; count = 0;
	getline( cin, str );
	for ( i = 0; i < str.length(); i++ )
		if ( str[i] >= 'a' && str[i] <= 'z' )
			count++;
	cout << "It has " << count << " lowercases" << endl;
	return(0);
}
输入：串的长度可以为零称之为空串，空串不包含任何字符， {‘\0’}才是空串

错误答案：18

正确答案：It has 18 lowercases