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–

进栈时检查上溢,出栈时检查下溢

img

2.队列

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

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

img

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

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

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

3.树

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

img

定义:一棵树是由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层上至多有2i12^{i-1}​个节点

性质2:深度为h的二叉树中至多含有2h12^{h-1}​个节点

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

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

5.图

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

图的概念、遍历:略(过于长且为最基本的知识)

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

​ (1)存在欧拉路的条件:图是连通的,有且只有2个奇点。(入度+出度为奇数)

​ (2)存在欧拉回路的条件:图是连通的,有0个奇点。