计算机二级级公共基础知识ppt课件.ppt

《计算机二级级公共基础知识ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算机二级级公共基础知识ppt课件.ppt（60页珍藏版）》请在三一办公上搜索。

1、计算机二级考试公共基础知识大纲,数据结构与算法 程序设计基础 软件工程基础 数据库设计基础,全国计算机等级考试二级公共基础知识不单独考试，与其他二级科目组合在一起，作为二级科目考核内容的一部分。考试方式:上机考试题型：选择题（ 注：10 道选择题，占 总分值的10%）,第一章 数据结构与算法(30%),考试大纲1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5

2、. 线性单链表、双向链表与循环链表的结构及其基本运算。6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。,算法的定义对解题方案准确而完整的描述称为算法。,算法是程序设计的核心,算法的基本概念,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法)，都是在实施某种算法。,例： n个数从大到小进行排序。 有多种排序方法 ，常用的有冒泡排序、选择排序等。,算法的基

3、本特征一个算法应该具有以下五个重要的特征：,有穷性 确定性 输入 输出 可行性,算法的两个基本要素：,基本运算和操作 算术运算 关系运算 逻辑运算 数据传输,控制结构 顺序 选择 循环,一是对数据对象的运算和操作； 二是算法的控制结构。,算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法,算法的复杂度 评价一个算法优劣的主要标准是算法的执行效率和存储需求： 时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量 空间复杂度：执行这个算法所需要的内存空间 算法在执行过程中临时占用的存储空间 时间复杂度它大致等于计算机执行一种简单

4、操作所需的平均时间与算法中进行简单操作的次数的乘积。 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分,计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。,数据结构,程序=算法+数据结构,数据结构是指相互有关联的数据元素的集合。 一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征

5、的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。,数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。,1. 数据的逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。,春,夏,秋,冬,数据结构的图形表示,父亲,儿子,女儿,数据逻辑结构是对数据元素之

6、间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。与数据在计算机中的存储位置无关，是独立于计算机的。,常见的逻辑结构有：线性结构、树形结构和图形结构。, 线性结构 结构中的每个元素之间存在一个对一个的关系； 树形结构 结构中的每个元素之间存在一个对多个的关系； 图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。,数据的存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的

7、位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有： 顺序存储结构 链式存储结构索引存储结构,只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结构。一种数据结构可以根据需要表示成一种或多种存储结构。,常见的数据结构：1.线性表 2.栈和队列 3.树,线性结构和非线性结构,线性结构在数据元素的非空有限集合中，线性结构的逻辑特征如下：存在一个唯一的被称为“第一个”的数据元素存在一个唯一的被称为“最后一个”的数据元素除第一个之外，集合中的每个数据元素均有且只有一个直接前驱除最后一个之外，集合中的每个数据元

8、素均有且只有一个直接后继非线性结构非线性结构的逻辑特征是：一个结点可能有多个直接前驱和直接后继，树和图都属于非线性结构。, 线性表,线性表是由n（n0）个数据元素a1，a2，ai，an组成的一个有限序列。,简单的线性表,复杂的线性表,记录1 02011001 张三 男,记录2 02011003 李四 女 ,记录3,记录4,线性表的存储结构有两种：顺序存储结构、链式存储结构,线性表的顺序存储,线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，即以“存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的

9、基地址。,所有数据元素的存储位置均可由第一个数据元素的存储位置得到 ADR(ai) = ADR(a1) + (i-1)C 基地址 一个数据元素所占存储量,顺序表的插入和删除运算,线性表的顺序存储结构称为顺序表。,顺序表的插入运算 顺序表的删除运算,在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。,线性表的链式存储结构线性表的链式存储结构称为线性链表。 链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。 链

10、式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：,单链表的插入运算 单链表的删除运算,线性链表的插入和删除运算,采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。,循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。,双向链表的存储结构,HEAD,3,1,5,10,双向链表可以克服单链表的单向性的缺点。 在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。,线性表的存储结构有两种,顺序存储结构,注意： 数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。 一个逻辑数据结构可以有多种

11、存储结构，且不同的存储结构影响数据处理的效率 。,链式存储结构,线性表 : a1，a2，a3，a4，a5 ,栈和队列,栈和队列都是特殊的线性表。 栈（Stack）及其基本运算 队列（Queue）及其基本运算 循环队列及其基本运算,栈,顺序栈的进栈和出栈运算：栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入，也是最后被删除的元素。因此，栈是一种先进后出（后进先出）的线性表。通常用指针top指示栈顶位置，用指针bottom指示栈底位置。,栈的物理存储结构可以用顺序结构，也可以

