全国计算机等级考试培训教材（二级C）课件 ch01 公共基础知识

计算机等级考试第一章公共基础知识高等院校公共课系列精品教材数据结构与算法01ONE1.1数据结构与算法01考点1算法1.算法定义算法是指对解题方案准确而完整的描述。算法不等于数学上的计算方法，也不等于程序。2.算法的特征算法的特征有4个：可行性、确定性、有穷性、拥有足够的情报。（1）可行性：在算法的执行过程中，每一个步骤都要可行、可通。经过执行能够得到一个结果。（2）确定性：算法中的每一个步骤都要有确切的含义，不能有二义性，对于相同的输入必须能得出相同的执行结果。（3）有穷性：一个算法包含的操优步骤是有限的。也就是说，在执行若干个操作步骤之后算法结束，而且每一个步骤都要在合理的时间内完成。（4）拥有足够的情报：即拥有足够的输入数据。通过大量的算法输入数据来验证算法输出的结果是否有误。1.1数据结构与算法3.算法复杂度（1）算法的复杂度是指运行该算法所需要的计算机资源的多少，所需的资源越多，该算法的复杂度越高：反之，所需资源越少，复东度越低。也就是说，算法的复杂度是对算法中的各种方法进行衡量的标准。（2）算法的复杂度有两种：算法的时间复杂度和算法的空问复杂度。①算法的时间复杂度：执行算法所需要的（计算工作量）基本运算次数。②算法的空间复杂度：执行算法所需要的内存空问。【注意】算法时间复杂度的好与坏不会影响空问复杂度的好与坏。01考点1算法1.1数据结构与算法01考点2数据结构1.数据的逻辑结构(1）数据结构定义数据结构主要研充和讨论了个方面的内容：逻辑结构、存储结构和运算。逻辑结构讨论的是现实世界中数据与数据之间的关系：存储结构也称物理结构，指的是逻辑结构在计算机存储空问的存放形式。(2）数据的逻辑结构满足逻辑结构的的条件：①表示数据元素的信息；②表示各数据元素之问的前后件关系。逻辑结构的分类：线性结构、非线性结构。①线性结构：有且只有一个根节点：每一个节点最多有一个前件，也最多有一个后件。在二级公共基础中，线性结构主要讲到的有：线性表、栈、队列。②非线性结构：不满足线性结构条件的就属于非线性结构。在二级公共基础中，非线性结构主要讲到的有：树、二叉树。1.1数据结构与算法01考点2数据结构2．数据的存储结构(1）概念：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。(2）数据的逻辑结构在计算机存储空间中的存储形式通常有两种：顺序存储结构、链式存储结构。①顺序存储结构：数据在存储空间中必须连续，且元素之问一定要有前后件的关系。②链式存储结构：数据在存储空问中不一定连续，且各元素的存储顺序是任意的。(3）两种存储结构的优缺点如下。①顺序存储结构：优点是查找方便；缺点是插入、刪除不方便。②链式存储结构：优点是插入、删除方便；缺点是查找不方便。1.1数据结构与算法01考点3线性表及顺序存储结构(1）一个非空的数据结构如果满足以下两个条件：有且只有一个根节点；每一个节点最多有一个前件，也最多有一个后件，那么该数据结构称为线性结构，也称为线性表。(2）线性表往计算机中进行存放，不仅可以采用顺序存储结构存放，还可以采用链式存储结构存放。①顺序表：线性表采用顺序存储结构存放。②线性链表：线性表采用链式存储结构存放。(3）顺序表和线性链表的特点如下。①顺序表：随机（访问〉存取、查找方便，插入、删除不方便，事先估计存储空间。②线性链表：顺序（访问）存取、插入、刪除方便，查找不方便，不必事先估计存储空间。1.1数据结构与算法01考点4栈和队列1.栈(1）栈是一种特殊的线性表，其特殊性是插入与删除运算都只在线性表的一端进行。即栈的一个考点：入栈和退栈都是在一端（栈顶）进行的。(2）栈在计算机中进行存储时通常采用的存储方式有顺序存储结构、链式存储结构。(3）栈的原则是先进后出、后进先出。2.队列(1）队列是一个允许在一端进行插入，而在另一端进行删除的线性表。即队列的一个考点：队列的入队运算是在队尾进行的，而退队运算是在队头进行的。(2）队列在计算机中进行存储时通常买用的存储方式有顺序存储结构、链式存储结构。(3）队列的原则是先进先出、后进后出。(4）循环队列是队列在计算机存储空间中采用顺序存储结构进行存储的一种形式。1.1数据结构与算法01考点4栈和队列3.循环队列循环队列是队列的一种顺序存储结构，用队尾指针rear指向队列中的队尾元素，用排头指针指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。1.1数据结构与算法01考点5树与二叉树(1）树是一种简单的非线性结构。在树中，所有数据元素之间的关系具有明显的层次特性。树的根书点可以没有或有一个。(2）二叉树的性质如下。性质1：在二叉树的第上层上至多有2k-1个节点(k≥1）。性质2：深度为四的二叉树至多有2m-1个节点。性质3：对任何一棵二叉树，度为0的节点(即叶子节点)总是比度为2的节点多一个。性质4：具有n个节点的完全二叉树的深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。（3）二叉树的特殊情记：满二叉树、完全二叉树。满二叉树：每一层的节点都达到了最多。完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点。完全二叉树中的度为1的节点个数为1或0。满二叉树也是完全二叉树，反之，完全二叉树不一定是满二叉树。性质5：具有n个节点的完全二叉树深度为[log2n]+1或[log2(n+1)]。1.1数据结构与算法01考点5树与二叉树2.二叉树的遍历方法二叉树遍历可以分为3种：前序遍历（访问根节点在访问左子树和访问右子树之前）、中序遍历(访问根节点在访问左子树和访问右子树两者之间)、后序遍历(访问根节点在访问左子树和访问右子树之后)。前序遍厉（先序遍厉）在不重复访问二叉树时，先访问根节点，再访问左子树，最后访问右子树。并且，在访问左子树和右子树时仍先访问根节点，再访问左子树，最后访问右子树。(2)中序遍厉在不重复访问二叉树时，先访问左子树，再访问根节点，最后访问右子树。并且，在访问左子树和右子树时仍先访问左子树，再访问根节点，最后访问右子树。(3)后序遍历在不重复访问二叉树时，先访问左子树，再访问右子树，最后访问根节点。并且，在访问左子树和右子树时仍先访问左子树，再访问右子树，最后访问根节点。1.1数据结构与算法01考点6查找技术查找的方法有两种：顺序查找、二分法查找（对分查找)。①顺序查找：顺序查找在最坏的情况下需要比较n次，即时间复杂度为n。②二分法查找（对分查找)：二分法查找在最坏的情况下需要比较log2n次，即时间复杂度为log2n。注意：只有在顺序存储，并且是有序表的情况下才可以进行二分法查找。1.1数据结构与算法01考点7排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。常见排序的比较次数如下。①交换类：冒泡排序法：n(n-1)/2；快速排序法：最坏情况下也比较n(n-1）/2次。②插入类：简单插入排序法：n(n-1)/2；希尔排序法：O(n1.5)。③选择类：简单选择排序法：n(n-1)/2；堆排序法：O(nlog2n）。程序设计基础02TWO1.2程序设计基础01考点8程序设计方法与风格考点9结构化程序设计(1）程序设计的风格注重的是清晰第一、效率第二。(2）要使程序的清晰达到最好，我们在程序设计的过程中将源程序文档化。①符号名的命名应具有一定的实际含义，以便于读者理解。②程序中的注释要尽量多，程序中的注释又分为序言性注释、功能性注释。③视觉组织要合理。(1）结构化程序设计的基本结构有3种：顺序结构、选择结构、循环结构。(2）结构化程序设计的基本原则有4种：自顶向下、逐步求精、模块化、限制使用语句。1.2程序设计基础01考点10面向对象的程序设计(1）对象：客观世界中任何的实体称为对象。对象的特点：标识唯一性、分类性、多态性、封装性、模块独立性。(2）类：具有共同属性、共同方法的对象的集合，即类是从对象抽象出来的。(3）实例：类中的实例称为对象；对象是类的实例。(4）消息：对象间传递信息的手段。(5）继承：类之间共享属性和操作的机制。继承的优点是可以提高软件的可重用性。(6）总结：类具有封装性，模块具有独立性，信息具有隐蔽性，继承具有传递性。软件工程基础03THREE1.3软件工程基础01考点11软件工程的基本概念1.软件(1）软件是包括程序、数据及其相关文档的完整集合。（2）软件按功能分为应用软件、系统软件、支撑软件（工具软件）。2.软件工程(1）定义：软件工程是指应用计算机科学、数学及管理科学等原理、采用工程化原则和方法开发软件系统。它不仅可以解决软件开发中的技术问题，还可以解决软件项目的管理问题和软件产品的生产率问题。(2）3个要素：方法、工具和过程。(3）核心思想：尽可能多地使用工程科学的原理来指导工作。(4）达到目标，要研究的内容：软件开发技术、软件工程管理。(5）原则：抽象、信息隐薇、模块化、局部化等。(6）软件开发环境：软件工具的集合。1.3软件工程基础01考点11软件工程的基本概念3.软件生命周期（1）软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。软件生命周期分为以下3个阶段。①定义阶段：提出、分析和定义。②开发阶段：编码、测试。③维护阶段：维护软件的功能，对软件的功能进行增加和删改。此阶段最重要，而且所花费用也最高。1.3软件工程基础01考点12结构化分析方法需求分析任务：准确地确定软件系统必须做什么，确定软件系统必领具备哪些功能。阶段：①需求获取；②需求分析：③编写需求规格说明书；④需求评审。在需求分析中，分析方法可以分为结构化分析方法和面向对象的分析方法。结构化分析方法是常用的一种，其目的是帮助弄清用户对软件的需求。结构化分析方法中常使用的工具有4种：数据流图、数据字典、判定表、判定树。(1）数据流图（DFD)：图形中的箭头表示“数据流”。(2）数据字典(DD)：字典的作用是解释；也是结构化分析方法的核心。2．软件需求规格说明书软件需求规格说明书的作用如下。(1）便于用户、开发人员进行理解和交流。(2）反映出用户问题的结构，可以作为软件开发工作的基础和依据。(3）作为确认测试和验收的依据。(4）软件需求规格说明书的特点：无歧义性这一特点是其中最为重要的。1.3软件工程基础(1）按技术观点来分类：结构设计、数据设计、接口设计、过程设计。(2）按工程管理角度分类：概要设计、详细设计。①概要设计：将软件的功能进行分解。•概要设计的工具：结构图(SC)。•结构图中的箭头表示调用关系；深度表示控制的层数；宽度表示跨度主数目。②详细设计：确定每个模块的实现算法和局部数据结构。•详细设计的工具：程序流程图（PFD)、N-S、PAD、HIPO、判定表、PDL。•程序流程图中的箭头表示控制流。•N-S是用方框图来代替传统的程序流程图的。01考点13结构化设计方法1.3软件工程基础01考点13结构化设计方法(3）软件设计的《原则）原理：抽象、模块化、信息隐蔽、模块独立性。其中模块独立性这一原则非常重要，其考点是：模块要想尽可能独立，必须要遵循“高可聚、低耜合”的设计原则。模块的独立程度可以由两个定性标准度量：一个是男合性，日来衡量不同模块彼此问互相依赖（连接）的紧密程度：另一个是内聚性，用来衡量一个其块内部各个元素彼此结合的紧密程度。(4）数据流的类型有两类：变换型、事务型。1.3软件工程基础01考点14软件测试(1）软件测试的实施（过程）：单元测试、集成测试、确认测试(验收测试）、系统测试。①单元测试：目的是发现各模块内部可能存在的各种错误。②集成测试：目的是发现与接口有关的错误。③确认测试（验收测试）：测试是否满足需求分析。④系统测试：将软件系统与硬件系统、外设等其他部件结合到一起，对整个软件系统测试。1.3软件工程基础01考点14软件测试（2）软件测试的方法如下。按是否需要执行被测软件可以分为静态测试、动态测试。①静态测试：不由计算机执行程序代码，主要是通过人看出程序错误。②动态测试：有计算机执行程序进行测试，是基于计算机的测试。按照功能划分，可以分为白盒测试和黑盒测试。①白盒测试：内部结构的测试，又称为“路径测试”。白盒测试的方法包括：逻辑覆盖测试、基本路径测试等。②黑盒测试：外部接口的功能测试。黑盒测试的方法包括：等价类划分法、边界值分析法、错误推测法、因果图法等。1.3软件工程基础01考点15程序调试(1）程序调试的目的：改正错误。(2）程序调试的方法：强行排错法、回溯法、原因排除法。数据库设计基础04FOUR1.4数据库设计基础01考点16数据库系统的基本概念1.基本概念(1）数据库系统（DBS）的组成主要有数据库（DB)、数据库管理系统(DBMS)。①数据库(DB）：存储在计算机存储设备上的结构化的相关数据集合。②数据库管理系统(DBMS)：对数据库进行建立、使用和维护而配置的软件。其中数据库管理系统是数据库系统的核心。(2）数据库管理系统提供的数据语言：数据定义语言（DDL）、数据操纵语言(DML)、数据控制语言(DCL)。①数据定义语言（DDL)：负责数据的模式定义与数据的物理存储构建。②数据操纵语言（DML)：负责数据的操纵，包括查询及增、删、改等操作。③数据控制语言(DCL）：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能。1.4数据库设计基础01考点16数据库系统的基本概念2.数据管理的发展(1）数据管理发展至今己经历了3个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。(2)数据库系统的特点如下。①数据的共享性高。②数据的冗余性低。③数据的独立性高。其中的数据独立性是指数据与程序之间互不依赖。数据独立性叉分为物理独立性、逻辑独立性。3.数据库系统的体系结构(1）三级模式：外模式、概念模式、内模式。①外模式是用户可以见到的模式。也称子模式或用户模式。②内模式是和物理数据库打交道的，也称物理模式。(2）两级映射：概念模式→内模式、外模式→概念模式。1.4数据库设计基础01考点17数据模型1.E-R模型(1）E-R模型又称E-R图，由一些基本图形组成，图形有矩形、補圆、菱形。①矩形：表示实体。②椭圆：表示属性。③菱形：表示联系。(2）实体与实体之间的联系有了种：一对一、一对多、多对多。1.4数据库设计基础2.数据模型(1）数据库的数据模型分为层次、关系和网状3种。①用树形结构表示实体及其之间联系的模型称为层次模型，模型中节点是实体，树枝是联系，从上到下是一对多的关系。②用网状结构表示实体及其之间联系的模型称为网状模型，它是层次模型的扩展，表示多个从属关系的层次结构，呈现一种交叉关系。③关系模型的数据结构非常单一，在关系模型中，现实世界的实体以及实体问的各种联系