CSP初赛知识点梳理

姓名： 梅耀元
赛道： 普及
类型： csp知识点

---

---

一、计算机存储知识

​ 美籍科学家冯.诺依曼提出“存储程序”工作原理：只要在计算机的存储装置中存入不同的程序，计算机就可以按照程序设定的步骤自动地完成不同的任务

存储器：用于保存各类程序的数据信息。存储器分为：主存储器和 辅助存储器或者说： 内部存储器，外部存储器。

1.1主存储器

​ 主存储器也称内存储器 ，简称内存（主存），是计算机存储程序和数据的部件，用于存放系统当前正在执行的数据和程序，属于临时存储器。

​ 主存储器的信息（内存）可以被CPU 直接访问，内存由半导体存储器组成，存取速度快，容量一般较小。内存中含有很多存储单元，每个存储单元可以存放1 个8 位二进制数（1 个字节），内存中每个字节有一个固定的编号，这个编号称为地址，CPU 在存取存储器中的数是按地址进行的。

​ 内存可分为： 只读存储器（ROM）、随机存储器（RAM）和高速缓冲存储器Cache 。

​ ROM：

• 是一种用专用设备才能写入的存储芯片，用户只能读取其中的内容；不能修改，只读存储器，信息只能被读入，不能写入新信息。
• 计算机断电后，ROM 中的信息不会丢失，
• 该芯片装配在系统主板上。
• BIOS（基本输入／输出系统）软件就存放在ROM内,它提供了最基本的和初步的操作系统服务，同时也是硬件与操作系统上层软件之间的接口，rom用于检查系统配置及提供基本的输入输出控制程序。
• 

​ RAM：

• 随机存取存储器又称为读写存储器RAM，用于存放现场程序和数据读写存储器，可读、可写。
• RAM不是永久性存储数据的，此类的内存就是我们常说的“内存”；RAM可被看作是电脑中使用的临时存储区，它能暂时存储程序运行时需要使用的数据或信息等。
• 因为RAM中的信息是由电路的状态表示的，所以 断电后RAM 中的信息全部丢失 。
• RAM 通常指的是计算机主机中的内存条
  • 

​ 高速缓冲存储器Cache：由于CPU 的速度不断提高，RAM 的读写速度很难满足CPU 的要求，因此在读写内存时会加入等待时间，对于高速CPU 而言是一种浪费，Cache 主要用于CPU与内存之间设置高速小容量存储器，固化于主板，用于提升CPU 的读写效率。

1.2 外存储器

​ 外存储器又称为辅助存储器，简称外存（辅存）。外存作为主存储器的后备和补充而广泛使用。
​ 外存储器的特点是：存储容量大、成本低、存取速度慢，可以永久地脱机保存信息。
​ 一台微机配备的硬盘容量越大越好，但容量越大，价格越高。 外存一般有硬盘、闪存（优盘）、光盘、软盘，现在用得比较多的是 闪存和硬盘 。

固态硬盘（Solid State Disk或Solid State Drive，简称SSD），又称固态驱动器，是用固态电子存储芯片阵列制成的硬盘。

光盘存储器，光盘也称为CD—ROM，光盘的容量一般为650MB

1.3 计算机的三总线结构

​ 总线是一组为系统部件之间各种数据信号传送的公共通道。可分为CPU总线、存储器总线、I/O通道总线和外围接口总线 四个层次。总线是一组导线、是公共通路，微型计算机中各个组成部件之间的信息传输都是通过它们来实现的。

每个层次又分为：

• 地址总线AB (Address Bus)
  • 地址总线是单向的。
  • 用以传送CPU 向外设或存储器发出的地址信息，
  • 地址总线的位数决定了CPU的 寻址能力，也决定了微型机的最大内存容量。
  • 地址总线的宽度决定可以访问存储器的容量大小 。
• 数据总线DB(Data Bus)
  • 数据总线用于传输数据。
  • 数据总线的传输方向是双向的，是CPU与存储器、CPU与I/O接口之间的双向传输。
• 控制总线CB (Control Bus)
  • 控制总线(CB)是双向总线
  • 控制总线是CPU对外围芯片和I/O接口的控制以及这些接口芯片对CPU的应答、请求等信号组成的总线。
  • 有的作为输出，有的作为输入，用以CPU 与内存或I/O 接口之间传送控制信息。

1.4 计算机主要的性能指标

中央处理器（CPU——Central Processing Unit）由运算器、控制器和一些寄存器组成；

• 运算器：主要任务是进行算术运算和逻辑运算，一般包括算术逻辑部件ALU、累加器和寄存器。它们的位数决定了CPU的字长。（同时处理的字节数）
• 控制器：计算机的神经中枢，控制器从存储器读入指令，并对输入的指令进行分析，然后，控制和指挥计算机的各个部件完成一定的任务。
• 字长：字长是CPU 的主要技术指标之一，指的是CPU 一次能并行处理的二进制位数，字长总是8 的整数倍，通常PC 机的字长为16 位（早期），32 位，64 位。字长越长、表示的数据范围就越大、计算出结果的有效位数就越多、能表示的信息也就越多、机器处理功能就更强。
  • 区分字节和字长， 1 个字节（byte）= 8 位（bit）
  • 我们常说的32 位和64 位主要区别在于CPU 单次执行的位数不同，32 位的系统一次执行32 位的数据，而64 位的系统一次执行64 位的数据，也就是CPU 的 寻址空间不同（寻址空间一般指的是CPU 对于内存寻址的能力。通俗地说，就是能最多用到多少内存）。
