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