计算机二级公共知识要点

《计算机二级公共知识要点》由会员分享，可在线阅读，更多相关《计算机二级公共知识要点（10页珍藏版）》请在装配图网上搜索。

1、文档供参考，可复制、编制，期待您的好评与关注！ 二级公共知识要点数据结构与算法所谓算法是指解题方案的准确而完整的描述。算法的基本特性：1、 可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。2、 确定性：算法中每一条指令都必须有确切的含义，不产生二义性。3、 有穷性：一个算法必须总是在执行有穷步骤之后结束。4、 拥有足够的情报：有足够的输入。算法的基本要素：一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二算法的控制结构。算法的时间复杂度：所谓算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，

2、而算法所执行的基本运算次数是问题规模的函数，即：算法的工作量=f（n），其中n 是问题的规模。例： 采用顺序搜索法，在长度为n 的一维数组中查找值为x的元素。即从数组的第一个元素开始，逐个与被查值x 进行了比较。基本运算为x 与数组元素的比较。最好的情况，第一个元素便是要找的元素，那么只要做一次比较；最坏的情况，这个一维数组中没有值为x 的元素，那么得进行n 次比较，所以这个算法的时间复杂度为n 的函数，即 O（n）。算法的空间复杂度：一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要

3、的额外的空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果说额外空间量相对于问题规模来说是常数，则称该算法是原地（in place）工作的。数据结构是指相互有关联的数据元素的集合。如表，树，图等的数据结构。数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。Data_Structure=(D,R)其中，D 是数据元素的集合，R是数据元素之间的关系。数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。数据结构的图形表示：例：一年四季的数据结构可以用如下的图形表示：春秋冬夏例：家庭成员间辈分关系的数据结

4、构可以用如下图形表示：父亲儿子女儿线性结构与非线性结构：如一个非空的数据结构满足下列两个条件：1、 有且只有一个根结点；2、 每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。如果一个数据结构不是线性结构，则称之为非线性结构。线性表：线性表由一组数据元素构成。数据元素的含义很广泛，在不同的具体情况下，它可以有不同的含义。例如：一个n 维向量（x1,x2,x3,xn）是一个长度为n 线性表，其中的每一个分量就是一个数据元素。又如，英文小写字母表（a,b,c,z）是一个长度为26的线性表，其中的每一个小写字母就是一个数据元素。线性表的顺序存储：线性表顺序存储

5、结构具有以下两个基本特点：1、 线性表中所有元素所占的存储空间是连续的；2、 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。顺序表的插入运算：顺序表的删除运算：栈是限定在一端进行插入与删除的线性表。“先进后出”，或者“后进先出”。与一般的线性表一样，在程序设计语言中，用一维数组S(1：n)作为栈的顺序存储空间，其中n 为栈的最大容量。通常指针指向栈空间的低地址一端（即数组的始地址这一端）。栈的基本运算有三种：入栈，出栈，读栈顶元素。入栈：入栈运算是指在栈顶位置插入一个新元素。这个运算有两

6、个基本操作：首先将栈顶指针进一（即top加1），然后将新元素插入到栈顶指针指向的位置。出栈：出栈运算是指取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作：首先将栈顶元素（栈顶指针指向的元素）赋给一指定变量，然后将栈顶指针退一（即top 减1）。当栈顶指针top为0时，说明栈空。读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。必须注意，这个运算不删除栈顶元素，只是将它的值赋给一个变量。队列是指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为队尾指针（rear）的指针指向队尾元素，允许删除的一端称为队头，通常用一个称为队头指针（front）来指

7、向队头元素。往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。线性表的链式存储结构称为线性链表。数据域 指针域Datalink线性链表的逻辑结构：Data1linkData2linkData3link线性链表的插入运算：线性链表的删除运算：双向链表：有两个指针，一是指向后件，一是指向前件。树是一种简单的非线性结构。在这种数据结构里，所有的数据元素之间的关系具有明显的层次性。如图：DHABCEFIJG在树的结构中，第一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为根。每个结点可以有多个后件，它们都称为该结点的子结点。ahijbcdefg二

8、叉树：二叉树具有如下的特点：1、 非空二叉树只有一个根结点；2、 每一个结点最多有两个子树，且分别称为该结点的左子树和右子树。由此可以看出，在二叉树中，每一个结点的度最大为2。二叉树的基本性质：性质1 在二叉树第K层上最多有2K-1（K=1）个结点。性质2 深度为M的二叉树最多有2M1个结点。性质3 在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。性质4 具有N个结点的二叉树，其深度到至少为log2N+1,其中log2N表示取log2N的整数部分。完全二叉树，满二叉树。二叉树的遍历：1、 前序遍历：根左右2、 中序遍历：左根右3、 后序遍历：左右根顺序查找：从线性表的第