• 运算速度：指的是计算机每秒钟能够执行的指令条数，一般用MIPS（Million ofInstruction Per Second，每秒百万条指令）为单位。
• 主频：计算机CPU 的时钟频率，一般主频越高，运算速度就越快（一个时钟周期内完成的指令越多）。

• 内存容量：内存储器能够存储信息的总字节数，目前计算机的内存储容量一般是2GB、4GB、8GB 等。

二、程序设计语言及流程图

​ 程序流程图又称程序框图，指用特定图形符号加上对应的文字描述表示程序中所需要的各项操作或判断的图示，程序流程图除了说明程序的流程顺序外，着重于说明程序的逻辑性。

2.1 程序流程图特点

当程序流程中有较多循环语句（内容）需要处理，且结构较为复杂给设计与理解造成困难时，通常会绘制一份符合逻辑的程序流程图表示算法，将程序流程图形化，使程序流程的内容更加直观、清晰、易于理解。当然了，简单的程序流程也可以借助程序流程图来呈现，并非只能绘制复杂的程序流程。

2.2 程序流程图基本图形

程序流程图与普通流程图的基本图形相似，通常由起止框、处理框、流程线、判断框、输出输入框构成。

• 起止框：表示程序流程的开始与结束，通常只有一个开始框和一个结束框。
• 处理框：表示程序流程中需要执行或处理的内容。
• 流程线：表示程序执行的方向与顺序。
• 判断框：表示对程序流程中的某一条件进行判断，用来决定执行某一操作。
• 输出输入框：表示程序流程中资料的输入或结果的输出，一般用做数据处理。

2.3 程序流程图基本结构

2.4 程序流程图案例

1. 顺序结构

if语句

多行if语句

多条件if语句

while语句

do while语句

2.5计算机语言

编程语言分类：机器语言，汇编语言，高级语言。

• 机器语言：最早出现的使用二进制代码编写的计算机能直接识别的语言。
• 汇编语言：用一些符号代替机器指令所产生的语言。虽然汇编语言比机器语言简单，但仍属于低级语言，并且多台机器之间互相不兼容。
• 高级语言：程序员容易理解的编程语言。比如：Basic, Pascal, c, c++, Viscal Basic, Java, Go,Python等。
  • 高级语言中有一类叫做面向对象的语言，比如：smalltalk、Java、C++、C#、Python、Object-C等，请注意C语言不是面向对象的。
• 计算机不能直接执行高级语言编写的源码，需要“翻译”为及其能理解的机器码才能运行。这种“翻译”有2种形式：编译型、解释型。
  • 编译：将源码直接转换为二进制代码，生成目标程序，然后将目标程序连接成可执行的程序。
    • 流程为：高级语言源码**—编译—>目标程序—连接—>**可执行程序。
  • 解释型：由解释程序边扫描源码，边解释，将源码逐句解释，不产生目标程序。
    • 流程为：高级语言源码**—解释程序—>**可执行程序。
  • 编译型语言有： C/C++、Pascal等。
  • 解释型程序有：Asp、PHP、Python等。

三、计算机网络知识

3.1 计算机网络分类

计算机网络的分类方式有很多种,可以按地理范围、拓扑结构、传输速率和传输介质等分类。

3.1.1 地理范围分类

① 局域网 LAN（Local Area Network）

局域网地理范围一般在几百米到二十公里之间，适用于一个建筑物（办公楼）或相邻的大楼内，属于一个部门或者单位组建的专用网络，如公司或高校的校园内部网络。

局域网的特点：
1、传输速率较高
2、 结构简单、灵活、便于扩充，易于实现；
3、工作可靠，单个工作站发生故障不会影响整个网络，并可通过总线对各工作站进行检测和诊断，便于维护和故障恢复。

局域网的组成:
(1)服务器:是局域网的核心
(2)客户机:也称用户工作站
(3)网络设备
网卡、交换机、网桥、路由器、网关
(4)通讯介质
(5)网络操作系统

② 城域网 MAN（Metropolitan Area Network）

城域网是一种大型的局域网，因此使用类似于局域网的技术，它可能覆盖一个城市。传输速率通常在10Mbps以上，作用距离在10到50公里之间。

③ 广域网 WAN（Wide Area Network）

广域网是一种跨度大的地域网络，通常覆盖一个国家或州。网络上的计算机称为主机（host），通过通信子网（communication sub net）连接，实现资源子网中的资源共享。

