搜索
第一章数据结构与算法算法：指解题方案的准确而完整的描述。1.基本特征：可行性、确定性、有穷性、拥有足够的情报2.基本要素：数据对象的运算和操作、算法的控制结构。3.算法控制结构：顺序结构、选择结构、循环结构。常用工具：流程图、N-S结构图、算法描述语言等。4.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法5.算法复杂度：时间复杂度（计算工作量）、空间复杂度（需要的内存空间）。数据结构：指相互有关联的数据元素的集合。包括：表示数据元素的信息、表示各数据之间的前后件关系1.数据的逻辑结构：反映数据元素之间的逻辑关系的数据结构。2.数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，或数据的物理结构。通常的数据存储结构有顺序、链接、索引等存储结构。线性结构：有且只有一个根结点；每一个结点最多只有一个前件，也最多只有一个后件。线性结构又称线性表。1.线性表中结点的个数称为结点的长度n。当n=0时，称为空表。2．顺序存储结构特点：线性表中所有的元素所占的存储空间是连续的；各数据元素在存储空间中是按逻辑顺序依次存放的栈：一种特殊的线性表，它是限定在一端进行插入和删除的线性表。原则：先进后出或后进先出。Top=0表示栈空；top=m表示栈满。队列：是允许在一端进行插入，而在另一端进行删除的线性表。规则：先进先出或后进后出循环队列：是次队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。1.循环队列的初始状态为空，即rear=front=m。这里m即为队列的存储空间。2.队列空的条件：s=0；队列满的条件：s=1、front=rear顺序存储：结构简单、运算方便。但运算效率较低；如果出现线性表的存储空间已满，还需要插入元素时，会发生“上溢”错误；有可能使有的队列空间不够或过多造成浪费。因此对于大的线性表或元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储结构。链式存储：1.假设每一个数据结点对应一个存储单元，该存储单元称为存储结点，简称结点。2.每一个结点由两部分组成：一部分用于存放数据元素，称为数据域；另一部分用于存放指针，称为指针域。3.存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系不一致4.链式存储结构既可以用于线性结构，也可用于非线性结构。二叉树的性质：1：在二叉树的第k层上，最多有2k-1（k≥1）个结点。2：深度为m的二叉树最多有2m-1个结点。3：在任意一棵二叉树中，度为0的结点（即叶子结点）总比度为2的结点多一个。4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。5：具有n个结点的完全二叉树的深度为[log2n]+1二叉树的遍历：二叉树的存储常采用链式存储结构1.前序遍历：根结点、左子树、右子树。在遍历左子树和遍历右子树时，依然是先遍历根结点，然后是左子树，再是右子树。2.中序遍历：左子树、根结点、右子树。3.后序遍历：左子树、右子树、根结点。查找技术：1．顺序查找：最坏情况的查找次数是n次2．二分查找：最坏情况的查找次数是log2n次。排序技术：1．交换类排序法：冒泡排序法、快速排序法2．插入类排序法：简单插入排序、希尔排序法3．选择类排序法：简单选择排序法、堆排序法第二章程序设计基础程序设计方法：主要经过了面向过程的结构化程序设计和面向对象的程序设计方法。程序设计风格：指编写程序时所表现出来的特点、习惯和逻辑思路。通常，要求程序设计的风格应强调简单和清晰，必须是可以读的，可以理解的。要形成良好的程序设计的风格，应考虑：源程序文档化、数据说明方法、语句的结构、输入和输出结构化程序设计1.原则：自顶而下、逐步求精，模块化，限制使用goto语句。2.基本结构：顺序结构、选择结构、重复结构3.特点：使程序结构良好、易读、易理解、易维护。面向对象的程序设计1.优点：与人类习惯的思维方法一致、稳定性好、可重用性好、易于开发大型软件产品、可维护性好。2.基本概念：对象（基本特点：标识的唯一性、分类性、多态性、封装性、模块独立性好）、类和实例、消息、继承、多态性第三章软件工程基础软件：与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。软件危机：泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题软件工程：应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。1.要素：方法、工具、过程（软件规格说明、软件开发、软件确认、软件演进过程）2.目标：在给定成本、进度的情况下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。3.理论和技术性研究内容：软件开发技术、软件工程管理。4.原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性。软件生命周期：1.主要阶段：软件定义、软件开发、软件维护2.主要活动阶段：可行性研究与计划制定、需要分析、软件设计、软件实现、软件测试、运行和维护。需求分析：指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。1.任务是发现需求、求精、建模和定义需求的过程。2.工作：需求获取、需求分析、编写需求规格说明书、需求评审3.方法：结构化分析方法、面向对象的分析方法结构化分析方法：实质是着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。常用工具：数据流图、数据字典、判定树、判定表软件需求规格说明书1.作用：便于用户、开发人员理解和交流；反映用户问题的结构，可以作为软件开发工作的基础和依据；作为确认测试和验收的依据2.特点：正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性、可追踪性软件设计：包括结构设计、数据设计、接口设计、过程设计。基本原理：抽象、模块化、信息隐蔽、模块独立性内聚性：一个模块内部各个元素间彼此结合的紧密程度的度量耦和性：模块间相互连接的紧密程序的度量结构化设计方法：即将软件设计成相对独立、单一功能的模块组成结构。工具是结构图。结构图中模块类型：传入模块、传出模块、变换模块、协调模块概要设计任务：设计软件系统结构、数据结构及数据库设计、编写概要设计文档、概要设计文档评审详细设计：为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种工具表示算法和数据结构的细节。工具：程序流程图、N-S、PAD、HIPO、判定表、PDL（伪码）软件测试：1.目的：检验它是否满足规定的需求或是否弄清预期的结果与实际结果之间的差别。2．方法：静态测试、动态测试、白盒测试（逻辑驱动测试）、黑盒测试（数据驱动测试，软件已经实现的功能是否满足需求）。3．实施：单元测试（发现模块内部的错误）、集成测试（发现与接口有关的错误）、确认测试（是否满足了需求规格说明）、系统测试（在实际运行环境中进行一系列的集成测试和确认测试）。程序的调试：1.活动：根据错误的迹象确定程序中错误的确切性质、原因和位置；对程序进行修改，排除错误。2.基本步骤：进行回溯测试，防止引进新的错误修改设计和代码，以排除错误错误定位3.方法：强行排错法、回溯法、原因排除法（演绎法、归纳法、二分法）。第四章数据库设计基础（一）数据库系统的基本概念1．数据、数据库、数据库管理系统1）数据数据是指存储在某一种媒体上能够被识别的物理符号，即描述事物的符号记录。数据是有结构的。首先，数据有型与值的区别，型即类型，值是符合指定类型的值。数据的概念在数据处理领域中已经大大地拓宽了。数据不仅包括数字、字母、文字和其他特殊字符组成的文本形式的数据，而且还包括图形、图像、动画、影像、声音等多媒体数据。但是使用最多、最基本的仍然是文字数据。2）数据库数据库（DataBase，DB），是存储在计算机存储设备上，结构化的相互关联的数据的集合。它不仅包括描述事物的数据本身，而且还包括相关事物之间的联系。它用综合的方法组织和管理数据，具有较小的数据冗余，可供多个用户共享，具有较高的数据独立性，具有安全机制，能够保证数据的安全、可靠，允许并发地使用数据库，能有效、及时地处理数据，并能保证数据的一致性和完整性。例如，某个学校的相关数据，如学生基本情况、选课情况、学籍管理等所涉及的相关数据的集合。3）数据库管理系统数据库管理系统（DataBaseManagementSystem，DBMS）是对数据库进行管理的系统软件，它的职能是有效地组织和存储数据、获取和管理数据，接受和完成用户提出的访问数据的各种请求。同时还能保证数据的安全性、可靠性、完整性、一致性，还要保证数据的高度独立性。数据库管理系统主要功能包括以下几个方面：（1）数据模式定义数据库管理系统负责为数据库构建模式，也为数据库构建其数据框架。（2）数据存取的物理构建数据库管理系统负责为数据模式的物理存取及构建提供有效的存取方法和手段。（3）数据操纵数据库管理系统为用户使用数据库中的数据提供方便，一般提供查询、插入、修改和删除数据的功能，此外，还具有简单的算术运算和统计功能，还具有专长强大的程序控制功能。（4）数据的完整性、安全性定义与检查数据库中的数据具有内存语义上的关联性与一致性，即数据的完整性。数据的完整性是保证数据库中数据正确的必要条件。（5）数据的并发控制与故障恢复数据库是一个集成、共享的数据集合体，它能为多个应用程序服务，因此，当多个应用程序对数据库并发操作时，要保证数据不被破坏。（6）数据的服务数据库管理系统提供了对数据库中数据的多种服务，如数据拷贝、转存、重组、性能监测、分析等。数据库管理系统提供的相应的数据语言包括如下：1）数据定义语言（DataDefinitionLanguage，DDL）D用户通过它可以方便地对数据库中的相关内容进行定义。例如，对数据库、表、索引进行定义。2）数据操纵语言（DataManipulationLanguage，DML）用户通过它可以实现对数据库的基本操作。例如，对表中数据的查询、插入、删除和修改。3）数据控制语言（DataControlLanguage，DCL）负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能，包括系统初启程序、文件读写与维护程序、存取路径管理程序、缓冲区管理程序、安全性控制程序、完整性检查程序、并发控制程序、事务管理程序、运行日志管理程序、数据库恢复程序等。目前流行的DBMS均为关系型数据库系统，发ORACLE、Sybase的PowerBuilder及IBM的DB2、微软件的SQLServer等。还有一些小型的数据库，如VisualFoxPro和Access等。4）数据库管理员数据库的管理员（DataBaseAdministrator，DBA）：对数据库的规划、设计、维护、监视等进行管理。主要工作如下：（1）数据库设计（2）数据库维护（3）改善系统性能，提高系统效率5）数据库系统数据库系统（DataBaseSystem，DBS）由如下几个部分组成：数据库（数据）数据库管理系统（软件）数据库管理员（人员）系统平台（硬件平台和软件平台）硬件平台包括：计算机网络软件平台包括：操作系统数据库系统开发工具接口软件6）数据库应用系统数据库应用系统（DataBaseApplicationSystem，DBAS）是数据库系统再加上应用软件及应用界面而构成的。它包括：数据库数据库管理系统数据库管理员硬件平台软件平台应用软件应用界面2．数据库系统的发展随着计算机软硬件技术的发展，数据处理方法也经历了从低级到高级的发展过程，按照数据管理的特点可将其划分为人工管理、文件系统及数据库系统三个阶段。1）人工管理阶段在20世纪50年代，计算机主要用于数值计算。从当时的硬件看，外存只有纸带、卡片、磁带，没有直接存取设备；从软件看（实际上，当时还未形成软件的整体概念），没有操作系统以及管理数据的软件；从数据看，数据量小，数据无结构，由用户直接管理，且数据间缺乏逻辑组织，数据依赖于特定的应用程序，缺乏独立