(知识总结)二级公共基础考点总结

二级公共基础考点总结第一章数据结构与算法(八大考点)考点一:算法1.算法是指解题方案的准确而完整的描述。它有4个基本特征，分别是可行性、确定性、有穷性和拥有足够的情报。2.算法的时间复杂度是指执行算法所需要的计算所需要的计算工作量,算法的空间复杂度是指执行这个算法所需要的内存空间.考点二:数据结构的基本概念1.数据结构是研究数据元素及其之间的相互关系和数据运算的一门学科.数据结构概念一般包括3个方面的内容：逻辑结构）、存储结构）（数据的运算）.数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构；数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式2.在链式存储结构中，存储数据结构的存储空间可以是连续的，也可以是不连续的，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。3.一般来说，一种数据结构根据需要可以表示成多种存储结构。常用的存储结构有顺序、链接、索引等，而采用不同的存储结构，其数据处理的效率是不同的；一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的。4.线性结构是指各数据元素之间的逻辑关系可以用一个线性序列简单地表示出来。否则称之为非线性结构。考点三:线性表及其顺序存储结构1.当线性表采用顺序存储结构实现存储时，其主要特点是数据元素按线性表的逻辑次序，依次存放在一组地址连续的存储单元中。在存储单元中各元素的物理位置和逻辑结构中各结点间的相邻关系是一致的。考点四:栈和队列栈和队列的共同特点是只允许在端点处插入和删除元素栈Top-b+1:线性链表(链式存储中每个结点由两部分组成:数据域和指针。用链表表示线性表的突出优点是便于插入和删除操作.考点六:树与二叉树1.树是一个或多个结点组成的有限集合，其中一个特定的结点称为根2.二叉树的遍历是指不重复地访问二叉树中的所有结点如:已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是cedba解题思路:由后序或前序遍历可判断根结点,再由中序遍历可判断左右子树.考点七:查找技术一.顺序查顺序查找的优点：对线性表的结点的逻辑次序无要求对线性表的存储结构无要求（顺序存储、链接存储皆可。）二.二分法查找二分法查找是一种效率较高的线性表查找方法。线性表结点必须进按关键码值排好序的，且线性表以顺序方式存储。花费时间，顺序方式存储的插入、删除不便。长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。考点八:排序技术1)冒泡排序法在最坏情况下，需要的比较次数为：N（N-1）/22)快速排序法快速排序的平均执行时间为O(nlog2n),显然优于起泡排序和直接插入排序、直接选择排序方法快速排序是以一个记录为基准，用交换的方法把文件分成两部分的思想。二.插入类排序法每步将一个待排序记录按其关键码值的大小插入到前面已排序的文件中的适当位置上，直到全部记录插入完为止。1）简单插入排序在最坏情况下，简单插入排序需要N(N-1)/2次比较2)希尔(Shell)排序法（缩小增量法）在最坏情况下,希尔排序所需要的比较次数为O(N1.5).希尔排序的效率与所选取的增量序列有关.1）简单选择排序简单选择排序法在最坏情况下需要比较N(N-1)/2次2）堆排序堆排序是完全二叉树结构的一个重要应用。堆排序的方法对于规模较小的线性表并不适合,但对于较大规模的线性表来说是很有效的.在最坏怀况下,堆排序需要比较的次数为nlog2n次,堆排序的执行时间为O（nlog2n）,适合于较大文件的排序方法。相关知识点:从平均时间性能而言，快速排序最佳，其所需时间最少，在待排序的元素序列基本有序的前提下，效率最高的排序方法是冒泡排序和简单选择排序第二章程序设计基础(三大考点)考点一:程序设计方法与风格1．源程序文档化文档是有关计算机程序功能、设计、编制、使用的文字或图形资料。编制一个好的程序首先要确保它的正确性和可靠性还应强调良好的编程风格。在书写时应考虑为程序作注释。程序编写要做到清晰第一、效率第二。考点二:结构化程序设计1．结构化程序设计的原则：自顶向下、逐步求精、模块化、限制使用GOTO语句。2．结构化程序的基本结构：顺序结构、选择结构、重复结构（或称为循环结构）数据成分：用来描述程序中的数据。运算成分：描述程序中所需的运算。控制成分：用来构造程序的逻辑控制结构。传输成分：定义数据传输成分，如输入输出语言。2．当程序之间发生调用关系时，调用命令所在的代码段被称为主程序，被调用的代码段被称为子程序。子程序是对功能的抽象，可分为过程和函数两类，两者的区别是函数是通过函数名来返回值的，而过程只能通过形式参数或对全局变量进行修改以返回值。考点三:面向对象的程序设计一．面向对象的优点：A．与人类习惯的思维方法一致B．稳定性好C．可重用性好D．易于开发大型软件产品E．可维护性好4．面向对象方法的基本概念1）对象优点：通过重用性提高软件的生产率。对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。对象是属性和方法的封装体。属性即对象包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。面向对象方法和技术以对象为核心，对象之间通过传递消息互相联系。面向对象方法的概念包括：对象、属性、方法、类、继承、多态性没有过程调用。对象有五个基本特点：A．标识惟一性B．分类性C．多态性D．封装性E．模块独立性好2）类和实例将属性、操作相似的对象归为类。类是具有共同属性、共同方法的对象的集合。所以，类是对象的抽象，它描述了属于该对象类型的所有对象的性质。而一个对象则是其对应类的一个实例。3）消息对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。消息是一个实例与另一个实例之间传递的信息，它请求对象进行某一处理或回答某一要求的信息，它统一了数据流和控制流。消息的使用类似于函数调用4）继承一个类直接继承其父类的描述或特性，子类自动地共享基类中定义的数据和方法。继承是指能够直接获得已有的性质和特征，而不必重复定义他们。继承性是面向对象程序设计语言不同于其他语言的主要标志。5）多态性对象根据所接受的消息而做出的动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。是否建立了丰富的类库是衡量一个面向对象程序设计语言成熟与否的一个重要标志。第三章软件工程基础(五大考点)考点一:软件工程基本概念一．软件定义与软件特点包括程序、数据及相关文档的完整集合。其中，程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令（语句）序列。数据是使程序能正常操纵信息的数据结构。计算机软件是指与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。软件的特点：它是一种逻辑实体，没有明显的制作过程，软件在运行、使用期间不存在磨损、老化问题，软件的开发具有依赖性，其复杂性高，成本高，软件开发涉及诸多的社会因素。分为：应用软件、系统软件、支撑软件二．软件危机与软件工程1．软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。软件危机归结为成本、质量、生产率等问题。软件工程包括3个要素，即方法、工具和过程。软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。软件工程过程通常包含4种基本活动：P–软件规格说明。D-软件开发C-软件确认A-软件演进2.软件生命周期分为软件定义、软件开发及软件运行维护3个阶段。软件定义包括可行性研究与计划制定、需求分析两个阶段；软件开发包括软件设计（概要设计和详细设计）、软件编码和软件测试三大阶段；软件运行维护阶段包括使用、维护、退役。软件维护活动包括以下几类：改正性维护、适应性维护、完善性维护、预防性维护。维护是软件生命周期的最后一个阶段，也是持续时间最长，花费代价最大的一个阶段，软件工程学的一个目的就是提高软件的可维护性，降低维护的代价。只有软件定义有用户的参与。软件产品从考虑其概念开始，到该软件产品不能使用为止的整个时期都属于软件生命周期。一般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动。三．软件工程的目标和原则1．基于软件工程的目标软件工程的理论和技术性研究的内容主要包括：软件开发技术，另一个内容是软件工程管理（1．软件工程的原则：其基本原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。四．软件开发工具与软件开发环境软件开发工具为软件工程学提供了自动的或半自动的软件支撑环境。软件开发工具的发展是从单项工具的开发逐步向集成工具发展的。软件开发环境或称软件工程环境是全面支持软件开发全过程的软件工具集合。考点二:结构化分析方法一．需求分析与需求分析方法1．需求分析阶段工作概括为四个方面：需求获取、需求分析、编写需求规格说明书、需求评审。需求分析是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期待。准确地解决了“软件系统必须做什么”。需求规格说明书是需求分析的最终结果。2.常见的需求分析方法有结构化分析方法和面向对象的分析方法两类。其中结构化分析方法又包括面向数据流的结构化分析方法（SA－Structuredanalysis），面向数据结构的Jackson方法（JSD－Jacksonsystemdevelopmentmethod）和面向数据结构的结构化数据系统开发方法（DSSD－Datastructuredsystemdevelopmentmethod）。从需求分析建立的模型的特性来分，需求分析方法又分为静态分析方法和动态分析方法。二．结构化分析方法结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用。1．结构化分析方法的实质是着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。2．结构化分析的常用工具：1）数据流图（DFD-DataFlowDiagram）。数据流。沿箭头方向传送数据的通道，一般在旁边标注数据流名。存储文件（数据源）。表示处理过程中存放各种数据的文件。源，潭。表示系统和环境的接口，属系统之外的实体。建立数据流图的步骤：由外向里，自顶向下，逐层分解。2）数据字典（DD-DataDictionary）数据字典是结构化分析方法的核心。结构化分析方法使用的描述工具数据字典定义了数据流图中的每个图形元素。3）判定树判定表判定表采用表格表达工具。三．软件需求规格说明书是需求分析阶段的最后成果，是软件开发中的重要文档之一。内容对软件主要功能、用户界面、运行环境、算法详细过程、软件的性能说明。作用：①便于用户、开发人员进行理解和交流；②反映出用户问题的结构，可以作为软件开发工作的基础和依据；③作为确认测试和验收的依据。考点三:结构化设计方法一．软件设计的基本概念1．软件设计的基础软件件设计是确定系统的物理模型。从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。，软件设计分两步完成：概要设计和详细设计。概要设计（又称结构设计）将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库模式；详细设计确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。软件设计的一般过程是：软件设计是一个迭代的过程；先进行高层次的结构设计；后进行低层次的过程设计；穿插进行数据设计和接口设计。2．软件设计的基本原理：1）抽象2）模块化3）信息隐蔽4）模块独立性耦合性是模块间互相连接的紧密程度的度量。）高内聚低耦合。二．概要设计软件的概要设计又称为总体结构设计，其主要任务是建立软件系统的总体结构。得到一个优化的软件结构图。常见的软件结构设计工具是结构图（SC），也称为程序结构图。经常使用的结构图有四种模块类型：传入模块、传出模块、变换模块和协调模块。深度：表示控制的层数。宽度：整体控制跨度（最大模块数的层）的表示。扇入：调用一个给定模块的模块个数。扇出：一个模块直接调用的其他模块数。原子模块：树中位于叶子结点