广域网特点：
1、覆盖范围广
2、数据传输速率较低
3、使用多种传输介质，例如有线有光纤、双绞线、 同轴电缆等，无线有微波、卫星、红外线、激光等。
4、数据传输延时大，例如卫星通信的延时可达几秒钟。
5、数据传输质量不高，例如误码率高，信号误差大等。
6、广域网管理、维护困难。

3.1.2 拓扑结构分类

拓扑结构：主要是指网内各个计算机结点相互联接的方式。
就局域网而言，它采用的拓扑结构可以有：
(1)总线型

采用一条称为公共总线的传输介质，将各计算机直接与总线连接，信息沿总线介质逐个节点广播传送。

总线型拓扑结构的优点是：总线结构简单，扩充性好；可靠性高，节点间响应速度快；所需的通信线的长度少。
总线型拓扑的缺点是：总线的长度不能太长；故障诊断困难；公用一条总线，数据通信量较大。

(2)环型

环型网络将计算机连成一个环,每台计算机按位置不同有一个顺序编号 。

环型拓扑结构的优点：通信线路短；增加或减少工作站时仅需要简单的连接。
环型拓扑结构的缺点：由于通信结构的封闭性，一个节点出现故障会引起全网的故障；检测故障困难。

(3)星型

星型网络由中心节点和其它从节点组成，中心节点可直接与从节点通信，而从节点间必须通过中心节点才能通信。

星型拓扑结构的优点：控制简单；网络的故障容易发现；在网络中通信容量不大的情况下通信速度较快。
星型拓扑结构的缺点：网络的可靠性差（网络的性能依赖于中心节点，一旦节点出现故障，就会危及整个网络）；中心节点的负担过重；所需通信线路较长且安装时的工作量较大。

3.1.3 传输介质分类

传输介质用来传送计算机网络中的数据。常用的传输介质有：

有线网：

（1）双绞线（Twisted Pair）
（2）同轴电缆（Coaxial Cable）
（3）光纤（Optical Fiber）

无线网：

（4）无线传送：FM（收音机）、GPRS（手机无线 2G、4G、5G）、WLAN（Wifi）、蓝牙（Bluetooth）等

3.2 计算机网络体系结构

3.2.1 计算机网络体系结构的核心OSI 模型

OSI（Open System Interconnect）开放式系统互联。 一般都叫OSI参考模型 ，ISO（国际标准化组织）组织在1985年研究的网络互联模型。 最早的时候网络刚刚出现的时候，很多大型的公司都拥有了网络技术，公司内部计算机可以相互连接。可以却不能与其它公司连接。因为没有一个统一的规范。计算机之间相互传输的信息对方不能理解。所以不能互联。

ISO为了更好的使网络应用更为普及，就推出了OSI参考模型。其含义就是推荐所有公司使用这个规范来控制网络。这样所有公司都有相同的规范，就能互联了。

七层参考模型又可转换为五层和四层{实际生产}，具体如下表所示

3.2.2 网络协议

常见的网络协议有:

IPX/SPX（互联网络数据包交换）,

TCP/IP（基本的通讯协议）：TCP，传输控制协议；IP 网际互连协议

HTTP（超文本传输协议）：WWW 的网页文件是用超文本标记语言 HTML 编写的，并在超文本传输协议 HTTP（HyperText Transmission Protocol）支持下运行。

FTP（文件传输协议）：用于计算机之间传输文件，如下载软件等。

常见的邮件服务协议有:

SMTP（Simple Mail Transfer Protocol，简单邮件传输协议）

POP3（Post Office Protocol、邮局协议）

IMAP（Internet Mail Access Protocol，Internet 邮件访问协议）。

3.2.3 IP地址

1. IP地址的基本概念
IP地址是==32位的二进制数值 ，用于在TCP/IP通讯协议中标记每台计算机的地址。通常我们使用点式十进制来表示，如192.168.1.6等。也就是说IP地址有两种表示形式：二进制和点式十进制，一个32位IP地址的二进制是由4个8位域==组成。

即==11000000 10101000 00000001 00000110 （192.168.1.6）==。

IP地址 = 网络号+主机号

每个IP地址又可分为两部分。即网络号部分和主机号部分：网络号表示其所属的网络段编号，主机号则表示该网段中该主机的地址编号。按照网络规模的大小，IP地址可以分为A、B、C、D、E五类，其中A、B、C类是三种主要的类型地址，D类专供多目传送用的多目地址，E类用于扩展备用地址。A、B、C三类IP地址有效范围如下表1所示：

需要再次指出的是，多接口主机具有多个IP地址，其中每个接口都对应一个IP地址。IP 规定网络上所有的设备都必须有一个 独一无二 的 IP 地址，就好比是邮件上都必须注明收件人地址，邮递员才能将邮件送到。

区分各类地址的最简单方法是看它的第一个十进制整数。图列出了各类地址的起止范围，其中第一个十进制整数用加黑字体表示。

现有的互联网是在 IPv4 协议的基础上运行的，IPv4 采用 32 位 地址长度，只有大约 43亿个地址，IP 地址将很快分配完毕。IPv6 是下一版本的互联网协议，采用 128 位地址长度，其地址数量号称可以为全世界的每一粒沙子编上一个地址。

