第五章 数据结构与算法（知识清单）信息技术浙教版2019选择性必修1

第五章 数据结构与算法 （知识清单） 【知识结构】 【考点清单】 1.算法是解决某一特定类型问题的有限求解步骤。描述一个算法可以采用某一计算机语言，也可以才用自然语言和流程图等。 2.算法效率的高低可由算法复杂度来度量。算法复杂度又分为算法的时间复杂度和空间复杂度，其中时间复杂度反映了算法执行所需要的时间，而空间复杂度反映了算法执行所需要占用的存储空间。 3.用O( )来体现算法时间复杂度，称之为大O记法。 4.时间复杂度常用符号〇表示，不包括T(n)函数的低阶项和首项系数如-(n-1)的量级与n2相同，其时间复杂度可表示成〇(n2)。 5.常见的时间复杂度耗费时间的大小关系为：〇(1)＜〇(log2n)＜〇(n)＜〇(n2)＜〇(n3)＜〇(2n)＜〇(n!)。 6.在分析算法的时间复杂度时，我们需要知道三个方面：（1）输入规模（2）算法的平均效率、最差效率和最优效率（3）增长次数。 7.在以顺序查找算法为例： 算法的最差效率：n个数据，在最后一次判断才找到，效率为n。 算法的最优效率：n个数据，第一次就判断就找到，效率为1 算法的平均效率：n个数据，我们先假设能找到的概率，然后我们需要求得在第一次查找到的概率、第二次查找到的概率等等一直求，然后算得总的操作次数，得出算法的平均效率 8.迭代是重复反馈的过程，其目的通常是为了接近并达到所需的目标或结果。每一次对过程的重复被称为一次迭代，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。 9.迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令(或一定步骤)这组指令(或这些步骤)每执行一次，都会将变量从原值推出一个新值。 10.用迭代算法解决问题，需要做好三个方面：确定迭代变量、建立迭代关系式、控制迭代过程。 11.迭代算法：利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令，这组指令每执行一次时，都会将变量从原值递推出一个新值，即由旧值不断推出新值的过程。 12.欧几里得算法又称辗转相除法，用于计算两个整数m，n的最大公约数。基于定理：gcd(m,n)=gcd(n, m mod n) 即：整数m，n的最大公约数等于n和m除以n的余数的最大公约数。欧几里得算法在执行时，也是一个反复迭代的过程，直到余数等于0为止。 13.在计算机科学中，递归指一种通过重复将问题分解为同类的子问题而解决问题的方法，它通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。 14.在设计递归算法时，要满足两个条件：确定递归公式和递归结束条件。 15.计算机在执行递归程序时，是通过栈的调用来实现的。递归程序是将复杂问题分解为一系列简单的问题，从要解的问题起，逐步分解，并将每步分解得到的问题放入“栈”中，运用栈的“后进先出”的性质，这样栈顶是最后分解得到的最简单的问题，解决了这个问题后，次简单的问题可以得到答案，以此类推。所以，分解问题可以看作是进栈的过程，而解决问题则是出栈的过程。 16.递归是重复调用函数自身实现循环；迭代是函数内某段代码实现循环。 17.排序（sorting）就是整理数据的序列，使其中元素按照某个值的递增（或递减）的次序重新排列的操作。在排序的过程中，数据元素的值保持不变，但其在序列中的顺序可能会改变。 18.对一次具体排序而言，总是针对某一组数据元素的某种具体的序关系进行操作。待排序数据的存储方式一般有两种：一种是将数据依次存放在一组地址连续的存储单元中，即以数组作为存储结构。在这种情况下，排序过程是对数据本身进行物理重排，即通过关键字之间的比较判断，将数据移到合适的位置。另一种存储方式是以链表作为存储结构，排序过程中无须移动数据，仅需修改指针即可。 19.Python中，对列表进行排序的方法有两种：一种是列表自带的sort方法，只适用于列表，直接对列表进行排序，不会产生新的序列；另外一种是内建函数sorted方法，返回一个新的序列，而原来的序列依然存在。 20.冒泡排序（Bubble Sort）是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。 21.常见的排序算法还有选择排序、插入排序、快速排序、堆排序、归并排序、桶排序等。 22.查找（Search）又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。 23.顺序查找（Sequential Search）又称线性查找，从顺序表的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。 24.二分查找（Binary Search）又称折半查找、对分查找。它是一种效率很高的查找方法，但被查找的数据序列必须是有序的。二分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素的数值与查找键不同，根据数组元素的有序性，就可确定在数组的前半部分还是后半部分继续查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 25.二分查找过程中的每一次判断都是将需要查找的值和数组的中间值进行不断的比较，直到找到或找遍整个序列。 26.二叉排序树也称为二叉查找树，这种结构的二叉树既能实现排序功能，也能实现查找功能。 27.二叉查找树的查找过程为：首先将给定值和根节点的关键字比较，若相等，则查找成功；若不相等，则根据给定值和根节点关键字之间的大小关系，在左子树或右子树中继续进行查找。若查到为空树时，说明该树中没有待查记录，故查找不成功。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$