12、用链表结构。栈的基本运算有三种：入栈、退栈和读栈顶元素,队列,队列是一种先进先出的线性表，它只允许在表的一端插入元素(队尾)，在另一端删除元素(队头)。通常定义头指针front指向队头元素的前一个位置，定义尾指针rear指向队尾元素的位置。队列是一种先进先出的数据结构。向队尾插入一个元素的操作称为入队，从队头删除一个元素的操作称为退队。,栈的物理存储结构可以用顺序结构，也可以用链表结构。队列的基本运算有三种：入队出队读队首元素,循环队列 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，当R指向存储空间的末端后，就把它重新置于始端。 循环队列的运算,队列中进行插入的一端称做队尾

13、(rear),进行删除的一端称做队首(front)。,线性表 线性结构栈 是特殊的线性表 队列 也是一种操作受限的特殊的线性表树 （树型结构）是一种重要的非线形数据结构,常见数据结构的逻辑结构,一个非空的数据结构若满足下面的两个条件，则这种数据结构即为线性结构。 有且仅有一个根结点； 除第一个结点外，每一个结点最多有一个直接前驱结点； 除最后一个结点外，每一个结点最多有一个直接后继结点。,线性结构与非线性结构线性表、栈和队列都是线性结构 一个数据结构不是线性结构，则称其为非线性结构。,树型结构是一种重要的非线性结构。 树的概念 二叉树的概念 二叉树的存储 二叉树的遍历,树与二叉树,树及其基本概

14、念,树是一种简单的非线性结构，在树中，所有的数据元素之间具有明显的层次性关系。树是(n0)个结点的有限集合，在任意一棵非空树中： (1)有且仅有一个特定的结点称为根结点。 (2)当n1时，其余的结点可分为m个互不相交的子集T1,T2,Tm，其中每个有限子集本身又是一棵树，并且称为根的子树。集合为空的树简称为空树；树中的元素称为结点。,树型结构的常用术语,A,B,D,F,E,C,G,H,I,J,K,M,1)度：结点拥有的子树数。2)叶子节点(终端结点)：度为0的结点。3)层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层。4)深度：树中结点的最大层次称为树的深度或高度。5)结点的层次 树

15、中根结点的层次为1，根结点子树的根为第2层，以此类推；6)树的深度 树中所有结点层次的最大值；,二叉树,二叉树是n(n0)个数据元素的有限集，它或为空集,或者含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为根的左子树和右子树。二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，其顺序不能任意颠倒。,定义：二叉树是一种有序的树形结构。它与一般树形结构的区别是： 1)每个结点最多有两棵子树； 2)子树有左右之分，次序不能任意颠倒。,二叉树的基本性质,【性质1】 在二叉树的第K层上最多有2k-1个结点（k1）【性质2】深度

16、为h的二叉树最多有2h -1个结点（h 1）【性质3】二叉树上叶子结点数比度为2的结点数多1,度为2的结点,叶子结点,满二叉树和完全二叉树,满二叉树：如果一个深度为h的二叉树拥有2h-1个结点，则将它称为满二叉树。完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结点位置一一对应，则称这棵二叉树为完全二叉树。,二叉树的存储结构,在计算机中，二叉树通常采用链式存储结构。,二叉树的存储结点的结构,A,B,D,C,F,G,E,t,二叉树的遍历,二叉树的遍历指不重复地访问二

17、叉树的所有结点。从二叉树的结构定义得知，二叉树是由根结点、左子树和右子树三部分构成，则遍历二叉树的操作可分解为访问根结点、遍历左子树和遍历右子树三个子操作，并且由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样递归进行。,查找技术,查找是数据处理的重要内容。 查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。 若找到了满足条件的结点，称查找成功；否则称查找失败。 衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。 通常根据不同的数据结构，采用不同的查找方法：1）顺序查找：线性表中最简单的查找方法。 最坏情况下需比较n次2）二分查找（折半查找）：是一种

18、效率较高的查找方法，但是只适合顺序存储的有序表。 最坏情况下需比较log2n,排序技术,排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。 排序方法中其排序对象一般是顺序存储的线性表。 根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法：,插入类排序法 简单插入排序 希尔排序,选择类排序法简单选择排序堆排序,交换类排序法 冒泡排序 快速排序,第二章 程序设计基础(15%),考试大纲1. 程序设计方法与风格。2. 结构化程序设计。3. 面向对象的程序设计方法，对象，方法，属性及继承与多态性。,结构化程序设计,结构化程序设计方法的四条原则是：1. 自顶向下；2. 逐步求精；3