通常一个 IPv4 地址共有 32 位，分为 4 段，每段 8 位（也即 1 个字节） 。它的表示方法如下：xxx.xxx.xxx.xxx，其中每段的取值范围为 0～255 。IP 地址是 Internet 上主机的一种数字标识，它由两部分组成，一部分是网络标识（netid），另一部分是主机标（hostid）。

3.2.4 域名

要记忆一组并无任何特征的IP地址是十分困难的。为了使IP地址便于用户记忆和使用，同时也易于维护和管理，Internet引入了域名服务系统DNS（Domain Name System）的主机内，使用者只需了解易记的域名地址，其对应转换工作就留给了域名服务器。域名服务器就是提供 IP 地址和域名之间的转换服务的服务器。。

它采用层次结构，每一层构成一个子域名，子域名之间用圆点隔开，自左向右分别为：
主机名.组织机构名.网络名.顶级域名
Mail. hz. zj. cn

顶级域名有三类：

国家顶级域名：如 cn（中国）、us（美国）、uk（英国）。

国际顶级域名：int，国际性组织可以在 int 下注册。

通用顶级域名：com（商业组织）、net（网络组织）、edu（教育机构）、org（非盈利性

组织）、gov（政府部门）

3.2.5 网络安全

计算机安全中最重要的是存储数据的安全，主要面临的威胁有：计算机病毒、非法访问、

计算机电磁辐射、硬件损坏等。

网络安全：

1. 防火墙的作用：防止网络攻击。
2. 大部分计算机病毒会主要造成计算机软件和数据的损坏。
3. 病毒主要通过磁盘和网络传播。
4. 发现病毒后，较为彻底的清除方法是格式化磁盘。

计算机安全的常用防护策略：

• 杀毒软件
• 防火墙
• 不下载来路不明的软件及程序
• 不要随意浏览不安全网站

计算机病毒的特性：

A、 隐蔽性；

B、 潜伏性；

C、 传播性；

D、 激发性：在一定的条件刺激下，病毒程序迅速活跃起来；

E、 破坏性和危害性；

3.3 计算机网络硬件

硬件系统是计算机网络的基础。硬件系统有计算机、通信设备、连接设备及辅助设备组成。硬件系统中设备的组合形式决定了计算机网络的类型。下面介绍几种网络中常用的硬件设备。

服务器：服务器是一台速度快，存储量大的计算机，它是网络系统的核心设备，负责网络资源管理和用户服务。服务器可分为文件服务器、远程访问服务器、数据库服务器、打印服务器等。

工作站：工作站是具有独立处理能力的计算机，它是用户向服务器申请服务，如传输文件，打印文件等的终端设备。

网卡：网卡又称为网络适配器，它是计算机和计算机之间直接或间接传输介质互相通信的接口，它插在计算机的扩展槽中。它将计算机的数字信号转换成通信线路能够传送的电子信号或电磁信号。

调制解调器：调制解调器(Modem)是一种信号转换装置。它可以把计算机的数字信号“==调制”==成通信线路的模拟信号，将通信线路的模拟信号==“解调”==回计算机的数字信号。调制解调器的作用是将计算机与公用电话线相连接。

集线器：集线器(Hub)是局域网中使用的连接设备。它具有多个端口，可连接多台计算机。在局域网中常以集线器为中心，用双绞线将所有分散的工作站与服务器连接在一起，形成星形拓扑结构的局域网系统。集线器是工作在带宽共享方式下的，多台计算机通过各个端口连接到集线器上时，它们只能共享一个信道的带宽；

交换机：而交换机(Switch)是模拟用网桥连接各个网络的方式工作。

网桥：网桥(Bridge)也是局域网使用的连接设备。网桥的作用是扩展网络的距离，减轻网络的负载。当信号通过网桥时，网桥会将非本网段的信号排除掉(即过滤)，使网络信号能够更有效地使用信道，从而达到减轻网络负担的目的。

路由器：路由器(Router)是互联网中使用的连接设备。它可以将两个网络连接在一起，组成更大的网络。路由器不仅有网桥的全部功能，还具有路径的选择功能。

网关：网关(Gateway)是一种复杂的网络连结设备，它工作在OSI的高三层（会话层、表示层和应用层），用来连接异构网络。网关具有对不兼容的高层协议进行转换的功能。网关的工作实际上是在一台计算机内运行一个转换软件。

四、计算机编码

4.1.字符编码(ASCII码)

​ 微机中普遍利用的字符编码是ASCII码，它是美国信息交换标准代码,也是国际上通用的微型机编码。我国据此制定GB1988，GB1988用52个英文大小写字母，32个标点符号、运算符和34个控制字符，共128种。每个字符用一个7位二进制数来表示，在微型机内用一个字节来存储，最高位D7恒为0。

用二进制和十六进制写出“xY”的ASCII编码。
二进制：01111000B 01011001B
十六进制：78H 59H
ASCII码值的大小规律：a~z>A~Z>09>空格>控制符

国标码：GB码（中文在计算机中的编码）

4.2 汉字机内码

