公共基础考试知识点.doc

公共基础一：考题特点1涉及面广，但难度小考试中有关公共知识部分的题目共有15道共30分设有10道选择题和5道填空题，涉及算法及数据结构、程序设计基础、软件工程基础和数据库设计基础等四门学科，但是从整体上分析，考核内容的难度不大，考点也相对集中些。2.考核重点为基本概念、基本方法和基本运算。3.考试中涉及的题目都是基本概念、基本方法和基本运算，考核以概念和认识性内容为主，理解性、应用性内容极少。二：复习建议二级考试的公共知识部分的覆盖面广，至少涵盖了计算机应用专业的四门核心课程：算法及数据结构、程序设计基础、软件工程基础和数据库。事实上，这些课程本身的涉及面就很广，难度系数较大。因此，这些课程甚至也是计算机专业学生最头疼的课程，对大多数考生来说其难度之大不言而喻。所以，考生应把80%的时间用在20%的重点知识点上，争取用20%的重点知识点来答对80%的考题，这是考生复习二级考试的公共知识部分的总体思路。三：公共基础内容 第一章：数据结构与算法第二章：程序设计基础第三章：软件工程基础第四章：数据库设计基础第一章：数据结构与算法一：算法1.概念:计算机解决问题的过程或步骤即解决方案的完整而准确的描述。算法不同于程序，算法优于程序。2.基本特征:可行性、确定性、有穷性、拥有足够的情报。（1） 可行性：针对实际问题而设计的算法，执行后能够得到满意的结果。（2） 确定性：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。（3） 有穷性：算法必须的有限时间内做完，即算法必须能在执行有限个步骤之后终止。 （4） 拥有足够的情报：要使算法有效必须为算法提供足够的情报。当算法拥有足够的情报时，此算法才是有效的；当提供的情报不够时，算法可能无效。3.结构：一个算法一般都可以用顺序，选择，循环3种基本控制结构组合而成。4.算法的复杂度：主要包括时间复杂度和空间复杂度。时间复杂度：指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量。空间复杂度：执行这个算法所需要的内存空间。注意：算法的时间复杂度与空间复杂度并不相关。二：数据结构的基本概念1概述：利用计算机进行数据处理是计算机应用的一个重要领域。在进行数据处理时，实际需要处理的数据元素一般很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。2概念：数据结构是指相互有关联的数据元素的集合。更通俗地说，数据结构是指带有结构的数据元素的集合。在此，所谓结构实际上就是指数据元素之间的前后件关系。 例如：在考虑一日三餐的时间顺序关系时，“早餐”是“午餐”的前件，而“午餐”是“早餐”的后件；同样，“午餐”是“晚餐”的前件，“晚餐”是“午餐”的后件。由上所述，一个数据结构应包含以下两方面的信息：1）表示数据元素的信息。 2）表示各数据元素之间的前后件关系。 3研究方向：数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题。（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，数据的存储结构； （3）对各种数据结构进行的运算。 4 数据的逻辑结构和存储结构(1)数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成 B=(D,R)其中B表示数据结构。为了反映D中各数据元素的前后件关系，一般用二元组表示。例如：如果把一日三餐看做一个数据结构，则可表示成B=(B,D)D=早餐，午餐，晚餐R=（早餐，午餐），（午餐，晚餐）(2)数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。注意：常用的存储结构有顺序、链接、索引等。 顺序存储结构：把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现，其优点是占用 最少的存储空间。链式存储结构：是用一组任意存储单元来存放表中的数据元素，为了表示出每个元素与其直接后继元素之间的关系，除了存储元素本身的的信息外，还需存储一个指示其直接后继的存储位置信息。采用不同的存储结构，其数据处理的效率是不同的。5 线性结构和非线性结构认识：在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称为叶子结点），其他称为内部结点。如：概念：根据数据结构中各数据元素之间前后件关系的复杂度，一般将数据逻辑结构分为两大类型：线形结构和非线性结构。(1)线性结构：指的是数据元素之间存在着“一对一”线性关系的数据结构，这样的结构中只有一个根结点。线性结构条件： 1）有且只有一个根结点； 2）每一个结点最多有一个前件，也最多有一个后件。 3）在一个线性结构中插入或删除任何一个结点后还应该是线性结构。(2)非线性结构：指的是数据元素之间存在着“一对多”非线性关系的数据结构，这样的结构中可能有一个根结点，也可能有多个根结点。注意：线性结构包括：线性表、堆栈、队列、线性列表和串。 非线性结构包括：树、二叉树、图（或网络）和广义表。三、分别详解讲解图示：1. 线性表(1)线性表的基本概念： 线性表是最简单、最常用的一种数据结构。 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。注意：通常以下列 n 个数据元素的序列”表示线性表 ： (a1,a2 ,.,ai ,.,an) 序列中数据元素的个数 n 定义为线性表的表长；n=0 时的线性表被称为空表。称 i 为ai在线性表中的位序。(2):线性表的顺序存储结构：线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，即以“存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址。 注意：线性表的顺序存储结构具有以下两个基本特点： 1）线性表中所有元素的所占的存储空间是连续的； 2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 (3):线性表的插入和删除运算：插入运算是指在线性表的某个指定位置增加一个新结点。一般情况下，要在第i(1in)个元素之前插入一个新元素时，首先要从最后一个元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，然后将新元素插入到第i项。删除运算是指撤销结构中的某个结点。一般情况，要删除第i(1in)个元素，要从第i+1个元素开始，直到第n个元素，共n-i个元素依次向前移动一个位置。(4):线性表的链式存储结构（线性链表）线性表的顺序存储结构具有简单、操作方便等优点。但在对其做插入或删除操作时，需要移动大量的元素。而在线性链表中进行插入与删除，不需要移动链表中的元素。因此，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是通常采用链式存储结构。在链式存储结构中。存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。在链式存储方式中，要求每个结点由两部分组成：一部分用以存放数据元素值，称为数据域。另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件和后件）单链表：在链表中，每个结点只有一个指针域单链表中每个结点的存储地址是存在其前件结点指针域中，而开始结点无前件，故应设头指针HRAD指向开始结点。同时，由于终端无后件，故终端结点的指针域为空，即NULL单链表的插入与删除运算循环链表：首尾相接的链表。双向链表：在单链表中的结点中增加一个指针域指向它的前件，这样的链表，就称为双向链表（一个结点中含有两个指针）2.栈（1）：定义 栈（Stack）是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）。栈的插入操作通常称为入栈（push），而栈的删除操作则称为出栈或退栈（pop）。当栈中无数据元素时，称为空栈。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。（2）栈的基本运算A：插入元素称为入栈运算；B：删除元素称为退栈运算；C：读栈顶元素是将栈顶元素赋给一个指定的变量，这个运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。 （3）栈也是线性表，也有顺序存储和链式存储。3.队列(1):定义：队列是一种先进先出的线性表，它只允许在表的一端插入元素(队尾)，在另一端删除元素(队头)。通常定义头指针front指向队头元素的前一个位置，定义尾指针rear指向队尾元素的位置。队列是一种先进先出的数据结构。向队尾插入一个元素的操作称为入队，从队头删除一个元素的操作称为退队。(2):循环队列：循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，因此它仍然是线性结构。注意：队列也是一种线性表，也有顺序存储和链式存储。4、树(1)定义：是一种简单的非线性结构，直观地来看，树是以分支关系定义的层次结构。由于它呈现与自然界的树相类似的结构形式，所以称它为树。(2)在树的图形表示中，一般认为在用直线连起来的两端结点中，上端结点是前件，下端结点是后件。(3)树的相关术语：在树结构中，每一个结点只有一个前件，称为父结点；没有前件的结点只有一个，称为树的根结点，简称树的根。如：上图中结点A是树的根结点。在树结构中，每一个结点可以有多个后件，称为该结点的子结点；没有后件的结点称为叶子结点。如：上图中的结点K、L、F、G、M、I、J均为叶子结点。在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。如：上图中根结点A和结点D的度为3，结点B和E的度为2，结点C和H的度为1，结点K、L、F、G、M、I、J的度为0，所以该树的度为3；定义一棵树的根结点所在的层次为1，其他结点所在的层次等于它的父结点所在的层次加1。树的最大层次称为树的深度。 如：上图中，根结点A在第一层，结点B、C、D在第二层，结点E、F、G、H、I、J在第三层，结点K、L、M在第四层，所以该树的深度为4.在树中，以某结点的一个子结点为根构成的树称为该结点的一颗子树。叶子结点没有子树。如：上图中，结点A有三颗子树，它们分别以B、C、D为根结点。5、二叉树因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。二叉树一种特殊的树型结构。具有以下两个特点：A：非空二叉树只有一个根结点；B：每一个结点最多有两颗子树，且分别称为该结点的左子树和右子树，且次序不能颠倒。即在二叉树中，不存在度大于2的结点。(1)定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两颗互不相干的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树或空的右子树。注意：(2)性质：二级-公共基础树和查找排序.ppt四历年真题第二章 程序设计基础一、程序设计风格 “清晰第一，效率第二”已成为当今主导的程序设计风格。二、结构化的程序设计1提出：20世纪70年代提提出了“结构化程序设计”的思想和方法。2原则：自顶向下、逐步求精、模块化和限制使用goto语句。自顶向下:程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求细节，先从最上层总目标开始设计，逐步使问题具体化。逐步求精:对复杂的问题，应设计一些子目标过渡，逐步细化。模块化:一个复杂问题肯定是有若干简单问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，每个小目标成为一个模块。严格限制GOTO语句的使用。注意：结构化程序结构仅由顺序、选择、循环三种基本控制结构复合而成。三、面向对象程序设计1、面向对象方法的基本概念（1）对象：是由数据和容许的操作组成的封装体。在面向对象程序设计中，对象是程序的基本单位。对象可以表示客观世界中的任何实体，是对问题域中某个实体的抽象。每个对象可以用它本身的一组属性和它可以执行的一组操作来定义。对象的基本特征（特点）：标识惟一性、分类性、多态性、封装性、模块独立性。（2）类：是具有共同属性、共同方法的对象的集合。（3）消息：是实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息。它统一了数据流和控制流。注意：一个消息由三部分组成：接收消息的对象的名称、消息标识符（消息名）和零个或多个参数。（4）继承：是指能够直接获得已有的性质和特征而不必重复定义它们。继承是对象方法的一个重要特征。注意：继承分为单继承和多重继承。单继承是指一个类只允许有一个父类。多重继承是指一个类允许有多个父类。（5）多态性：对象根据所接受的信息而做出的动作，同样的消息被不同的对象接受时可导致完全不同的行为，该现象称为多态性。2面向对象程序设计的特点稳定性好可重用性好按照人的思维方式对客观世界进行抽象易于开发大型软件可维护性好四、程序设计基础历年考题第三章 软件工程基础一软件工程基本概念1.软件：指的是计算机系统中与硬件相互依存的另一部分，包括程序、数据和相关文档的完整集合。2.软件的特点： （1）软件是一种逻辑实体，而不是物理实体，具有抽象性；（2）软件的生产与硬件不同，它没有明显的制作过程；（3）软件在运行、使用期间不存在磨损、老化问题；（4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；（5）软件复杂性高，成本昂贵；（6）软件开发涉及诸多的社会因素。3.软件的分类根据应用目标的不同，软件可分应用软件、系统软件和支撑软件（或工具软件）。（1）应用软件：它是在特定领域内开发，为特定目的服务的一类软件。（2）系统软件：它能与计算机硬件紧密配合在一起，使计算机系统各个部分、相关的软件和数据协调、高效的工作的软件。例如：操作系统、数据库管理系统。（3）支撑软件：它是协调用户开发软件的工具性软件，其中包括开发软件。4软件工程：软件工程是指应用计算机科学、数学及管理科学等原理，以工程化的原则和方法来解决软件问题的工程。5.软件工程目的：提高软件生产率、提高软件质量、降低软件成本。6.软件危机：早期的软件主要指程序，采用个体工作方式，缺少相关文档，质量低，维护困难，这些问题称为“软件危机”所以软件危机主要表现在成本、质量、生产率三个方面。7.软件工程研究的主要包括软件开发技术和软件工程管理两个方面。(1）软件开发技术：主要有软件开发方法学、开发过程、软件工具、软件工程环境，其主体内容是软件开发方法学。(2）软件工程管理：主要有软件管理、软件工程经济学、软件心理学。8.软件工程的主要思想：将工程化原则运用到软件开发过程，它包括3个要素：方法、工具和过程。（1）方法是完成软件工程项目的技术手段；（2）工具是支持软件的开发、管理、文档生成；（3）过程支持软件开发的各个环节的控制、管理。9.软件生命周期（1）概念：将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期（如下图）（1）软件定义阶段：包括制定计划和需求分析。制定计划：确定总目标；可行性研究；探讨解决方案；制定开发可行性研究与计划制定、需求分析、软件设计、软件实施、软件测试及运行与维护。计划。需求分析：对待开发软件提出的需求进行分析并给出详细的定义。可用到的工具有：数据流图（DFD）软件设计：分为概要设计和详细设计两个部分。软件实现：把软件设计转换成计算机可以接受的程序代码。软件测试：在设计测试用例的基础上检验软件的各个组成部分。软件投入运行，并在使用中不断地维护，进行必要的扩充和删改。软件生命周期中所花费最多的阶段是软件运行维护阶段。注意：还可以将软件生命周期分为如上图所示的软件定义、软件开发及软件运行维护3个阶段。（2）.软件生命周期的主要活动阶段是：可行性研究与计划制定、需求分析、软件设计、软件实施、软件测试及运行与维护。（3）.软件工程三要素：方法：完成软件工程项目的技术手段工具：支持软件的开发、管理、文档生成过程：支持软件开发的各个环节的控制、管理二结构化设计方法1.结构化设计方法： 结构化设计方法的基本思想是将软件设计成由独立、单一功能的模块组成结构。2.软件设计的基础：（1）从技术观点上看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。（2）从工程管理角度来看，软件设计分两步完成：概要设计和详细设计。3.软件设计的基本原理：（1）抽象：软件设计中考虑模块化解决方案时，可以定出多个抽象级别。抽象的层次从概要设计到详细设计逐步降低。（2）模块化：模块是指把一个待开发的软件分解成若干小的简单的部分。模块化是指解决一个复杂问题时自顶向下逐层把软件系统划分成若干模块的过程。（3）信息隐蔽：信息隐蔽是指在一个模块内包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问的。（4）模块独立性：模块独立性是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。注意：模块的独立程度是评价设计好坏的重要度量标准。衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准。内聚性模块内部各个元素之间彼此结合的紧密程度的度量。 一个模块只做一件事。7种类型。耦合性模块间互相连接的紧密程序的度量 取决于接口的复杂程度、调用方式、哪些信息通过接口模块连接方式有7种，构成耦合性的7种类型 注意：一般较优秀的软件设计，应尽量做到高内聚， 低耦合4.结构化分析的常用工具：（1）数据流图（DFD）；（2）数据字典（DD）；（3）判定树；(4）判定表。（1）数据流图：数据流图以图形的方式描绘数据在系统中流动和处理的过程，它反映了系统必须完成的逻辑功能，是结构化分析方法中用于表示系统逻辑模型的一种工具。画数据流图的基本步骤：自外向内，自顶向下，逐层细化，完善求精注意：在数据流表中，矩形表示数据的外部实体，圆角的矩形表示变换数据的逻辑处理，双横线表示数据的存储，箭头表示数据流。（2）数据字典：对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。注1：数据字典的作用是对数据流图中出现的被命名的图形元素的确切解释。注2：数据字典是结构化分析方法的核心。（3）判定树：从问题定义的文字描述中分清哪些是判定的条件、哪些是判定的结论，根据描述材料中的链接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定树。（4）判定表：与判定树类似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作时由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。5.软件需求规格说明书：软件需求规格说明书是需求分析阶段的最后成果，通过建立完整的信息描述、详细的功能和行为描述、性能需求和设计约束的说明、合适的验收标准，给出对目标软件的各种需求。注意：软件需求规格说明书是确保软件质量的措施，它的内涵是：正确性（必须保证）；无歧义性；完整性；可验证性；一致性；可理解性；可修改性；可追踪性。6. 详细设计（1）概念：详细设计的任务是为软件结构图中的每个模块确定实现算法和局部数据结构，用某种选定的表达表示工具算法和数据结构的细节。（2）详细过程设计的常用工具有：图形工具：程序流程图，N-S，PAD，HIPO表格工具：判定表。语言工具：PDL（伪码）。程序流程图：（1）程序流程图的5种控制结构：顺序型、选择型、先判断重复型、后判断重复型和多分支选择型。（2）图形元素：（1）方框：处理步骤（2）菱形：逻辑条件（3）箭头：控制流：（3）椭圆：表示事实描述。N-S图PAD图PDL ：过程设计语言（PDL）也称为结构化的语言和伪码，它是一种混合语言，采用英语的词汇和结构化程序设计语言，类似编程语言。注意：复习教材（知识点必须记）三、软件测试1.意义目的：（1）为了发现错误。（2）希望能以最少的人力和时间发现潜在的各种错误和缺陷。（3）保证系统质量和可靠性的关键步骤。2.静态测试与动态测试（1）静态测试：人工评审软件文档或程序，借以发现其中的错误，由于评审的文档或程序不必运行所以称为静态测试。主要方法：代码检查、静态结构分析、代码质量度量（2）动态测试：通过运行软件来检验软件中的动态行为和运行结果的正确性。分两类：白盒和黑盒测试方法。1.白盒测试-结构测试或逻辑驱动测试将软件看成透明的白盒，根据程序的内部结构和逻辑结构来设计测试例子，对程序的路径和过程进行测试，检查是否满足设计的要求主要方法：逻辑覆盖、基本路径测试2. 黑盒测试功功能测试或数据驱动测试将软件看成黑盒子，在完全考虑软件内部结构和特性的情况下，测试软件的外部特性。主要方法：等价类划分法；边界值分析法；错误推测法3.软件测试的实施：软件测试过程分4个步骤，即单元测试、集成测试、确认测试和系统测试。四、软件调试1.软件调试的任务是诊断和改正程序中的错误而软件测试是尽可能多地发现软件中的错误。背：软件测试的目的是发现错误，软件调试的目的是更正错误。2. 程序调试的基本步骤(1)错误定位；(2)修改设计和代码，以排除错误；(3)进行回归测试，防止引入新的错误。调试原则(1)确定错误的性质和位置的原则；(2)修改错误的原则；3. 软件调试的方法(1)强行排错法；(2)回溯法排错；(3)归纳法排错；(4)演绎法排错五、历年真题第四章 数据库设计基础一、基本概念1.数据：实际上就是描述事物的符号记录。分为临时性数据和永久性数据。软件中的数据是有一定结构的。2.数据库：存储在计算机内，大量的、有组织、可共享的数据的集合。数据库最大的特点是：有结构、可共享、冗余度低。3.数据库管理系统：它是一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。是数据库系统的核心。其具体功能如下：A:数据模式定义B:数据存取的物理构建C:数据操纵D:数据的完整性、安全性定义与检查E:数据的并发控制与故障恢复F:数据的服务4.数据库管理员：对数据库进行规划、设计、维护、监视的专门人员，主要工作如下：A:数据库设计B:数据库维护C:改善系统性能，提高系统效率5.数据库系统：6.数据库系统的特点数据的集成性 采用统一的结构方式表示 按照多个应用的需要组织全局的统一的数据结构 数据库系统中的数据模式是多个应用共同的、全局的数据结构，每个应用的数据则是全局结构中的一部分，这种全局与局部结构模式构成了数据库系统的集成性的主要特征数据的高共享性与低冗余 数据库中的数据是面向全局的，提高了数据的共享性，降低了数据冗余，避免了可能出现的数据不一致现象数据独立性A:物理独立性：数据的逻辑结构与数据的存储结构以及存取方法无关。B:逻辑独立性数据的逻辑结构的改变不会影响应用程序对数据的使用数据统一管理与控制A:数据的完整性检查：检查数据库中数据的正确性以及保证数据的正确性。B:数据的安全性保护检查数据库访问者以防止非法访问C:并发控制控制多个应用的并发访问所产生的相互干扰以保证其正确性。7.数据库管理技术的发展人工阶段文件系统阶段数据库系统阶段8.数据库应用系统：利用数据库系统进行应用开发。数据库应用系统中的核心问题是：数据库设计。9.数据库系统的内部结构体系：三级模式两级映射三级模式概念模式：也称为模式，对数据库系统中全局数据逻辑结构的描述。外模式：也称为子模式或用户模式，是对用户所