计算机等级考试公共基础知识第一章.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,计算机等级考试公共基础知识第一章,前言,一、公共基础知识考试,1.,考试性质：,无论选择二级的哪一个种类，均需要考公共基础知识，每年在全国范围内举行两次。,前言,级别,证书种类,获证条件,二级,语言程序设计类,C,语言程序设计,科目,24,考试合格,VB,语言程序设计,科目,26,考试合格,Java,语言程序设计,科目,28,考试合格,C+,语言程序设计,科目,61,考试合格,Web,程序设计,科目,64,考试合格,数据库程序设计,VFP,数据库程序设计,科目,27,考试合格,Access,数据库程序设计,科目,29,考试合格,MySQL,数据库程序设计,科目,63,考试合格,办公软件,MS Office,高级应用,科目,65,考试合格,2.,考试介绍：,前言,3.,考试形式：,公共基础知识不单独考试，与其他二级科目结合在一起，作为二级科目考核内容的一部分。,考试方式为上机考试，,10,道选择题，占,10,分。,前言,4.,考试题型：,在无纸化上机考试的,40,道选择题中，有,10,个单项选择题是考核公共基础知识的，每题,1,分。,前言,二、,2013,全国计算机等级考试二级教程,教材简介,教材名称：,全国计算机等级考试,2,级教程：公共基础知识（,2013,年版）,/,教育部考试中心（编著）,出版单位：,高等教育出版社,版次：,第一版（,2013,年,5,月,1,日）,前言,三、复习应考策略,1.,理解基本概念,2.,消化理论知识，多做习题,3.,常用的名词一定要记忆,4.,与所学的知识要联系起来，增加对知识的理解能力,前言,四、公共基础知识考试要求,1.,掌握算法的基本概念,2.,掌握基本数据结构及其操作,3.,掌握基本排序和查找算法,4.,掌握逐步求精的结构化程序设计方法,5.,掌握软件工程的基本方法，具有初步运用相关技术进行软件开发的能力,6.,掌握数据库的基本知识，了解关系数据库的设计,前言,五、考试内容大纲,基本数据结构与算法,1.,算法的基本概念；算法复杂度的概念和意义（时间复杂度和空间复杂度）,2.,数据结构的定义；数据的逻辑结构与存储结构，数据结构的图形表示；线性结构与非线性结构的概念,3.,线性表的定义；线性表的顺序存储结构及其插入语删除运算,4.,栈和队列的定义；栈和队列的顺序存储结构及其基本运算,前言,五、考试内容大纲,基本数据结构与算法,5.,线性单链表、双向链表与循环链表的结构及其基本运算,6.,树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历,7.,顺序查找与二分查找算法；基本排序算法（交换类排序、选择类排序、插入类排序）,前言,程序设计基础,1.,程序设计方法与风格,2.,结构化程序设计,3.,面向对象的程序设计方法、对象、方法、属性及继承与多态性。,前言,软件工程基础,1.,软件工程基本概念，软件生命周期概念，软件工具与软件开发环境,2.,结构化分析方法，数据流图，数据字典，软件需求分析规格说明书,3.,结构化设计方法，总体设计与详细设计,4.,软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试，继承测试盒系统测试,5.,程序的调试，静态调试与动态调试,前言,数据库设计基础,1.,数据库的基本概念：数据库，数据库管理系统，数据库系统,2.,数据模型，实体联系模型机,E-R,图，从,E-R,图导出关系数据模型,3.,关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论,4.,数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略,前言,六、本门课程培训班培训目标,1.,梳理教材知识点，帮助考生构建本门课程知识体系,2.,重点讲解历年考试常考的知识点,3.,让广大学员能听懂、学明白。不仅能顺利通过考试，更要在以后的工作中能够学以致用。,第一章 数据结构与算法,第一章 数据结构与算法,一、算法的概念,解决方案的准确而完整的描述,对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。,算法不等于程序，也不等于计算方法,第一章 数据结构与算法,特征：可行性、确定性、有穷性、拥有足够的情报,可行性,算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；,确定性,对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。,并且在任何条件下，算法都只有一条执行路径,第一章 数据结构与算法,有穷性,对于任意一组合法输入值，在执行有穷步骤之后一定能结束，算法中的每个步骤都能在有限时间内完成；,如：天气预报，加密解密,拥有足够的情报,一个算法与输入的初始数据有关，不同的输入将会有不同的结果输出。当算法拥有足够多的情报时，此算法才是有效的，而当提供的情报不够时，算法可能无效。,第一章 数据结构与算法,算法的基本要素：,对数据运算操作（算术、逻辑）,算法的控制结构（执行顺序）,描述算法的工具通常有传统流程图（在软件测试时会讲到）、,N-S,结构化流程图（是无线的流程图，又称盒图）、算法描述语言等。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。,第一章 数据结构与算法,案例：计算,sum=1+2+3+n,的算法,一、用自然语言描述（了解即可）,1.,输入,n,，即数据个数；,2.,设置累加器,sum,，初始值为,0,，设置计数器,i,，初始值为,1,；,3.,当,i,小于或等于,n,时，做累加，即将,sum,与,i,相加，其和再放到,sum,中。计数器,i,取下一个数，即,i=i+1,，直到,i,大于,n,时终止；,4.,输出累加和,sum,。,第一章 数据结构与算法,二、流程图描述（了解即可）,开始,输入,n,Sum=0,i=1,i=0,结束,输入,sum,Sum=sum+1,iNext,指向,ai,的后件结点，即把,ai,从链上摘下。最后释放结点,ai,的空间,。,第一章 数据结构与算法,线性双向链表的结构及其基本运算,1.,双向链表的定义,2.,双向链表的基本运算（插入、删除）,第一章 数据结构与算法,树与二叉树,树的定义,树,(Tree),是一种简单的非线性结构，直观地来看，树是以分支关系定义的层次结构。由于它呈现与自然界的树类似的结构形式，所以称它为树。树结构在客观世界中是大量存在的。,在树结构中，每一个结点只有一个前件，称为父结点；没有前件的结点只有一个，称为树的根结点，简称树的根。,在树结构中，每一个缓点可以有多个后件，称为该结点的子结点；没有后件的结点称为叶子结点。,第一章 数据结构与算法,二叉树的定义及其基本性质,1.,叉树的定义,二叉树是由,n(n,O),个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。,第一章 数据结构与算法,二叉树具有以下两个特点：,(l),非空二又树只有一个根结点；,(2),每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。,二叉树的每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于,2,的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒，因此，二叉树有,5,种不同的形态,第一章 数据结构与算法,2.,二叉树的基本性质,性质,1,：在二叉树的第,k,层上至多有,2,k-1,（,k,1,）个结点。,性质,2,：深度为,m,的二叉树至多有,2,m,-1,个结点。,性质,3,：对任何一棵二叉树，度为,0,的结点（即叶子结点）总是比度为,2,的结点多一个。,性质,4,：具有,n,个结点的完全二叉树的深度至少为,log,2,n+1,，其中,log,2,n,表示,log,2,n,的整数部分。,第一章 数据结构与算法,3.,满二叉树与完全二叉树,满二叉树和完全二叉树是两种特殊形态的二叉树。,(1),满二叉树,满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。即在满二叉树的第,k,五层上有,2,k-1,个结点。,从上面满二叉树定义可知，必须是二叉树每一层上的结点数都达到最大，否则就不是满二叉树：深度为,m,的满二叉树有,2,m-1,个结点。,在满二叉树中，只有度为,2,和度为,0,的结点，没有度为,1,的结点。所有度为,0,的结点即叶子结点都在同一层，即最后一层。,第一章 数据结构与算法,(2),完全二叉树,完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。,完全二叉树也可以这样描述：如果对满二叉树的结点进行连续编号，从根结点开始，对二叉树的结点自上而下，自左至右用自然数进行连续编号，则深度为,K,的，有,n,个结点的二叉树，当且仅当其每一个结点都与深度为,K,的满二叉树中编号从,1,到,n,的结点一一对应时，称之为完全二叉树。,由完全二叉树可知，满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。,第一章 数据结构与算法,完全二叉树还具有以下两个性质。,性质,1,：具有,n,个结点的完全二叉树深度为,log,2,n+1,。,性质,2,：如果对一棵有,n,个结点的完全二叉树的结点按层序编号（从第,1,层到第,log,2,n+1,层，每层从左到右。），则对任一结点,k,（,I,k,n,），有：,如果,k=l,，则,结,点,k,为父结点，是二叉树的根；如果,k1,，则该结点的父结点编号为,INT(k/2),；,如果,2k,n,，则结点,k,的左子结点编号为,2k,；否则该结点没有左子结点（显然也没有右子结点）：,如果,2k+l,n,，则结点,k,的右子结点编号为,2k+1;,否则该结点没有右子结点。,第一章 数据结构与算法,4.,二叉树的存储结构,在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由两部分组成：数据域与指针域。但在二叉树中，由于每一个元素可以有两个后件（两个子结点）,因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域,由于二叉树的存储结构中每一个存储结点有两个指针域，因此，二叉树的链式存储结构也称为二叉链表。,第一章 数据结构与算法,二叉树的遍历,在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。在先左后右的原则下，根据访问根结点的次序不同，二叉树的遍历可以分为,3,种：前序遍历、中序遍历、后序遍历。,第一章 数据结构与算法,1.,前序遍历,前序遍历中“前”的含义是：访问根结点在访问左子树和访问右子树之前。即首先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左子树和右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。,前序遍历可以描述为：若二叉树为空，则执行空操作；否则访问根结点，前序遍历左子树，前序遍历右子树。,第一章 数据结构与算法,2.,中序遍历,中序遍历中“中”的含义是：访问根结点在访问左子树和访问右子树两者之间。即首先遍历左子树，然后访问根结点，最后遍历右子树。并且在遍历左子树和右子树时，仍然首先遍历左子树，然后访问根结点，最后遍历右子树。,中序遍历可以描述为：,若,二叉树为空，则执行空操作；否则中序遍历左子树，访问根结点，中序遍历右子树。,第一章 数据结构与算法,3.,后序遍历,后序遍历中“后”的含义是：访问根结点在访问左子树和访问右子树之后。即首先遍历左子树，然后遍历右子树，最后访问根结点；并且在遍历左子树和右子树时，仍然首先遍历左子树，然后遍历右子树，最后访问根结点。,后序遍历可以描述为：若二叉树为空，则执行空操作；否则后序遍历左子树，后序遍历右子树，访问根结点。,第一章 数据结构与算法,查找技术,查找就是在某种数据结构中，找出满足指定条件的元素。查找是插入和删除等运算的基础，是数据处理的重要内容。由于数据结构是算法的基础，因此，对于不同的数据结构，应选用不同的查找算法，以获得更高的查找效率。,第一章 数据结构与算法,1.,顺序查找,顺序查找（顺序搜索）是最简单的查找方法，它的基本思想是：从线性表的第一个元素开始，逐个将线性表中的元素与被查元素进行比较，如果相等，则查找成功，停止查找；若整个线性表扫描完毕，仍未找到与被查元素相等的元素，则表示线性表中没有要查找的元素，查找失败。,在进行顺序查找过程中，如果绂性表中的第一个元素就是要查找的元素，则比较次数为,1,；如果最后一个元素才是要查找的元素，或者在线性表中，没有要查找的元素，则需要与线性表中所有的元素比较，这是顺序查找的最坏情况。在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。,第一章 数据结构与算法,由此可以看出，对于大的线性表来说，顺序查找的效率很低。虽然顺序查找的效率不高，,但在下列两种情况下也只能采用顺序查找：,(l),如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找；,(2),即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,第一章 数据结构与算法,2.,二分查找,二分法查找，也称拆半查找，是一种高效的查找方法。能使用二分法查找的线性表必须满足两个条件：,用顺序存储结构；,线性表是有序表。,第一章 数据结构与算法,对于长度为凡的有序线性表，利用二分法查找元素,X,的过程如下。,将,X,与线性表的中间项比较：,如果,X,的值与中间项的值相等，则查找成功，结束查找；,如果,X,小于中间项的值，则在线性表的前半部分以二分法继续查找；,如果,X,大于中间项的值，则在线性表的后半部分以二分法继续查找。,第一章 数据结构与算法,顺序查找法每一次比较，只将查找范围减少,1,，而二分法查找，每比较一次，可将查找范围减少为原来的一半，效率大大提高。,可以证明，对于长度为凡的有序线性表，在最坏情况下，二分法查找只需比较,log,2,n,次，而顺序查找需要比较,n,次。,第一章 数据结构与算法,排序技术,所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。排序的方法有很多，根据待排序序列的规模以及对数据处理的要求，可以采用不同的排序方法。,第一章 数据结构与算法,交换类排序,交换类排序法是借助数据元素的“交换”来进行排序的一种方法。,1.,冒泡排序,冒泡排序法是最简单的一种交换类排序万法。在数据元素的序列中，对于某个元素，如果其后存在一个元素小于它，则称之为存在一个逆序。,冒泡排序,(Bubble Sort),的基本思想就是通过两两相邻数据元素之间的比较和交换，不断地消去逆序，直到所有数据元素有序为止。,第一章 数据结构与算法,冒泡排序法的基本过程如下：,第一遍，在线性表中，从前往后扫描，如果相邻的两个数据元素，前面的元素大于后面的元素，则将它们交换，并称为消去了一个逆序。在扫描过程中，线性表中最大的元素不断地往后移动，最后，被交换到了表的末端。此时，该元素就已经排好序了。,然后对当前还未排好序的范围内的全部结点，从后往前扫描，如果相邻两个数据元素，后面的元素小于前面的元素，则将它们交换，也称为消去了一个逆序。在扫描过程中，最小的元素不断地往前移动，最后，被交换到了线性表的第一个位置，则认为该元素已经排好序了。,对还未排好序的范围内的全部结点，继续第二遍，第三遍的扫描，这样，未排好序的范围逐渐减小，最后为空，则线性表已经变为有序了。,在最坏情况下对长度为,n,的线性表排序，冒泡排序需要比较的次数为,n(n-l)/2,。,第一章 数据结构与算法,2.,快速排序,在冒泡排序中，一次扫描只能确保最大的元素或最小的元素移到了正确位置，而未排序序列的长度可能只减少了,l,。快速排序,(Quick Sort),是对冒泡排序方法的一种本质的改进。,快速排序的基本思想是：在待排序的,n,个元素中取一个元素,K(,通常取第一个元素,),，以元素,K,作为分割标准，把所有小于,K,元素的数据元素都移到,K,前面，把所有大于,K,元素的数据元素都移到,K,后面。这样，以,K,为分界线，把线性表分割为两个子表，这称为一趟排序。然后，对,K,前后的两个子表分别重复上述过程。继续下去，直到分割的子表的长度为,l,为止，这时，线性表已经是排好序的了。,第一章 数据结构与算法,第一趟快速排序的具体做法是：附设两个指针,low,和,high,，它们的初值分别指向线性表的第一个元素（,K,元素）和最后一个元素。首先从,high,所指的位置向前扫描，找到第一个小于,K,元素的元素并与,K,元素互相交换。然后从,low,所指位置起向后扫描，找到第一个大于,K,元素的数据元素并与,K,元素交换。重复这两步，直到,low=high,为止。,第一章 数据结构与算法,快速排序的平均时间效率最佳，为,O(nlog,2,n),，最坏情况下，即每次划分，只得到一个子序列时间效率为,O(n,2,),。,第一章 数据结构与算法,选择类排序,选择排序的基本思想是通过每一趟从待排序序列中选出值最小的元素，顺序放在已排好序的有序子表的后面，直到全部序列满足排序要求为止。,第一章 数据结构与算法,1.,简单选择排序法,简单选择排序,(Simple Selection Sofi),的基本思想是：首先从所有,n,个待排序的数据元素中选择最小的元素，将该元索与第,1,个元素交换，再从剩下的,n-1,个元素中选出最小的元素与第,2,个元素交换。重复这样的操作直到所有的元素有序为止。,简单选择排序法在最坏的情况下需要比较,n(n-1)/2,次。,第一章 数据结构与算法,2.,堆排序法,堆排序属于选择类的排序方法,在最坏情况下，堆排序,法,时间复杂度为,O(nlog,2,n),。,第一章 数据结构与算法,插入类排序法,插入排序是每次将一个待排序元素，按其元素值的大小插入到前面已经排好序的子表中的适当位置，直到全部元素插入完成为止。,第一章 数据结构与算法,1.,简单插入排序,简单插入排序是把几个待排序的元素看成是一个有序表和一个无序表，开始时，有序表只包含一个元素，而无序表包含另外,n-l,个元素，每次取无序表中的第一个元素插入到有序表中的正确位置，使之成为增加一个元素的新的有序表。插入元素时，插入位置及其后的记录依次向后移动。最后有序表的长度为,n,，而无序表为空，此时排序完成。,在最好情况下，即初始排序序列就是有序的情况下，简单插入排序的比较次数为,n-l,次，移动次数为,0,次。,第一章 数据结构与算法,2.,希尔排序法,希尔排序的时间效率与所取的增量序列有关，如果增量序列为,d,1,=n/2,，,d,i,+1=d,2,，当,n,较大时，希尔排序时间复杂度为,0,（,n,）。,谢谢观赏！,2020/11/5,89,