第二章、数据结构与算法
1、查找技术：
主要有顺序查找（最基本和最简单）和二分法查找
只能采取顺序查找的情况：线性表是无序，则不管是顺序存储结构还是链式存储
有序线性表，但是采用的是链式存储结构
二分法查找只适用于顺序存储的线性表，且表中元素必须按关键字有序
对于长度为n的有序线性表，最坏情况下，二分法查找需要比较次数为
顺序查找需要比较次数为
3、线性表是相同数据元素组成的有限序列，元素间具有一对一的关系，n=0时，为空表。是一种线性结构，第一个结点无前件，最后一个结点无后件，其它有且只有一个前件和一个后件。
线性表的顺序存储结构具备的2个基本特征：
线性表中的所有元素所占的存储空间是连续的
线性表中各数据元素在存储空间中是按逻辑顺序依次存放的
线性表的链式存储空间可以是连续的也可以是不连续的
2、栈是限定在表尾进行插入或删除操作的线性表，具有记忆作用。允许插入和删除的一端叫栈顶（top）；另一端为栈底。按“先进后出”的原则，存在空栈。
3、队列只能在一端进行插入（队尾），另一端进行删除（队头）。按“先进先出”的原则。存在空队列。
循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，它仍是线性结构。循环队列有队头指针和队尾指针，其队列中的元素个数由队头指针和队尾指针共同决定。
4、数据结构是指带有结构的数据元素的集合，结构是指数据元素之间的前后件关系
数据结构包括数据的逻辑结构、存储结构和数据的操作。
逻辑结构有线性结构（线性表）和非线性结构（树和图）。
存储结构是逻辑结构在计算机上的表示（一逻对应多存，存储结构有顺序、链接和索引等。不同存储结构影响数据处理的效率）
5、算法的时间复杂度（执行算法所需要的计算工作量或基本运算次数）
算法的空间复杂度（执行过程中所需要的计算机的存储空间）
两者不一定相关
6、算法的5个特征：
有穷性（有穷步后能结束；有限时间内能完成）
确定性：每个步骤有明确的定义
可行性：针对实际问题而设计的算法执行后能够得到满意的结果
输入（0个或多个）
输出（1个或多个）
拥有足够的情报
7、二叉树的遍历：
先序遍历：（根左右）
中序遍历：（左根右）
后序遍历：（左右根）
8、二叉树的一些性质：
9、排序的分类如下所示：
第三章、程序设计基础
1、结构化程序设计的3种基本结构：顺序、选择和循环
结构化程序设计方法的4条原则：
自顶向下：先整体，后细节；最上层总目标，逐步问题具体化
逐步求精：对复杂问题，设计子目标做过度，逐步细化
限制使用goto语句
模块化
模块独立性度量标准：内聚性和耦合性。应该高内聚和低耦合。
2、面向对象程序设计的基本概念：
对象：包含属性和方法。
基本特点有：标识唯一性、分类性、多态性、封装性、继承性、模块独立
性好
类：是一对具有相似行为对象的一种抽象
封装性
继承性：类之间共享属性和操作机制。分为单继承和多继承
多态性
3、良好的程序设计风格：
源程序文档化：符号名具有一定实际含义、有正确的程序注释、良好的视觉组织数据说明
语句结构（语句结构清晰第一，效率第二）
输入和输出方法
第四章、软件设计基础
1、程序调试：通常也称为Debug；诊断和改正程序中的错误，方法有强行排错法、回溯法、原因排除法。调试后还应该在进行测试。调试步骤是错误定位、修改设计和代码以排除错误、进行回归测试以防止引入新的错误。
2、软件测试是为了发现错误，一般按4个步骤进行：（单元、集成、确认、系统）有动态测试、静态测试和正确性证明。
也可分为白盒测试（主要方法有逻辑覆盖和基本路径测试）
黑盒测试（主要方法有等价类划分法、边界值分析法、错误推测法、因果法）
3、软件是程序、数据和相关文档的集合，是一种逻辑实体；
软件按功能分为：
应用软件：为解决特定领域的应用而开发（事务处理软件、人工智能软件等）系统软件：计算机管理自身资源、提高计算机使用效率并为永华提供各种服务（操作系统、编译程序、汇编程序网络软件、数据库管理系统等）支撑软件（或工具软件）
4、软件工程是指采用工程的概念、原理和技术、方法指导软件的开发和维护。其3要素：
方法：技术手段
工具：支持软件的开发、管理文档生成
过程：支持软件开发的各个环节的控制、管理
其基本原则包括抽象、信息隐蔽（采用封装技术，将程序模块的实现细节隐藏起来，使模块接口更加隐蔽）、模块化、局部化、确定性、一致性、完整性和可验证性
5、结构化设计常用工具有成程序流程图（PFD）、盒图（N-S图）、问题分析图
（PAD）、过程设计语言（PDL）；
需求分析阶段常用工具有数据流图（DFD）、数据字典（DD）、判定树和判定表PFD主要元素有：
方框：表示一个加工步骤、菱形框：表示一个逻辑条件、箭头：表示控制流向
DFD的4种基本符号：
数据的源点或终点
数据流：沿箭头方向传送数据的通道
数据存储
加工（转换）：输入数据经加工变换产生输出
源，潭：表示系统和环境的接口
6、软件维护有4类：
改正性维护、适应性维护、完善性维护、预防性维护
7、软件的生命周期：（软件产品从提出、实现、使用维护到停止使用退役的过程
8、软件危机：（成本、质量、生产率）
软件需求的增长得不到满足
软件开发的成本和进度无法控制（不断提高）
软件质量难以保证
软件不可维护或维护程度非常低
软件开发生产力的提高赶不上硬件的发展和应用需求的增长
第五章、数据库设计基础
1、数据：是描述现实世界中各种具体十五和抽象概念的可以储存并有明确意义
的信息，包括数据内容和数据形式。
2、数据库：
定义：存放数据的仓库
特点：数据按一定数据模型组织、描述和存储
冗余度小（数据共享）
数据独立性高（物理独立性和逻辑独立性）
易扩展
多个用户可共享
