第五章 数据结构与算法（复习课件）信息技术浙教版2019选择性必修1

复习课件 第五章 数据结构与算法 浙教版（2019） 选修一 数据结构与算法效率 01 迭代与递归 02 数据排序 03 数据查找 04 复习内容总览 数据结构与算法效率 PART 01 第1节 数据结构与算法效率 知识结构 第1节 数据结构与算法效率 知识点一 算法是解决某一特定类型问题的有限求解步骤。描述一个算法可以采用某一计算机语言，也可以才用自然语言和流程图等。 1 2 算法效率 时间复杂度 反映了算法执行所需要的时间 空间复杂度 反映了算法执行所需要占用的存储空间 算法效率的高低可由算法复杂度来度量。 第1节 数据结构与算法效率 知识点一 算法运行需要时间，一般将算法中语句的执行次数作为时间复杂度的度量标准。语句 总的执行次数T(n)是关于问题规模n的函数。 所谓问题规模（也称为输入的大小）是指处理问题的大小，即用来衡量输入数据量的整数。 在约瑟夫问题中，用数组或链表中元素的个数作为问题规模。 1 2 3 第1节 数据结构与算法效率 知识点一 时间复杂度常用符号〇表示，不包括T(n)函数的低阶项和首项系数如-(n-1)的量级与n2相同，其时间复杂度可表示成〇(n2)。 用〇()来体现算法时间复杂度，称之为大〇记法。 输入规模 不管使用什么算法，输入规模越大，运行效率肯定会更长。 算法的平均效率、最差效率和最优效率 在输入最优情况下的算法就叫最优效率。 在输入最坏情况下的算法就叫最差效率。 增长次数 在大规模的输入情况下考虑执行次数的增长次数。 1 2 3 在分析算法的时间复杂度时，我们需要知道三个方面： 第1节 数据结构与算法效率 知识点二 数据结构与算法的关系 在计算机科学中，数据结构与算法有着密不可分的关系。解决实际问题时，数据总是以一定的组织结构关系体现并存储，数据结构的设计和选择关注的是数据的逻辑结构、存储结构以及基本操作；算法的设计和选择更多的是关注如何在数据结构的基础上综合运用各种基本操作来解决实际问题。 数据组织成不同的结构，是为了满足不同问题的需求，便于算法对数据的操作，提高孙发处理数据的效率。算法的设计和选择总是依赖于数据结构，算法设计的同时也伴随着数据结构设计，两者都是为最终解决问题服务。算法是编程思想，数据结构则是这些思想的基础。 第1节 数据结构与算法效率 提升练习 1.下列有关算法的时间复杂度的说法,错误的是( ) A.如果时间复杂度为常数,则时间复杂度为〇(0) B.仅包含顺序结构的算法的时间复杂度为〇(1) C.如果算法中语句的执行次数与问题规模n呈线性增大关系,则时间复杂度为〇(n) D.如果算法中语句的执行次数与问题规模n呈平方增大关系,则时间复杂度为〇(n2) A 解析 本题主要考查的是时间复杂度的表示。如果时间复杂度为常数,则时间复杂度为〇(1),因此答案为A。 第1节 数据结构与算法效率 提升练习 2.某同学网购的书,三本书是三个不同的物流公司派送的,将图中每个节点进行编号,作为根节点的“家”编号为“H”其3个子节点(快递门店A，快递门店 B，快递门店 C)分别编号为“A”“B”“C”，图中两结点的连接线表示“权”,值为用时，详见下图。依次列出所有可能走法的分析树，求出取书用时最短时的路径，下列选择正确的是( ) A 解析 将图中的图结构可以转换为下图的数结构，依次计算每一种情况。其中路径H-A-C-B-H、H-B-C-A-H用时最短，其时长为2+6+4+5=17故选:A。 A.H-A-C-B-H B.H-C-B-A-H C.H-A-B-C-H D.H-B-A-C-H 第1节 字符串 提升练习 3.有如下 Python程序代码: n=int(input("please input n:")) s=0 for i in range(n-1): for j in range(n): s=s+i print("s=",s) 则该程序的时间复杂度为( ) A.〇(1) C.〇(logzn) B.〇(n) D.〇(n2) D 解析 本题程序使用的是二重循环,外循环共执行n一1次,内循环共执行n次,因此,时间复杂度为 〇(n),答案为 D。 迭代与递归 PART 02 第2节 迭代与递归 知识结构 第2节 迭代与递归 知识点一 概念 迭代是重复反馈的过程，其目的通常是为了接近并达到所需的目标或结果。每一次对过程的重复被称为一次迭代，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。 特性 迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令(或一定步骤)这组指令(或这些步骤)每执行一次，都会将变量从原值推出一个新值。 第2节 迭代与递归 知识点一 03 02 01 利用迭代算法解决问题， 需要做好三个方面 确定迭代变量 在能够用迭代算法处理问题中，至少具有一个直接或间接地不断有旧值推出新值的变量，这个变量就是迭代变量。 建立迭代关系式 所谓迭代关系式，指如何从变量的前一个值推出下一个值的公式(或关系)。 控制迭代过程 迭代过程在经过若干次重复执行以后要能结束，因此，要设定迭代结束的条件。 (元素的入栈顺序和出栈顺序相反) 迭代算法的设计方法 第2节 迭代与递归 知识点二 概念 在计算机科学中，指一种通过重复将问题分解为同类的子问题而解决问题的方法，它通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。 把大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，规模较小的又转化为规模更小的问题求解，当问题小到一定程度时，可以直接得出它的解，从而回归求解问题原来的解。即“大事化小，小事化了”的思想。 1、每一步解决问题的方法有一致的规律：递归公式 2、可以达到某个边界条件：递归出口 能使函数的定义和算法的描述简洁且易于理解，极大地减少程序代码量。 思想 条件 作用 第2节 迭代与递归 知识点二 特征 为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，递归核心整体方法和局部方法是一致的。 迭代：速度快，效率高；但程序冗杂 递归：程序简洁易懂；但速度慢，效率低 解题技巧 1.某二下列有关迭代算法和递归算法的描述，不正确的是( ) A.在使用递归算法时，必须有一个明确的递归结束条件，称为递归出口 B.一般来说，迭代算法效率较低，而递归算法效率较高 C.递归中一定有迭代，但迭代中不一定有递归 D.通常情况下，迭代算法和递归算法可以相互转换 解析 [解析]迭代算法通常效率较高，而递归算法可能效率较低。这是因为递归算法在递归调用时需要保存上下文，包括局部变量和返回地址，而这可能导致开销较大。此外，递归算法在递归深度较深时可能引起栈溢出，因此需要小心处理递归深度。所以选项B符合题意。故选:B。 B 解题技巧 2.下列程序代码采用的算法是( ) def mi (x,n): if n==0: return 1 else: return x*mi (x,n-1) A.迭代法 B.枚举法 C.递归法 D.解析法 解析 [解析]递归算法是一种直接或者间接调用自身函数或者方法的算法。说简单了就是程序自身的调用。分析本题代码可知采用的算法是递归法。故选:C。 c 解题技巧 3.定义如下函数: def f(s): if len(s)==1: return s[0] elif len(s)==2: return s[0]+s[1] else: return f(s[0:len(s)//3])+f(s[len(s)//3:len(s)]) 执行语句s-f([1,2,3,4,5,6]),函数f被调用的次数是( ) A.3 B.5 C.7 D.15 解析 递归过程如下所示,s=f([1,2,3,4,5,6]),调用1次;f([1,2,3,4,5,6])，return f([1,2])+f([3,4,5,6]),调用2次;f([3,4,5,6]),return f([3])+f([4,5,6]),调用2次;f([4,5,6]),return f([4])+f([5,6]),调用2次;累计7次。 C 数据排序 PART 03 第3节 数据排序 知识结构 第3节 数据排序 知识点一 概念 将无序数据按照某种规则(递增或递减)，重新排列使其变成有序数据。 (元素的入 对一次具体排序而言，总是针对某一组数据元素的某种具体的序关系进行操作。 通过关键字之间的比较判断，将数据移到合适的位置 对链表进行排序无须移动数据，只需修改指针即可 未排序数据的存储方式 以数组作为存储结构 以链表作为存储结构 第3节 数据排序 知识点二 Python中的排序函数 Python中，对列表进行排序的方法有两种：一种是列表自带的sort方法，只适用于列表，直接对列表进行排序，不会产生新的序列；另外一种是内建函数sorted方法，返回一个新的序列，而原来的序列依然存在。 冒泡排序（Bubble Sort）是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。 第3节 数据排序 知识点二 (元素的入 在选取排序算法时，可以根据待排序数据自身的特点来选择相应的算法。 时间 复杂度 空间 复杂度 稳定性 第3节 抽象数据类型的描述 知识点二 描述 定义一个抽象数据类型，需要清晰地表述出各方面的形式要求（操作的名字、参数的个数和类型等）和功能要求（希望这个操作完成什么样的计算或产生什么效果等）。 当然，还需要为这一抽象数据类型确定一个类型名。 描述抽象数据类型的标准格式 解题技巧 1.某场篮球联赛中，有5个班级的比赛积分依次为14,11,13,8,9。若 采用冒泡排序算法从右到左对其进行升序排序，则第二轮排序后的结果是 ( ) A.8,11,13,14,9 B.8,9,13,14,11 C.8,9,14,11,13 D. 14,13,11,9,8 解析 [解析]据题意:该数组进行从小到大排序第1种情况:从数组第1个到最后一个元素向后走访数组，进行数据比较，则: 第一趟:14与11比较并交换，14与13比较并交换，14与8比较并交换，14与9比较并交换，数组顺序为:11，13，8，9，14。第二趟:11与13比较，13与8比较并交换，13与9比较并交换，13与14比较，数组顺序为:11，8，9，13，14.这种情况，选项里没有答案，故放弃。第2种情况:从数组最后一个到第1个元素向前走访数组，进行数据比较，则:第一趟:9与8比较，8与13比较并交换，8与11比较并交换，8与14比较并交换，数组顺序为:8，14，11，13，9。第二趟:9与13比较并交换，9与11比较并交换，9与14比较并交换，9与8比较，数组顺序为:8，9，14，11，13。故选:C。 C 解题技巧 2.某 Python程序如下： a=[3,1,9,7,6,3] n=len(a) for i in range(1,n): for j in range(n-2,i-2,- 1): if a[jka[j+1]: a[j],a[j+1]=a[j+1],a[j] 程序运行后，数组a的值是（ ） A.[9,3,1,7,6,3] B.[9,7,6,3,3,1] C.[1,3,3,9,7,6] D.[1,3,3,6,7,9] 解析 [解析]程序功能是使用冒泡排序算法对数组a进行降序排序。注意比较的两个相邻元素是a[j]和a[j+1],故变量j的取取值范围为 range(n-2,i-2,-1)。 B 解题技巧 3.某 Python程序如下： a=[92,22, 11,98,96,71] n=len(a) for i in range(n): for j in range( ): if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] print(a) 为实现n个数的升序排序，划线处应填入的代码是 。 解析 [解析]本题主要考查冒泡排序算法。分析程序,外层循环变量i的范围是0~n-1,该程序实现升序排序,比较的是索引j与j+1,内层循环可以从左往右比较,每次将一个最大值放到最右边,代码为ange(n-i-1);也可以从右往左比较交换,每次将一个最小值放到最左边,代码为 range(n-2,i-1,-1)。 range(n-2,i-1,-1) 数据查找 PART 04 第4节 数据查找 知识结构 第4节 数据查找 知识点一 概念 查找（Search）又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。 返回特定值，表明查找失败； 表明查找成功，一般要求返回该对象的存储位置或对象值本身。 查找 没有找到满足条件的对象 查找到满足条件的对象 第4节 数据查找 知识点二 顺序查找 1 算法思想 算法特点 从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据与给定值相等，则查找成功，记录所查数据的位置；反之，则查找不成功。 算法简单，对数据是否有序没有要求。 查找效率较低，当数据量大时不宜使用。 01 02 第4节 数据查找 知识点二 二分查找 2 算法思想 二分查找（Binary Search）又称折半查找、对分查找。 首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，则根据有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。 算法特点 要求被查找数据必须有序。 查找效率非常高，适用于大数据查找。 01 02 在数组中的数据是有序的，若是升序的，是指下标越小的数组元素中存储的数据也越小，降序则相反。 第4节 数据查找 知识点二 基本方法 为简单起见，设数组d中存储了n个互不相同的数据，并且数组d中的数据是升序的，则应有：d[0]＜d[1]＜…＜d[n–2]＜d[n–1]。 使用两个变量i和j分别记录查找范围内的第一个数组元素和最后一个数组元素的下标。开始时，整个数组中的所有n个元素都在查找范围内，即变量i的初值为0，j的初值 为n–1，用(i, j)表示查找范围从d[i]起到d[j]为止。 二分查找的基本方法是：在查找范围(i, j)内，可以利用数据的有序性，而不必逐个地进行查找。 ①首先确定该区间的中点位置： m= (i+j)/2」（m表示小于等于 的最大整数）。 第4节 数据查找 知识点二 key＜d[m]，查找键小于中点d[m]处的数据。因为数组d中的数据递增，可以确定在(m, j)内不可能存在值为key的数据，所以只需在新的范围(i, m–1)中继续查找。 key=d[m]，找到了需要的数据。 key＞d[m]，由与（a）相同的理由，只需在新的范围(m+1, j)中继续查找。 (a) (b) (c) ②然后将查找键key与d[m]比较，结果必然是如下三种情况之一： 在通过一次比较后，新的查找范围不会超过上一次查找范围的一半。 第4节 数据查找 知识点二 （1） 二分查找算法的递归实现 二分查找过程中的每一次判断都是将需要查找的值和数组的中间值进行不断的比较，直到找到或找遍整个序列。 （2） 二叉排序树 二叉排序树也称为二叉查找树，这种结构的二叉树既能实现排序功能，也能实现查找功能。 解题技巧 1.数组里有12个元素，依次为:34、40、41、43、53、55、65、70、72、74、80、95，下列选项中不正确的是( ) A.如使用顺序查找法，53需要查找5次 B.如使用对分法查找，53需要查找3次 C.如使用顺序查找法，70需要查找8次 D.如使用对分法查找，70需要查找4次 解析 [解析]顺序查找是比数据的第一个元素开始依次比较，AC两项分别查找53和70的次数为5次和8次，说法正确;B项对分查找53，i=1，j=12，m=(i+j)2=6，第6个元素为55，比53大，因此i=1，j=m-1=5，m=(i+j)\2=3，第3个元素为41,41比53小，i=m+1=4，j=5，m=(i+j)\2=4,第4个元素为43，43比53小，因此，i=m+1=5，j=5，m=(i+j)\2=5，第5个元素为53，找到元素，共查找了4次，而非3次;故选:B. B 解题技巧 2.已知单调函数f()在[0,1]区间上存在一个x0，使f(x0)=0。现用对分查找法搜索x0的值，开始搜索区间为[0,1]，若经过10次对分查找后还需继续搜索，则第11次搜索区间的长度为（ ） A.1/2 B.1/10 C.1/102 D.1/210 解析 [解析]由题知知f(x)是单调函数，意味着f(x)已按大小有序排列，根据对分查找的概念，开始搜索区间为[0,1]，经过1次对分查找后，第2次的搜索长度变为1/2,经过2次对分查找后，第3次的搜索长度变为1/22...经过10次对分查找后，第11次的搜索长度变为1/210，故选D。 D 解题技巧 3.某查找算法的代码如下: key=int(input( )) S=0 a=[3,5,8,10,5,6,9,5,36,35] for i in range(len(a)): if a[i]==key: S=S+1 print(s) 当输人key的值为5时,执行该代码处理后输出的结果是( ) A.0 B.1 C.2 D.3 解析 [解析]该代码是查找列表中5的个数,先人列表a中存在3个5,所以返回的值为3,故答案选D. D 第5章 数据结构与算法 浙教版（2019） 选修一 谢谢观看 $$