在计算机内部传输、存储、处理的汉字编码称为汉字机内码。
通常利用字节的最高位来区分某个码值是代表汉字还是ASCII字符，最高位为“1”视为汉字符，为”0”是为ASCII字符。
机内码就是在国标码的基础上将两个字节的最高位一律由“0”改 “1”。

如“大”的国标码为3473H：
3473H 00110100 01110011 (国标码)“大”
B4F3H 10110100 11110011 (机内码)“大”

4.3 汉字输入码

为了利用计算机上现有的标准西文键盘来输入，必须为汉字设计输入编码。输入编码也称外码。归纳数量众多的输入码有四大类：数字编码、拼音码、字形码和音形码。其中，目前应用最广泛的是拼音码和字形码。
注意：无论采用哪一种汉字输入法，当用户向计算机输入汉字时存入计算机中的总是它的 机内码，与所采用的输入法无关。

4.4 汉字交换码

​ 计算机内部处理的信息，都是用二进制代码表示的，汉字也不例外。而二进制代码使用起来是不方便的，于是需要采用信息交换码。中国标准总局 1981 年制定了中华人民共和国国家标准 GB2312–80《信息交换用汉字编码字符集–基本集》，即国标码。《信息技术 中文编码字符集》（GB 18030-2022）强制性国家标准发布，将于2023年8月1日正式实施。

第一个标准：GB2312 采用 两个 字节对每个汉字进行编码，按照使用 频率 将汉字区分为一级汉字和二级汉字

• 一级汉字：按照拼音顺序排序（用的多）
• 二级汉字：按照部首排序

全角标点：两个字节

半角标点：一个字节

​ GB2312-80 标准包含 6763 个汉字，按使用频度分为一级汉字 3755 个、二级汉字 3008个。一级汉字按拼音排序，二级汉字按部首排序。

4.5 汉字字形码

字形存储码是指供计算机输出汉字（显示或打印）用的二进制信息，也称字模。通常采用的是数字化点阵字模。是表示汉字字形信息（汉字的结构、形状、笔划等）的编码，用来实现计算机对汉字的输出（显示、打印）。由于汉字是方块字，因此字形码最常用的表示方式是点阵形式，有16 ×16点阵、24×24点阵、32× 32点阵、48 ×48点阵等等。例如， 16 ×16点阵的含义为：用256（16 ×16=256）个点来表示一个汉字的字形信息，例如需 16×16bit=16×16/8byte=32 byte 的存储空间。在相同点阵中，不管其笔划繁简，每个汉字所占的字节数相等。。每个点有“亮”或“灭”两种状态，用一个二进制位的“1”或“0”来对应表示。因此，存储一个16 ×16点阵的汉字需要256个二进制位，共32个字节。

汉字字库由所有汉字的字模码构成，一个汉字字模码究竟占多少个字节由汉字的字形决定。
常用的字模码有4种：

• 简易型16*16点阵，字模码为32字节
• 普通型24*24点阵，字模码为72字节
• 提高型32*32点阵，字模码为128字节
• 精密型48*48点阵，字模码为288字节
  汉字库的分类：
  软字库（将汉字库文件存储在软盘或硬盘中）
  硬字库（利用汉卡将汉卡安装在机器的扩展槽中）

同一汉字的汉字交换码和汉字机内码内容并不相同，对于ASCII字符来说，机内码和交换码是一样的。

4.6 视频帧率与码率

帧率：

先说一下帧，1 帧就是一张图片。帧率就是每一秒包含的帧数。

视频实际上就是把一连串的图片，用很快的速度连续切换，看不出中间切换的空隙，就成了视频。那么每一秒包含的图片越多，视频看起来也就越流畅。

码率：

码率也叫比特率，是指每秒传送的比特(bit)数，数值越大，传送数据速度越快。是一个决定整体视频质量的参数。一般主流视频平台的最高码率在1Mbit左右。

4.6 Unicode 统一码

统一码 (Unicode)，也叫万国码、单一码，是计算机科学领域里的一项业界标准。Unicode 是 为了解决传统的字符编码方案的局限而产生的，它为每种语言中的每个字符设定了统一并且唯一的 二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。

为每种语言的每个字符都统一设定了唯一的二进制编码：

Unicode 字符集可以简写为 UCS (Unicode Character Set)，UCS-2 用两个字节编码， UCS-4 用四个字节编码。现在常见的方案有

UTF-8、UTF-16、UTF-32，UTF 是 Unicode Transformation Format 的缩写。

4.7 原码、补码、反码

4.7.1 原码

• 符号位为 0 表示正数，符号位为 1 表示负数，其余各位表在用二进制原码表示的数中 数值部分。

如：10000010，00000010。

4.7.2 反码

反码的定义如下：

• 对于正数，它的反码表示与原码相同。即[ x ]反=[ x ]原
• 对于负数，则除符号位仍为“1”外，其余各位 “1”换成”0”，”0”换成 1”，即得到反码[ X ]反。例如[-1101001] 反=10010110。
• 对于 0，它的反码有两种表示:[+0] 反=00…0 [-0] 反=11…1

