CSP 初赛复习

CSP 初赛考察的计算机基本知识。

计算机

发展

年代 实现方式
1946-1958 电子管
1959-1964 晶体管
1965-1970 集成电路
1971-? 超大规模集成电路

分类

巨型机大、中型机小型机微型机工作站

关键人物

  • 阿兰·图灵（Alan Mathison Turing）（英）：数学家，逻辑学家，计算机科学、人工智能之父，首次提出了计算机科学理论。现代计算机的基础是抽象的图灵机。“图灵奖”以他命名，被称为“计算机界的诺贝尔奖”，目前获得该奖项的华人学者仅有 2000 年图灵奖得主姚期智教授。

  • 约翰·冯·诺依曼（John von Neumann）（美）：科学家，现代计算机之父，首次提出了存储程序控制原理，称为“冯·诺依曼结构”。

  • 克劳德·香农（Claude Elwood Shannon）（美）：科学家，创造了信息论，提出了某种信息从一处传送到另一处所需的全部设备所构成的系统。

  • 王选（中）：汉字激光照排系统的创始人，为新闻、出版全过程的计算机化奠定了基础，被誉为“汉字印刷术的第二次发明”。中国计算机学会王选奖原名“中国计算机学会创新奖”，于2005年创立，每年评选一次，属于社会力量设立的科学技术奖。2006年，为了纪念王选院士为中国计算机事业做出的非凡贡献，学中国计算机学会将中国计算机学会创新奖更名为中国计算机学会王选奖。

  • 莱布尼茨（德）：数学家，发明了“乘法器”，即能够连续重复地做加法减法。

构成

  • CPU：即中央处理器，计算机的核心部件，由运算器（计算）、控制器（指挥）、寄存器组成。

  • 主存储器（内存储器）：属于主机的一部分，属于临时存储器。相对外存而言，读写速度快，但是存储空间小。内存储器通常可以分为 RAM（随机存储器）、ROM（只读存储器）、Cache（高速缓存存储器）。

  • 辅助存储器（外存储器）：属于外部设备，属于永久存储器。常见的外存通常有软盘、硬盘、U 盘和光盘。

  • 输入设备：在计算机与人交互时，接受外部命令或者需要加工的数据。常用的输入数据包括键盘、鼠标、麦克风和摄像头。

  • 输出设备：在计算机与人交互时，将处理结果以人类能够识别、感受的方式呈现出来的设备。常有的输出设备包括显示器、音响、打印机等。

语言

  • 机器语言：计算机可以直接识别，速度快，用二进制代码编写，一般很难掌握，属于低级语言。

  • 汇编语言：用一些符号代替机器指令，源程序不能被计算机直接识别，可移植性差，属于低级语言。

  • 高级语言：计算机不能直接识别，通过编译或解释使计算机识别。

高级语言的运行方式

  • 编译：将整个程序都转换成二进制代码，生成目标程序，然后把目标程序连接成可执行程序，编译性语言有 C/C++、Pascal。
  • 解释：解释程序边扫描边解释，对源程序解释一条执行一条，不产生目标程序，解释性语言有 PHP、JS、Python。

杂项

冯·诺依曼结构

  • 计算机硬件设备由运算器、控制器、存储器、输入设备和输出设备5部分组成。

  • 存储程序思想——把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和数据一起输入计算机，计算机对已存入的程序和数据处理后，输出结果。

ACSCII

ASCII 码（American Standard Code for Information Interchange）是美国国家交换标准代码，现成为世界交换代码标准。

ASCII 码是一种用 8 个比特组成的二进制编码（即一个字节），用于表示 128 个国际通用字符。

机器数与真值

  • 原码：原码将一个整数表示成符号位加二进制串。符号位上，0 表示正数，1 表示负数。

  • 反码：对于一个正数，反码就是其原码；对于一个负数，反码就是除符号位外，原码的各位全部取反，即 0 变 1，1 变 0。

  • 补码：对于一个正数，补码就是其原码；对于一个负数，补码等于反码加 1。

对于 -5，其原码为 1101，反码为 1010，补码为 1011。

