数据结构与算法基本知识
一、 算法的基本概念
1、定义：是指解题方而完整的描述。 2、特性：有穷性、确定性、可行性、输入和输出。 3、算法复杂度
（1）算法复杂度：指执行算法所耗费的时间和存储空间。 （2）它分为：时间复杂度和空间复杂度
时间复杂度：指执行算法所需要的计算工作量。 空间复杂度：指执行算法所需要的内存空间。
二、数据结构的基本概念
1、数据结构定义：是指相互有关联的数据元素的集合。
2、数据结构构成：数据的逻辑结构、数据的物理结构和数据的运算三个部分。 3、数据的逻辑结构
（1）定义：是指数据元素之间的逻辑关系。它分为线性结构和非线性结构两种。（2）线性结构：数据元素体现强烈的前后唯一的关系。如线性表。 （3）非线性结构：数据元素的前后关系不是唯一的。如树和图。 4、数据的存储结构（即物理结构）
（1）定义：数据元素及其关系在计算机存储器内的表示。即逻辑结构的计算机实现。 （2）常用存储方式
顺序存储方式：每一个存储结点只含一个数据元素，所有存储结点相继存储在一
个连续的存储区里。用存储结点之间的位置关系表示数据元素之间的逻辑关系。 链式存储方式：每个存储结点不仅含有一个数据元素，还包括指针。每一个指针
指向一个与本结点有逻辑关系的结点，即用指针表示逻辑关系。 索引存储方式：在顺序存储方式基础上增加一个索引表。
散列存储方式：每个存储结点仅含一个数据元素，数据元素按散列函数据确定存
储位置。
三、线性表及其顺序存储结构
1、线性表：是n个数据元素的有限序列。它是最常用最简单的一种数据结构。
2、线性表的顺序存储结构：用一组地址连续的存储单元依次存储线性表中的数据元素。存
储单元的物理位置直接体现数据元素的逻辑关系。 3、线性表操作：插入和删除。
四、栈和队列
1、栈及其基本运算
（1）定义：限定仅在表尾进行插入和删除操作的线性表。表尾称栈顶，表头称栈底。 （2）数据组织原则：按“先进后出”（FILO）或“后进先出”（LIFO）的原则。它具有记忆作用。
（3）基本运算：进栈和出栈。
2、队列及其基本运算
（1）定义：限定仅在表的一端进行插入，而在表的另一端删除数据元素的线性表。插入端称队尾，删除端称队头。
（2）数据组织原则：按“先进先出”（FIFO）或“后进后出”（LILO）的原则。 （3）基本运算：入队和出队。
五、线性链表
1、线性链表的基本概念
（1）线性链表：是指线性表的链式存储结构。
（2）线性链表的结点结构：由数据域和指针域两部分组成。
（3）线性单链表的特点：每个链表都有一个头结点和一个尾结点，尾结点的指针域值为空。
（4）带链的栈：采用链式存储结构的栈。 （5）带链的队列：采用链式存储结构的队列。 2、基本运算：查找、插入和删除。
六、树与二叉树
1、树的基本概念
（1）什么是树：n（n>=0）个结点的有限集，n=0时称空树，是一种非线性数据结构。 （2）树的特点：仅有一个树根（n=1），n>1时含有子树。 （3）结点的度：结点拥有的子树数。 （4）叶子：度为0的结点。
（5）孩子和双亲：结点的子树称孩子，该结点称双亲。 （6）层次：根为第一层，根的孩子为第二层，依次类推。 （7）深度：最大的层次数为该树的深度或高度。 2、二叉树及其基本性质
（1）二叉树：指每个结点最多有两棵子树的树。 （2）存储结构有：顺序存储结构和链式存储结构 （3）基本性质
二叉树的第k(k≥1)层上最多有2个结点。 深度为m(m≥1)的二叉树最多有2-1个结点。
在任何一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。 具有n个结点的二叉树，其深度至少为int(1og2n)+1。 （4）满二叉树：指一棵树深度为k且有2k-1个结点的二叉树。
（5）完全二叉树：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，此二叉树称为完全二叉树。 3、二叉树的遍历
（1）先序遍历：若二叉树为空树，则空操作；否则，①访问根结点；②先序遍历左子树；③先序遍历右子树。
（2）中序遍历：若二叉树为空树，则空操作；否则，①中序遍历左子树；②访问根结点；③中序遍历右子树。
（3）后序遍历：若二叉树为空树，则空操作；否则，①后序遍历左子树；②后序遍历右子树；③访问根结点。
mk-1
七、查找技术
1、顺序查找
（1）长度为n的顺序表，在等概率情况下查找成功的平均查找长度为：(n+1)／2，最好长度为1，最坏长度为n。
（2）一般应用在线性表无序或采用链式存储结构的有序线性表的情况。 2、二分查找（又称折半查找）
（1）对于长度为n的顺序存储的有序线性表，在最坏情况下，其比较次数只要int(1og2n)+1次。
（2）只适合于顺序存储的有序表的情况。
八、排序技术
1、插入排序
最好情况下比较次数为n-1次，最坏情况下比较次数为n(n-1)/2次。其排序方法是稳定的。 2、冒泡排序
最好情况下比较次数为n-1次，最坏情况下比较次数为n(n-1)/2次。其排序方法是稳定的。 3、快速排序
最好情况下比较次数为n1og2n次，最坏情况下比较次数为n(n-1)/2次。其排序方法是不稳定的。
程序设计基础知识
一、 程序设计方法
1、结构化程序设计
（1）结构化程序设计方法：采用自顶向下逐步求精的设计方法和单入口单出口的控制结构。 （2）基本结构：顺序结构、分支结构和循环结构。 （3）设计的原则如下：
采用自顶向下、逐步求精的方法，准确清晰地表达系统的功能； 使用顺序、选择、循环三种基本控制结构描述程序流程； 程序结构模块化，每个模块只有一个入口和一个出口； 复杂结构应该用基本控制结构进行组合嵌套来实现； 严格控制GOTO语句的应用。 2、面向对象程序设计
（1）面向对象方法：是以客观世界中的不同对象(客观存在的实体)为基本元素，并以类和继承来表达事物之间具有的共性和它们之间存在的关系。 （2）特征：类、封装、继承和多态性。 （3）面向对象方法中的常用基本概念
对象：在现实世界中，每个实体都是对象，每个对象都有它的属性和操作。 类：是一组具有相同属性和相同操作的对象的集合。一个类中的每个对象都是这
个类的一个实例。
属性：是描述对象状态的数据
方法：允许作用于某个对象上的各种操作。
事件：是为了完成某一任务，一个对象所提供的、并体现其功能的操作。 继承：是表达类之间相似性的一种机制。 消息：是对象间通信的手段
多态性：是指同一个操作作用于不同的对象上可以有不同的解释，并产生不同的
执行结果。
（4）面向对象技术的特点
可重用性 可维护性 表示方法的一致性
二、 程序设计风格
1、源程序文档化
2、数据说明：是对程序中数据结构的组织和描述。 3、语句结构 4、输入／输出格式
软件工程基础知识
一、 软件工程的基本概念
1、软件工程
（1）定义：是指应用计算机科学、数学及管理科学等原理，以工程化的原则和方法来解决软件问题的工程。
（2）研究软件工程的主要目的是提高软件生产率，提高软件质量，降低软件成本等。
2、软件生命周期
（1）八个阶段：问题定义、可行性研究、需求分析、概要设计、详细设计、编码、测试、运行维护。 （2）三个时期
软件定义时期：包括问题定义、可行性研究、需求分析三阶段。 软件开发时期：包括、概要设计、详细设计、编码、测试四个阶段。 软件维护时期：即运行维护阶段。 3、软件详细设计的表达 （1） 流程图
（2） N-S图（又称盒图） （3） PAD图（又称问题分析图） （4） 判定树
（5） 过程设计语言PDL（又称伪码或结构化语言） 4、应用软件开发的原则
两个原则：自顶向下系统结构和模块化结构的开发原则。
二、 结构化分析方法（简称SA）
1、结构化分析使用的工具有：数据流图、数据字典、结构化英语、判定表和判定树。 2、数据流图(Data Flow Diagram，简称DFD)
（1）数据流图，简称DFD，是结构化分析方法中用于表示系统逻辑模型的一种工具。 （2）数据流图由数据流、加工(又称数据处理)、数据存储(又称文件)、数据源点 或终点四种基本成分组成。
①数据流：数据流是数据在系统内传播的路径。用 图形表示 ②加工：对数据流进行某些操作或变换。 用 处理名 图形表示
文件名
③数据存储：指暂时保存的数据，它可以是数据库文件或任何形式的数据组织。用
图形表示
④数据源点或终点：是本软件系统外部环境中的实体(包括人员、组织或其他 软件系
实体名 统)，统称为外部实体。用 图形表示。 3、数据字典(DD)
（1）数据字典(Data Dictionary，简称DD)就是用来定义数据流图中的各个成分的具体含义。 （2）数据字典有四类条目：数据流、数据项、数据存储和基本加工。
（3）它和数据流图共同构成了系统的逻辑模型
三、 结构化设计方法(简称SD)
1、结构化设计方法是一种面向数据流的设计方法。SD方法采用结构图来描述程序的结构。结构图的基本成分有模块、调用和数据。
2、结构化设计：分概要设计（系统设计）和详细设计（模块设计）两步。 3、模块性评价：耦合度尽可能低，内聚度尽可能高。
四、 测试与调试
1、测试
（1）测试的目的：就是尽可能多地发现软件产品中的错误和缺陷。 （2）测试步骤
单元测试也称模块测试，通常采用白盒测试。 集成测试也称组装测试或联合测试，
确认测试又称为有效性测试,通常采用黑盒测试 系统测试
（3）黑盒测试：测试人员完全不考虑程序内部的逻辑结构和内部特征，只依据程序的需求规格说明书，检查程序的功能是否符合它的功能说明。它又称为功能测试或数据驱动测试。有以下四种方法：
等价类划分法 边界值分析法 错误推测法 因果图法
（4）允许测试人员利用程序内部的逻辑结构及有关信息，设计或选择测试用例，对程序所有逻辑路径进行测试。通过在不同点检查程序的状态，确定实际的状态是否与预期的状态一致。它又称为结构测试或逻辑驱动测试。有以下六种方式：
语句覆盖 判定覆盖 条件覆盖 判定／条件覆盖 条件组合覆盖
路径覆盖 2、调试
（1）调试的目的：在于诊断和改正程序中潜在的错误。 （2）分为两大类：静态调试和动态调试
数据库基础知识
一、 数据库（DB）的基本概念
1、数据管理技术的发展
（1） 分三个阶段：人工管理阶段、文件管理阶段和数据库管理阶段。 （2）数据库技术的根本目标是要解决数据的共享问题。 （3）数据库管理的三个主要特点是
数据是结构化的
数据具有性：数据性分为逻辑性与物理性。物理性指当数
据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改。逻辑性指当总体逻辑结构改变时，其局部逻辑结构可以不变，从而根据局部逻辑结构编写的应用程序也可以不必修改。 数据具有完整性、安全性和并发性。 2、数据库管理系统（DBMS）
（1）定义：指为了实现数据的共享，保证数据的性、完整性和安全性，管理数据库中数据，处理用户对数据库的访问的一组软件。它是数据库系统的核心。 （2）功能：定义数据库、管理数据库、建立和维护数据库以及数据通信。 3、数据库系统（DBS）的构成
由操作系统、数据库管理系统和应用程序在一定的硬件支持下所构成的。其中数据库管理系统是整个数据库系统的核心。
二、 数据描述与数据模型
1、实体间的联系分三类：一对一（1：1）、一对多（1：n）和多对多（n：n）的联系。 2、数据模型分三种：层次、网状和关系模型。 3、关系数据模型
（1）关系数据模型把数据库表示为关系的一个集合。数据库中的每一个数据表就是一个关系。
（2）组成：
数据结构：表示为二维数据表形式。
数据操作：数据查询及对数据进行增、删、改操作。 数据完整性：实体完整性、参照完整性和用户自定义完整性。
三、 关系代数
关系R
A a d x B b e y A a d x w m C c f z B b e y u n C c f z v p
关系S A x w m B y u n C z v p 1、并运算：表示RUS，指包含关系R和S中的所有记录。
2、交运算：表示R∩S，指包含关系R和S中的公共记录。
A x B y C z
3、差运算：表示R-S，指包含在关系R中，但又不在关系S中的记录。
A a d B b e C c f 4、笛卡尔积：表示R×S
关系R 关系S
A a d B b e C c f D m x E n y 关系R×S
A a a d d
B b b e e C c c f f D m x m x E n y n y 5、选择运算：从关系中选择满足条件的记录组成一关系子集。
例：σ
score=80
6、投影运算：从关系中选择需要的字段组成一关系子集。
例：Πsno,sname,sex
四、 数据库设计方法
1、数据库设计
是指在已有数据库管理系统的基础上建立数据库的过程。 2、数据库设计的过程 （1） 需求分析
（2） 概念结构设计：借助E-R图进行概念模型的描述。
（3） 逻辑结构设计：将概念模型转换为特定数据库管理系统所支持的数据模型。 （4） 物理结构设计：为逻辑数据模型选择一个最适合应用环境的物理结构。 3、E-R图
（1） 定义：指描述实体及其相互之间的联系的工具。 （2） 组成：有实体、实体的属性和实体之间的联系三个要素 （3）图形表示：
用矩形框表示实体，框内标明实体名。 用椭圆形框表示实体的属性，框内标明属性名。 用菱形框表示实体间的联系，框内标明联系名。
校长 领导 教师 姓名 4、数据字典
年龄 职称 用于存储关于数据描述的信息的库。
