CSP-JS 第一轮复习资料

计算机硬件

1. 计算机发展

• 第一代计算机（1946–1958）：

  • 使用电子管作为主要元件，体积巨大、能耗大，计算速度较慢。
  • 代表性计算机：ENIAC（电子数值积分和计算机）。

• 第二代计算机（1959–1964）：

  • 使用晶体管替代电子管，体积更小、效率更高、能耗更低。
  • 代表性计算机：IBM 1401、CDC 1604。

• 第三代计算机（1965–1970）：

  • 使用集成电路（IC），计算机性能大幅提升，体积进一步缩小。
  • 代表性计算机：IBM 360系列。

• 第四代计算机（1971至今）：

  • 使用大规模集成电路（VLSI），使得计算机高度集成，进入个人计算机时代。
  • 代表性计算机：Apple II、IBM PC。

2. 我国的计算机发展情况

• 1960年：我国成功研制出107机，成为第一台国产计算机。
• 1997年：我国研制出超算银河III，每秒运行130亿次，为世界领先水平。

3. 冯·诺依曼理论

• 提出了计算机的存储程序原理：程序和数据共存于内存中，计算机通过顺序读取指令并执行。
• 计算机由五大部分组成：输入设备、输出设备、运算器、控制器和存储器。

4. 计算机硬件组成部分

• 中央处理单元（CPU）：

  • 负责执行计算机的程序和指令。
  • 包含算术逻辑单元（ALU）、控制单元（CU）和寄存器。

• 内存（RAM）：

  • 临时存储数据，读写速度快。

• 硬盘/固态硬盘（HDD/SSD）：

  • 用于长期存储数据。

• 输入设备：

  • 如键盘、鼠标、扫描仪等。

• 输出设备：

  • 如显示器、打印机等。

5. 计算机常识

• 操作系统：计算机的软件系统，负责硬件管理和资源调度。
• 常见操作系统：Windows、Linux、macOS。

6. 计算机相关人物与奖项

• 图灵奖：计算机科学界的最高奖项，被称为“计算机界的诺贝尔奖”。
• 冯·诺依曼：提出了冯·诺依曼结构，并奠定了计算机体系结构的基础。

例题

1. 问题：第一代计算机使用的是什么技术？

   • 选项：
     A) 晶体管
     B) 电子管
     C) 集成电路
     D) 大规模集成电路
   • 答案：B) 电子管

2. 问题：下列哪一项不是冯·诺依曼计算机结构的一部分？

   • 选项：
     A) 输入设备
     B) 输出设备
     C) 集成电路
     D) 存储器
   • 答案：C) 集成电路

软件与操作系统

1. 操作系统功能

• 资源管理：负责分配和管理计算机的硬件资源（CPU、内存等）。
• 任务调度：管理多个进程的执行顺序，保证系统的高效性和稳定性。
• 文件管理：负责文件的存储、访问和权限管理。

2. 操作系统类型

• 单任务操作系统：如MS-DOS，每次只能运行一个任务。
• 多任务操作系统：如Windows、Linux，可以同时运行多个任务。

3. 操作系统的常见类型

• Windows：广泛使用的图形用户界面操作系统，适用于个人电脑。
• Linux：开源操作系统，广泛应用于服务器和嵌入式系统。
• macOS：苹果公司开发的操作系统，基于Unix系统。

CSP-JS 第一轮复习资料（第二版）

目录

1. 进制与编码

   • 进制的标识
   • 进制间的相互转换
   • 带符号数的机器码表示方法
   • 编码 - ASCII码
   • 机器数与真值
   • 逻辑运算
   • 位运算符
   • 例题

进制与编码

1. 进制的标识

在计算机中，进制指的是数字系统中用来表示数字的基数。常见的进制有：

• 二进制（Binary）：基数为2，仅包含两个数字：0和1。计算机内部使用二进制来表示数据。
• 十进制（Decimal）：基数为10，使用数字0到9。十进制是我们日常生活中最常用的数制。
• 八进制（Octal）：基数为8，使用数字0到7。在计算机中，八进制用于简化二进制表示。
• 十六进制（Hexadecimal）：基数为16，使用数字0到9和字母A到F来表示数字。十六进制是计算机中常用于表示二进制的简便形式，特别是在处理内存地址时。

进制的表示方法：

• 二进制：0b 或 0B 前缀表示，如：0b1101。
• 八进制：0 前缀表示，如：071。
• 十六进制：0x 前缀表示，如：0x1F。

2. 进制间的相互转换

二进制与十进制的转换

