01:00

算法的特性

可行性，确定性，有穷性，足够的情报

程序不等于算法

算法是指对阶梯方案的准确而完整的描述。

04:54

算法的基本要素

对数据对象的运算和操作

基本结构

顺序，选择，循环

06:00

算法的时间复杂度

是指算法执行所需要的计算工作量，可以用算法所执行的基本运算次数度量。

算法的空间复杂度

是指算法所执行的内存空间。包括算法程序，输入的初始数据以及算法执行过程中需要的额外空间

算法的时间复杂度和空间复杂度相互独立

1.2 数据结构的基本概念 P2 - 00:19

数据元素是数据的基本单位

数据项是数据的最小单位

1.2 数据结构的基本概念 P2 - 01:19

数据结构：是指相互有关联的数据元素的集合

数据结构的分类：

逻辑结构：反映数据间逻辑关系的数据结构

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

每个节点最多有一个前件，也只有一个后件

非线性结构：主要是指树形结构和网状结构

存储结构：是数据结构在计算机存储空间中的存放方式

运算

顺序存储结构

链式存储结构

1.一种逻辑结构可以有多种存储结构

2.不同的存储结构其数据处理的效率不同

1.3线性表及其顺序存储结构 P3 - 02:25

线性表的顺序存储又叫顺序表

特点：

1.线性表中所有元素所占的存储空间是连续的；

2.线性表中数据元素在存储空间中是按逻辑顺序依次存放的；

3.可以随机访问数据元素；

4.做插入，删除时需移动大量元素，因此线性表不便于插入和删除元素。

1.4 上 栈 P4 - 00:23栈是限定在一端进行插入和删除的线性表

栈的特点：

1.只能在栈顶进行插入和删除；

2.修改原则是“先进后出”或“后进先出”；

3.栈底指针不变，栈中元素随栈顶指针的变化而动态变化；

4.具有记忆功能；

5.支持子程序调用。

1.5线性链表 P6 - 02:44

线性表的链式存储结构叫做线性链表。

特点：

1.个数据节点的存储空间可以不连续。

2.各数据元素的存储顺序与逻辑顺序可以不一致。

1.6 上 树与二叉树 P7 - 00:27

树是n个元素的集合，它有且只有一个称为根的元素；其余元素是互不相交的子树。

一个节点所拥有的后键的个数称为该结点的度。

所有结点中最大的度称为树的度。

1.6 上 树与二叉树 P7 - 06:58

二叉树的特点：

1.非空二叉树中有一个根结点；

2.每个结点最多有两棵子树，且分别成为该结点的左子树和右子树。

完全二叉树：

除最后一层外，每一层上的结点数均达到最大值，在最后一层只缺少右边若干结点。

1.6 下 树的遍历 P8 - 00:45

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

1.7 查找技术 P9 - 01:03



顺序查找适用于无序表或线性表（不管有序还是无序）。

1.8 排序 P10 - 01:43

要记住每种排序的最坏情况

快速排序：

1.在要排序的序列中找一个数作为基准数（通常为第一个数）；

2.通过交换，把序列中所有比基数大的数放在右边，比基数小的数放在左边；

3.以基数为分割线分为两个子表，对子表重复上述步骤。

2.1 2.2程序设计风格以及结构化程序设计 P11 - 02:55

结构化程序设计原则

自顶向下，逐步求精，模块化，限用go to

2.3 面向对象的程序设计 P12 - 03:05

对象的特点

标识唯一性

分类性

多态性

封装性

模块独立性好

消息的组成

1.接收对象的名称

2.消息标识符，也称消息名

3.零个或者多个参数

消息的多态性

值同样的小四被不同的对象接受时可能会导致完全不同的行动的现象。

面向对象的主要特征：抽象，封装，继承，多态

面向对象设计方法主要特征是：继承

3.1软件工程基本概念 P13 - 01:52

软件的分类

软件工程的核心思想：

把软件当做一个工程产品来处理

软件危机

软件工程三要素

方法，工具，过程

软件的生命周期

软件的定义，软件的开发，软件运行维护

3.2 结构化分析方法 P14 - 02:16

结构化分析方法：使用数据流图，数据字典，判定表和判定树等工具，来建立系统的逻辑模型。

数据字典是结构化分析的核心。

3.3 结构化设计方法 P15 - 01:50

软件设计的划分

