李赛红 2011-03全国计算机等级考试全国计算机等级考试二级公共基础知识（一）河海大学文天学院教育培训中心河海大学文天学院教育培训中心1.数据结构与算法数据结构与算法1.2 1.2 数据结构的数据结构的基本概念基本概念 1.3 1.3 线性表的顺序存储线性表的顺序存储1.4 1.4 栈和队列栈和队列 1.1 1.1 算法基本概念及算法评价算法基本概念及算法评价 第一章第一章数据结构与算法数据结构与算法1.6 1.6 树与二叉树树与二叉树 1.7 1.7 查找与排序查找与排序 1.5 1.5 线性表的链式存储线性表的链式存储第一章第一章数据结构与算法数据结构与算法1.1 1.1 算法基本概念及算法评价算法基本概念及算法评价 1.1.1 1.1.1 算法算法 考点考点1 1 算法的定义算法的定义 算法是用来解决某个特定类型问题的有限运算序列。简算法是用来解决某个特定类型问题的有限运算序列。简单的说：单的说：算法就是解决问题的方法算法就是解决问题的方法. . eg. eg.程序是用计算机语言表达的算法程序是用计算机语言表达的算法; ; 流程图是图形化的算法流程图是图形化的算法 第一章第一章数据结构与算法数据结构与算法算法特征：算法特征： （1 1）有穷性：一个算法（对任何合法的输入）在执行有）有穷性：一个算法（对任何合法的输入）在执行有穷穷步后能够结束步后能够结束，并且在有限的时间内完成。，并且在有限的时间内完成。（2 2）确定性：算法中的每一步都有）确定性：算法中的每一步都有确切确切的含义。的含义。（3 3）可行性：算法中的操作能够用已经实现的基本运算执）可行性：算法中的操作能够用已经实现的基本运算执行有限次来实现。行有限次来实现。（4 4）输入：一个算法有）输入：一个算法有零个零个或者多个输入或者多个输入，零个输入就是，零个输入就是算法本身缺定了初始条件。算法本身缺定了初始条件。（5 5）输出：一个算法有）输出：一个算法有一个一个或者多个输出或者多个输出，以反映出数据，以反映出数据加工的结果。加工的结果。 （拥有足够的情报）（拥有足够的情报） 第一章第一章数据结构与算法数据结构与算法例例1. 1. 问题处理方案的正确而完整的描述称为问题处理方案的正确而完整的描述称为_。20052005年年4 4月月 填空第填空第5 5题题 例例2. 2. 以下叙述中正确的是以下叙述中正确的是(A)(A)用用C C语言实现的算法必须要有输入和输出操作语言实现的算法必须要有输入和输出操作 (B)(B)用用C C语言实现的算法可以没有输出但必须要有输入语言实现的算法可以没有输出但必须要有输入 (C)(C)用用C C程序实现的算法可以没有输入但必须要有输出程序实现的算法可以没有输入但必须要有输出 (D)(D)用用C C程序实现的算法可以既没有输入也没有输出程序实现的算法可以既没有输入也没有输出 20052005年年9 9月月 选择题第选择题第1313题题 例例3. 3. 算法具有五个特性算法具有五个特性, ,以下选项中不属于算法特性的是以下选项中不属于算法特性的是 (A)(A)有穷性有穷性(B)(B)简洁性简洁性(C)(C)可行性可行性(D)(D)确定性确定性 2005年年4月月选择题第选择题第11题题算法算法C CB B第一章第一章数据结构与算法数据结构与算法第一章第一章数据结构与算法数据结构与算法3 3算法设计的基本方法算法设计的基本方法(1)(1)列举法列举法-根据提出的问题列举所有可能的情况，并用问题中给定的条件检根据提出的问题列举所有可能的情况，并用问题中给定的条件检验哪些是需要的而哪些是不需要的；验哪些是需要的而哪些是不需要的；(2)(2)归纳法归纳法-通过列举足够多的特殊情况发现其中一些规律，经过分析最终找通过列举足够多的特殊情况发现其中一些规律，经过分析最终找出一般的关系；出一般的关系；(3)(3)递推法递推法-从已知的初始条件出发，逐次地推出所要求的各中间结果和最后从已知的初始条件出发，逐次地推出所要求的各中间结果和最后结果；结果；(4)(4)递归法递归法-首先将问题逐层分解最后归结为一些最简单的问题，解决这些首先将问题逐层分解最后归结为一些最简单的问题，解决这些最简单问题后再沿着原来分解的逆过程逐步进行综合。最简单问题后再沿着原来分解的逆过程逐步进行综合。(5)(5)减半递推技术减半递推技术-工程上常用的分治法，即将问题的规模减半来解，最工程上常用的分治法，即将问题的规模减半来解，最后重复后重复“减半减半”的过程；的过程；(6)(6)回溯法回溯法-在处理复杂数据结构时，通过对问题的分析找出一在处理复杂数据结构时，通过对问题的分析找出一个解决问题个解决问题的线索，然后沿着次线索逐步试探，若失败就逐步回退并换别的路线再进行试的线索，然后沿着次线索逐步试探，若失败就逐步回退并换别的路线再进行试探；探；第一章第一章数据结构与算法数据结构与算法考点考点2 2 算法的复杂度算法的复杂度 1.1.算法设计的要求：（算法设计的要求：（一个好的算法要达到的目标一个好的算法要达到的目标） (1)(1)正确性正确性 (2)(2)健壮性健壮性 (3)(3)可读性可读性 (4)(4)效率与低存储量的要求效率与低存储量的要求 2.2.算法效率的度量算法效率的度量 1)1)算法的时间复杂度算法的时间复杂度 算法的执行时间算法的执行时间= =每条语句执行时间之和；每条语句执行时间之和； 每条语句执行时间每条语句执行时间= =语句执行（频度）次数语句执行（频度）次数 * * 语句执行一次所需时间；语句执行一次所需时间； 独立于软硬件系统来分析算法的时间耗费独立于软硬件系统来分析算法的时间耗费 可以设每条语句执行时间均为一个单位时间可以设每条语句执行时间均为一个单位时间 算法的执行时间算法的执行时间= =所有语句频度之和所有语句频度之和 第一章第一章数据结构与算法数据结构与算法算算法法复复杂杂度度第一章第一章数据结构与算法数据结构与算法例例1. 1. 算法复杂度主要包括时间复杂度和算法复杂度主要包括时间复杂度和 【1 1】 复复杂度。杂度。20052005年年9 9月月 填空第填空第2 2题题 例例2. 2. 对长度为对长度为N N的线性表的线性表( (一维数组一维数组) )进行顺序查找进行顺序查找, ,在最坏的情况下所需要的比较次数为在最坏的情况下所需要的比较次数为 20052005年年4 4月月 选择第选择第4 4题题 (A)log2n(A)log2n(B)n/2(B)n/2(C)n(C)n(D)n+1(D)n+1 。 空间复杂度空间复杂度C C第二节第二节数据结构基本概念数据结构基本概念1.2 1.2 数据结构的基本概念数据结构的基本概念1.2.1 1.2.1 数据结构数据结构 考点考点3 3 数据结构的定义数据结构的定义 ： 数据结构数据结构(data structure)(data structure)是指相互之间存在一种或多是指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。种特定关系的数据元素的集合，即数据的组织形式。 数据数据+ +关系关系数据结构学科，主要研究和讨论以下三个方面：数据结构学科，主要研究和讨论以下三个方面： (l)(l)数据集合中个数据元素之间所固有的逻辑关系，即数数据集合中个数据元素之间所固有的逻辑关系，即数据的据的逻辑结构逻辑结构； (2)(2)在对数据元素进行处理时，各数据元素在计算机中的在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储关系，即数据的存储结构存储结构； (3)(3)对各种数据结构进行的对各种数据结构进行的运算运算。 第二节第二节数据结构基本概念数据结构基本概念基本概念：基本概念： （1 1）数据）数据(data)(data)：是对客观事物的符号表示，在计算机：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符科学中是指所有能输入到计算机中并被计算机程序处理的符号的号的总称总称。 （2 2）数据元素）数据元素(data element)(data element)：是数据的：是数据的基本单位基本单位，在，在计算机程序中通常作为一个整体进行考虑和处理。计算机程序中通常作为一个整体进行考虑和处理。 （3 3）数据对象）数据对象(data object)(data object)：是性质相同的数据元素：是性质相同的数据元素的集合的集合。（数据元素是数据对象的一个实例）。（数据元素是数据对象的一个实例）例如：所有书的书目信息为数据对象，每一条书目信息为数据例如：所有书的书目信息为数据对象，每一条书目信息为数据元素。元素。第二节第二节数据结构基本概念数据结构基本概念（4 4）数据的逻辑结构）数据的逻辑结构 ： 对数据元素之间逻辑关系的描述。一个数据结构应该对数据元素之间逻辑关系的描述。一个数据结构应该对数据元素之间逻辑关系的描述。一个数据结构应该对数据元素之间逻辑关系的描述。一个数据结构应该包含两方面的信息：数据元素的集合和定义在这个集合上包含两方面的信息：数据元素的集合和定义在这个集合上包含两方面的信息：数据元素的集合和定义在这个集合上包含两方面的信息：数据元素的集合和定义在这个集合上的关系来表示的关系来表示的关系来表示的关系来表示. . . .（5 5）数据的存储结构）数据的存储结构 (物理结构) 数据的逻辑结构在计算机中存储空间中的存放形式称数据的逻辑结构在计算机中存储空间中的存放形式称数据的逻辑结构在计算机中存储空间中的存放形式称数据的逻辑结构在计算机中存储空间中的存放形式称为数据的存储结构（物理结构）。为数据的存储结构（物理结构）。为数据的存储结构（物理结构）。为数据的存储结构（物理结构）。1 1）顺序存储方式（向量存储）顺序存储方式（向量存储）2 2）链式存储方式）链式存储方式3 3）索引存储方式）索引存储方式第二节第二节数据结构基本概念数据结构基本概念考点考点4 4 数据结构的图形表示数据结构的图形表示 例如：一年四季的图形表示：例如：一年四季的图形表示：例如：反映家庭成员辈分关系的图形表示例如：反映家庭成员辈分关系的图形表示春春夏夏秋秋冬冬父亲父亲儿子儿子女儿女儿第二节第二节数据结构基本概念数据结构基本概念1.2.3 1.2.3 线性结构与非线性结构线性结构与非线性结构 考点考点5 5 线性结构与非线性结构线性结构与非线性结构 如果在一个数据结构中一个数据元素都没有，则称该数如果在一个数据结构中一个数据元素都没有，则称该数据结构为据结构为空空的数据结构。的数据结构。 根据数据结构中各数据元素之间逻辑关系，一般将数据根据数据结构中各数据元素之间逻辑关系，一般将数据结构分为两大类型：结构分为两大类型：线性结构与非线性结构线性结构与非线性结构。 非空数据结构满足：非空数据结构满足： (l)(l)有有且只有一个没有前件且只有一个没有前件的结点；的结点； (2)(2)每一个结点每一个结点最多有一个前件最多有一个前件（直接前驱），（直接前驱），也最多有也最多有一个后件（直接后继）。一个后件（直接后继）。则称该数据结构为则称该数据结构为线性结构线性结构。1.3 1.3 线性表的线性表的顺序存储顺序存储结构及结构及链式链式存储存储 1.3.1 1.3.1 线性表的基本概念线性表的基本概念考点考点6 6 1. 1.线性表线性表( (逻辑逻辑) )的定义的定义 线性表是线性表是n(n0)n(n0)个元素构成的有限序列个元素构成的有限序列(a1(a1，a2a2，an)an)。n=0n=0n=0n=0时称为空表时称为空表时称为空表时称为空表 2.2.线性表的特性：线性表的特性： (1) (1) 当当1in1inext=NULLB)p=NULLC) p-next=headC) p-next=headC) p-next=headC) p-next=headD)p=head循环链表的主要优点是A)不再需要头指针了B) 从表中任一结点出发都能访问到整个链表从表中任一结点出发都能访问到整个链表C)在进行插入、删除运算时，能更好的保证链表不断开D)已知某个结点的位置后，能够容易的找到它的直接前件线性表的顺序存储结构和线性表的链式存储结构分别是A)顺序存取的存储结构、顺序存取的存储结构B) 随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构C)随机存取的存储结构、随机存取的存储结构D)任意存取的存储结构、任意存取的存储结构当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为【1】。用链表表示线性表的突出优点是【2】。1、上溢上溢 2、便于插入和删除操作便于插入和删除操作刚才的发言，如刚才的发言，如有不当之处请多指有不当之处请多指正。谢谢大家！正。谢谢大家！64