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(上)栈

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

只能在栈顶删除和插入先进后出，后进先出栈底指针不变，栈中元素随栈顶指针变化栈具有记忆功能，支持子程序调用例. 设栈的存储空间为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

特点：

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

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

考点：

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

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

1.5线性链表

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

特点：

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

1.6（上）树与二叉树

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

一些术语：

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

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

深度：层数

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

二叉树：

有左右之分，不能颠倒

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

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

1.7(上)树的遍历

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

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

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

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

1.7（下）查找技术

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

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

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

1.8排序

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

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

2.1程序设计风格

清晰第一，效率第二

良好的程序风格应：

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

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外所有所需运行资源