文档介绍：全国计算机等级考试
二级公共基础知识
1
编辑ppt
公共基础知识
内容：
考试大纲
数据结构与算法
程序设计基础
软件工程基础
数据库设计基础
2
编辑ppt
考试大纲
基本要求
1、掌握算法的基本概念。
2、掌空间和额外空间入手。
12
编辑ppt
算法
定义
特征
复杂度（时间/空间）
数据结构
线性→线性表→栈、队列
非线性→树形结构→二叉树（满二叉树、完全二叉数）
顺序存储
链式存储
索引存储
散列存储
查找（顺序、二分）
修改
排序（交换、插入、选择）
插入
删除
修改
13
编辑ppt
数据结构与算法
数据结构的基本概念
1、数据结构 数据结构是指相互有关联的数据元素的集合 数据结构是指带有结构的数据元素的集合。结构 通常指前后件关系。 主要研究：数据元素间的固有逻辑关系 数据元素在计算机中的存储关系 对各种数据结构进行的运算
2、数据的逻辑结构 指反映数据元素之间逻辑关系的数据结构 前后件(直接前驱和直接后继)关系就是指逻辑关系
3、数据的存储结构 数据的逻辑结构在计算机中的存储形式 存储结构也称为物理结构 同一种逻辑结构可以有不同的存储结构 常用的有：顺序、链接、索引等形式
14
编辑ppt
数据结构与算法
数据结构的基本概念
4、数据结构的表示 二元关系表示： 两个要素：数据元素的集合D，该集合上的关系R。 即：B=(D,R) 如：D={春,夏,秋,冬} R={(春,夏),(夏,秋),(秋,冬)} 图形表示： 标有元素值的方框表示结点，有向线段表示逻辑关系。 春 → 夏 → 秋 → 冬
5、线性结构和非线性结构 线性结构：一个非空的线性结构有且只有一个根结点，每个结点最多只有一个直接前驱、最多只有一个直接后继。 非线性结构：不是线性结构的数据结构。
15
编辑ppt
数据结构与算法
线性表及其顺序存储结构
1、线性表 线性表是由 n (n≥0)个元素组成的有限序列： (a1,a2,…,ai,…,an) ①有且只有一个根结点，它无直接前驱。 ②有且只有一个终端结点，它无直接后继。 ③除根结点和终端结点外，其他所有结点都有且只有一个直接前驱和直接后继。结点个数n称为线性表的长度。n=0时，称为空表。
2、线性表的顺序存储 顺序存储也称为顺序分配 线性表中所有元素所占的存储空间是连续的 线性表中各元素在存储空间中按照逻辑顺序依次存储
3、顺序表的运算 线性表的顺序存储结构通常称为顺序表 包括：插入、删除、查找、分解、合并、复制、 逆转等。 在高级语言中，顺序表对应一维数组。 顺序表的查找方便，插入和删除较麻烦。
16
编辑ppt
数据结构与算法
线性表及其顺序存储结构
注意： ① 线性表属于线性结构。 ② 线性表的顺序存储结构通常称为顺序表。 ③ 在顺序表中，所有元素按照其逻辑顺序连续存储，前后件元素紧邻，前件元素一定存储在后件元素的前面。逻辑上相邻的数据元素物理上也相邻 ④ 在程序设计语言中，线性表的顺序存储结构对应了一维数组。因为在程序设计语言中，一维数组与计算机中实际的存储空间结构是一致的。 ⑤ 在顺序表中，如果要在第 i 个位置插入一个新元素，则原第 i 个元素以及之后的所有元素都要依次后移一个位置。在平均情况下，在顺序表中插入一个新元素，需要移动 n/2 个元素。 ⑥ 在顺序表中，如果要删除第 i 个位置的元素，则原第 i 个元素之后的所有元素都要依次前移一个位置。在平均情况下，在顺序表中删除一个元素，需要移动 n/2 个元素。
17
编辑ppt
数据结构与算法
栈及其基本运算
1、栈 栈(stack)是限定在一端进行插入和删除的线性表 允许进行插入或删除的一端称为栈顶。 不允许进行插入或删除的另一端称为栈底。 其特点为“先入后出”(FILO)或“后入先出”(LIFO)。(记忆作用) 通常设置指针top指向栈顶，指针bottom指向栈底。
2、栈的顺序存储结构 栈的各个数据元素按其逻辑顺序依次连续存储。 由于插入删除操作只能在栈顶一端进行，所以 不需要移动数据元素。
3、栈的基本运算 入栈：在栈顶位置插入新元素。 出栈：取出栈顶位置的元素。 读栈顶元素：读出栈顶位置的元素。 “上溢”：入栈时堆栈已满。 “下溢”：出栈时堆栈已空。
18
编辑ppt
数据结构与算法
队列及其基本运算
1、队列 队列(queue)是限定在一端进行插入另一端进行删除的线性表 允许进行插入的一端称为队尾。 允许进行删除的另一端称为队头。 其特点为“先入先出”(FIFO)或“后入后出”(LILO)。(先来先服务