1.1算法

算法不等于程序

1.特征：1）可行性 2）确定性 3）有穷性 4）足够的情报

2.基本结构：顺序，选择（分支），循环

3.时间复杂度：指计算工作量，基本运算次数

   空间复杂度：需要的内存复杂度。与时间复杂度互相独立

1.2数据结构

是相互有关联的数据元素的集合

1.数据项是数据的最小单位，数据元素是数据的基本单位

2.逻辑结构：

       线性结构：1）有且只有一个根节点，无前件

                       2）最多一个前件一个后件

       非线性结构：树形&网状

3.存储结构：数据的逻辑结构在计算机中的表示

       顺序存储：主要运用线性。

       链式存储：每个结点至少包括一个指针域。

              [结]：不同存储结构效率不同    

1.3线性表及顺序存储结构

线性表：n个数据元素组成的有限序列，线性。可以顺序存储（顺序表），链式存储。

特点：

       1）所有元素占空间连续 2）按逻辑顺序依次存放 3）随机访问  4）不便于插入删除

        包括：双向链表，循环链表

1.4(上)栈

限定在一端进行插入和删除的线性表

1. 只能在栈顶删除和插入
2. 先进后出，后进先出
3. 栈底指针不变，栈中元素随栈顶指针变化
4. 栈具有记忆功能，支持子程序调用