19、. 模块化；4. 限制使用goto语句。 结构化程序的基本结构和特点：（1）顺序结构： 简单的程序设计，最基本、最常用的结构；（2）选择结构（分支结构）： 包括简单选择和多分支选择结构，（3）重复结构（循环结构）： 可根据给定条件，判断是否需要重复执行某一相同程序段。,面向对象的程序设计,1、对象：是面向对象方法中最基本的概念。属性即对象所包含的信息操作描述了对象执行的功能，操作也称为方法或服务。2、类：是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。3、消息：是一个实例与另一个实例之间传递的信息。消息的组成包括 （1）接收消息的对象的名称； （2）消息标识

20、符，也称消息名； （3）零个或多个参数。4、继承：是指能够直接获得已有的性质和特征，而不必重复定义他们。 单继承指一个类只允许有一个父类 多重继承指一个类允许有多个父类。5、多态性：是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。,第三章 软件工程基础,考试大纲 1. 软件工程基本概念，软件生命周期的概念，软件工具与软件开发环境。 2. 结构化分析方法，数据流图，数据字典，软件需求规格说明书。 3. 结构化设计方法，总体设计与详细设计。 4. 软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。 5. 程序的调试，静态调试与动态调试。,软

21、件工程概念,软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程包括3个要素：方法、工具和过程。软件周期：软件产品从提出、实现、使用维护到停止使用退役的过程。软件生命周期三个阶段:软件定义、软件开发、运行维护，主要活动阶段是：（1）可行性研究与计划制定；（2）需求分析；（3）软件设计；（4）软件实现；（5）软件测试；（6）运行和维护。,结构化分析方法和设计方法,结构化分析方法：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。结构化分析的常用工具:1)数据流图；2)数据字典；3)判定树；判定表。结

22、构化分析方法：软件设计包括：总体设计与详细设计 在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。常见的过程设计工具有：图形工具（程序流程图,N-S,PAD）表格工具（判定表）语言工具（PDL伪码）,程序流程图,N-S图,PAD图,软件测试,软件测试的目的：发现错误而执行程序的过程。 软件测试方法：1)静态测试：包括代码检查、静态结构分析、代码质量度量。不实际 运行软件，主要通过人工进行。2)动态测试： 是基本计算机的测试，主要包括白盒测试方法和黑盒 测试方法 白盒测试方法有：逻辑覆盖；基本路径测试黑盒测试方法有：等价类划分法；边界值分析法；错误推测法软件测试过程一般按4

23、个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。,程序的调试,程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。 软件调试静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段。动态调试是辅助静态调试。主要调试方法有：（1）强行排错法；（2）回溯法；（3）原因排除法。,第四章 数据库设计基础,考试大纲1. 数据库的基本概念：数据库，数据库管理系统，数据库系统。2. 数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。3. 关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4. 数据库设计方法和步骤：需求分析、概念设计、逻辑设计

24、和物理设计的相关策略。,数据库系统的基本概念,数据：实际上就是描述事物的符号记录。数据库：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。数据库管理系统：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。数据库系统：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。数据库应用系统：由数据库系统、应用软件及应用界面三者组成。,数据库管理系统(DBMS),数据库管理系统是一个帮助用户创建和管理数据库的应用程序的集合。因此，数

25、据库管理系统也就是一个可以帮助完成定义、构造和操纵数据库等处理目的的通用软件系统。其主要功能如下：数据模式定义数据存取的物理构建数据操纵数据的完整性、安全性定义和检查数据库的并发控制和故障恢复数据的服务为完成上述功能，DBMS提供了相应的语言：数据定义语言(DDL)数据操纵语言(DML)数据控制语言(DCL),数据库系统,数据库系统是由数据库、数据库管理系统、数据库管理员、硬件平台和软件平台等几个部分组成的完整的运行实体。数据库系统的特点数据的集成性数据的高共享性和低冗余性数据的独立性数据统一管理和控制,。(1)人工管理阶段：人工管理阶段：存储设备比较落后 第一代计算机：输入 处理 输出(2)

