搜索
第一章数据结构与算法一、算法1、算法：是指解题方案的准确而完整的描述。2、算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。3、算法的基本要素：一是对数据对象的运算和操作，二是算法的控制结构。4、算法的运算和操作：算术运算、逻辑运算、关系运算、数据传输四类。5、算法的控制结构：顺序、选择、循环三种基本结构。6、算法的复杂度：包括时间复杂度和空间复杂度。所谓时间复杂度是指执行算法需要的工作量。而空间复杂度是指执行这个算法所需要的内存空间。二、数据结构及其操作1、数据结构：包括数据的逻辑结构、数据的存储结构及各种数据结构进行的运算。2、数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。3、数据的存储结构：是指数据的逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。常用的存储结构有顺序、链接、索引。4、线性结构：一个非空的数据结构有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件。没有前件的结点称为根结点；没有后件的结点的称为终端结点（叶子结点）5、线性表：是最简单最常用的线性结构。6、线性表的顺序存储结构的特点：一是线性表中所有元素所占空间是连续的，二是各数据元素在存储空间中是按逻辑顺序依次存放的。7、栈：是限定在一端进行插入与删除的顺序存储线性表，栈是按照先进后出或后进先出的原则组织数据的。8、栈的基本运算：入栈、退栈、读栈。当栈已满，不能进行入栈操作，这种情况称“上溢”，当栈已空，不能退栈，称为“下溢”9、队列：是指允许在一端进行插入、而在另一端进行删除的顺序存储线性表。队列是按照先进先出或后进后出的原则组织数据的。10、队列的基本运算：入队、退队。不能进行入队操作，这种情况称为“上溢”，当队列为空，不能退队，称为“下溢”。11、线性链表：线性表的链式存储结构。它克服了顺序存储结构的缺点，它的结点空间可以动态申请与释放。它的数据元素的逻辑次序靠结点指针指示，不需要移动数据。便于插入和删除操作。12、链式存储结构的缺点：一是每个结点指针域需占用存储空间，二是一种非随机存储结构。三、数与二叉树1、树：一种简单的非线性结构。2、根：没有前件的结点只有一个，称为树的根结点，简称根。3、叶子结点：没有后件的结点称为叶子结点。4、度：一个结点所拥有的后件个数称为该结点的度。所有结点中最大的度称为该树的度。5、深度：树的最大层次称为树的深度。6、二叉树：一种非线性结构。7、二叉树的特点：一是二叉树只有一个根结点，二是每个结点最多有两棵子树，分别为左子树与右子树。8、二叉树的基本特征：1在二叉树的第K层上，最多有2k-1个结点。2深度为M的二叉树最多有2M-1个结点。3在任意一棵二叉树中，度为0的结点总是比度为2的结点多一个。4具有N个结点的二叉树，其深度至少为[log2N]+15具有N个结点的完全二叉树的深度为[log2N]+19、二叉树的存储结构：一般采用链式存储结构。10、二叉树的遍历：1前序遍序：先访问根结点，前序遍历左子树，前序遍历右子树。中序遍历：中序遍历左子树，访问根结点，中序遍历右子树。后序遍历：后序遍历左子树，后序遍历右子树，访问根结点。四、查找技术与排序技术1、顺序查找：如线性表为无序表，或采用链式存储结构，只能用顺序查找。2、二分法查找：只适用于顺序存储的有序表。3、当长序为N的有序线性，在最坏的情况下，二分查找只需要比较log2N次，而顺序查找比较需要N次。4、排序：是指将一个无序序列整理成按值非递减顺序排列的有序序列。5、排序方法：交换类排序法、插入类排序法、选择类排序法。6、冒泡排序法：冒泡排序法是一种简单的交换类的排序方法。假设线性表的长度为N，则在最坏的情况下需要的比较次数为：N(N-1)/27、希尔排序法：希尔排序法是一种插入类排序法。假设线性表的长度为N，则在最坏的情况下需要比较次数为O(N1..5)第二章程序设计基础一、程序设计方法与风格1、程序设计：就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。2、程序设计的风格：最主要强调简单和清晰，程序必须是可以理解的。保证“清晰第一，效率第二”。3、结构化程序设计的主要原则：自顶向下、逐步求精、模块化、限制使用goto语句。4、结构化程序的基本结构：顺序、选择、重复(循环)。5、结构化程序设计的优点：一是程序便于理解、使用和维护，二是提交了编程工作的效率，降低了软件开发成本。二、面向对象的程序设计1、面向对象方法的主要优点：一是与人类习惯的思维方式一致，二是稳定性好，三是可重用性好，四是易于开发大型软件产品，五是可维护性。2、对象：客观世界里的任何实体都可以被看作是对象，它由一组属性和操作组成。3、对象的基本特点：标识惟一性、分类性、多态性、封装性、模块独立性好。信息隐蔽是通过对象的封装性来实现的。4、类：具有共同属性、共同方法的对象的集合。5、实例：是指一个具体的对象，对象属于类的实例。6、消息：在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发消息完成的。7、继承：在面向对象方法中，类之间共享属性和操作的机制称为继承。8、多态性：同样的消息被不同的对象接受可导致完全不同的行为。第三章、软件工程基础一、软件工程基本概念1.计算机软件：是包括程序、数据及相关文档的完整集合。2.软件按功能可以分为：应用软件、系统软件、支撑软件（工具软件）3.软件工程概念的出现源自软件危机。4.软件工程：是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。5.软件工程的要素：方法、工具、过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档的生成，过程支持软件开发的各个环节的控制、管理。6.软件工程过程：是把输入转化为输出的一组彼此相关的资源和活动。7.软件工程过程的基本活动：一是软件规格说明，二是软件开发，三是软件确认，四是软件演进。8.软件生命周期：将软件产品从提出、实现、使用维护到停止使用退役的过程。9.软件生命周期分为软件定义、软件开发、软件运行维护三个阶段。10.软件工程的理论内容主要包括：软件开发技术和软件工程管理。11.软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境。12.软件工程管理包括：软件管理学、软件工程经济学、软件心理学。13.软件工程的原则包括：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可应证性。二、结构化分析方法1.需求分析：将创建所需要的数据模型、功能模型和控制模型进行分析。2.需求分析的工作：需求获取、需求分析、编写需求规格说明书、需求评审3.需求分析的方法：结构化分析方法、面向对象的分析方法。4.结构化分析方法：是结构化程序设计理论在软件需求分析阶段的运用。5.结构化分析的常用工具：数据流图（DFD）6.数据流图中各元素及说明：О加工（转换）数据流〓存储文件(数据流)□源，潭7.据流图的步骤：一是由外向里，二是自顶向下，三是逐层分解。8.数据字典(DD)：是结构化分析方法的核心。9.软件需求规格说明书的作用：一是便于用户、开发人员进行理解和交流，二是反映出用户问题的结构，可以作为软件开发工作的基础和依据，三是作为确认测试和验收的依据。三、结构化设计方法1.软件设计：是软件工程的重要阶段，是一个把软件工程环境需求转换为软件表示的过程。2.从技术观点来看，软件设计包括：软件结构设计、数据设计、接口设计、过程设计。3.从工程管理角度来看，软件设计包括：概要设计和详细设计。4.软件设计的基本原理：抽象、模块化、信息隐蔽、模块独立性。5.衡量软件模块独立性的指标：耦合性和内聚性。内聚性是指模块内部各个元素间彼此结合的紧密程度来度量。耦合性是指模块间互相连接的紧密程度来度量.6.概要设计的基本任务:一是设计软件系统结构,二是数据结构及数据库设计,三是编写概要设计文档,四是概要设计文档评审.7.典型的数据类型:变换型和事务型.8.详细设计的任务:为软件结构图中每个模块实现算法和局数数据结构,用某种选定的表达工具表示算法和数据结构的细节.9.构成程序流程图的基本符号及含义:→↓:控制流□:加工步骤◇:逻辑条件四、软件测试1.软件测试：是为了发现错误而执行的过程。经验表明，为了提高测试效率，测试人员应该集中对付那些错误群集的程序。2.软件测试的方法和技术：若从是否需要执行被测试软件的角度，可以分为静态测试和动态测试。若按功能划分可以分白盒测试和黑盒测试。3.白盒测试方法：也称结构测试或逻辑驱动测试，白盒测试是在程序内部进行，主要用于完成软件内部操作的验证。4.黑盒测试方法：也称功能测试及数据驱动测试，黑盒测试完全不考虑程序内部的逻辑结构和特性，只依靠程序的需求和说明，检查程序功能是否符合。5.软件测试的步骤：单元测试、集成测试、确认测试、系统测试。6.单元测试：是对软件设计的最小单位（模块）进行测试，其目的是发现各模块内部可能存在的各种错误。7.集成测试：是测试和组装的过程。其目的是发现与接口有关的错误。8.确认测试：是验证软件功能与需求规格说明中确定的各种需求。9.系统测试：其目的是在真实的系统环境下检验软件的正确性。五、软件调试程序调试的方法：强行排错法、回溯法、原因排除法。第四章数据库设计基础一、数据库系统的基本概念1.数据：实际描述事物的符号记录。2.数据库：简称DB，是数据的集合。3.数据库管理系统：简称DBMS，是数据库的核心。4.数据库系统：简称DBS，它包括数据库、数据库管理系统、数据库管理员、硬件平台、软件平台。5.数据库应用系统：简称DBAS，利用数据库系统进行应用开发可构成一个数据库应用系统。6.数据库系统的发展：人工管理阶段、文件系统阶段、数据库系统阶段。7.数据库系统的特点：数据的集成性、数据的高共享性与低冗余性、数据的独立性、数据统一管理与控制。8.数据独立性：分为物理独立性及逻辑独立性。物理独立性是指当数据物理结构改变时，而不引起应用程序的变化；逻辑独立性是指数据库总体逻辑结构改变时，不需要修改相应的程序。9.数据库系统的三级模式：概念模式、内模式、外模式。概念模式是指数据库中全局数据逻辑结构的描述；外模式也称子模式或用户模式，也就是用户所见到的数据模式；内模式又称物理模式，它给出了数据库物理存取结构与物理存取方法。二、数据模型1.数据模型：可以将复杂的现实世界的要求反映到计算机数据库中的物理世界中。2.数据模型的阶段：从现实世界开始，经历信息世界而计算机世界。3.数据模型所描述的内容：数据结构、数据操作、数据约束。4.E—R模型：面向现实世界，有效和自然地模拟现实世界，广泛使用的概念模型。5.E—R模型的组成：由实体、联系、属性三个基本概念组成。6.E—R模型符号及含义：□：实体集○：属性◇：联系7.层次模型：是早的数据库模型，其基本结构是树形结构。8.关系模型：采用二维表来表示，简称表。9.键：具有标识元组、建立元组间联系等作用。10.外键：当一个表中的某属性集是另一个表的键，则表中属性集为此表的外键。11.关系模型的操作：查询、增加、删除和修改。12.关系中数据约束：实体完整性、参照完整性、用户自定义完整性。三、关系代数1．关系的基本运算分为两类：传统的集合运算和专门的关系运算。传统的集合运算包括并、交、差，专门的关系运算包括选择、投影和联接。2．当有关系S、R时，集合运算，并产生既包含S元组，又包含R元组的集合。交产生既属于S又属于R元组的集合。差产生属于S但不属于R的元组集合。四、数据库设计与管理1.数据库设计的步骤：需求分析、概念设计、逻辑设计、物理设计。2.数据库设计的方法：面向数据的方法、面向过程的方法。第五章补充文件扩展名及文件类型.pjx：项目.dbc：数据库.dbf：表.dct：数据库备注.fpt：表备注.idx：单索引.cdx：复合索引.scx：表单.mnx：菜单.frx：报表.mpr：生成的菜单程序.qpr：生成的查询程序.prg：程序