第一章数据结构与算法P1—P381.1算法1.1.1算法的基本概念P1—P4所谓算法是指解题方案的准确完整的描述。1.算法的基本特征1可行性2确定性3有穷性4拥有够的情报2.算法的基本要素一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。1算法中对数据的运算和操作插入、删除2算法的控制结构一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。1.1.2算法复杂度P4—P6算法的复杂度主要包括时间复杂度和空间复杂度。1．算法的时间复杂度所谓算法的时间复杂度，是指执行算法所需要的计算工作量。可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。3.算法的空间复杂度一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。1.2数据结构的基本概念数据结构，主要研究和讨论以下三个方面的问题：①数据的逻辑结构；②数据的存储结构；③对各种数据结构进行的运算。插入、删除主要目的是为了提高数据处理的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，时间复杂度二是尽量节省在数据处理过程中所占用的计算机存储空间。空间复杂度1.2.1什么是数据结构P6—P111.数据的逻辑结构所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。2.数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构也称为数据的物理结构一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。1.2.3线性结构与非线性结构P12一般将数据分为两大类型：线性结构与非线性结构。线性结构又称线性表如果一个数据结构不是线性结构，则称之为非线性结构。1.3线性表及其顺序存储结构1.3.1线性表的基本概念P12—P13线性表是由nn≥0个数据元素a1，a2，…，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为。a1,a2,…,ai,…,an非空线性表有如下一些结构特征：①有且只有一个根结点a1，它无前件；②有且只有一个终结点an，它无后件；③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。1.3.2线性表的顺序存储结构P13—P14在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。线性表的顺序存储结构具有以下两个基本特点：①线性表中所有元素据所占的存储空间是连续的；②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。假设线性表中的第一个数据元素的存储地址为ADRa1，每一个数据元素占K个字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为ADRa1=ADRa1+i-1K1.3.3顺序表的插入运算P14—P15在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的。1.3.4顺序表的删除运算P15—P16在平均情况下，要在线性表中删除一个元素，需要移动表中表中一半的元素。因此，在线性表顺序存储的情况下，要删除一个元素，其效率也是很低的。由线性表在存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单。但这种顺序存储的方式对于元素经常需要变动的大线性表就不太合适了，因为插入删除的效率比较低。1.4栈和队列1.4.1栈及其基本运算P16—P181.什么是栈栈是限定在一端进行插入与删除的另一端称为栈底。即栈是按照“先进后出”FILO或“后进先出”LIFO的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。2.栈的顺序存储及其运算采用顺序存储结构的栈称为顺序栈栈的基本运算有三种：入栈、退栈与读栈顶元素。1入栈运算2退栈运算3读栈顶元素1.4.2队列及其基本运算P18—P201.什么是队列队列queue是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针rear的指针指向队尾元素，一端称为排头也称为队头通常也用一个排头指针front指向排头元素的前一个位置。队列双称为“先进先出”或“后进后出”的线性表。3.循环队列及其运算在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。1入队运算2退队运算1.5线性链表1.5.1线性链表的基本概念P20—P23由于线性表的顺序存储结构存在以上这些缺点，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用下面要介绍的链式存储结构。在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。在链式存储结构中，存储数据结构的存储空间可以下连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可用于表示线性结构，也可以用于表示非线性结构。1.线性链表线性表的链式存储结构称为线性链表。2.带链的栈栈也是线性表，也可以采用链式存储结构。3.带链的队列与栈类似，队列也是线性表，也可以采用链式存储结构。1.5.2线性链表的基本运算P23—P25线性链表在插入过程中不发生数据元素移动的现象，只需改变有关结点的指针即可，从而提高了插入的效率。从线性链表的删除过程可以看出，在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。1.5.3循环链表及其基本运算P25—P26循环链表具有以下两个特点：1在循环链表中增加了一个表头结点，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。2循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。1.6树与二叉树1.6.1树的基本概念P26—P28在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件个数称为该结点的度在树中，所有结点中的最大的度称为树的度。根结点在第1层。树的最大层次称为树的深度。1.6.2二叉树及其基本性质P28—P311.什么是二叉树二叉树具有以下两个特点：①非空二叉树只有一个根结点；②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。2.二叉树的基本性质性质1在二叉树的第K层上，最多有2K-1K≥1个结点。性质2深度为m的二叉树最多有2m-1个结点。性质3在任意一棵二叉树中，度为0的结点即叶子结点总是比度为2的结点多一个。3.满二叉树与完全二叉树1满二叉树所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点，这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第K层上有2K-1个结点，且深度为m的满二叉树有2m-1个结点。2完全二叉树所谓完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边若干结点。满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。性质6设完全二叉树共有n个结点。从根结点开始，按层序用自然数1,2，…，n给结点进行编号，则对于编号为kk=1,2,…,n的结点有以下结论：①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INTk/2。②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点。③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。1.6.3二叉树的存储结构P31—P32在计算机中，二叉树通常采用链式存储结构。1.6.4二叉树的遍历P32—P33二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。1.前序遍历DLR2.中序遍历LDR3.后序遍历LRD1.7查找技术1.7.1顺序查找P33顺序查找又称顺序搜索。对于大的线性表来说，顺序查找的效率是很低的。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找：1线性表无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。2即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。1.7.2二分法查找P33—P34二分法查找只适用于顺序存储的有序表。显然，当有序线性表为顺序存储时都能采用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。1.8排充技术1.8.1交换类排序法P34—P351.冒泡排序法冒泡排序法是一种最简单的交换类排序方法。假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为nn-1/2。2.快速排序法快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。1.8.2插入类排序法P35—P371.简单插入排序法自以为插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。在简单插入排序法中，这种排序方法的效率与冒泡排序法相同。在最坏情况下，证券交易插入排序需要nn-1/2次比较。2.希尔排序法希尔排序法属于插入类排序，但它对简单插入排序做了较大的改进。1.8.3选择类排序法P37—P381.简单选择排序法从中选出最小的元素，将它交换到表的最前面。简单选择排序法在最坏情况下需要比较nn-2/2次。2.堆排序法堆排序法属于选择类的排序方法。堆排序的方法对于规模较小的线性表并不合适，但对于较大规模的来说是很有效的。分享到搜狐微博第2章程序设计基础P40—P452.1程序设计方法与风格程序设计的风格总体而言应该强调简单和清晰，程序必须是可以理解的。可以认为，著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。源程序文档化应考虑如下几点：1符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。2程序注释：正确的注释能够帮助读者理解程序。注释一般分为序言性注释和功能性注释。3视觉组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。2.2结构化程序设计2.2.1结构化程序设计的原则P41—P42结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句。2.2.2结构化程序的基本结构与特点P42—P431.顺序结构2.选择结构：选择结构又称为分支结构。3.重复结构：重复结构又称为循环结构。2.3面向对象的程序设计今天面向对象方法已经发展成为主流的软件开发方法。一些著名的面向对象语言如C++、Java2.3.2面向对象方法的基本概念P45—P481.对象对象是面向对象方法中最基本的概念。对象可以用来表示客观世界中的任何实体。面向对象的程序设计方法中涉及的对象由一组表示其静态特征的属性和它可执行的一组操作组成。4封装性。2.类Class和实例Instance将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共同方法方法的对象的集合。所以，类是对象的抽象，而一个对象则是其对应类的一个实例。3.消息对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。消息是一个实例与另一个实例之间传递的信息。4.继承继承是面向对象的方法的一个主要特征。第3章软件工程基础3.1软件工程基本概念3.1.1软件定义与软件特点P50计算机软件是包括程序、数据及相关文档的完整集合。可见软件由两部分组成：一是机器可执行和程序和数据；二是机器不可执行的，与软件开发、运行、维护、使用等有关的文档。软件的特点：①软件是一种逻辑实体，而不是物理实体，具有抽象性。②软件的生产与硬件不同，它没有明显的制作过程。③软件在运行、使用期间不存在磨损、老化问题。④软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题。⑤软件复杂性高，成本昂贵。⑥软件开发涉及诸多的社会因素。3.1.2软件危机与软件工程P51—P52软件工程概念的出现源自软件危机。20世纪60年代末以后，“软件危机”。所谓软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。1968年在北大西洋公约组织会议NATO会议上，讨论摆脱软件危机的办法，软件工程作为一个概念首次被提出。软件工程包括个要素，即方法、工具和过程。3.1.3软件工程过程与软件生命周期P52—P532.软件生命周期通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。3.1.4软件工程的目标与原则P53—P541.软件工程的目标软件工程内容主要包括：软件开发技术和软件工程管理。3.1.5软件开发工具与软件开发环境P541.软件开发工具VB、VC++、VFP2.软件开发环境软件开发环境或称软件工程环境是全面支持软件开发全过程的软件工具集合。计算机辅助软件工程CASE3.2结构化分析方法3.2.1需求分析与需求分析方法P53—P591.需求分析1需求分析阶段的工作需求分析阶段的工作，可以概括为四个方面：①需求获取②需求分析③编写需求规格说明书④需求评审2.需求分析方法常见的需求分析方法有：①结构化分析方法。主要包括：面向数据流的结构化分析方法SA面向数据结构的Jackson方法JSD面向数据结构的结构化数据系统开发方法DSSD②面向对象的分析方法OOA3.2.2结构化分析方法P55—P592.结构化分析的常用工具1数据流图DFD2数据字典DD数据字典是结构化分析方法的核心。3判定树4判定表3.2.3软件需求规格说明书P59—P60软件规格说明书SRS是需求分析阶段的最后成果，是软件开发中的重要文档。软件需求规格说明书的作用是：①便于用户、开发人员进行理解和交流。②反映出用户问题的结构，可以作为软件开发工作的基础和依据③作为确认测试和验收的依据。3.3结构化设计方法3.3.1软件设计基本概念P60—P621.软件设计的基础软件设计分两步完成：概要设计和详细设计。2.软件设计的基本原理1抽象2模块化3信息隐蔽4模块独立性模块独立程度是评价设计好坏的重要度量标准。衡量软件的模块独立软件的模块独立性使用耦合性和内聚性两个定性的度量标准。①内聚性：内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。②耦合性：耦合性是模块间互相连接的紧密程度的度量。耦合性与内聚性是模块独立性的两个定性标准，耦合与内聚是相互关联的。在程序结构中，各模块的内聚性越强，则耦合性越弱。一般较优秀的软件设计，应尽量做到高内聚，低耦合。3.3.3详细设计P67—P71几种主要的工具：1.程序流程图PFD2.N-S盒图3.PAD图PAD图是问题分析图ProblemAnalysisDiagram的英文缩写。4.PDL过程设计语言PDL也称为结构化的英语和伪码。3.4软件测试软件测试的投入，通常其工作量、成本占软件开发总工作量、总成本的40%以上。软件测试是保证软件质量的重要手段，其主要过程涵盖了整个软件生命期的过程。3.4.1软件测试的目的P71关于软件测试的目的，软件测试是为了发现错误而执行程序的过程。3.4.3软件测试技术与方法综述P71—P77可以分为静态测试和动态测试方法。若按照功能划分可以分为白盒测试和黑盒测试方法。1.静态测试与动态测试1静态测试静态测试可以由人工进行，充分发挥人的逻辑思维优势。2动态测试静态测试不实际运行软件，主要通过人工进行。动态测试是基于计算机的测试，是为了发现错误而执行程序的过程。2.白盒测试白盒测试方法也称结构测试或逻辑驱动测试。3.黑盒测试方法黑盒测试方法也称功能测试或数据驱动测试。黑盒测试是对软件已经实现的功能是否满足需求进行测试和验证。黑盒测试完全不考虑程序内部和逻辑结构和内部特性。3.4.4软件测试的实施P77—P80软件测试是保证软件质量的重要手段。软件测试过程一般按4个步骤进行，1.单元测试单元测试是对软件设计的最小单位——模块程序单元进行正确性检验的测试。2.集成测试集成测试是测试和组装软件的过程。3.确认测试4.系统测试3.5程序的调试3.5.1基本概念P80—P81程序调试的任务是诊断和改正程序中的错误。它与软件测试不同，软件测试是尽可能多地发现软件中的错误。软件测试贯穿整个软件生命期，调试主要在开发阶段。3.5.2软件调试方法P81—P821.强行排错法2.回溯法3. 原因排除法第4章数据库设计基础P84—P1114.1数据库系统的基本概念4.1.1数据、数据库、数据库管理系统P84—P871.数据数据Data实际上就是描述事物的符号记录。2.数据库数据库简称DB是数据的集合。3.数据库管理系统数据库管理系统简称DBMS它是一种软件。数据库管理系统是数据库系统的核心。目前流行的DBMS均为关系数据库系统，如微软的VisualFoxPro和Access等。4.数据库管理员简称DBA5.数据库系统数据库系统简称DBS由如下几部分组成：数据库数据、数据库管理系统软件、数据库管理员人员、系统平台之一____硬件平台硬件、系统平台之二——软件平台软件这五个部分构成了一个以数据库为核心的完整的运行实体，称为数据库系统。4.1.2数据库系统的发展P87—P88数据管理发展至今已经历了三个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。1.关系数据库系统阶段数据管理三个阶段的比较人工管理文件系统数据库系统特点数据共享程度无共享冗余度大共享性差冗余度大共享性大冗余度小数据独立性不独立，完全依赖于程序独立性差具有高度的物理独立性和一定的逻辑独立性4.1.3数据库系统的基本特点P88—P890数据库系统具有以下特点：1.数据的集成性2.数据的高共享性与低冗余性3.数据独立性数据独立性是数据与程序间的互不依赖性，数据独立性一般分为物理独立性与逻辑独立性两级。1物理独立性：物理独立性即是数据的物理结构的改变，从而不致引起应用程序的变化。2逻辑独立性：数据库总体逻辑结构的改变，不需要相应修改应用程序，这就是数据的逻辑独立性。4.数据统一管理与控制4.1.4数据库系统的内部结构体系P89—P911.数据库系统的三级模式1概念模式。概念模式是数据库系统中全局数据逻辑结构的描述，是全体用户应用公共数据视图。2外模式。外模式也称子模式或用户模式。它是用户的数据视图。3内模式。内模式又称物理模式，它给出了数据库物理存储结构与物理存取方法。2.数据库系统的两级映射1概念模式到内模式的映射。2外模式到概念模式的映射。4.2数据模型4.2.1数据模型的基本概念P91数据模型按不同的应用层次分成三种类型，它们是概念数据模型、逻辑模型、物理数据模型，概念模型有E-R模型、逻辑数据模型又称数据模型，层次模型、网状模型、关系模型，物理数据模型又称物理模型。1.2.2E-R模型P91—P95概念模型是E-R模型或实体联系模型1.E-R模型的基本概念1实体现实世界中的事物可以抽象成为实体2属性现实世界均有一些特性，这些特性可以用属性来表示。属性刻画了实体的特征。3联系一对一的联系，简记为1：1。一对多或多对一联系，简记为1：M1：m或M：1m：1。多对多联系，简高为M：N或m:n。3.E-R模型的图示法在E-R图中用椭圆形表示属性。在E-R图中用菱形表示联系。4.2.3层次模型的基本结构是树形结构P954.2.4网状模型P95—P96网状模型是一个不加任何条件限制的无向图。4.2.5关系模型P96—P981.关系的数据结构关系模型采用二维表来表示。4.3关系代数4查询①投影运算②选择运算③笛卡尔积运算则关系R与S经笛卡尔积记为R×S。3.关系代数中的扩充运算1交运算还有并和差关系R与S经交运算后所得到的关系是由那些既在R内又在S内的有序组成，记为R∩S。2除运算如果将笛卡尔积运算看作乘运算的话，那么除运算就是它的运算。T÷R=S或R/R=S4.4数据库设计与管理数据库设计是数据库应用核心。4.4.1数据库设计概述P104整个数据库应用系统的开发成目标独立的若干阶段。它们是：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段。4.4.2数据库设计的需求分析P104—P1054.4.3数据库概念设计画E-R图P105—P1084.4.4数二级公共基础知识除运算据库的逻辑设计P108—P1091.从E-R图向关系模式转换。4.4.5数据库的物理设计P110。 二级公共基础知识除运算 二级公共基础知识除运算
扫一扫，手机继续看
部分数据为事业单位考试网(www.sydw.cn)收集整理，转载或复制请注明出处！-事业单位考试网-