26、文件系统阶段 ：按名存取（出现数据与程序的概念） 实现了以文件为单位的数据共享(3) 数据库系统管理阶段:实现了以记录和数据项为单位的文件共享 特点：1）提高数据的共享性 2）减少数据的冗余（但并没有消除） 3）增加了数据余程序的独立性,数据库管理系统的发展,数据库系统的内部体系结构,三级模式概念模式：数据库系统中全局数据逻辑结构的描述，全体用户的数据视图外模式：又称为用户模式，是每个用户的局部数据描述，用户的数据视图内模式：又称为物理模式，是数据库物理存储结构和物理存取方法的描述二级映射概念模式到内模式的映射外模式到概念模式的映射,数据模型,数据是现实世界符号的抽象，数据模型是现实世界数据特

27、征的抽象，它从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表示和操作提供一个抽象的框架。数据模型描述的内容包括三部分：数据结构数据操作数据约束数据模型按不同的应用层次分成三种类型：概念数据模型逻辑数据模型物理数据模型,实体联系(ER)模型,E-R模型的基本概念（1）实体：现实世界中的事物；（2）属性：事物的特性；（3）联系：现实世界中事物间的关系。联系：联系反映概念世界中的实体集之间存在的一定关系。一对一联系(1:1)一对多联系(1:M)多对多联系(M:N),ER模型图示法,ER图是实体联系模型的直观图形表示。E-R模型之间的联接关系：实体是概念世界中的基本单位，属性

28、有属性域，每个实体可取属性域内的值。一个实体的所有属性值叫元组。E-R模型的图示法：（1）实体集表示法：用长方形（2）属性表法：用椭圆形（3）联系表示法：用菱形,层次模型（采用树型结构）,图1-4 层次模型示例,网络模型（采用无向图型结构）,关系模型（采用二维表结构）,关系数据模型,关系模型用二维表结构来表示实体之间联系的模型，简称表，由表框架及表的元组组成。一个二维表就是一个关系。关系 二维表（等价） 关系的组成：1）元组：二维表的每一行-记录（除过第一行） 2）属性：二维表的每一列-字段,一个二维表要满足下面7个性质就可称为一个关系。二维表中元组个数是有限的二维表中元组均不相同 二维表中元

29、组的次序可任意交换 二维表中元组的分量是不可分割的基本数据项二维表中属性名各不相同二维表中属性与次序无关，可任意交换二维表属性中的分量具有与该属性相同的值域,关系模型的基本运算：查询选择、投影、连接、并、交、差、笛卡尔积运算数据更新插入、删除、更新关系操作的特点集合操作方式，即操作的对象和结果都是集合。,关系操作,集合的并运算,（1）投影对于关系R内的域指定称为投影运算。S关系就是对R关系指定A和B两个域的结果,R,S,关系操作：选择,（2）选择选择运算的关系是由关系R中那些满足逻辑条件的元组所组成。S关系就是R关系中满足A=a的结果,R,S,有了投影和选择运算，我们对一个关系内的任意行、列的

30、数据都可以方便的找到。,笛卡尔积：是对两个关系的合并操作。 由两个关系R、S得到T,R,S,T,笛卡尔积和自然连接运算,自然连接运算：在实际应用中一般相互连接的关系往往须满足一些条件，所得到的结果也较为简单。自然连接满足两个关系：1）中有公共域；2）通过公共域的相等值进行连接。,数据库设计与管理,数据库设计的两种方法：（1）面向数据：以信息需求为主，兼顾处理需求；（2）面向过程：以处理需求为主，兼顾信息需求。 数据库的生命周期：需求分析阶段 结构析方法和面向对象的方法 数据字典是各类数据描述的集合，包括5个部分：数据项、数据结构、数据流、数据存储、处理过程。概念设计阶段 分析数据内在语义关系。E-R模型 逻辑设计阶段物理设计阶段编码阶段测试阶段运行阶段进一步修改阶段,数据库设计与管理,需求分析,概念设计,逻辑设计,物理设计,编码,测试,运行,进一步修改,分析客户的业务和数据处理需求;,设计数据库的E-R模型图，确认需求信息的正确和完整;,将E-R图转换为多张表，进行逻辑设计,并应用数据库设计的三大范式进行审核;,数据库内模式包括存储结构和存取方法。,重点记,8个阶段,选择具体数据库进行物理实现，并编写代码实现前端应用;,数据库管理的内容,（1）数据库的建立；（2）数据库的调整；（3）数据库的重组；（4）数据库安全性与完整性控制；（5）数据库的故障恢复；（6）数据库监控。,