• 二进制转十进制：将二进制数的每一位乘以2的对应幂次，然后求和。例如，二进制数1011转换为十进制：
  [
  1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 8 + 0 + 2 + 1 = 11
  ]
• 十进制转二进制：将十进制数除以2，记录余数，直到商为0，然后将余数逆序排列。例如，十进制数13转换为二进制：
  [
  13 \div 2 = 6 \text{余} 1 \
  6 \div 2 = 3 \text{余} 0 \
  3 \div 2 = 1 \text{余} 1 \
  1 \div 2 = 0 \text{余} 1
  ]
  余数逆序排列得到二进制数1101。

十进制与八进制的转换

• 十进制转八进制：将十进制数除以8，记录余数，直到商为0，然后将余数逆序排列。
• 八进制转十进制：将八进制数的每一位乘以8的对应幂次，然后求和。

十进制与十六进制的转换

• 十进制转十六进制：将十进制数除以16，记录余数，直到商为0，然后将余数逆序排列。十六进制的余数可以是0-9，或者A-F，表示数字10到15。
• 十六进制转十进制：将十六进制数的每一位乘以16的对应幂次，然后求和。

二进制与十六进制的转换

• 二进制转十六进制：将二进制数从右到左每4位分成一组，转换为十六进制数。例如，11011110转为十六进制：
  [
  1101 = D, \ 1110 = E \Rightarrow \text{十六进制} = DE
  ]
• 十六进制转二进制：将十六进制的每一位转换为对应的4位二进制数。

3. 带符号数的机器码表示方法

计算机中使用补码表示法来表示带符号的整数，补码表示法能够简化加法和减法操作。

• 正数：正数的补码与原码相同。
• 负数：负数的补码是其对应的绝对值的二进制表示按位取反后加1。

例如，8位补码表示法：

• 正数+5的原码和补码都是00000101。
• 负数-5的补码是：先写出5的二进制00000101，按位取反得到11111010，再加1得到11111011。

4. 编码 - ASCII码

ASCII（美国信息交换标准代码）是计算机中用于表示字符的标准编码，使用7位二进制表示字符。ASCII码包括英文字母、数字、标点符号等常用字符。

• ASCII码表：

  • 字母A的ASCII值为65，二进制表示为01000001。
  • 字母a的ASCII值为97，二进制表示为01100001。
  • 数字0的ASCII值为48，二进制表示为00110000。

扩展ASCII：为了表示更多字符，ASCII的扩展使用了8位，即添加了128个字符，通常用于表示其他语言的字符、符号以及图形符号等。

5. 机器数与真值

• 机器数：机器数是计算机内部存储的数值，在计算机中通常使用补码表示法来表示带符号数。
• 真值：真值是数字在实际数学中表示的数值。对于补码表示法，真值可以通过将补码转换为原码来获得。

例如，11111111的机器数在8位补码表示法下是-1，其真值为-1。

6. 逻辑运算

在计算机中，逻辑运算用于对二进制数据进行处理，常见的逻辑运算有：

• 与（AND）：两个操作数对应位都为1时，结果才为1，否则为0。

  • 例：1010 AND 1100 = 1000

• 或（OR）：两个操作数对应位都为0时，结果为0，否则为1。

  • 例：1010 OR 1100 = 1110

• 非（NOT）：对每一位进行取反，0变为1，1变为0。

  • 例：NOT 1010 = 0101

• 异或（XOR）：两个操作数对应位不同时，结果为1，否则为0。

  • 例：1010 XOR 1100 = 0110

7. 位运算符

位运算符用于对整数的二进制位进行操作，常见的位运算符有：

• 与（&）：按位与运算。
• 或（|）：按位或运算。
• 异或（^）：按位异或运算。
• 取反（~）：按位取反，将0变为1，将1变为0。
• 左移（<<）：将二进制数的所有位向左移动指定的位数，相当于乘以2。
• 右移（>>）：将二进制数的所有位向右移动指定的位数，相当于除以2。

例题

1. 问题：将二进制数1011转换为十进制是多少？

   • 选项：
     A) 8
     B) 9
     C) 10
     D) 11
   • 答案：D) 11
   • 解析：1011的二进制转为十进制是：1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 = 8 + 0 + 2 + 1 = 11。

2. 问题：将十进制数10转换为二进制是多少？

   • 选项：
     A) 101
     B) 110
     C) 1001
     D) 1111
   • 答案：A) 101
   • 解析：10的十进制转为二进制是：10 / 2 = 5余0，5 / 2 = 2余1，2 / 2 = 1余0，1 / 2 = 0余1。逆序排列余数得到101。

数据结构

1. 字符串

