一、计算机系统知识
1.1 计算机系统的基础知识
1.1.1 计算机系统硬件基本组成
计算机的基本硬件系统：运算器、控制器、存储器、输入设备、输出设备；
1.1.2 中央处理单元（CPU）
中央处理单元：运算器、控制器等部件被集成在一起统称为中央处理单元（Center Processing Unit，CPU）；
1、CPU的功能
- 程序控制
- 操作控制
- 时间控制
- 数据处理
2、CPU的组成
CPU主要由运算器、控制器、寄存器组和内部总线等组件组成；
运算器
运算器由算术逻辑单元（Arithmetic and Logic Unit，ALU）、累加寄存器、数据缓冲寄存器和状态条件寄存器等组成，是数据加工处理部件，用于完成各种算术和逻辑运算（只能完成计算），所有的操作由控制器发出控制信号指挥，故为执行组件；
功能：
- 执行所有的算术运算，如加、减、乘、除等基础运算及附加运算；
- 执行所有的逻辑运算并进行逻辑测试，如与、或、非、零值测试或两个值的比较等；
各组成部件的功能：
算术逻辑单元（ALU）
负责处理数据，实现对数据的算术运算和逻辑运算；
累加寄存器（AC）
简称累加器，为算术逻辑单元（ALU）提供工作区，运算器中至少有一个累加器；
数据缓冲寄存器（DR）
作为CPU和内存、外部设备之间数据传送的中转站，在操作速度上的缓冲；
对内存存储器进行读/写操作时，用DR暂时存放读/写的一条指令或一个数据字，将不同时间段的读/写数据隔离；
状态条件寄存器（PSW）
PSW保存由算术指令和逻辑指令运行或测试的结果建立的各种条件码内容，主要分为状态标志和控制标志；
通常，一个算术操作产生一个运算结果，而一个逻辑操作产生一个判决；
控制器
用于控制整个CPU的工作，决定了计算机运行过程的自动化（程序的正确执行、异常事件的处理）；
一般包括指令控制逻辑、时序控制逻辑、总线控制逻辑和中断控制逻辑等；
指令控制逻辑要完成取指令、分析指令和执行指令的操作，过程：取指令=>指令译码=>按指令操作码执行=>形成下一条指令地址=>等步骤；
指令寄存器（IR）
CPU执行一条指令时，先从内存储器取到缓冲寄存器（DR），在送入指令寄存器（IR）暂存，指令译码器（ID）通过指令寄存器（IR）中的内容产生各种微操作指令，由此控制其他组成组件工作，完成相关功能；
程序计数器（PC）
具有寄存信息、计数两种功能，又称指令计数器；
程序的执行分两种情况：顺序执行、转移执行；
地址寄存器（AR）
保存当前CPU所访问的内存单元的地址；
由于内存和CPU操作速度上的差异，所以地址寄存器要保存地址信息知道内存的读/写操作完成；
指令译码器（ID）
指令包含：操作码、地址码；
指令译码器对指令中的操作码字段进行分析解释，识别指令的操作，向操作控制器发出操作信号，控制各部件工作，完成所需功能；
时序控制逻辑要为每条指令按时间顺序提供应有的控制信号；
总线控制逻辑是为多个功能组件服务的信息通路的控制电路；
中断控制逻辑用于控制各种中断请求，并根据优先级的高低对中断请求进行排队，逐个交给CPU；
寄存器组
寄存器组可分为：专用寄存器（如运算器和控制器中的寄存器，作用固定）、通用寄存器（用途广泛）；
3、多核CPU
1.1.3 数据表示
二进制计数制
原码、反码、补码、移码（小数无移码）
原码表示法中，最高位是符号位，0表示正号，1表示负号，其余的n-1位表示数值的绝对值；
| +1 | -1 | +0.5 | -0.5 | +0 | -0 | |
|---|---|---|---|---|---|---|
| 原码 | 00000001 | 10000001 | 0.1000000 | 1.1000000 | 00000000 | 10000000 |
| 反码 | 00000001 | 11111110 | 0.1000000 | 1.0111111 | 00000000 | 11111111 |
| 补码 | 00000001 | 11111111 | 0.1000000 | 1.1000000 | 00000000 | 00000000 |
| 移码 | 10000001 | 01111111 | 无 | 无 | 10000000 | 10000000 |
- 一个正数的原码、反码、补码相同；一个正数的移码除最高位与其原码、反码、补码最高位不同外，其他位都相同（即其原码最高位+1）；
- 一个负数的原码除最高位与其绝对值的原码不同外，其他位都相同（即其绝对值的原码最高位+1）；
- 一个负数的反码与其绝对值的原码、反码每一位都不相同，（即绝对值反码每一位取反）；
- 一个负数的补码等于其反码末尾+1；
- 除小数外，任何一个数的补码符号位取反即是相对应的移码；
1.1.4 校验码
- 奇偶校验码
- 水平奇偶校验码
- 垂直奇偶校验码
- 水平垂直校验码
- 海明码
- 循环冗余校验码
二、程序设计语言基础知识
三、数据结构
四、操作系统知识
五、软件工程基础知识
六、结构化开发方法
七、面向对象技术
八、算法设计与分析
8.1 算法设计与分析的基本概念
8.1.1 算法
算法一般具有五个特性：有穷性、确定性、可行性、输入、输出；
8.1.2 算法设计
好的算法应考虑：正确性、可读性、健壮性、高效性等；
常用算法设计技术包括：分治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等；
8.1.3 算法分析
8.1.4 算法的表示
8.2 算法分析基础
8.2.1 时间复杂度
8.2.2 渐进符号
8.2.3 递归式
8.3 分治法
概念
递归的两个基本要素：
边界条件
递归模式
基本思想
一般来说，分治算法在每一层递归都有三个步骤：
分解
求解
合并
实例
归并排序
8.4 动态规划法
基本思想
找出最优解的性质，并刻画其结构特征
递归定义最优解的值
自底向上算出最优值
构造最优解
实例
0-1背包问题
8.5 贪心法
实例
活动选择问题
背包问题
8.6 回溯法
以深度优先的方式系统地搜索问题的解的方法称为回溯法。
界限函数的设计是回溯法的一个核心问题；
8.7 分支限界法
8.8 概率算法
8.9 近似算法
8.10 数据挖掘算法
8.11 智能优化算法
快速排序算法
快速排序算法是一种经典的排序算法，其基本思想是选择一个基准元素(通常选择第一个元素或者最后一个元素)，通过一趟排序将待排序序列分成两部分，一部分比基准元素小，一部分大于等于基准元素，此时基准元素在其排好序后的正确位置；然后再递归地排序划分的两部分，因此本质上快速排序是一种分治算法。由于在排序的过程中，各元素与基准元素比较大小，若小于基准元素则与基准元素交换位置，因此该算法是不稳定的排序算法。当每一趟排序进行后，选择的基准元素恰好最大或者最小时，就把序列分成极端不均衡的两部分，即一部分为空，另一部分为待排序序列的元素个数减1，此时算法处于最坏情况，其时间复杂度为O(n2)。当输入数据基本有序或者所有元素值相等时，不论选择第一个元素还是最后一个元素作为基准元素，都恰好把序列分成极端不均衡的两部分，快速排序算法具有最坏情况下的时间复杂度。
- 完全二叉树
- 描述：完全二叉树是深度为k的，有n个节点的二叉树，其特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。每个节点最多只能有两棵子树，且有左右之分。
- 举例：考虑一个深度为3的完全二叉树，它有7个节点。按照完全二叉树的定义，这些节点会被排列成三层，第一层1个节点（根节点），第二层2个节点（左右子节点），第三层4个节点（填满最后一层）。
- 线索二叉树
- 描述：线索二叉树是对普通二叉树进行线索化得到的。线索化的过程是在二叉树的结点上加上线索，即利用二叉链存储结构中的空链域来存放前驱和后继结点的指针。通过线索化，可以方便地实现二叉树的遍历，提高了遍历速度并节约了存储空间。
- 举例：假设有一个简单的二叉树，其节点有空链域。通过线索化，我们可以在这些空链域中存储指向前驱和后继节点的指针，从而方便地按某种顺序（如中序）遍历整棵树。
- 二叉排序树（二叉查找树）
- 描述：二叉排序树是一种特殊的二叉树，其中左子树上所有结点的值均小于根节点的值，右子树上所有结点的值均大于根节点的值。它的主要优势在于可以快速地（二分查找）查询、插入和删除某个特定值的节点。
- 举例：假设我们有一个包含整数的二叉排序树，例如{4, 2, 6, 1, 3, 5, 7}。按照二叉排序树的规则，这些数字会被组织成一个树形结构，使得对于任何节点，其左子节点的值都小于它，右子节点的值都大于它。
- 最优二叉树（哈夫曼树）
- 描述：最优二叉树或哈夫曼树是在给定权值序列的情况下构造的带权路径长度最短的二叉树。它通常用于数据压缩和编码，通过给定权值（如字符频率）构造出最优的树形结构，使得编码后的数据尽可能小。
- 举例：假设我们有4个字符和它们的频率（权值）：A(5), B(9), C(12), D(13)。根据哈夫曼树的构造算法，我们首先选择频率最低的两个字符（A和B）作为子节点构造一个新的内部节点（频率为14），然后重复这个过程，直到只剩下一个节点。最终得到的哈夫曼树将用于编码这些字符，以实现最优的压缩效果。
排序
- 直接插入排序：
- 原理：每次将一个待排序的记录，按其顺序码大小插入到前面已经排序好的子序列的合适位置，直到全部插入排序完成为止。
- 举例：对于序列[3，1，4，1，5，9，6，5]，初始时认为第一个元素已排序。然后，将第二个元素1与第一个元素3比较，发现1更小，于是将3后移，1插入到前面。继续这个过程，直到所有元素都排序完毕。
- 时间复杂度：O(n^2)，其中n是待排序元素的数量。
- 冒泡排序：
- 原理：通过重复地遍历待排序的序列，比较每对相邻的元素，如果它们的顺序错误就把它们交换过来。这个过程会重复进行，直到没有更多的元素需要交换，也就是说该序列已经排序完成。
- 举例：对于序列[3，1，4，1，5，9，6，5]，首先比较第一对元素(3和1)，交换它们的位置。接着比较第二对元素(1和4)，不需要交换。然后比较第三对元素(4和1)，再次交换。这个过程持续进行，直到整个序列有序。
- 时间复杂度：在最好情况下为O(n)，最坏情况下为O(n^2)。
- 选择排序：
- 原理：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
- 举例：对于序列[3，1，4，1，5，9，6，5]，首先在未排序部分找到最小的元素1，将其与第一个位置的元素交换。然后在剩余未排序部分继续找到最小的元素1，与第二个位置的元素交换。这个过程持续进行，直到所有元素排序完毕。
- 时间复杂度：O(n^2)。
- 快速排序：
- 原理：通过选择一个“基准”元素，将序列分为两部分，其中一部分的所有元素都比基准元素小，另一部分的所有元素都比基准元素大。然后递归地对这两部分进行快速排序。
- 举例：对于序列[3，1，4，1，5，9，6，5]，选择第一个元素3作为基准。将比3小的元素移到其左边，比3大的元素移到其右边。然后递归地对左右两部分进行快速排序。
- 时间复杂度：平均情况下为O(n log n)，最坏情况下为O(n^2)。
- 归并排序：
- 原理：采用分治策略，将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列段间有序。
- 举例：对于序列[3，1，4，1，5，9，6，5]，首先将其分成两个子序列[3，1，4，1]和[5，9，6，5]，然后分别对这两个子序列进行归并排序。排序完成后，再将这两个有序子序列合并成一个有序序列。
- 时间复杂度：O(n log n)。
九、数据库技术基础
9.9.1 数据库与数据库系统
数据库系统（DataBase System，DBS）是一个采用了数据库技术，有组织地、动态地存储大量相关数据，方便多用户访问的计算机系统。
DBS由数据库、硬件、软件和人员组成。
数据库
数据库（DataBase，DB）是统一管理的、长期存储在计算机内的、有组织的相关数据的集合。
特点：数据间联系密切、冗余度小、独立性高、易拓展，并且可为各类用户共享。
硬件
软件
数据库管理系统简称DBMS。
主要功能包括：数据定义、数据操作、数据库运行管理、数据库的建立与维护。
人员
主要有四类：系统分析员和数据库设计人员、应用程序员、最终用户、数据库管理员（Data Base Administrator，DBA）
9.1.2 数据库管理系统的功能
数据库管理系统主要实现对共享数据有效地组织、管理和存取，具有以下六个方面的功能：
- 数据定义
- 数据库操作
- 数据库运行管理
- 数据的组织、存储和管理
- 数据库的建立和维护
- 其他功能
9.1.3 数据库管理系统的特征及分类
- DBMS的特征
- DBMS的分类
- 关系型数据库系统
- 面向对象的数据库系统
- 对象关系数据库系统
9.1.4 数据库系统的体系结构
- 集中式数据库系统
- 客户端/服务器结构
- 并行数据库系统
- 分布式数据库系统
为了保证数据库中数据的安全可靠和正确有效，数据库管理系统(DBMS)提供数据库恢复、并发控制、数据完整性保护与数据安全性保护等功能。
标准SQL对数据库对象(基本表、索引和视图等)的创建、修改和删除定义了一组操作分别为CREATE、ALTER和DROP；对基本表和视图中数据的插入、删除和修改定义了操作分别为INSERT、DELETE和UPDATE。
十、网络与信息安全基础知识
10.1 网络概述
10.1.1 计算机网络的概念
目前人们已公认的有关计算机网络的定义是：利用通信设备和线路将地理位置分散、功能独立的自主计算机系统或由计算机控制的外部设备连接起来，在网络操作系统的控制下，按照约定的通信协议进行信息交换，实现资源（硬件资源（CPU、大容量的磁盘、光盘以及打印机等）、软件资源（语言编译器、文本编辑器、各种软件工具和应用程序等））共享的系统。
1、计算机网络的发展（点、线、面、体）
- 具有通信功能的单机系统（终端-计算机网络）
- 具有通信功能的多机系统（计算机-计算机网络）
- 以共享资源为目的的计算机网络
- 以局域网及因特网为支撑环境的分布式计算机系统
2、计算机网络的功能
数据通信
资源共享
提高系统资源的利用率，软件资源共享、硬件资源共享；
负载均衡
多台计算机相互协作，均衡负载、共同完成任务，某台计算机任务过重时，可将任务分配给其余空闲的多台计算机；
高可靠性
避免单机无后备的情况，某台计算机出现故障后，其任务可由其他计算机代为处理；
10.1.2 计算机网络的分类
局域网（Local Area Network，LAN）
局域网指传输距离有限、传输速度较高、以共享网络资源为目的的网络系统；
特点：
- 分布范围有限；（园区网、校园网）
- 有较高的通信带宽，数据传输率高；（1Mbps<= <=1000Mbps）
- 数据传输可靠，误码率低；（百万分之一到万分之一）
- 通常采用同轴电缆或双绞线作为传输介质，跨楼宇时使用光纤；
- 拓扑结构简单。简介，大多采用总线、星型和环形等，系统容易配置和管理；（网络上的计算机一般多采用多路控制访问技术或令牌技术访问信道）
- 网络的控制一般趋向于分布式，从而减少了对某个结点的依赖，避免并减少了一个结点故障对整个网络的影响；
- 通常，网络归单一组织所拥有和使用，不受任何公共网络管理机构
城域网
广域网
10.1.3 网络的拓扑结构
- 总线型结构
- 星型结构
- 环形结构
- 树形结构
- 分布式结构
10.1.4 ISO/OSI网络体系结构
十一、标准化和软件知识产权基础问题
软件许可
软件许可使用一般有独占许可使用、独家许可使用和普通许可使用三种形式。
独占许可使用，许可的是专有使用权，实施独占许可使用后，软件著作权人不得将软件使用权授予第三方，软件著作权人自己不能使用该软件；
独家许可使用，许可的是专有使用权，实施独家许可使用后，软件著作权人不得将软件使用权授予第三方，软件著作权人自己可以使用该软件；
普通许可使用，许可的是非专有使用权，实施普通许可使用后，软件著作权人可以将软件使用权授予第三方，软件著作权人自己可以使用该软件。
十二、软件系统分析与设计
模块独立性是创建良好设计的一个重要原则，一般采用模块间的耦合和模块的内聚两个准则来进行度量。耦合是模块之间的相对独立性的度量，模块之间的连接越紧密，联系越多，耦合性就越高，而其模块独立性就越弱。
一般来说，模块之间的耦合有7种类型，根据耦合性从低到高为非直接耦合、数据耦合、标记耦合、控制耦合、外部耦合、公共耦合和内容耦合。
如果一个模块访问另一个模块时，彼此之间是通过数据参数(不是控制参数、公共数据结构或外部变量)来交换输入、输出信息的，则称这种耦合为数据耦合；如果一组模块通过数据结构本身传递，则称这种耦合为标记耦合；若一组模块都访问同一个公共数据环境，则它们之间的耦合就称为公共耦合；若一个模块直接访问另一个模块的内部数据、一个模块不通过正常入口转到另一个模块内部、两个模块有一部分程序代码重叠或者一个模块有多个入口，上述几个情形之一发生则说明两个模块之间就发生了内容耦合。