9、一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找到元素（即查找失败）。二分法查找：二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻两个元素相等）。设有序线性表的长度为n ，被查元素为x ，则对分查找的方法如下：将x 与线性表的中间项进行比较：若中间项的值等于x ，则说明查找成功，查找结束；若x 小于中间项的值，则在线性表的前半部分（即中前项以前的部分）以相同的方法进行查找；若x 大于中间项的值，则在线性表的后半部分（即中间

10、项以后的部分）以相同的方法进行查找。这个过程一直进行到查找到成功或者子表长度为0（说明线性表里没有这个元素）为止。显然，当这个有序线性表为顺序存储时才能采用二分查找，并且， 二分查找的效率要比顺序查找高得多。10 / 10交换类排序法冒泡排序法：快速排序法：插入类排序法简单插入排序法：希尔排序法：选择类排序法简单选择排序：堆排序法：程序设计基础结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto 语句。面向对象程序设计中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。属性即对象所包含的信

11、息，它在设计对象时确定，一般只能通过执行对象的操作来改变。继承是面向对象的方法的一个主要特征。继承是使用已有的类定义作为基础建立新类的定义技术。广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。多态性：对根据所接受的消息而做出动作，同样的消息被不同的对象接受可导致完全不同的行动，该现象称为多态性。软件工程软件工程学科是一门指导计算机软件开发和维护的工程学科。软件工程是一类求解软件的工程。它应用计算机科学、数学及管理科学等原理，借鉴传统工程的原则、方法，创建软件以达到提高质量，降低成本的目的。其中，计算机科学、数学用于构造模型与算法，工程科学用于制定规范设计范型、评估成本及确定

12、权衡，管理科学用于计划、资源、质量、成本等管理。软件工程的方法、工具、过程构成了软件工程的三要素。软件生命周期：通常将软件产品从提出，实现，使用维护到停止，使用退役的过程称为软件生命周期。一般包括可行性研究与需求分析，设计，实现，测试交付使用以及维护等活动。软件开发工具：软件开发环境：软件开发环境是全面支持软件开发全过程的软件工具集合。计算机辅助软件工程（CASE, Computer Aided Software Engineering）是当前软件开发环境中富有特色的研究工作和发展方向。需求分析方法：结构化析方法，主要包括：面向数据流的结构化分析方法（SAStructured analysis

13、），面向数据结构的Jackson方法（JSDJackson system development method），面向数据结构的结构化数据系统开发方法（DSSDData structured system development method）。面向对象分析方法（OOAObjectOriented method）。结构化分析方法的实质是着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。数据流图（DFDData Flow Diagram）数据流图从数据传递和加工的角度,来刻画数据流从输入到输出的移动变换过程.数据字典（DDData Dict

14、ionary）数据字典是结构化分析方法的核心。数据字典是对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。概括地说，数据字典的作用是对DFD中出现的被命名的图形元素的确切解释。软件需求规格说明书是需求分析阶段的最后成果，是软件开发中的重要文档之一。软件需求规格说明书的作用：1、 便于用户、开发人员进行理解和交流。2、 反映出用户问题的结构，可以作为软件开发工作的基础和依据。3、 作为确认测试和验收的依据。模块的独立性：每一个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。模块的独立

15、程度是评价软件设计好坏的重要标准。衡量软件的模块独立使用耦合性和内聚性两个定性的度量标准。1、 内聚性：模块内部各个元素彼此结合的紧密程度的度量。常见的内聚：（1）偶然内聚 （2）逻辑内聚（3）时间内聚 （4）过程内聚（5）通信内聚 （6）顺序内聚（7）功能内聚。2、耦合性：软件结构中各个模块之间相互关联程度的度量。常见的耦合：（1）非直接耦合 （2）数据耦合 （3）标记耦合 （4）控制耦合 （5）公共耦合 （6）内容耦合设计原则：尽量使用数据耦合，少用控制耦合，限制公共耦合的范围，避免使用内容耦合。低耦合，高内聚。结构化设计就是采用最佳的可能方法设计系统的各个组成部分以及各部分之间的内部联系

16、的技术。结构化设计方法的基本思想是将软件设计成由相对独立，单一功能的模块组成的结构。常见的过程设计工具有：图形工具：程序流程图，NS，PAD，HIPO；表格工具：判定表；语言工具：PDL（伪码）。软件测试的方法：若从是否需要执行被测试软件的角度的，可以分为静态测试和动态测试方法。若按照功能划分可以分为白盒测试和黑盒测试方法。白盒测试法：也称为结构测试或逻辑驱动测试。它是根据软件产品的内部工作过程，检查内成分，以确认每种内部操作符合设计规格要求。白盒测试把测试对象看作一个打开的盒子，允许测试人员利用程序内部的逻辑结构及有关信息来设计或选择测试用例，对程序所有的逻辑路径进行测试。白盒测试是在程序内

