资源描述：
《全国计算机等级考试_二级_公共基础知识_课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、二级公共基础知识二级公共基础知识第一章算法与数据结构第二章程序设计基础第三章软件工程基础第四章数据库设计基础2第一章算法与数据结构本章要求算法的基本概念、算法复杂度的概念和意义（时间复杂度与空间复杂度）。数据结构的定义、数据的逻辑结构与存储结构、数据结构的图形表示、线性结构与非线性结构的概念。线性表的定义、线性表的顺序存储结构及其插入与删除运算。栈和队列的定义、栈和队列的顺序存储结构及其基本运算。线性单链表、双向链表与循环链表的结构及其基本运算。树的基本概念，二叉树的定义及其存储结构，二叉树的前
2、序、中序和后序遍历。顺序查找与二分法查找算法、基本排序算法（交换类排序、选择类排序与插入类）。3第一章算法与数据结构一、算法二、数据结构三、线性表四、栈五、队列六、线性链表七、树与二叉树八、查找技术九、排序技术4一、算法1.算法的基本概念算法是指为了解决某类问题而规定的一个有限长度的操作（指令）序列。（1）算法的特点：可行性、确定性、有穷性、拥有足够的情报。（2）算法的两个基本要素： 一是对数据对象的运算和操作，具体包括算术运算、逻辑运算、关系运算和数据传输等； 二是算法的控制结构，具体包括顺序
3、结构、选择结构和循环结构。52.算法的复杂度算法的复杂度(代价)是衡量算法好坏的量度，具体可分为两种:时间复杂度和空间复杂度。（1）时间复杂度是指执行算法所需要的计算工作量，即算法执行过程中所需要的基本运算次数。 通常记作： 常见的时间复杂度有：（2）空间复杂度是指执行该算法所需要的内存空间。具体包括（1）算法程序所占的空间；（2）输入的初始数据所占的存储空间；（3）算法执行过程中的额外空间6二、数据结构1.数据结构的基本概念数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。 在此概念
4、中:（1）数据是指所有能输入到计算机中并被计算机程序处理的符号的总称;（2）数据元素是指数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理;（3）一个数据元素可以由若干个数据项组成,数据项是数据的最小单位。7数据结构有三个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。2.数据的逻辑结构数据的逻辑结构是指数据元素之间的逻辑关系，从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据的逻辑结构的表示方法 表示数据的逻辑结构时必须表示清楚两个关键点，一个是数据元素的集合D
5、，另一个是数据元素之间的前后关系R。表示数据结构的方法有两种：二元关系表和图形表示方法。8A.二元关系表示方法：一个数据结构可以表示为B=（D、R），其中R用二元组来表示(a、b)。a表示前件，b表示后件。例如，一年四季的数据结构可以表示成: B=（D、R）D={春，夏，秋，冬} R={（春，夏），（夏，秋），（秋，冬）}B.在图形表示方法中，用中间标有元素值的方框来表示数据元素，称为数据结点，简称为结点；用一条有向线段从前件结点指向后件结点（注意：有时可以省略箭头）来表示元素之间的前后关系。9
6、例如，同样是一年四季的数据结构，若用图形方法表示则如图所示。数据的逻辑结构一般分为两种:线性结构和非线性结构。线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。如：一年四季。非线性结构：线性以外的数据结构。如：反映家庭成员间辈分关系的数据结构。10A.线性结构①线性表例:英文字母表(A,B,C,·······，X,Y,Z)例:学生成绩表②栈——后进先出③队列——先进先出86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号11B.非线性结构①
7、树形结构例:全校学生档案管理的组织方式例:计算机文件管理系统也是典型的树形结构12②图形结构——结点间的连结是任意的例:数据结构B(D,R)D={1,2,3,4} R={(1,2),(1,3),(1,4), (2,3),(3,4),(2,4)}例:数据结构C(D,R)D={1,2,3} R={(1,2),(2,3),(3,2),(1,3)}1423213133.数据的存储结构数据的存储结构(又称物理结构):是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储空间中的存放形式。数
8、据的存储结构有4种：顺序存储方式、链式存储方式、索引存储方式和散列存储方式。需要注意的是，对于同一个逻辑结构来说，采用不同的存储结构时，其数据处理的效率是不同的。4.数据的运算：检索、排序、插入、删除、修改等。14三、线性表线性表是最简单的、最常用的一种线性结构。1.线性表的定义:线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2，……，ai，……，an，其中n称作表的长度，当n=0时，称作空表。线性表（非空线性表）必须同时满足以下3个条件： （1）有且只有一个根结点a1
