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

计算机二级考试公共基础知识大纲数据结构与算法程序设计基础软件工程基础数据库设计基础全国计算机等级考试二级公共基础知识不单独考试,与其他二级科目组合在一起,作为二级科目考核内容的一部分。考试方式:上机考试题型:选择题(注:10道选择题,占总分值的10%)第一章数据结构与算法(30%)考试大纲 ;算法复杂度的概念和意义(时间复杂度与空间复杂度)。;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。;线性表的顺序存储结构及其插入与删除运算。;栈和队列的顺序存储结构及其基本运算。、双向链表与循环链表的结构及其基本运算。;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。;基本排序算法(交换类排序,选择类排序,插入类排序)。算法的定义对解题方案准确而完整的描述称为算法。算法是程序设计的核心算法的基本概念算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程(计算的方法)。在这个过程中,无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法),都是在实施某种算法。例:n个数从大到小进行排序。有多种排序方法,常用的有冒泡排序、选择排序等。算法的基本特征一个算法应该具有以下五个重要的特征:有穷性确定性输入输出可行性一个算法必须保证执行有限步之后结束;算法的每一步骤必须有确切的定义;一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定除了初始条件;一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成算法的两个基本要素:基本运算和操作算术运算关系运算逻辑运算数据传输控制结构顺序选择循环一是对数据对象的运算和操作;二是算法的控制结构。算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法算法的复杂度评价一个算法优劣的主要标准是算法的执行效率和存储需求:时间复杂度:执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度:执行这个算法所需要的内存空间算法在执行过程中临时占用的存储空间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分计算机在进行数据处理时,实际需要处理的数据元素一般有很多,而这些大量的数据元素都需要存放在计算机中,因此,大量的数据元素在计算机中如何组织,以便提高数据处理的效率,并且节省计算机的存储空间,这是进行数据处理的关键问题。数据结构程序=算法+数据结构数据结构是指相互有关联的数据元素的集合。一般来说,人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素,对于具有不同特征的数据元素总是分别进行处理。一般情况下,在具有相同特征的数据元素集合中,各个数据元素之间存在有某种关系(即联系),这种关系反映了该集合中的数据元素所固有的一种结构。数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科,它包括三个方面。(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。。春夏秋冬数据结构的图形表示父亲儿子女儿数据逻辑结构是对数据元素之间存在的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合上的若干关系表示。与数据在计算机中的存储位置无关,是独立于计算机的。常见的逻辑结构有:线性结构、树形结构和图形结构。①线性结构结构中的每个元素之间存在一个对一个的关系;②树形结构结构中的每个元素之间存在一个对多个的关系;③图形结构或网状结构结构中的每个元素之间存在多个对多个的关系。其中,树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示,也可以直观地用图形来表示。数据的存储结构(物理结构)计算机在实际进行数据处理时,被处理的各数据元素总是被存放在计算机的存储空间中,并且,各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的,而且一般也不可能相同。存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有:顺序存储结构链式存储结构索引存储结构只抽象地反映数据元素之间的关系的结构,而不管其存储方式的数据结构称为