1、基本数据结构及算法.ppt

全国计算机等级考试二级 公共基础知识 基本数据结构与算法 公共基础知识 基本要求1. 掌握算法的基本概念。2. 掌握基本数据结构及其操作。3. 掌握基本排序和查找算法。4. 掌握逐步求精的结构化程序设计方法。5. 掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。6. 掌握数据的基本知识，了解关系数据库的设计 一、数据结构与算法 二、程序设计基础 三、软件工程基础 四、数据库设计基础 数据结构与算法 1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5. 线性单链表、双向链表与循环链表的结构及其基本运算。6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。 一.算法的基本概念 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。 1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。2.算法的基本要素：算法中对数据的运算和操作、算法的控制结构。3.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。4.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求 在计算机中，算法是指______。(C)A. 查询方法B. 加工方法C. 解题方案的准确而完整的描述D. 排序方法 二.算法的复杂度1.算法的时间复杂度：指执行算法所需要的计算工作量(基本运算次数) 2.算法的空间复杂度：执行这个算法所需要的内存空间 算法的复杂度的表示 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n)) 表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。 空间复杂度：算法所需存储空间的量度。记作：S(n)=O(f(n)) 算法的时间复杂度是指______。(C)A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数 下面叙述正确的是______。(C)A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令（或语句）的条数C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对 算法的空间复杂度是指______。(D)A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 算法执行过程中所需要的存储空间 算法一般都可以用哪几种控制结构组合而成______。(D)A. 循环、分支、递归B. 顺序、循环、嵌套C. 循环、递归、选择D. 顺序、选择、循环 算法的复杂度主要包括______复杂度和空间复杂度。答：时间 三.数据结构的定义 数据结构：相互之间存在一种或多种特定关系的数据元素的集合 1.数据的逻辑结构：反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。2.数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构，又称存储结构。常用的存储结构有顺序、链接、索引等存储结构。 数据的逻辑结构在计算机存储空间中的存放形式称为数据的______。答：存储结构 数据的存储结构是指______。(B)A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据 四.数据结构的图形表示：在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点。插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。 （1）集合：松散的关系。 （2）线性结构:一对一 （3）树形结构:一对多 （4）图状结构:多对多 五.线性结构和非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构和非线性结构。线性结构：非空数据结构满足：有且只有一个根结点；每个结点最多有一个前件，最多只有一个后件。 非线性结构：如果一个数据结构不是线性结构，称之为非线性结构。常见的线性结构：线性表、栈、队列