定义：字符串是由一系列字符组成的序列，通常用于表示文本数据。字符串在许多编程语言中都有特殊的处理方式。在C++中，std::string是一个常用的字符串类型，而在C语言中，字符串通常是字符数组。

常见操作：

• 查找：寻找某个字符或子串在字符串中的位置。
• 替换：将字符串中的某些字符或子串替换为新的字符或子串。
• 连接：将两个或多个字符串连接成一个新的字符串。
• 截取：从字符串中提取指定位置的子串。

应用场景：

• 文本处理：如文本搜索、替换、格式化等。
• 字符串匹配：如正则表达式匹配、子串查找等。

2. 链表

定义：链表是一种由多个节点组成的线性数据结构，每个节点包含数据和指向下一个节点的指针（或引用）。与数组不同，链表在内存中不需要连续存储。

类型：

• 单链表：每个节点包含一个指向下一个节点的指针。
• 双链表：每个节点包含两个指针，一个指向下一个节点，另一个指向前一个节点。
• 循环链表：最后一个节点的指针指向头节点，形成循环。

常见操作：

• 插入：在链表的头部、尾部或中间插入新的节点。
• 删除：删除链表中的指定节点。
• 查找：查找链表中是否包含指定的数据。

应用场景：

• 动态数据结构：链表适用于无法预知数据量的情况，如实时插入和删除操作频繁的场景。
• 内存管理：操作系统中的内存分配往往使用链表结构。

3. 栈

定义：栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。即最后插入的元素最先被删除。

常见操作：

• push：将元素压入栈中。
• pop：将栈顶元素弹出。
• peek：查看栈顶元素，但不删除。

应用场景：

• 函数调用栈：计算机内部使用栈来管理函数调用和返回。
• 括号匹配：使用栈来检查表达式中的括号是否匹配。
• 深度优先搜索（DFS）：使用栈来实现图的深度优先遍历。

4. 队列

定义：队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构。即最早插入的元素最先被删除。

常见操作：

• enqueue：将元素添加到队列的尾部。
• dequeue：将队列的头部元素移除。
• peek：查看队列的头部元素，但不删除。

应用场景：

• 任务调度：操作系统中的任务调度通常使用队列来管理任务的执行顺序。
• 广度优先搜索（BFS）：使用队列来实现图的广度优先遍历。
• 消息队列：在分布式系统中，队列用于处理异步消息。

5. 树形结构

定义：树是一种层次结构的非线性数据结构，由若干节点组成，每个节点有一个父节点和若干个子节点。树的顶端节点称为根节点。

常见类型：

• 二叉树：每个节点最多有两个子节点。
• 平衡树：一种自平衡的二叉搜索树，保持树的高度平衡，从而保证最优的查找性能。
• 堆：一种特殊的二叉树，满足堆的性质，如最大堆或最小堆。

常见操作：

• 遍历：常见的遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历。
• 插入：在树中插入新的节点。
• 删除：从树中删除指定的节点。

应用场景：

• 表达式树：用于解析和计算数学表达式。
• 决策树：在机器学习中用于分类问题。
• 二叉查找树（BST）：用于高效地查找、插入、删除操作。

6. 二叉树

定义：二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，通常分别称为左子节点和右子节点。

常见类型：

• 满二叉树：每个节点都具有两个子节点，除了叶子节点。
• 完全二叉树：除了最后一层外，每层都是满的，且最后一层的节点都靠左对齐。
• 平衡二叉树（AVL树）：树的左右子树的高度差不超过1，保证了最优的查找性能。

常见操作：

• 前序遍历：根节点 -> 左子树 -> 右子树。
• 中序遍历：左子树 -> 根节点 -> 右子树。
• 后序遍历：左子树 -> 右子树 -> 根节点。
• 层序遍历：逐层遍历树的所有节点。

应用场景：

• 表达式树：表示数学表达式，通过遍历树来计算结果。
• 二叉查找树：常用于快速查找、插入、删除数据。

7. 前/中/后缀表达式

前缀表达式（Polish Notation）：操作符位于操作数之前。例如，+ 3 4表示3 + 4。

中缀表达式：操作符位于操作数之间，是最常见的数学表示方式。例如，3 + 4。

后缀表达式（Reverse Polish Notation）：操作符位于操作数之后。例如，3 4 +表示3 + 4。

应用场景：

• 计算器实现：后缀表达式常用于计算机中实现计算器，因为它不需要括号来明确操作顺序。
• 表达式解析：前缀和后缀表达式用于避免括号，使表达式计算更加简便。

8. 图