4.7.3 补码

• 正数的补码就是该正数本身。[01100100]补 ＝01100100
• 对于负数：两头的 1 不变，中间取反。（负数取反加一）[10100100]补 ＝11011100
• [+0]补＝[-0]补＝00…0。
• 在计算机中，正数是直接用原码表示的，如单字节5，在计算机中就表示为：0000 0101。负数用补码表示，如单字节-5，在计算机中表示为1111 1011。

总结： 正数的原码、反码、补码相同，负数反码符号位不变其余取反，负数的补码=反码+1。（补码的作用主要方便计算机运算）

4.7.4 BCD 码（8421 码）

BCD 码就是用二进制代码表示的十进制数，也称 BCD 数。它是用 4 位二进制代码 0000—1001 来表示十进制数 0—9。如：39 的 BCD 码为 00111001。

---

不快乐的练习题：

（1） 一个有符号整数的二进制补码为 1111111111101101，则其原码对应的 10 进制为 ？

（2）一个有符号整数的二进制原码为 1011010，则其反码为 ，补码为 ？

（3）一个 10 进制整数-2，如果表达为带符号的 8 位 2 进制，那么其原码为 ，反码为 ，补码为 ？

---

五、进制基础

5.1 数制

• 数制是数的表示和计算方法。
• 十进制数
  表示：０～９
  计算的方法：逢十进一
  例：18+74=92
• 二进制数

​ 表示：100010

​ 计算的方法：逢二进一

​ 例：10+10=100

5.2 进制的表示方法

• 第一种：（数值）R，R为进制的类型。
• 第二种：数值后跟一特定大写英文字母。
  • ​ 十进制数： 表示符D(可省略)
  • ​ 二进制数： 表示符B
  • ​ 八进制数： 表示符Q（为避免把字母O误认作零，改由Q代替）
  • ​ 十六进制数：表示符H，前缀为0X或0x
    例如：
• 十进制数423，表示为（423）10或 423D或423
• 二进制数1001，表示为（1001）2或1001B
• 八进制数237，表示为（237）8或237Q
• 十六进制数5FE，表示为（5FE）16 或5FEH。

计算机内部用二进制来表示数据主要原因：
(1)电路实现简单可行
(2)可靠性高
(3)运算简单
(4)逻辑性强。

5.3 R进制转十进制

R进制： 非十进制

5.4 十进制转R进制

短除法: 除基数取余数、由下而上排列 两例。

例子： 将10转换为二进制数

结果为: 1010

5.5 十进制小数转R进制小数

进位法：用十进制小数乘基数，当积为或达到所要求的精度时, 将整数部分由上而下排列,乘R取整。

示例：

将(0.625)10​转换成二进制小数

• 0.625×2=1.250… 取整 1
• 0.250×2=0.500… 取整 0
• 0.500×2=1.000… 取整 1

结果为：0.101

示例：

将0.65转换成八进制小数

• 0.65×8=5.20… 取整 5
• 0.20×8=1.60… 取整 1
• 0.60×8=4.80… 取整 4
• 0.80×8=6.40… 取整 6

结果为：0.5146

数值信息在计算机内的表示方法就是用二进制数来表示。一般说来，如果数制只采用 R 个基本符号（0~R-1），则称为基 R 数值，R 称为数制的基数，而数制中每一固定位置对应的单位值称为权。

5.6 R进制的相互转换

每位八进制数相当于三位二进制数，每位十六进制数相当于四位二进制数。在转换时，位组划分是以小数点为中心向左右两边延伸，中间的 0 不能省略，两头不够时可以补 0。尤其是小数后末尾的 0。

例如: 将 1011010.12​ 转换成八进制和十六进制数

001101015​01131010. A ​ 010. 2.10008​1004 1011010. 12​=5 A. 816​​ 1011010. 12​=132.48​

例如：将十六进制数 F7.28 变为二进制数

F 1111​7⋅20111.00101000​8​ F7. 2816​=11110111.001012​​

六、数学函数

6.1 常用数学函数

C++提供了很多实用的数学函数，如果要使用先添加头文件<cmath>或<math.h>

#include<cmath>
#include<math.h>

1 绝对值

解释

fabs()
double fabs (double);//求实数的绝对值。
cout<<"-54.29的绝对值是："<<fabs(-54.29);
-54.29的绝对值是：54.29

abs()
cout<<"-53的绝对值是:"<<abs(-53);
-53的绝对值是:53

labs()
long labs(long n); 求长整型数的绝对值。
cout<<"-123456789的绝对值是："<<labs(-123456789);
-123456789的绝对值是：123456789

2 取整

解释

floor( )//向下取整
double floor(double x); 求不大于x的最大整数，它相当于数学函数[x]。
cout<<"51.12的向下取整是:"<<floor(51.12)<<endl;
cout<<"26.81的向下取整是:"<<floor(26.81)<<endl;  

51.12的向下取整是:51
26.81的向下取整是:26
  
