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

专题一 算法与程序基础 算法与程序设计-C# 专题复习讲练测 掌握国家标准《机械制图》中有关图幅、比例、字体图线等基本规定。 考纲要求 一 1．掌握算法的概念，理解算法描述方法，理解算法的设计步骤； 2．理解算法时间复杂度、空间复杂度等算法性能评价基本方法； 3．理解算法与程序的关系； 4．掌握下列典型算法：选择法、冒泡法、插入等排序算法，顺序查找、二分法查找等查找算法；递归算法；最值、均值、公约数、素数、累加、累乘、阶乘、回文数、斐波那契数列等数学算法；字符串的加密算法。 知识点梳理 二 知识点梳理 二 一：算法的概念 算法就是解决问题的方法和步骤，而且步骤是有限的。 二：算法三要素 1.操作：操作包括以下几方面： （1）算术运算:加、减、乘、除。 （2）关系比较:大于、小于、等于、不等于。 （3）逻辑运算:与、或、非。 （4）数据传送:输入、输出、赋值(计算)。 知识点梳理 二 二：算法三要素 2.控制结构：一个算法功能的实现不仅取决于所选用的操作，还取决于各操作之间的执行顺序，即控制结构。包括： （1）顺序结构:各操作是依次进行的。 （2）选择结构:由条件是否成立来决定选择执行。 （3）循环结构:有些操作要重复执行，直到满足某个条件时才结束，这种控制结构也称为重复或迭代结构。 3.数据结构：算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就是数据结构。 知识点梳理 二 三：算法描述 1.自然语言：使用语言描述解决问题的过程 2.流程图：图形化描述 3.N-S图； 知识点梳理 二 三：算法描述 知识点梳理 二 四：算法的重要特性 1.有穷性 2.确定性 3.可行性 4.算法有零个或多个的输入 5.算法有一个或多个的输出 知识点梳理 二 五：算法复杂度 1.算法的时间复杂度 时间复杂度不是一个明确的执行时间，而是一个函数。用O(n)表示。 2.算法的空间复杂度 一个算法空间复杂度S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。 对于一个算法，其时间复杂度与空间复杂度往往是相互影响的。算法的时间复杂度与空间复杂度合称为算法的复杂度。在设计一个算法时，要综合考虑算法的各项性能等。 知识点梳理 二 六：算法与程序的关系 1.算法 算法是一种抽象的概念，是一种解决问题的方法，可以用自然语言、流程图、伪代码等形式来描述。 2.程序 程序是算法的具体实现，它是一组指令的集合，用来告诉计算机如何执行某个任务。 算法和程序之间的关系非常密切。算法是程序的灵魂，程序是算法的具体实现。没有算法就没有程序，没有程序就没有算法的实现。 知识点梳理 二 七：典型算法 (1)选择排序 知识点梳理 二 七：典型算法 (2)冒泡排序 知识点梳理 二 七：典型算法 (3)插入排序 知识点梳理 二 七：典型算法 （4）顺序查找法 知识点梳理 二 七：典型算法 （5）二分查找法 知识点梳理 二 七：典型算法 (6)阶乘 知识点梳理 二 七：典型算法 (7)斐波那契数列 限时练习 三 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#学的有很重要的作用。 $$