定义：图是一种由节点（也称为顶点）和连接节点的边组成的数据结构。图可以是有向图（每条边有方向）或无向图（边没有方向）。

常见类型：

• 有向图：边具有方向，例如：从A到B。
• 无向图：边没有方向，例如：A与B互相连接。
• 加权图：每条边有一个权重，用于表示边的代价或距离。

常见表示方法：

• 邻接矩阵：使用一个二维矩阵来表示图中的边，适合于稠密图。
• 邻接表：使用链表或其他数据结构来表示每个节点的邻接节点，适合于稀疏图。

常见操作：

• 深度优先搜索（DFS）：从一个节点开始，尽可能深入地访问每个子节点。
• 广度优先搜索（BFS）：从一个节点开始，首先访问所有邻接节点，然后逐层向外扩展。

应用场景：

• 社交网络：图可以表示社交网络中的用户和他们的关系。
• 地图和导航：图用于表示城市之间的道路和距离，广泛应用于最短路径算法。

例题

1. 问题：下列哪种数据结构适合用来实现回溯算法？

   • 选项：
     A) 栈
     B) 队列
     C) 链表
     D) 图
   • 答案：A) 栈
   • 解析：回溯算法使用栈来存储选择的状态和回溯的路径。

2. 问题：在二叉树中，哪种遍历方式是左子树 -> 根节点 -> 右子树？

   • 选项：
     A) 前序遍历
     B) 中序遍历
     C) 后序遍历
     D) 层序遍历
   • 答案：B) 中序遍历
   • 解析：中序遍历的顺序是左子树 -> 根节点 -> 右子树。

排列组合

1. 加法原理（分类计数原理）

加法原理又称为分类计数原理，它是用于求解多个互不重叠事件总的可能性数的方法。具体来说，如果一个事件A有m种可能，另一个事件B有n种可能，并且事件A和事件B没有重叠（即两者互斥），那么这两个事件的总可能性数为 m + n。

例子：

• 假设你有两种选择：买一台电视有5个品牌，买一台手机有3个品牌。如果你只能选择其中一种，那么你有5 + 3 = 8种选择。

应用场景：

• 这种方法常用于选择问题，特别是当多个选择事件互不重叠时。

2. 乘法原理（分步计数原理）

乘法原理用于计算当有多个步骤的过程中，每个步骤的选择不相互影响时，总的可能性数。例如，如果事件A有m种可能，事件B有n种可能，那么事件A和事件B同时发生的总可能性数为 m * n。

例子：

• 假设你选择一种饮料（有3种选择），然后选择一种小吃（有4种选择），则你一共可以选择 3 * 4 = 12 种不同的饮料和小吃组合。

应用场景：

• 这种方法常用于当事件依次发生并且每一步的选择互不干扰时。

3. 排列

排列是从n个不同元素中按一定顺序选出r个元素的不同排列方式。排列的顺序是非常重要的，因为不同的顺序会产生不同的排列。

排列的公式为：

[
P(n, r) = \frac{n!}{(n - r)!}
]

其中：

• n是元素的总数。
• r是选出的元素的个数。
• n!是n的阶乘，即n (n-1) (n-2) ... 1。

例子：

• 从5个不同的球中，选出3个球的不同排列数为：(\frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{5 \times 4 \times 3 \times 2!}{2!} = 60)。

应用场景：

• 排列在实际中经常用于安排、排序等情境，如安排比赛、选拔等。

4. 组合

组合是从n个不同元素中，不考虑顺序地选出r个元素的不同方式。与排列不同，组合不考虑顺序，因此选出的元素在不同的顺序下是相同的。

组合的公式为：

[
C(n, r) = \frac{n!}{r!(n - r)!}
]

其中：

• n是元素的总数。
• r是选出的元素的个数。
• n!、r!、(n - r)!都是阶乘。

例子：

• 从5个球中选3个球的组合数为：(\frac{5!}{3! \times 2!} = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10)。

应用场景：

• 组合通常用于不考虑顺序的选取问题，如从一组学生中选出班长、副班长等。

5. 排列组合解题技巧

对称性

排列和组合公式具有对称性，即：

[
C(n, r) = C(n, n - r)
]

例如，从10个元素中选5个和从10个元素中去除5个，结果是相同的。

递推法

有时候可以通过递推来简化计算。例如，组合数满足递推关系：

[
C(n, r) = C(n - 1, r - 1) + C(n - 1, r)
]

这个递推关系在很多组合问题中都有应用，特别是当问题分解成多个子问题时。

排列组合的拆分与组合