17、部进行，主要用于完成软件内部操作的验证。白盒测试的主要方法有逻辑覆盖，基本路径测试等。黑盒测试法：也称为功能测试或数据驱动测试。黑盒测试是对软件已经实现的功能是否满足需求进行测试和验证。黑盒测试完全不考虑程序内部的逻辑结构和内部特性，只依据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明。所以黑盒测试是在软件接口处进行，完成功能验证。黑盒测试方法主要有等价类划分法，边界值分析法，错误推测法，因果图等。主要用于软件确认测试。软件测试过程一般按四个步骤进行，即单元测试，集成测试，验收测试（确认测试）和系统测试。单元测试：是对软件设计的最小单位模块（程序单元）进行正确性检验的测试。单元测

18、试的目的是发现各模块内部可能存在的各种错误。单元测试的主要依据是详细设计说明书和源程序。单元测试的技术可以采用静态分析和动态测试。对动态高度通常以白盒动态测试为主，辅之以黑盒测试。集成测试：是高度和组装软件的过程。它是指把模块在按照设计要求组装起来的同进进行测试，主要目的是发现与接口有关的错误。集成测试的依据是概要设计说明书。集成测试所涉及的内容包括：软件单元的接口测试，全局数据结构测试，边界条件和非法输入的测试等。集成测试时将模块组装成程序通常采用两种方式：非增量方式组装与增量方式组装。确认测试：它的任务是验证软件的功能和性能及其他特性是否满足了需求规格说明中确定的各种需求，以及软件配置是否

19、完全，正确。系统测试：是将通过测试确认的软件，作为整个基于计算机系统的一个元素，与计算机硬件，外设，支持软件，数据和人员等其他系统元素组合在一起，在实际运行（使用）环境下对计算机系统进行一系列的集成测试和确认测试。程序的调试：程序的调试的任务是诊断和改正程序中的错误。它与软件测试不同，软件测试是尽可能多地发现软件中的错误。程序调试活动由两部分组成，其一是根据错误的迹象确定程序中错误的确切性质，原因和位置。其二，对程序进行修改，排除这个错误。程序调试的方法：静态调试和动态调试。数据库数据库：（Database，DB）是数据的集合，它具有统一的结构形式并有存放于统一的存储介质内，是多种应用数据的集

20、成，并可被各个应用程序所共享。数据库管理系统：（DBMS，Database Management System）是数据库的机构，它是一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。是指数据库系统中对数据进行管理的软件系统，它是数据库系统的核心组成部分。数据库系统：（DBS，Database System）由如下的几个部分组成：数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台、软件平台。这五个部分构成了一个发数据库为核心的完整的运行实体，称为数据库系统。数据独立性：物理独立性 逻辑独立性数据库系统的体系结构是数据库系统的一个总的框架。尽管实

21、际的数据库系统软件产品多种多样，它们支持不同的数据模型，使用不同的数据库语言，建立在不同的操作系统之上，数据的存储结构也各不相同，但是绝大多数数据库系统在总的体系结构上都具有三级模式的结构特征。数据库系统的三级模式结构是对数据的三个抽象级别，它把数据的具体组织留给DBMS管理，使用户能逻辑地抽象地处理数据，而不必关心数据在计算机中的表示和存储。这三级模式结构由外模式、模式、内模式组成，具体如图 1模式：亦称为逻辑模式，是数据库中全体数据的逻辑结构和特性的描述，是所有用户的公共数据视图。 2外模式：亦称子模式或用户模式，是数据库用户看到的数据视图，它是与某一应用有关的数据的逻辑表示。3. 内模式

22、：亦称存储模式，是全体数据库数据的内部表示或者低层描述，用来定义数据的存储方式和物理结构。 数据模型：(data model)表示实体类型及实体间联系的模型称为“数据模型”。目前广泛使用的数据模型可分为两个层次。第一层数据模型是独立于计算机系统的模型，称为“概念数据模型”；第二层数据模型是依赖于计算机系统的模型，称为“结构数据模型”。概念数据模型通常是用实体-联系模型(简称E-R图)来描述的。设计ER图的方法称为ER方法,下面通过设计ER图的过程来了解基本的ER方法。ER图是直观表示概念模型的工具。 在ER图中有四个基本成分：1矩形框：表示实体类型(考虑问题的对象)。2菱形框：表示联系类型(实体间的联系)。3椭圆形框：表示实体类型和联系类型的属性。相应的命名均记入各种框中。对于键码的属性，在属性名下划一横线。4直线：联系类型与其涉及的实体类型之间以直线连接，并在直线端部标上联系的种类(1：1，1：N，M：N)。