1、第一章 数据结构与算法算法 是一组有穷的指令集，通俗地说就是计算机解题的过程。算法有四个基本特征：确定性、有穷性、可行性、拥有足够的情报。算法的组成要素：对数据对象的运算和操作（算术运算、逻辑运算、关系运算、数据传输操作） 、控制结构（算法一般由顺序、选择、循环三种基本结构组合而成） 。算法的复杂度(复杂度的高低体现在运行该算法时所需占用计算机资源的多少) ：算法的时间复杂度是指执行算法所需要的计算工作量，即基本运算次数；算法的空间复杂度是指执行算法所需要的内存空间。数据结构是指相互有关联的数据元素的集合。前后件关系是数据元素之间最基本的关系。依据视点不同，数据结构可以分为数据的逻辑结构（它是
2、面向问题的，与所使用的计算机无关）和存储结构（也称物理结构，它是面向计算机的，是数据的逻辑结构在计算机中的表示） 。依据数据元素之间的关系，数据结构一般分为线性结构和非线性结构。线性结构（也称线性表）：非空的数据结构、有且只有一个根结点、每一个结点最多有一个前件（也最多有一个后件） 。线性表的顺序存储结构的特点是逻辑关系相邻的结点物理位置上也相邻。链表的优点是在进行插入和删除运算时，只需要改变指针即可，不需要移动元素，当存储空间不足时，可以动态为其分配内存空间，所以不必估计存储空间的大小。顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。顺序存储结构的插入运算：
3、在顺序表第 i 个位置上插入一个值，就要先把第 i 个元素（包括 i）之后的所有元素依次向后移动一个位置，然后再插入，最后长度加 1.顺序存储结构的删除运算：要删除第 i 个表项，则必须把第 i 个元素（不包括 i）之后的所有元素依次向前移动一个位置，把第 i 个表项覆盖掉，最后长度减 1.栈是一种后进先出（先进后出）的线性表，具有记忆功能。栈的基本运算有：入栈，出栈（删除栈顶元素） ，初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。列队只允许在表的一端插入（队尾） ，而在另一端删除（队头） ，是一种先进先出（后进后出）的线性表。栈和队列的共同点：都是操作受限的线
4、性表，只允许在表的端点处进行操作。树 （非线性结构）对于任意的一棵非空树都具有两个特性：有且只有一个根结点；当n（结点）1 时，除根结点外的其余结点可分为 m(m0)个互不相交的有限集。 结点的度：结点所拥有的子树棵数。度为 0 的结点为叶子结点。树的度：树中所有结点的度的最大值。树的深度则为所处层次最大的那个结点的层次。总结点数=总度数+1 （一棵树中每个结点的度树之和与边的条数相等）二叉树的基本性质：在二叉树的第 k 层上，最多有 2 的 k-1 次方个结点；深度为 m 的二叉树最多有 2 的 m 次方-1 个结点；任意二叉树中，度为 0 的结点（叶子结点）总比度为 2 的结点多一个；具有
5、 n 个结点的二叉树，其深度不小于log2n+1 (“”取整)满二叉树就是每一层上的所有结点数都到达最大值；完全二叉树：具有 n 个结点的完全二叉树的深度为log 以 2 为底 n 的对数+1；完全二叉树中度为 1 的结点数为 0 或 1；二叉树的编历 如果二叉树为空，则执行空操作；前序遍历：访问根结点，前序遍历左子树，前序遍历右子树 中序遍历：中序遍历左子树，访问根结点，中序遍历右子树后序遍历：后序遍历左子树，后序遍历右子树，访问根结点。(层层分左右根)顺序查找，从表的一端开始，依次扫描表中的元素，若查找失败则返回-1（失败时元素的位置） ，在一个有 n 个元素的线性表中进行顺序查找，则查找
6、成功时的平均比较次数为（n+1）/2 次，最坏的情况则是比较 n 次。二分查找，先将线性表中的元素进行排序，然后再依次进行折中查找。 （只用于顺序存储的有序表）在长度为 n 的有序线性表中进行二分查找，需要的比较次数为 log ,最坏情况下需要比较2n的次数是 O（log ）2冒泡排序，在最坏情况下需要比较 n(n-1)/2 次，时间复杂度为 O(n（n-1）/2)（冒泡排序需要经过 n-1 趟排序） ， （简单插入排序、快速排序也一样） 。希尔排序，在最坏情况下需要比较 O( )次。 1.5n堆排序，在最坏情况下需要比较 nlog 次。2第二章 程序设计基础程序设计的主导风格“清晰第一，效率
7、第二”程序设计的方法主要有两种：结构化程序设计和面向对象程序设计结构化程序设计必须遵循的原则：模块化（以模块化设计为中心） 、自顶向下、逐步求精、限制使用 goto 语句。结构化程序的基本结构：顺序结构、选择结构（分支结构） 、循环结构（重复结构） 。面向对象方法的基本概念有：对象是其最基本的概念，对象具有 5 个基本特点：标识唯一性、分类性、多态性、封装性 （实现信息隐蔽） 、模块独立性 （与信息隐蔽的概念直接相关）好。 类和实例，类的实例称为对象（对象是类的实例） ，类描述的是具有相似性质的一组对象集合；消息（一个对象通过向另一对象发送信息来请求其服务） 。继承的优点：相似的对象可以共享程
8、序代码和数据结构，继承具有传递性。多态性，同样的消息被不同的对象接受时可产生完全不同的行为。第三章 软件工程基础软件，是由程序、数据及相关文档构成的完整集合；按功能可分为三大类：应用软件、系统软件、支撑软件（工具软件） 。软件危机，是指在计算机软件的开发和维护过程中所遇到的一系列严重问题； 集中表现在成本、质量、生产率等方面。软件工程包括三个要素：方法、工具和过程。其中，过程支持软件开发的各个环节的控制和管理。软件开发过程，是把用户的要求转变成软件产品的过程；此过程包括对用户的要求进行分析，解释成软件需求，把需求变换成设计，把设计变成现实，测试并交付使用。软件生命周期，是指软件产品从提出、实现
9、、使用维护到停止使用退役的整个过程；软件生命周期可分为：软件定义（可行性研究与需求分析） 、软件开发（设计、实现、测试） 、软件运行维护（使用、维护及退役）3 个阶段。用户的参与只局限在软件定义期。需求分析阶段的工作主要包括四个方面：需求获取、需求分析、编写需求规格说明书（数据字典） 、需求审评。需求分析方法主要有两种：结构化分析方法、面向对象的分析方法。结构化分析方法是面向 数据流的 自顶向下逐步求精进行需求分析的方法；需求分析的常用工具：数据流程图、数据字典、判断树、判断表。数据字典是用于描述系统中所用到全部数据和文件的文档数据流图的四种基本图形，箭头表示数据流，圆或椭圆表示加工，双杠表示
10、数据存储，方框表示源、潭。建立数据流图的步骤一般分三步：由外向内、自顶向下、逐层分解。软件设计（是确定系统的物理模型） ，是将需求准确地转化为软件产品或系统的唯一途径。软件设计的基本原理：模块化、抽象、信息隐藏和局部化、模块独立性（与耦合性（模块之间）成反比，与内聚性（模块内）成正比） 。在设计中应该力求松散耦合，避免紧密耦合。内聚性越强，则耦合性越弱，高质量的软件设计，应尽量做到高内聚，低耦合，有利于提高模块的独立性。 典型的数据流类型有两种：变换型和事务型。 好的软件设计结构通常顶层高扇出，中间扇出较少，底层高扇入。软件测试，测试的根本目的是尽可能地发现并排除软件中隐藏的错误。一个好的程序
11、测试用例能够发现至今尚未发现的错误；一个成功的程序测试是发现了至今尚未发现的错误。软件测试的方法，按是否需要执行被测软件分为静态和动态测试，按功能则分为黑盒（功能、数据驱动测试）和白盒测试（结构、逻辑测试） ，黑盒测试的主要方法有等价类划分法、边界值分析法、错误推测法。软件测试过程分为 4 个步骤：单元测试、集成测试、验收（确认）测试和系统测试。程序调试的目的是诊断和改正错误。软件调试的方法：强行排错法、回溯法、原因排除法。第四章 数据库设计基础数据，描述事物的符号记录。数据库（DB）,就是存放数据的仓库。数据库中的数据具有两大特点：集成与共享。数据库管理系统（DBMS） ，目前流行的均为关系
12、数据库系统，数据库管理系统是数据库系统的核心。数据的完整性与安全性的维护是数据库管理系统的基本功能。数据管理系统的数据语言有三种：数据定义语言（DDL） 、数据操纵语言（DML ） 、数据控制语言（DCL） 。数据库系统，由数据库、数据库管理系统、应用系统、数据库管理员和用户构成。数据库应用系统（DBAS） ，包括数据库、数据库管理系统、数据库管理员、硬件平台、软件平台、应用软件、应用界面 7 个部分。数据管理技术经历了 3 个阶段，人工管理阶段、文件系统阶段和数据库系统阶段。数据库系统的基本特点：数据的高集成性、髙共享性与低冗余性、高独立性。物理独立性，存储结构改变时，其逻辑结构可以不变，且
13、基于逻辑结构的应用程序也无须改变；逻辑独立性，数据的逻辑结构改变了，用户的应用程序可以不变。三级模式和两级映射：内模式、概念模式、外模式；外模式-概念模式映射、概念模式-内模式映射。 概念模式是全体用户的公共数据视图，外模式是用户的数据视图，内模式是数据物理结构和存储方式的描述。数据库技术的根本目的是解决数据共享的问题。数据模型通常由数据结构、数据操作和完整性约束组成。数据模型分为概念数据模型、逻辑数据模型和物理数据模型 3 类。键（码）能够唯一标识实体的属性集。主键，表中能够唯一确定一个元组的属性值，如学号。两个实体集之间的联系有三种：一对一、一对多、多对多。在 E-R 图中，实体用矩形表示
14、，属性用椭圆形表示，联系用菱形表示。逻辑数据模型分为四种：层次、网状、关系模型和面向对象模型。 （前两种为非关系及格式化模型）层次模型，有且只有一个结点无双亲结点（根结点） ，其他结点只有一个双亲结（结点的双亲是唯一的） 。查询子女结点必须通过双亲结点，删除双亲结点值，则相应的子女结点也同时被删除。树型结构用于表示层次模型，关系模型采用二维表来表示。网状模型，允许一个以上的结点无双亲，一个结点可以有多于一个的双亲。关系模型由关系数据结构、关系操纵和关系完整性约束 3 部分组成。分量，元组中的一个属性值，元组的分量不能再分成更小的数据项了。表中一定要有主键，元组的分量可以出现 NULL 值，但主
15、键中则不允许出现空值。关系模型的 6 个基本操作：属性指定、元组选择、两个关系合并、一个或多个关系的查询、元组的插入、元组的删除。关系模型允许的 3 类完整性约束：实体完整性（主键不为空） 、参照完整性（外键应相互存在）和用户定义完整性。运算的三大要素：运算对象、运算符、运算结果。关系模型的基本运算：插入、删除、修改、查询。笛卡尔积运算(pq)后得到新的表，表中元组数是运算前两表中元组数目相乘，属性则为运算前表中属性相加。例如RR1 R2a bc dSS1 S2e fg hT=RSR1 R2 S1 S2a b e fa b g hc d e fc d g h自然链接，两关系间有公共域，通过公共域的相等值进行连接。数据库设计是指在已有的数据库管理系统的基础上建立数据库。数据库设计包括概念设计和逻辑设计和物理设计三方面的内容，其根本目标是解决数据共享问题（与数据库技术的目标一致）商品与顾客，多对多；宿舍与学生，一对多；项目主管与项目，一对多；学校与教师，一对多。
