CSP-S初赛知识点整理

如题，2021届。

一、计算机硬件软件基础知识

• 第一台计算机：1946.2 ENIAC

• 第一位程序员：Ada Lovelace

• 计算机届最高奖：图灵奖

• 冯诺依曼理论：计算机硬件设备：存储器、运算器、控制器、输入设备、输出设备。

• 1KB=1024B 1MB=1024KB 1GB=1024MB 1TB=1024GB 1PB=1024TB

• RAM是读写存储器，当断电时数据全部丢失;ROM是只读存储器，断电时数据不丢失。

• 外存储器——>内存储器——>Cache——>CPU

• 总线结构: 数据总线:传输数据信息 地址总线:传送地址信息 控制总线:传送控制信号，协调各部件之间的操作。

• CPU种类:

  Intel: Core ，Itanium、Pentium、8086

  AMD：Ryzen、Athlon64、Opteron

• 桌面操作系统：

  Unix系统:Linux发行版（如Ubuntu、Arch、Centos、Redhat等）、Mac OS X、FreeBSD、Solaris等

  类Unix：Windows

• 计算机语言:机器语言---->汇编语言----->高级语言

  汇编语言: 汇编源程序 ---翻译程序---> 目标程序 ---连接程序---> 可执行程序

  编译型语言(高级语言):C/C++、Pascal等 源程序 ---编译程序---> 目标程序 ---连接程序---> 可执行程序

  解释型语言(高级语言):ASP、PHP、Java、JavaScript、Python等 源程序 ---解释程序---> 可执行程序

  面向对象语言：几乎当代所有的高级语言都是面向对象的（C语言除外，C++面向对象）（世界上第二个面向对象语言是Smalltalk）

  高级语言的程序可移植性好、汇编语言的精简程度高。

• 进制转换：略

• 信息编码: 最小单位**:Bit（比特）**表示一个"0"或"1"

  一个字节：由8个Bit组成。是存储器系统的最小存取单位。

  ASCII编码:7位二进制码（1个字节）

  一个中文字符：2个字节

二、基本数据结构

1.栈

定义：栈是只能在某一端插入和删除的特殊线性表。栈也称为后进先出表（LIFO表）

表示方法：一个栈可以用定长为n的数组s来表示，用一个指针top指向栈顶。top=0时栈空，top=n时栈满，top<0时为下溢，top>n是为上溢。

进栈时top++，x[top]=n

出栈时top--

进栈时检查上溢，出栈时检查下溢。

2.队列

定义:队列是限定在一端进行插入，另一端进行删除的特殊线性表。队列也称为先进先出表（FIFO）

表示方法：一个队列可以用一个数组q来表示，用一个指针front指向队头，rear指向队尾。

由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

对于这种现象可以使用循环队列。即当尾指针越过上界时，可以判断底部是否还有剩余空间，从而讲尾指针指向队尾。形象地来看，就像一个循环一样。

PS:对于循环队列中元素个数:n=(r-f+n)%n(其中r表示尾指针，f为头指针，n为数组大小)

3.树

树是一种非线性的数据结构

定义：一棵树是由n个元素组成的有限集合，其中：

​ （1）每个元素称为节点（node）。

​ （2）有一个特定的节点，无父节点，称为根节点（root）。

​ （3）除根节点外，其余节点能分成m个互不相交的有限集合，其中每个子集又都是一棵树。

基本概念：

​ （1）一棵树至少有一个节点，每个节点除根节点外都有一个前驱结点（父节点），可以有0个或多个后继节点。

​ （2）一个节点的子树的个数，称为这个节点的度。

​ （3）定义根节点的深度为1，其他节点的深度是其父节点+1。

遍历方式：

​ （1）先序遍历：先访问根节点，然后从左到右按照先序思想遍历各个子树。如上图：ABDECF（根-左-右）

​ （2）后序遍历：先从左到右遍历各个子树，然后访问根节点。如上图：DEBFCA（左-右-根）

​ （3）层次遍历：按深度从小到大逐个访问，同一深度按照从左到右的顺序。如上图：ABCDEF

4.二叉树

二叉树（binary tree）是一种特殊的树型结构，它是度数为2的树。

每个节点的子节点分别称为左孩子、右孩子，两棵子树分别称为左子树、右子树。

性质1：二叉树的第i层上至多有​个节点

性质2：深度为h的二叉树中至多含有​个节点

性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1

性质4：具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）

5.图

gragh=(V,E)。V是一个非空有限集合，代表顶点，E代表边的集合。

图的概念、遍历：略（过于长且为最基本的知识）

一笔画问题：如果一个图存在一笔画，则一笔画的路径称为欧拉路，如果最后回到起点，那么这个路径称为欧拉回路。

​ （1）存在欧拉路的条件：图是连通的，有且只有2个奇点。（入度+出度为奇数）

​ （2）存在欧拉回路的条件：图是连通的，有0个奇点。