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

1、计算机等级考试公共基础知识第一章一、公共基础知识考试1.考试性质：无论选择二级的哪一个种类，均需要考公共基础知识，每年在全国范围内举行两次。级别证书种类获证条件二级语言程序设计类C语言程序设计科目24考试合格VB语言程序设计科目26考试合格Java语言程序设计科目28考试合格C+语言程序设计科目61考试合格Web程序设计科目64考试合格数据库程序设计VFP数据库程序设计科目27考试合格Access数据库程序设计科目29考试合格MySQL数据库程序设计科目63考试合格办公软件MS Office高级应用科目65考试合格2.考试介绍：3.考试形式：公共基础知识不单独考试，与其他二级科目结合在一起，作

2、为二级科目考核内容的一部分。考试方式为上机考试，10道选择题，占10分。4.考试题型：在无纸化上机考试的40道选择题中，有10个单项选择题是考核公共基础知识的，每题1分。二、2013全国计算机等级考试二级教程教材简介教材名称：全国计算机等级考试2级教程：公共基础知识（2013年版）/教育部考试中心（编著）出版单位：高等教育出版社版次：第一版（2013年5月1日）三、复习应考策略1.理解基本概念2.消化理论知识，多做习题3.常用的名词一定要记忆4.与所学的知识要联系起来，增加对知识的理解能力四、公共基础知识考试要求1.掌握算法的基本概念2.掌握基本数据结构及其操作3.掌握基本排序和查找算法4.掌

3、握逐步求精的结构化程序设计方法5.掌握软件工程的基本方法，具有初步运用相关技术进行软件开发的能力6.掌握数据库的基本知识，了解关系数据库的设计五、考试内容大纲基本数据结构与算法1.算法的基本概念；算法复杂度的概念和意义（时间复杂度和空间复杂度）2.数据结构的定义；数据的逻辑结构与存储结构，数据结构的图形表示；线性结构与非线性结构的概念3.线性表的定义；线性表的顺序存储结构及其插入语删除运算4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算五、考试内容大纲基本数据结构与算法5.线性单链表、双向链表与循环链表的结构及其基本运算6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序

4、遍历7.顺序查找与二分查找算法；基本排序算法（交换类排序、选择类排序、插入类排序）程序设计基础1.程序设计方法与风格2.结构化程序设计3.面向对象的程序设计方法、对象、方法、属性及继承与多态性。软件工程基础1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境2.结构化分析方法，数据流图，数据字典，软件需求分析规格说明书3.结构化设计方法，总体设计与详细设计4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试，继承测试盒系统测试5.程序的调试，静态调试与动态调试数据库设计基础1.数据库的基本概念：数据库，数据库管理系统，数据库系统2.数据模型，实体联系模型机E

5、-R图，从E-R图导出关系数据模型3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略六、本门课程培训班培训目标1.梳理教材知识点，帮助考生构建本门课程知识体系2.重点讲解历年考试常考的知识点3.让广大学员能听懂、学明白。不仅能顺利通过考试，更要在以后的工作中能够学以致用。一、算法的概念 解决方案的准确而完整的描述 对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。算法不等于程序，也不等于计算方法特征：可行性、确定性、有穷性、拥有足够

6、的情报可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，算法中的每个步骤都能在有限时间内完成；如：天气预报，加密解密拥有足够的情报 一个算法与输入的初始数据有关，不同的输入将会有不同的结果输出。当算法拥有足够多的情报时，此算法才是有效的，而当提供的情报不够时，算法可能无效。算法的基本要素：对数据运算操作（算术、逻辑）算法的控制结构（执行顺序）描述算法

7、的工具通常有传统流程图（在软件测试时会讲到）、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。二、流程图描述（了解即可）开始输入nSum=0,i=1i=0结束输入sumSum=sum+1,iNext指向ai的后件结点，即把

8、ai从链上摘下。最后释放结点ai的空间。线性双向链表的结构及其基本运算1.双向链表的定义2.双向链表的基本运算（插入、删除）树与二叉树树的定义树(Tree)是一种简单的非线性结构，直观地来看，树是以分支关系定义的层次结构。由于它呈现与自然界的树类似的结构形式，所以称它为树。树结构在客观世界中是大量存在的。在树结构中，每一个结点只有一个前件，称为父结点；没有前件的结点只有一个，称为树的根结点，简称树的根。在树结构中，每一个缓点可以有多个后件，称为该结点的子结点；没有后件的结点称为叶子结点。二叉树的定义及其基本性质1.叉树的定义二叉树是由n(nO)个结点的有限集合构成，此集合或者为空集，或者由一个