ceil( )//向上取整
double ceil(double x);求不小于x的最小整数。
cout<<"不小于45.06的最小整数:"<<ceil(45.06);
不小于45.06的最小整数:46

3 指数与对数

解释

double pow (double, double);//求x的y次方。
cout<<"4.2的5次方是:"<<pow(4.2,5);
4.2的5次方是:1306.91
  
double sqrt (double);// 求x的平方根
cout<<"9的平方根是:"<<sqrt(9);
9的平方根是:3
  
double log (double); 以e为底的对数
double log10 (double);c++中自然对数函数：log(N)  
//以10为底：log10(N)但没有以2为底的函数但是可以用换底公式解决：log2(N)=log10(N)/log10(2)

4 三角函数

double sin (double);// 正弦函数。
double cos (double);//余弦函数。
double tan (double);// 正切函数。

5 反三角函数

double asin (double); //结果介于[-PI/2, PI/2]
double acos (double); //结果介于[0, PI] PI=acos(-1)

6 min和max函数

解释

C = max(A, B);返回队列中的最大值。
C = min(A, B);返回队列中的最小值。 
    
INT_MAX 和 INT_MIN 是 C++ 的两个预定义宏，代表了整型变量能够存储的最大正整数和最小负整数，分别为 2147483647 和 -2147483648。

INT_MAX 表示一个 32 位符号整数所能够表示的最大值，也就是 231−1，而 INT_MIN 则表示最小的负整数。这个值是相对于二进制补码表示法的，也就是说，负数的范围比正数大 1。

6.2 位运算

6.2.1 位运算

一 位运算符号
and，&，∧ ,∩

• 按位与： 如果两个相应的二进制位都为1，则该位的结果值为1，否则为0

or，|，∨，∪

• 按位或: 两个相应的二进制位中只要有一个为1，该位的结果值为1

not，! ,~, ¬

• 取反~是一元运算符: 用来对一个二进制数按位取反，即将0变1，将1变0

xor,^ ,⊕

• 按位异或: 若参加运算的两个二进制位值相同则为0，否则为1

举例：

     1000101             1000101         1000101         1000101
 &   0101100           | 0101110      !                ^ 0101110
 =   0000100           = 1101111       = 0111010         1101011

6.2.2 移位运算

左移（<<）运算

a<<b是指将整数a的各个二进制位左移b位，高位丢弃，低位用0补齐。需要注意的是b必须是非负整数。在高位没有1丢弃的情况下，a<<1相当于a*2。

右移（>>）运算

a>>b是指将整数a的各个二进制位右移b位，低位丢弃。对于无符号数，高位补0。对于有符号数，某些机器将对左边空出的部分用符号位填补（即“算术移位”），而另一些机器则对左边空出的部分用0填补（即“逻辑移位”）。同样，b必须是非负整数。a>>1相当于a/2。

6.3 运算优先级

说明：

同一优先级的运算符，运算次序由结合方向所决定。
简单记就是：！ > 算术运算符 > 关系运算符 > && > || > 赋值运算符

---

蜜汁小口诀

括号成员在第一;     //括号运算符[]() 成员运算符.  ->
全体单目是第二;     //所有的单目运算符比如++、 --、 +(正)、 -(负) 、指针运算*、&乘除余三,加减四;      //这个"余"是指取余运算即%
移位五，关系六;   //移位运算符：<< >> ，关系：> < >= <=                       
等和不等排第七;   //即== 和!=
位与异或和位或;    //这几个都是位运算: 位与(&)异或(^)位或(|)   
"三分天下"八九十;  
  逻辑或跟与;       //逻辑运算符:|| 和 &&
  十二和十一;       //注意顺序:优先级(||)  底于 优先级(&&) 
 条件高于赋值,     //三目运算符优先级排到13 位只比赋值运算符和","高
逗号运算级最低!   //逗号运算符优先级最低 

七、循环嵌套

循环结构与分支结构的嵌套类似，也可以在一个循环语句的循环体里出现另一个循环语句，不管是 while 语句、do-while 语句还是 for 语句。这样的循环结构称为“循环嵌套”。

循环嵌套的基本结构：

解释

for ( i 初始值; i 循环条件; i 让循环停止的方法){
  for ( j 初始值; j 循环条件; j 让循环停止的方法){
    执行语句
  }
}

注意: 外层循环用了 i, 内层循环就要用 j, 目前来说不可能出现嵌套循环的情况下外层循环和内层循环用同一个变量的情况！

7.1 嵌套循环用法

作用： 在循环体中再嵌套一层循环，解决一些实际问题

例如我们想在屏幕中打印如下图片，就需要利用嵌套循环

示例：

解释

int main() {

	//外层循环执行1次，内层循环执行1轮
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			cout << "*" << " ";
		}
		cout << endl;
	}


	return 0;
}

7.2 循环嵌套模拟

用一张一元票换1分、2分和5分的硬币，每种至少一枚， 问有几种换法？

输出只有一行（这意味着末尾有一个回车符号），包括1个整数。

解释