软件设计的基本原则

抽象

模块化

信息隐蔽

模块独立性：高内聚性，低耦合性

概要设计

工具：程序结构图

详细设计

工具：

图形工具：程序流程图，N-S图，PAD，HIPO

表格工具：判定表

语言工具：PDL（伪码）

3.4 软件测试 P16 - 00:15

目的：发现程序中的错误

测试方法：

静态测试（软件不需要执行）

动态测试

白盒测试：1.逻辑覆盖测试；2.基本路径测试。

黑盒测试：1.等价类划分法；2.边界值分析法；3.错误推测法。（不考虑程序的内部，只检查是否正确接收并输出正确的信息）

软件测试的步骤

单元测试，集成测试，确认测试，系统测试

3.5 程序的调试 P17 - 00:40

任务：诊断和改正程序的错误。

4.1 数据库系统的基本概念 P18 - 00:38

描述事物的符号记录称为数据。

数据库是指长期存储在计算机内的，有组织的，可共享的数据集合。

数据库中的数据具有两大特点：集成，共享。

数据库管理系统（DBMS）

数据库管理系统是数据库系统的核心。

数据定义语言（DDL）的作用：

1.数据模式定义；

2.数据存取的物理构建。

数据操纵语言（DML）的作用

1.数据操纵，包括查询与增，删，改等操作

数据控制语言（DCL）的作用

1.数据的安全性的定义与检查；

2.并发控制与故障恢复；

3.数据的完整性。

数据库系统（DBS）

数据库应用系统

包含：数据库系统，应用软件以及应用界面。

数据管理三个阶段

人工管理

文件管理

数据库系统

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

数据库的特点

集成性

高共享低冗杂

独立性

统一管理控制

三级模式和两级映射

三级模式包括外模式（针对用户），概念模式和内模式

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

4.2 数据模型 P19 - 00:59

数据模型的三要素：数据结构，数据操作和数据约束。

数据模型的分类：

1.概念数据模型：E-R模型

2.逻辑数据模型：层次模型，网状模型，关系模型，面向对象模型

3.物理数据模型

关系模型

采用二维表来表示，简称表，每一个二维表称为一个关系。

二维表中的一列称为属性

二维表中的一行称为元组，元组的分量不可再分，主键不能为空。

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

4.3 关系代数 P20 - 01:28

投影选择的是列。

选择选择的是行。

属性（列）增加一般是自然连接

4.4 数据设计与管理 P21 - 00:38

数据库设计概述

面向数据的设计方法已成为主流方法。

数据库设计的步骤

1.需求分析，建立数据字典

2.概念设计，设计E-R图

3.逻辑设计，把设计E-R图转换为关系模式

4.物理设计

数据库的管理

其他

带链的栈与队列是一个链表，链表的存储空间是不连续的，所以只真不会规律的变化。

当top=bottom=NULL时，为栈空（队列空）；

当top=bottom不等于NULL时，栈（队列）中只有一个元素，其他情况无法确定。

正数的原码，反码，补码均相同；负数的反码是对该数的原码除符号位各位取反，补码是在该数的反码的最后一位的最后（即最右边）一位加上1；不管正数还是负数，其补码的符号位取反即是偏移码。

整数在计算机中存储和运算通常采用的格式是补码。

如果front<rear， 则队列中的元素个数为rear-front个； 如果front>rear， 则队列中的元素个数为rear-front+m

在长度为n的线性表中寻找值最大的元素，最坏情况下需要比较的次数为n-1。

在多道程序并发执行的情况下，程序的执行过程由当时的系统环境与条件所决定，程序与其执行过程就不再有一一对应的关系。

模块独立性的概念是抽象，模块化，信息隐蔽和局部化的直接结果。

数据独立性是数据库中数据独立于应用系统且不依赖于应用程序，即数据的存储结构与存取方式的改变不会影响应用程序。

计算机的虚拟内存受计算机地址位数的限制。

将文件名转换成文件存储地址的结构是文件目录。

扇出指由一个模块直接调用的其他模块个数。

关系模型采用二维表来表示关系。

概念模型是一种面向客观世界，面向用户的模型，它与具体的数据库管理系统和具体的计算机平台无关。

逻辑数据模型，也称数据模型，是面向数据库系统的模型，着重于数据库系统一级的实现。

程序可以作为算法的一种描述方法。