二级公共基础知识1-数据结构与算法1

全国计算机二级培训课件————李文琴QQ：387724525全国计算机等级考试二级公共基础知识(1)1.数据结构与算法1.2数据结构的基本概念★★★★★1.3线性表的顺序存储1.4栈和队列★★★计算机二级1.1算法基本概念及算法评价★★★★★第一章数据结构与算法1.6树与二叉树★★★★★1.7查找与排序★★1.5线性表的链式存储计算机二级第一章数据结构与算法1.1算法基本概念及算法评价1.1.1算法考点1算法的定义算法是用来解决某个特定类型问题的有限运算序列。简单的说：算法就是解决问题的方法.eg.程序是用计算机语言表达的算法;流程图是图形化的算法计算机二级第一章数据结构与算法算法特征：（1）有穷性：一个算法（对任何合法的输入）在执行有穷步后能够结束，并且在有限的时间内完成。（2）确定性：算法中的每一步都有确切的含义。（3）可行性：算法中的操作能够用已经实现的基本运算执行有限次来实现。（4）输入：一个算法有零个或者多个输入，零个输入就是算法本身确定了初始条件。（5）输出：一个算法有一个或者多个输出，以反映出数据加工的结果。（拥有足够的情报）计算机二级第一章数据结构与算法例1.问题处理方案的正确而完整的描述称为______。[2005年4月填空第5题]例2.以下叙述中正确的是(A)用C语言实现的算法必须要有输入和输出操作(B)用C语言实现的算法可以没有输出但必须要有输入(C)用C程序实现的算法可以没有输入但必须要有输出(D)用C程序实现的算法可以既没有输入也没有输出[2005年9月选择题第13题]例3.算法具有五个特性,以下选项中不属于算法特性的是(A)有穷性(B)简洁性(C)可行性(D)确定性[2005年4月选择题第11题]计算机二级第一章数据结构与算法2算法的基本要素(1)算法中对数据的运算和操作：在一般的计算机系统中，基本的运算和操作有以下4类：①算术运算②逻辑运算③关系运算④数据传输：主要包括赋值、输入、输出等操作。(2)算法的控制结构：一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。第一章数据结构与算法3算法设计的基本方法(1)列举法---根据提出的问题列举所有可能的情况，并用问题中给定的条件检验哪些是需要的而哪些是不需要的；(2)归纳法---通过列举足够多的特殊情况发现其中一些规律，经过分析最终找出一般的关系；(3)递推法---从已知的初始条件出发，逐次地推出所要求的各中间结果和最后结果；(4)递归法---首先将问题逐层分解最后归结为一些最简单的问题，解决这些最简单问题后再沿着原来分解的逆过程逐步进行综合。(5)减半递推技术---工程上常用的分治法，即将问题的规模减半来解，最后重复“减半”的过程；(6)回溯法---在处理复杂数据结构时，通过对问题的分析找出一个解决问题的线索，然后沿着次线索逐步试探，若失败就逐步回退并换别的路线再进行试探；计算机二级第一章数据结构与算法考点2算法的复杂度1.算法设计的要求：（一个好的算法要达到的目标）(1)正确性(2)健壮性(3)可读性(4)效率与低存储量的要求2.算法效率的度量1)算法的时间复杂度算法的执行时间=每条语句执行时间之和；每条语句执行时间=语句执行（频度）次数*语句执行一次所需时间；独立于软硬件系统来分析算法的时间耗费可以设每条语句执行时间均为一个单位时间算法的执行时间=所有语句频度之和计算机二级第一章数据结构与算法算法所执行的运算次数是问题规模的函数（f(n)）在同一问题规模下，算法中的执行的次数还随问题的输入数据集不同而不同，这时采用以下两种方法来分析算法的时间复杂度：(1)平均性态(AverageBehavior)所谓平均性态是指各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。设x是所有可能输入中的某个特定输入，p(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为：A(n)=∑p(x)t(x)x∈DnDn表示当规模为n时，算法执行的所有可能输入的集合。计算机二级第一章数据结构与算法(2)最坏情况复杂性(Worst-caseComplexity)所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。例：采用顺序搜索法，在长度为n的一维数组中查找值为x的元素，即从数组的第一个元素开始，逐个与被查值x进行比较。平均形态分析（(n+1)/2）最坏情况分析(n)2)算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。计算机二级第一章数据结构与算法例1.算法复杂度主要包括时间复杂度和【1】复杂度。[2005年9月填空第2题]例2.对长度为N的线性表(一维数组)进行顺序查找,在最坏的情况下所需要的比较次数为[2005年4月选择第4题](A)log2n(B)n/2(C)n(D)n+1。计算机二级第二节数据结构基本概念1.2数据结构的基本概念1.2.1数据结构考点3数据结构的定义：数据结构(datastructure)是指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。数据+关系数据结构学科，主要研究和讨论以下三个方面：(l)数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；(2)在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；(3)对各种数据结构进行的运算。计算机二级第二节数据结构基本概念基本概念：（1）数据(data)：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。（2）数据元素(dataelement)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。（3）数据对象(dataobject)：是性质相同的数据元素的集合。（数据元素是数据对象的一个实例）例如：所有书的书目信息为数据对象，每一条书目信息为数据元素。计算机二级第二节数据结构基本概念（4）数据的逻辑结构：对数据元素之间逻辑关系的描述。一个数据结构应该包含两方面的信息：数据元素的集合和定义在这个集合上的关系来表示。（二元组表示）B=(D,R)D:数据元素的集合;R:D上关系的集合例如：一年四季的数据结构可以表示成B={D,R}D=(春，夏，秋，冬)R={春，夏，夏，秋，秋，冬，冬，春}家庭成员数据结构可以表示成B={D,R}D=(父亲，儿子，女儿)R={父亲，儿子，父亲，女儿}计算机二级第二节数据结构基本概念（5）数据的存储结构数据的逻辑结构在计算机中存储空间中的存放形式称为数据的存储结构（物理结构）。1）顺序存储方式（向量存储）2）链式存储方式3）索引存储方式计算机二级第二节数据结构基本概念考点4数据结构的图形表示数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。（有时可省略箭头）例如：一年四季的图形表示：春夏秋冬计算机二级第二节数据结构基本概念例如：反映家庭成员辈分关系的图形表示：例如：用图形表示数据结构B=(D,R),其中D={Ki|1≦i≦8}R={k1,k2,k1,k3,k3,k4,k3,k5,k4,k7,k4,k6,k5,k8}??????父亲儿子女儿计算机二级第二节数据结构基本概念1.2.3线性结构与非线性结构考点5线性结构与非线性结构如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。根据数据结构中各数据元素之间逻辑关系，一般将数据结构分为两大类型：线性结构与非线性结构。非空数据结构满足：(l)有且只有一个没有前件的结点；(2)每一个结点最多有一个前件（直接前驱），也最多有一个后件（直接后继）。则称该数据结构为线性结构。计算机二级1.3线性表的顺序存储结构及链式存储1.3.1线性表的基本概念考点61.线性表的定义线性表是n(n≥0)个元素构成的有限序列(a1，a2，…，an)。n=0时称为空表2.线性表的特性：(1)当1in时，ai的直接前驱为ai-1,ai的直接后继为ai+1(2)除了第一个元素与最后一个元素,序列中任何一个元素有且仅有一个直接前驱元素,有且仅有一个直接后继元素。第三节线性表计算机二级1.3.2考点7线性表的顺序存储结构用一组地址连续的存储单元依次存储线性表中的数据元素，数据元素之间的逻辑关系通过元素的存储位置直接反映。第三节线性表内存状态存储地址元素在线性表中的次序b=ADR(a1)b+kb+(i-1)*kb+(n-1)*kb+(max-1)*k12in空闲a1a2…ai…an顺序存储的线性表的寻址公式：ADR(ai)=ADR(a1)+(i-1)*k1≤i≤nADR(a1)为线性表的第一个元素a1的存储地址k为每个元素所占的存储单元个数计算机二级线性表的顺序存储结构特点：(1)线性表中所有元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在程序设计语言中用一维数组来表示线性表的顺序存储空间。第三节线性表顺序存储的优点1.可以随机存取2.空间利用率高3.结构简单计算机二级考点8线性表的插入运算在长度为n的线性表L的第i个位置上插入一个新的数据元素X第三节线性表插入前：元素序号12345678插入27插入后：元素序号1234567892831437811142520283143781114252027主要操作1.将第i到n个元素依次后移一个位置2.将新元素x放到线性表的第i个位置3.将线性表的表长由n修改为n+1计算机二级插入运算时间复杂度分析:第三节线性表若设pi为插入一个元素于线性表第i个位置的概率(概率相等)，则在长度为n的线性表中插入一个元素需要移动元素的平均次数（期望值）为：Pi(i=1,2,…,n,n+1)(其中pi=1/(n+1)）T=Pi(n-i+1)=(n-i+1)/(n+1)=n/2称该算法的时间复杂度是O(n)。n+1i=1n+1i=11C2D(1)在计算机中，算法是指______。A.查询方法B.加工方法C.解题方案的准确而完整的描述D.排序方法(2)算法一般都可以用哪几种控制结构组合而成______。A.循环、分支、递归B.顺序、循环、嵌套C.循环、递归、选择D.顺序、选择、循环复习题(3)一个算法应该具有“确定性”等5个特性，下面对另外4个特性的描述中错误的是A)有零个或多个输入B)有零个或多个输出C)有穷性D)可行性(4)算法分析的目的是______。A.找出数据结构的合理性B.找出算法中输入和输出之间的关系C.分析算法的易懂性和可靠性D.分析算法的效率以求改进3B4D5C6D解析：算法的复杂度主要包括算法的时间复杂度和空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度一般是指执行这个算法所需要的内存空间。(5)算法的时间复杂度是指______。A.执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数D.算法程序中的指令条数(6)算法的空间复杂度是指______。A.算法程序的长度B.算法程序中的指令条数C.算法程序所占的存储空间D.算法执行过程中所需要的存储空间7A(7)下列对于线性表的描述中正确的是A)存储