9、根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。二叉树具有以下两个特点：(l)非空二又树只有一个根结点；(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒，因此，二叉树有5种不同的形态2.二叉树的基本性质性质1：在二叉树的第k层上至多有2k-1（k1）个结点。性质2：深度为m的二叉树至多有2m-1个结点。性质3：对任何一棵二叉树，度为0的结点（即叶子

10、结点）总是比度为2的结点多一个。性质4：具有n个结点的完全二叉树的深度至少为log2n+1，其中log2n表示log2n的整数部分。3.满二叉树与完全二叉树满二叉树和完全二叉树是两种特殊形态的二叉树。(1)满二叉树 满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。即在满二叉树的第k五层上有2k-1个结点。从上面满二叉树定义可知，必须是二叉树每一层上的结点数都达到最大，否则就不是满二叉树：深度为m的满二叉树有2m-1个结点。在满二叉树中，只有度为2和度为0的结点，没有度为1的结点。所有度为0的结点即叶子结点都在同一层，即最后一层。(2)完全二叉树 完全二叉树是指除最后一层外，每一层上

11、的结点数均达到最大值；在最后一层上只缺少右边的若干结点。完全二叉树也可以这样描述：如果对满二叉树的结点进行连续编号，从根结点开始，对二叉树的结点自上而下，自左至右用自然数进行连续编号，则深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。由完全二叉树可知，满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。完全二叉树还具有以下两个性质。性质1：具有n个结点的完全二叉树深度为log2n+1。性质2：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第log2n+1层，每层从左到右。），则对任一结点k（Ikn），有

12、：如果k=l，则结点k为父结点，是二叉树的根；如果k1，则该结点的父结点编号为INT(k/2)；如果2kn，则结点k的左子结点编号为2k；否则该结点没有左子结点（显然也没有右子结点）：如果2k+ln，则结点k的右子结点编号为2k+1;否则该结点没有右子结点。4.二叉树的存储结构 在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由两部分组成：数据域与指针域。但在二叉树中，由于每一个元素可以有两个后件（两个子结点）因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域 由于二

13、叉树的存储结构中每一个存储结点有两个指针域，因此，二叉树的链式存储结构也称为二叉链表。二叉树的遍历在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。在先左后右的原则下，根据访问根结点的次序不同，二叉树的遍历可以分为3种：前序遍历、中序遍历、后序遍历。1.前序遍历前序遍历中“前”的含义是：访问根结点在访问左子树和访问右子树之前。即首先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左子树和右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。前序遍历可以描述为：若二叉树为空，则执行空操作；否则访问根结点，前序遍历左子树，前序遍历右子树。2.中序遍历中序遍历中“中”的含义是：访问根

14、结点在访问左子树和访问右子树两者之间。即首先遍历左子树，然后访问根结点，最后遍历右子树。并且在遍历左子树和右子树时，仍然首先遍历左子树，然后访问根结点，最后遍历右子树。中序遍历可以描述为：若二叉树为空，则执行空操作；否则中序遍历左子树，访问根结点，中序遍历右子树。3.后序遍历 后序遍历中“后”的含义是：访问根结点在访问左子树和访问右子树之后。即首先遍历左子树，然后遍历右子树，最后访问根结点；并且在遍历左子树和右子树时，仍然首先遍历左子树，然后遍历右子树，最后访问根结点。后序遍历可以描述为：若二叉树为空，则执行空操作；否则后序遍历左子树，后序遍历右子树，访问根结点。查找技术 查找就是在某种数据结

15、构中，找出满足指定条件的元素。查找是插入和删除等运算的基础，是数据处理的重要内容。由于数据结构是算法的基础，因此，对于不同的数据结构，应选用不同的查找算法，以获得更高的查找效率。1.顺序查找顺序查找（顺序搜索）是最简单的查找方法，它的基本思想是：从线性表的第一个元素开始，逐个将线性表中的元素与被查元素进行比较，如果相等，则查找成功，停止查找；若整个线性表扫描完毕，仍未找到与被查元素相等的元素，则表示线性表中没有要查找的元素，查找失败。在进行顺序查找过程中，如果绂性表中的第一个元素就是要查找的元素，则比较次数为1；如果最后一个元素才是要查找的元素，或者在线性表中，没有要查找的元素，则需要与线性表

16、中所有的元素比较，这是顺序查找的最坏情况。在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。由此可以看出，对于大的线性表来说，顺序查找的效率很低。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找：(l)如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找；(2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。2.二分查找 二分法查找，也称拆半查找，是一种高效的查找方法。能使用二分法查找的线性表必须满足两个条件：用顺序存储结构；线性表是有序表。对于长度为凡的有序线性表，利用二分法查找元素X的

17、过程如下。将X与线性表的中间项比较：如果X的值与中间项的值相等，则查找成功，结束查找；如果X小于中间项的值，则在线性表的前半部分以二分法继续查找；如果X大于中间项的值，则在线性表的后半部分以二分法继续查找。顺序查找法每一次比较，只将查找范围减少1，而二分法查找，每比较一次，可将查找范围减少为原来的一半，效率大大提高。可以证明，对于长度为凡的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。排序技术所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。排序的方法有很多，根据待排序序列的规模以及对数据处理的要求，可以采用不同的排序方法。交换类排序 交换类排序

18、法是借助数据元素的“交换”来进行排序的一种方法。1.冒泡排序冒泡排序法是最简单的一种交换类排序万法。在数据元素的序列中，对于某个元素，如果其后存在一个元素小于它，则称之为存在一个逆序。冒泡排序(Bubble Sort)的基本思想就是通过两两相邻数据元素之间的比较和交换，不断地消去逆序，直到所有数据元素有序为止。冒泡排序法的基本过程如下：第一遍，在线性表中，从前往后扫描，如果相邻的两个数据元素，前面的元素大于后面的元素，则将它们交换，并称为消去了一个逆序。在扫描过程中，线性表中最大的元素不断地往后移动，最后，被交换到了表的末端。此时，该元素就已经排好序了。然后对当前还未排好序的范围内的全部结点，

19、从后往前扫描，如果相邻两个数据元素，后面的元素小于前面的元素，则将它们交换，也称为消去了一个逆序。在扫描过程中，最小的元素不断地往前移动，最后，被交换到了线性表的第一个位置，则认为该元素已经排好序了。对还未排好序的范围内的全部结点，继续第二遍，第三遍的扫描，这样，未排好序的范围逐渐减小，最后为空，则线性表已经变为有序了。在最坏情况下对长度为n的线性表排序，冒泡排序需要比较的次数为n(n-l)/2。2.快速排序 在冒泡排序中，一次扫描只能确保最大的元素或最小的元素移到了正确位置，而未排序序列的长度可能只减少了l。快速排序(Quick Sort)是对冒泡排序方法的一种本质的改进。快速排序的基本思想

20、是：在待排序的n个元素中取一个元素K(通常取第一个元素)，以元素K作为分割标准，把所有小于K元素的数据元素都移到K前面，把所有大于K元素的数据元素都移到K后面。这样，以K为分界线，把线性表分割为两个子表，这称为一趟排序。然后，对K前后的两个子表分别重复上述过程。继续下去，直到分割的子表的长度为l为止，这时，线性表已经是排好序的了。第一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别指向线性表的第一个元素（K元素）和最后一个元素。首先从high所指的位置向前扫描，找到第一个小于K元素的元素并与K元素互相交换。然后从low所指位置起向后扫描，找到第一个大于K元素的数据元素并与K

21、元素交换。重复这两步，直到low=high为止。快速排序的平均时间效率最佳，为O(nlog2n)，最坏情况下，即每次划分，只得到一个子序列时间效率为O(n2)。选择类排序选择排序的基本思想是通过每一趟从待排序序列中选出值最小的元素，顺序放在已排好序的有序子表的后面，直到全部序列满足排序要求为止。1.简单选择排序法 简单选择排序(Simple Selection Sofi)的基本思想是：首先从所有n个待排序的数据元素中选择最小的元素，将该元索与第1个元素交换，再从剩下的n-1个元素中选出最小的元素与第2个元素交换。重复这样的操作直到所有的元素有序为止。简单选择排序法在最坏的情况下需要比较n(n-

22、1)/2次。2.堆排序法堆排序属于选择类的排序方法在最坏情况下，堆排序法时间复杂度为O(nlog2n)。插入类排序法 插入排序是每次将一个待排序元素，按其元素值的大小插入到前面已经排好序的子表中的适当位置，直到全部元素插入完成为止。1.简单插入排序 简单插入排序是把几个待排序的元素看成是一个有序表和一个无序表，开始时，有序表只包含一个元素，而无序表包含另外n-l个元素，每次取无序表中的第一个元素插入到有序表中的正确位置，使之成为增加一个元素的新的有序表。插入元素时，插入位置及其后的记录依次向后移动。最后有序表的长度为n，而无序表为空，此时排序完成。在最好情况下，即初始排序序列就是有序的情况下，简单插入排序的比较次数为n-l次，移动次数为0次。2.希尔排序法希尔排序的时间效率与所取的增量序列有关，如果增量序列为d1=n/2，di+1=d2，当n较大时，希尔排序时间复杂度为0（n）。谢谢大家！谢谢大家！