在复杂的排列组合问题中，通常需要将问题拆分成多个简单的子问题，然后根据加法原理和乘法原理逐一解决。例如，首先选择一个类别的元素，再从另外的类别中选择，最后合并结果。

6. 排列组合的经典问题

排列与组合的应用问题：

1. 选举问题：

   • 从10个候选人中选出3个，进行排列选择。
   • 使用排列公式：(\frac{10!}{(10-3)!} = 720)。

2. 宝石问题：

   • 有5种不同颜色的宝石，每种颜色至少选1颗，要选出3颗宝石的排列方式。
   • 解法：可以选任意颜色的组合，然后排列这些选出的宝石。

3. 球队选拔问题：

   • 从11名球员中选出5名参加比赛，不考虑顺序。
   • 解法：使用组合公式：(\frac{11!}{5!(11 - 5)!} = 462)。

排列组合的经典解法：

1. 从n个不同元素中选r个元素的排列数：

   • 在不考虑顺序的情况下，选出r个元素。

2. 从n个元素中选r个元素，不放回的抽取：

   • 需要考虑不放回的情况，即每次选择后，元素数量减少。

7. 排列组合与概率

排列组合也广泛应用于概率论中。例如，计算从一个装有不同球的盒子中抽取球的概率时，可以使用排列组合方法来计算总可能性数和期望事件的可能性数，从而得出概率。

例题

1. 问题：从6个人中选出3个人参加比赛，选法有多少种？

   • 选项：
     A) 20
     B) 30
     C) 60
     D) 120
   • 答案：B) 20
   • 解析：从6个人中选出3个，无需考虑顺序，使用组合公式：(\frac{6!}{3!(6 - 3)!} = 20)。

2. 问题：从5本书中选3本，按照不同顺序排列，有多少种方法？

   • 选项：
     A) 60
     B) 100
     C) 120
     D) 150
   • 答案：A) 60
   • 解析：选出3本书并排列使用排列公式：(\frac{5!}{(5 - 3)!} = 60)。

3. 问题：在一个盒子里有4个红球、3个绿球、2个蓝球，从中随机取2个球，问取到1个红球和1个蓝球的概率是多少？

   • 选项：
     A) (\frac{4}{9})
     B) (\frac{2}{9})
     C) (\frac{3}{9})
     D) (\frac{1}{9})
   • 答案：B) (\frac{2}{9})
   • 解析：从9个球中取2个，组合数为(\frac{9!}{2!(9 - 2)!} = 36)，取到1个红球和1个蓝球的情况为4 * 2 = 8种。概率为(\frac{8}{36} = \frac{2}{9})。

复杂度

1. 定义

复杂度是算法分析中的重要概念，它衡量算法在执行时对资源（时间和空间）的消耗情况。主要分为时间复杂度和空间复杂度。

时间复杂度

时间复杂度是指算法执行所需时间随输入规模的增长而变化的规律。它主要用来衡量一个算法执行所需的时间。常见的时间复杂度包括：

• O(1)：常数时间复杂度，表示算法的执行时间不随输入规模的变化而变化。例如，访问数组的元素。
• O(n)：线性时间复杂度，表示算法的执行时间与输入规模n成正比。例如，遍历数组的每个元素。
• O(n^2)：平方时间复杂度，表示算法的执行时间与输入规模n的平方成正比。例如，冒泡排序、选择排序。
• O(log n)：对数时间复杂度，表示算法的执行时间与输入规模n的对数成正比。常见于分治算法，如二分查找。
• O(n log n)：线性对数时间复杂度，常见于高效的排序算法，如快速排序和归并排序。

空间复杂度

空间复杂度是指算法执行过程中所需内存空间的大小随输入规模的变化而变化的规律。它主要用来衡量算法执行时所需要的存储空间。常见的空间复杂度包括：

• O(1)：常数空间复杂度，表示算法所需空间不随输入规模的变化而变化。例如，交换两个变量的值。
• O(n)：线性空间复杂度，表示算法所需空间与输入规模n成正比。例如，复制数组时需要额外的空间来存储新的数组。
• O(n^2)：平方空间复杂度，通常出现在需要构造二维数组的情况下，如矩阵乘法。

2. 时间复杂度的详细分析

常数时间复杂度 (O(1))：

• 例子：访问数组的元素（arr[i]）。无论数组的大小如何，访问一个元素的时间总是相同的。
• 常见操作：简单的赋值、条件判断、函数调用。

线性时间复杂度 (O(n))：

• 例子：遍历一个数组或链表的每个元素。例如，求数组中所有元素的和。
• 公式分析：若输入规模为n，则算法需要进行n次操作，因此时间复杂度为O(n)。