专题一 算法与程序基础（讲义）-《算法与程序设计--C#》（河北科学技术出版社）高考备考讲练测（河北省）

专题一 算法与程序基础（讲义） ---《算法与程序设计-C#》专题复习讲练测 [考纲要求] 1．掌握算法的概念，理解算法描述方法，理解算法的设计步骤； 2．理解算法时间复杂度、空间复杂度等算法性能评价基本方法； 3．理解算法与程序的关系； 4．掌握下列典型算法：选择法、冒泡法、插入等排序算法，顺序查找、二分法查找等查找算法；递归算法；最值、均值、公约数、素数、累加、累乘、阶乘、回文数、斐波那契数列等数学算法；字符串的加密算法。 [课时安排] 2课时 [知识梳理] 一：算法的概念 算法就是解决问题的方法和步骤，而且步骤是有限的。 二：算法三要素 1.操作：操作包括以下几方面： （1）算术运算:加、减、乘、除。 （2）关系比较:大于、小于、等于、不等于。 （3）逻辑运算:与、或、非。 （4）数据传送:输入、输出、赋值(计算)。 2.控制结构：一个算法功能的实现不仅取决于所选用的操作，还取决于各操作之间的执行顺序，即控制结构。包括： （1）顺序结构:各操作是依次进行的。 （2）选择结构:由条件是否成立来决定选择执行。 （3）循环结构:有些操作要重复执行，直到满足某个条件时才结束，这种控制结构也称为重复或迭代结构。 3.数据结构：算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就是数据结构。 三：算法描述 1.自然语言：使用语言描述解决问题的过程 2.流程图：图形化描述 3.N-S图； 四：算法的重要特性 1.有穷性----算法的步骤是有限的，在有限的时间内完成。 2.确定性----算法都只有一条执行路径 3.可行性 4.算法有零个或多个的输入 5.算法有一个或多个的输出 五：算法复杂度 1.算法的时间复杂度 时间复杂度不是一个明确的执行时间，而是一个函数。用O(n)表示。时间复杂度通常使用大写的符号“O”, 表示算法执行时间与输入规模之间的关系。 2.算法的空间复杂度 一个算法空间复杂度S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。 对于一个算法，其时间复杂度与空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，反之，当追求一个较好空间复杂度时，可能会使时间复杂度的性能变差。算法的时间复杂度与空间复杂度合称为算法的复杂度。在设计一个算法时，要综合考虑算法的各项性能等。 六：算法与程序的关系 1.算法 算法是一种抽象的概念，是一种解决问题的方法，可以用自然语言、流程图、伪代码等形式来描述。算法的好坏直接影响程序的效率和质量。 2.程序 程序是算法的具体实现，它是一组指令的集合，用来告诉计算机如何执行某个任务。程序的好坏取决于算法的好坏和编程人员的水平。 算法和程序之间的关系非常密切。算法是程序的灵魂，程序是算法的具体实现。没有算法就没有程序，没有程序就没有算法的实现。 七：典型算法 1. 排序算法 (1) 选择排序 选择排序是最基础的算法。在要排序的一组数中，假设第一个元素是最小值，然后依次与后面的元素作比较，如果有更小的值，就让其交换位置，以此类推重复这样的操作，直到最后完成排序。 (2) 冒泡排序 冒泡排序就是从一组序列中的第一个元素开始，依次对相邻的两个元素进行比较，如果前一个元素大于后一个元素则交换它们的位置。反之，如果前一个元素小于或等于后一个元素，则不交换它们，以此类推。直到比较到最后一个元素为止。 (3) 插入排序 插入排序就是在排序开始前，设想有排序区和未排序区两个区域。并且先将这组序列的第一个元素看作在排序区里，其他元素再未排序区里。排序开始时，每次将未排序区第一个元素取出用于和排序区中元素比较(从后往前)，若满足条件（较大或者较小），则将排序区中元素往后移动一个位置。以此类推，直到完成排序。 2. 查找算法 （1） 顺序查找法 顺序查找也称线性搜索，是在一个已知无(或有序）序队列中找出与给定关键字相同的值的具体位置。原理是让关键字与队列中的第1个（或最后1个）位置的值逐个比较，直到找出与给定关键字相同的值为止。 （2） 二分查找法 二分查找是一种高效的搜索算法，适用于有序数组。它通过不断将搜索范围缩小一半来查找目标值，直到找到目标值或确定目标值不存在。 3. 递归算法 （1） 阶乘 阶乘是指从1到给定数字之间所有正整数的乘积。 （2）斐波那契数列 斐波那契数列是指数列从第3项开始，每一项都等于前两项之和。因此在数学上，这一数列以如下递推的方法定义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。 [限时练习] 1.下列选项中，不是算法的基本特征的是（ ） A. 有穷性 B. 确定性 C. 可读性 D. 可行性 【答案】C 【解析】算法的基本特征包括：有穷性、可行性、确定性、有0个或多个输入、有一个或多个输出。 2.流程图中表示判断框的是（ ）。 A. 矩形框 B. 菱形框 C. 圆形框 D. 椭圆形框 【答案】B 【解析】菱形框表示判断，矩形框表示处理，椭圆形框表示开始/结束 3.算法的有穷性是指（ ）。 A. 算法程序所处理的数据量是有限的 B. 算法程序的运行时间是有限的 C. 算法只能被有限的用户使用 D. 算法程序的长度是有限的 【答案】B 【解析】算法的有穷性指算法必须在有限的时间内完成执行，即在有限的步骤后终止。 4.算法的输入和输出特征是指（ ）。 A. 算法必须有输入，但可以没有输出 B. 算法可以没有输入，但必须有输出 C. 算法必须同时有输入和输出 D. 算法可以既没有输入也没有输出 【答案】B 【解析】算法可以没有输入，但必须至少有一个输出，以提供计算结果。 5.以下选项中的描述不符合算法的特征的是（ ）。 A. 算法必须在有限步骤内结束 B. 算法的每一步操作都必须明确 C. 算法可以无限循环下去 D. 算法必须能够被计算机执行 【答案】C 【解析】算法必须满足有穷性，不能无限循环，否则无法终止。 6.算法的空间复杂度主要衡量的是（ ） A. 算法程序的长度 B. 算法执行时所需的存储空间 C. 算法中输入数据的大小 D. 算法中输出数据的大小 【答案】B 【解析】空间复杂度是对算法在执行过程中临时占用存储空间大小的度量。 7.时间复杂度主要衡量的是（ ）。 A. 算法执行所需的具体时间 B. 算法执行所需的基本操作次数 C. 算法占用的内存空间 D. 算法的代码长度 【答案】B 【解析】时间复杂度是衡量算法执行所需基本操作次数的函数，反映算法的效率。 8.对有序数组[2, 5, 8, 12, 16, 23, 38]使用二分查找目标值 16，第一次比较的中间元素是（ ） A. 5 B. 8 C. 12 D. 23 【答案】C 【解析】二分查找的中间元素索引计算公式为mid = (left + right) / 2（向下取整）。 9.算法的时间复杂度用于衡量算法的 _________ 效率。 【答案】执行（运行） 【解析】时间复杂度描述算法执行时间随输入规模增长的趋势（如 O (n)、O (log n)）。 10.二分法查找（折半查找）要求被查找的数据集必须是______的，且存储结构为随机存取结构（如数组）。 【答案】有序 【解析】二分法查找的前提是待查找的数据是有序的。 11.优化算法时，时间复杂度和空间复杂度通常可以同时降低。（ ） 【答案】× 【解析】为减少时间消耗，可能需要增加存储空间；反之，为节省空间，可能需要增加计算时间。两者往往难以同时最优。 12.冒泡排序的核心逻辑是通过相邻元素的比较和交换，让最大（或最小）的元素逐步 “浮” 到数组末尾。（ ） 【答案】√ 【解析】冒泡排序每完成一趟遍历，只有一个最大（或最小）元素会被确定在最终位置。 [内容小结] 1.本章节基本概念较多，可以利用思维导图对本章知识点进行梳理总结。 2.本章节的重点在于算法与程序的基本概念，如算法的概念、算法与程序的关系等。 3.本章节的难点在于对各种典型算法的理解，可借助程序流程图帮助理解。 4.本章节的知识点的学习对于后续C#学的有很重要的作用。 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$