逻辑运算

  • 逻辑非： 或 ，操作数的反值。

  • 逻辑与： 或 ，全部操作数都为真，结果才为真。

  • 逻辑或： 或 ，至少一个操作数为真，结果才为真。

  • 运算优先级：逻辑非逻辑与逻辑或。

数据存储

对于一张无压缩的图，分辨率为 ， 位色，则大小为 字节（Byte）。

对于一段无压缩的音频，码率为 kbps，时常为 s，则大小为 KiB。

网络

  • 局域网（LAN），城域网（MAN），广域网（WAN）。

  • 传输控制协议（TCP），网际协议（IP）。

  • TCP/IP 协议共有 4 层协议

OI

进制

  • 十进制转 进制：整数部分，辗转除 ，取余。小数部分，辗转乘 ，取整数部分。

  • 进制转十进制：按位转换，第 位的数字乘以要转换的进制的 次幂即可。

  • 进制转 进制：以十进制作为中转，先将 进制转为十进制，再将十进制转为 进制。

排列组合

  • 加法原理：完成一项工作有 种方法， 代表完成第 类方法的数目，共有 种不同的方法。

  • 乘法原理：完成一项工作有 个步骤， 代表完成第 个步骤的数目，共有 种不同的方法。

  • 错排

主定理

见主定理。

二叉树遍历

  • 前序遍历：根结点 -> 左子树 -> 右子树

  • 中序遍历：左子树 -> 根结点 -> 右子树

  • 后序遍历：左子树 -> 右子树 -> 根结点

  • 计算前缀表达式：

- + 1 × + 2 3 4 5

从右至左扫描，将 压入堆栈；

遇到 运算符，弹出 和 （ 为栈顶元素， 为次顶元素），计算 的值，得到 ，将 压入栈；

遇到 运算符，弹出 和 ，计算 的值，得到 ，将 压入栈；

遇到 ，将 压入栈；

遇到 运算符，弹出 和 ，计算 的值，得到 ，将 压入栈；

遇到 运算符，弹出 和 ，计算 的值，得到 为最终结果。

  • 计算后缀表达式：

1 2 3 + 4 × + 5 -
从左至右扫描，将 压入栈；
遇到 运算符， 和 弹出，计算 的值，得到 ，将 压入栈；
遇到 ，将 压入栈
遇到 运算符，弹出 和 ，计算 的值，得到 ，将 压入栈；
遇到 运算符，弹出 和 ，计算 的值，得到 ，将 压入栈；
遇到 ，将 压入栈；
遇到 运算符，弹出 和 ，计算 的值，得到 为最终结果。

图

有向图：若有 个顶点，则最多有 条边，此时称作有向完全图。

无向图：若有 个顶点，则最多有 条边，此时称作无向完全图。

路径长度：路径上边或弧的数目。若路径上顶点没有重复出现，则称这条路径为简单路径。

生成树：极小连通子图。包含图的所有 个结点，但只含图的 条边。在生成树中添加一条边之后，必定会形成回路或环。

哈夫曼树：给定 个权值作为 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树（Huffman Tree）。

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。运用了贪心思想。

算法

算法的特征：有穷性，确切性，至少一个输出，可行性

表示方法：自然语言法，程序流程图法（顺序结构，选择结构，循环结构），程序法。

复杂度：时间复杂度，通常题目中给出的是时间递推关系式。

排序

  • 选择排序：对待排序的记录序列进行 遍的处理。第一遍处理是将 中最小
    者与 交换位置，第二遍处理是将 中最小者与 交换位置，以
    此类推，时间复杂度为 。选择排序是不稳定排序。

  • 插入排序：经过 遍处理后， 已排好序。第i遍处理仅将 插入 的适当位置 ，原来 后的元素一一向右移动一个位置，使得 又是排好序的序列，时间复杂度为 。插入排序是稳定排序。

  • 希尔排序：插入排序的优化版，时间复杂度不稳定，但略优于插入排序。希尔排序是不稳定排序。

  • 冒泡排序：又称交换排序。对待排序的记录的关键字进行两两比较，如果发现是反序的，则进行交换，时间复杂度为 。冒泡排序是稳定排序。

  • 堆排序：是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于它的父节点，时间复杂度为 。堆排序是不稳定排序。

  • 快速排序：先从数据序列中选一个元素，并将序列中所有比该元素小的元素都放在它的一边，
    再对左右两边分别用同样的方法处理，直到每一个待处理的序列长度为 ，处理结
    束。时间复杂度下限为 ，上限为 。快速排序是不稳定排序，基于分治思想。