• 例. 设栈的存储空间为S(1:50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=1，则栈中的元素个数为（ ）

                A. 50                  B. 49                  C. 0                   D. 1

【题目解析】经过运算后当前栈中元素个数为初始top和结果top之差，即51-1=50,选A

1.4(下)队列

一端插入，另一端删除（类比排队），先进先出。队头为front,队尾为rear

特点：

1. 队尾插入，对头删除                                            
2. 先进先出
3. 元素随对头指针和队尾指针变化而变化

循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间

考点：

• rear>front,s=rear-front;②rear<front,s=容量+rear-front;③rear=front=NULL，s=0; rear=front≠NULL,s=1或0
• Q（1：m），front=rear=m,s=0; front=rear≠m,s=满或0.

当s满，再插入会“上溢错误”

1.5线性链表

线性表的顺序存储结构叫做顺序表，链式存储结构叫做线性链表

特点：

1. 存储空间可以不连续
2. 元素存储顺序与逻辑顺序可以不一致
3. 链式存储占存储空间大于顺序存储
4. 查找结点比顺序存储慢
5. 插入删除更灵活

1.6（上）树与二叉树

树：非线性结构。有且仅有一个根，其余元素为互不相交的子树

一些术语：

       根节点：无前件；叶子结点：无后件

       结点的度：一个结点有后件的个数；树的度：所有结点中最大的度

       深度：层数

性质：树的总节点数为树中所有结点度数之和再加一

二叉树：

有左右之分，不能颠倒

有五种形态：空二叉树；只有一个结点的；左节点；右结点；左右双全

1. 满二叉树，满二叉树是完全二叉树
2. 完全二叉树：设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树
3. 在二叉树第K层，最多有2**(k-1)个 结点
4. 深度为m的二叉树最多有2**m -1个结点
5. 度为0 的结点总比度为2的结点多一个
6. 有n个结点的二叉树深度至少为[log2n ]+1

1.7(上)树的遍历

分为：前序、中序、后序遍历

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

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

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

1.7（下）查找技术

1.顺序查找：最坏比较n次，平均而言2/n

       适用于无序表或链式线性表（不管无序有序）

2.二分查找：顺序存储且有序，最坏查找log2n 次

1.8排序

快速排序：取一个数作为基准数，通过交换把大的放右边，小的放左边，以基准数分为两个子表，重复步骤。一次能消除多个逆序。

选择排序：找出最小的数，如果此数不在第一个位置，就和在第一个位置的数进行交换

2.1程序设计风格

清晰第一，效率第二

良好的程序风格应：

1. 数据说明
2. 输入输出
3. 语句结构
4. 源程序内部文档化： 注释：序言性注释：首部，包括程序标题，功能说明，开发历史，程序作者…功能性注释

2.2结构化程序设计原则

①自顶向下②逐步求精③模块化④限用goto 语句

程序化语言基本成分：数据、运算、控制、传输

顺序，选择和循环

2.3面向对象程序设计

类的实例称为对象

对象特点：①标识唯一性②分类性③多态性④封装性⑤模块独立性

对象构成成分：标识（对象名），属性，操作

    抽象、封装、继承、多态

继承：使用已有类建立新类的定义技术，直接获得已有性质，不必重复定义

3.1软件工程

软件：程序&数据&文档

软件分类：1.系统软件：数据库管理系统，操作系统，汇编系统等

                  2.应用软件：教务管理系统

                  3.支撑软件（工具软件）

软件工程：把软件当作工程产品处理

       三要素：方法，工具，过程

生命周期：3时期8阶段。软件定义、开发及运行维护

       定义：可行性研究、需求分析

       开发：概要设计，详细设计，实现，测试

       维护：使用，维护

              需求分析：需求规格书:

• 便于用户和开发人员理解交流
• 作为软件开发的基础和依据
• 确认测试，验收的依据

3.2结构化分析方法：确定逻辑模型

需求分析方法：1.结构化分析方法：

                                   数据流图DFD,数据字典DD,判定表和判定树，建立系统逻辑模型

                                   数据字典是所有元素的定义的集合，是结构化分析的核心！

                         2.面向对象分析方法

3.3结构化设计方法：确定物理模型

划分：工程管理角度：概要设计 详细设计

      结构设计 数据设计 接口设计 过程设计

软件设计原理：抽象，模块化，信息隐蔽，模块独立性：高内聚低耦合

概要设计：程序结构图SC

详细设计：程序流程图，N-S图，PAD，PDL,HIPO

3.4软件测试：发现错误

1.静态测试：不实际运行；动态测试：上机运行

2.白盒测试：考虑内部逻辑结构

            ①逻辑覆盖测试②基本路径测试

  黑盒测试：完全不考虑程序内部逻辑结构，只检查正确的输出信息，考虑程序外部功能

            ①等价类划分法②边界值分析法③错误推测法

3.测试步骤：单元测试，集成测试，确认测试，系统测试

软件测试用例：是为测试设计的数据，包括输入数据和预期输出结果

3.5程序调试：诊断和改正程序错误

       【注】区分软件测试：发现错误

方法：强行排除法，回溯法，原因排除法

4.1数据库系统

数据：软件中数据有一定结构，有“型”“值”

1.数据库DB：数据集合。特点：集成&共享

2.数据库管理系统DBMS：系统软件。是数据库系统的核心

                     语言：数据定义语言DDL：数据模型定义，存取物理构建

                               数据操纵语言DML：数据操纵，增删改

                              数据控制语言DCL：安全性定义，并发控制故障恢复，数据完整性

3.数据库管理员DBA：设计维护改善提高效率

4.数据库系统DBS：

数据库应用系统DBAS：包括数据库系统、应用软件和界面

数据管理的阶段：人工管理->文件系统->数据库系统

数据库技术根本目标：解决数据共享问题

数据库系统特点：集成性，高共享低冗余，独立性，统一管理控制

三级模式和两级映射：
            外模式（子模式/用户模式）：用户的数据视图，外层

            概念模式：全体用户公共数据视图，逻辑结构，中层

            内模式（物理模式）：给出物理存储的结构和存取，最底层

            两级映射保证了：数据具有较高的逻辑独立性和物理独立性

关系数据库规范化：数据冗余，插入异常等问题

4.2数据模型

三要素：数据结构，数据操作，数据约束

按不同应用层次分：①概念数据模型：E-R ②逻辑数据模型 ③物理模型

E-R模型：

    实体（矩形）—属性（椭圆）—联系（菱形）

数据模型：层次模型：树

                 网状模型：无向图

                 关系模型：二维表

                             属性：列

                     ​        元组：行

                             关系操纵：查询增加删除，修改

                    ​​​​​​​         数据约束：实体完整性约束，主键不能为空；

                               ​​​​​​​        ​​​​​​​       参照完整性约束；

                               ​​​​​​​        ​​​​​​​       束和用户定义完整性约束

                       分量不能再分为最小的数据项

4.3关系代数

基本运算：差，并，笛卡尔积，投影，选择

                     投影：选择列

                     选择：选择行

                     笛卡尔积：T=RxS

                      并：T=R+S

                      差：T=R-S

查询运算：笛卡尔积，投影，选择

第一范式：每个属性都已不能再分为简单项

4.4数据设计与管理

数据设计：数据应用的核心。

方法：面向数据方法（多），信息需求为主；面向过程方法，处理需求为主

步骤：

       需求分析：建立数据字典

       概念设计：设计E-R

       逻辑设计：E-R转换成关系模型

       物理设计

5.1计算机结构

虚拟内存：硬盘储存空间划分出的位置，不是真正内存，最大容量取决于计算机地址位数

机器数：原码，补码，反码。整数用补码

文件名转换为文件存储地址->文件目录

I/O方式：程序查询，中断，直接存储器存取DMA，通道控制

       通道：减轻CPU负担，并行程度最高

总线带宽指总线的数据传输率

一个进程活动有：运行，就绪，阻塞（等待），创建，终止。运行，就绪，阻塞（可以相互转化。就绪：已获得除CPU外所有所需运行资源