#include<iostream>
using namespace std;
int main(){
   int i,j,x,y;
    int c=0;
        for(int i=1;i<=100-2-5;i++){
            x=100-i;
            for(j=1;j<=(x-5)/2;j++){
                y=x-j*2;
                if(y%5==0){
                    c++;
                }
            }
        }
    cout<<c<<endl;
    return 0;
}

7.3 真题模拟

【问题描述】
输入一个正整数 n，输出 n 行的数字三角形。其中，第 1 行为数字 1，第 2 行为数字 23，第 3行为数字 456，第 4 行为数字 7890，第 5 行为数字 12345，…
【输入格式】
一行一个正整数 n，1≤n≤100。
【输出格式】
n 行的数字三角形。
【样例输入】
4
【样例输出】
1
23
456
7890

解释

#include<cstdio>
using namespace std;
int main(){
    int n,t = 1;
    scanf ("%d",&n);
    for(int i = 1; i <= n; i++){
          for(int j = 1; j <= i; j++){
                 printf( “ %d ” ,t % 10);
                 t++;
                 }
          printf( “ \n ” );
          }
    return 0;
}

八、多层循环分支语句

8.1 break与continue

8.1.1 break语句

​ 在循环体中遇到 break 语句，就会立刻跳出循环体，执行循环结构后面的语句。或者 switch 语句中，用来跳出整个语句块。

• break 跳出最里层的循环，并且继续执行该循环下面的语句。也就是说如果有多层循环，break只跳出当前这一层的循环。

解释

#include<bits/stdc++.h>
using namespace std;
int main() {
	for (int i = 0; i <= 9; i++) {
		int a = 0;
		for (int j = 0; j <= 9; j++) {
			cout << a++;
			if (a == 5) {
				break;  //跳出本层的循环
			}
		}
		cout << endl;
	}
	return 0;
}

8.1.2 continue 语句

在循环体中遇到 continue 语句，就会忽略本次循环的后续语句而去执行下一次循环。

continue 适用于任何循环控制结构中。作用是让程序立刻跳转到下一次循环的迭代。

解释

#include<bits/stdc++.h>
using namespace std;
int a;
int main() {
	for (int i = 0; i <= 9; i++) {
		a = 0;
		for (int j = 0; j <= 9; j++) {
			cout << a++;
			if (a == 5) {
				continue;  //忽略本次循环的后续语句而去执行下一次循环
				cout<<"this";

			}

		}
		cout << endl;
	}
	return 0;
}

九、 枚举算法

计算机的特点之一就是运算速度快，善于重复做一件事。“枚举”正是基于这一特点的最古老的算法。它一般是在一时找不出解决问题的更好途径，即从数学上找不到求解的公式或规则时，根据问题中的“约束条件”，将解的所有可能情况一一列举出来，然后再逐个验证是否符合整个问题的求解要求，从而求得问题的可行解或者最优解。

某公园门票价格为：成人票8元/张，儿童票3元/张；某旅游团来公园游玩，该团内有成人和儿童（成人和儿童都有），共花了40元买门票，请你分别计算出成人和儿童可能的人数，按照成人从少到多，儿童从多到少的规律数出结果。

若干行，每行2个整数用空格隔开，分别代表成人和儿童可能的人数（成人从少到多，儿童从多到少）

解释

#include<bits/stdc++.h>
using namespace std;
int x;
int main() {
	for (int i = 1; i <= (40-3)/8; i++) {
		x=40-i*+8;
		if(x%3==0) {
			cout<<i<<" "<<x/3<<endl;
		}
	}
	return 0;
}

素数的判定
【问题描述】
输入一个正整数，判断其是否为素数。如果是，则输出“prime”；否则，输出“not prime”。
【输入格式】
一行一个正整数 n，2≤n≤10^7 。
【输出格式】
一行一个字符串。
【样例输入】
8
【样例输出】
not prime

解释

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int x;
    cin >> x;
    for(int i = 2; i <= sqrt(x); i++){// 或者 i*i < =x
           if(x % i == 0){
                  cout <<  “ not  “ ;
                  break; 
           }
    }
    cout <<  “ prime ” << endl;
    return 0;
}

(2021年9月真题)比 n 小的最大质数 对于给定的 n，求比 n 小的质数中最大的一个。 质数是指一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数。 输入一个整数 n。（2<n<10000） 输出一个整数，即题目要求的解。
样例输入 100 样例输出 97

解释

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int n;
    int i, j, t;
    cin >> n;
    for (i = n - 1; i >= 2; i--)
    {
        t = i;
        for (j = 2; j < t; j++)
        {
            if (t % j == 0)
                break; //找到一个符合条件的即退出循环
        }
        if (j == t) //循环到最后没有找到能被整除的数
        {
            cout << i;
            break; //找到一个符合条件的即退出循环
        }
    }
    return 0;
}

讲的太好了

。。。。。。谢谢。。。。。。

知识点有点广，虽然很长，但显得有些臃肿，不过还可以的

oiiaoiiaooaoi

好东西收藏下

二出了，可以看看
CSP初赛知识点梳理(2) - 【活动】信奥笔记分享 / 普及组 - 信友队论坛 (xinyoudui.com)