CCF

NOI：中国计算机学会于 1984 年（当年，领导人提出计算机要从娃娃抓起）创办全国青少年计算机程序设计竞赛，即全国青少年信息学奥林匹克竞赛，是国内包括港澳在内的省级代表队最高水平的大赛。

NOIP：中国计算机学会于 1995 年创办全国青少年信息学奥林匹克联赛。NOIP 在同一时间、不同地点以各省市为单位由特派员组织。全国统一大纲、统一试卷，初、高中或其他中等专业学校的学生可报名参加。联赛分初赛和复赛，初赛考察通用和实用的计算机科学知识，以笔试为主。复赛为程序设计，须在计算机上调试完成。参加初赛者须达到一定分数线后才有资格参加复赛。联赛分普及组和提高组两个组别，难度不同，分别面向初中和高中阶段的学生。

从 2005 年开始，NOIP 不再支持 Basic；从 2022 年开始，不再支持 Pascal。
选手进入考场时，只许携带笔、橡皮等非电子文具入场。禁止携带任何电子产品或机器设备入场，无存储功能的手表除外；手机（关机）、U盘或移动硬盘、键盘、鼠标、闹钟、计算器、书籍、草稿纸及背包等物品必须存放在考场外。如有违规带入的，一经发现， NOI 各省特派员可直接取消违规选手的参赛资格。

CCSP：大学生计算机系统与程序设计竞赛，由中国计算机学会（CCF）于 2016 年发起的一个面向大学生的竞赛，每年举办一次，考察的是算法、编程以及计算机系统设计能力，旨在进一步提高计算机教育质量，使学生通过竞赛进一步学习和掌握计算机系统知识，同时对高校计算机教育产生引领作用。

CSP：中国计算机学会于 2014 年推出 CCF 计算机软件能力认证，该项认证重点考察软件开发者实际编程能力，由中国计算机学会统一命题、统一评测，委托各地设立的考试机构进行认证考试。该项认证每年大约3、9、12月各举办一次。认证者不限年龄，不限学历，不限报考次数，不限国籍 ，在报名官网注册账户后均可报名参加认证。

CSP 认证考试可以带纸质资料进入考场，不过只能是常用语言的程序设计基础书、数据结构的相关书籍。不允许U盘、手机等电子设备进入考场。

CSP-S/J：认证开始 15 分钟后，认证者不能再进入认证点。如有认证者提前离开认证点，除身体特别原因外，须在认证进行2小时后方可准予离开。在第一轮认证期间，任何人不得将试卷携带出考场。认证者进入考场时，监考检查认证者携带物品。认证者只许携带笔、橡皮等非电子文具入场。禁止携带任何电子产品或机器设备入场，无存储功能的手表除外；手机（关机）、U盘或移动硬盘、键盘、鼠标、闹钟、计算器、书籍、草稿纸及背包等物品必须存放在考场外。如有违规带入的，一经发现，CSP-J/S 认证总负责人可直接取消违规认证者的参加资格。

CSP-S/J：认证开始 15 分钟后，认证者不能再进入认证点。如有认证者提前离开认证点，除身体特别原因外，须在认证进行 2 小时后方可准予离开。在第一轮认证期间，任何人不得将试卷携带出考场。认证者进入考场时，监考检查认证者携带物品。认证者只许携带笔、橡皮等非电子文具入场。禁止携带任何电子产品或机器设备入场，无存储功能的手表除外；手机（关机）、U 盘或移动硬盘、键盘、鼠标、闹钟、计算器、书籍、草稿纸及背包等物品必须存放在考场外。如有违规带入的，一经发现，CSP-J/S 认证总负责人可直接取消违规认证者的参加资格。

算法
#计算机知识
CSP 初赛复习
https://operapeking.github.io/2022/08/31/csp-preliminary-round/
作者
Peking Opera
发布于
2022年8月31日
许可协议