第19卷 算法与程序基础（1）河北省对口招生考试-计算机类《算法与程序设计双析卷》

编写说明：河北省普通高等学校对口招生考试计算机类《算法与程序设计考点双析卷》，依据《河北省普通高等学校对口招生计算机类专业考试考试大纲》编写。“考点双析卷”即围绕一个考点，一份是老师的讲解卷一份是学生的练习卷。助力师生构建 “讲练结合” 的学习闭环，适用于高考复习教学。 本专辑第19、第20卷精准对标河北省考纲，知识模块（三）算法与程序基础： 1． 掌握算法的概念，理解算法描述方法，理解算法的设计步骤； 2． 理解算法时间复杂度、空间复杂度等算法性能评价基本方法； 3． 理解算法与程序的关系； 4． 掌握下列典型算法：选择法、冒泡法、插入等排序算法，顺序查找、二分法查找等查找算法；递归算法；最值、均值、公约数、素数、累加、累乘、阶乘、回文数、斐波那契数列等数学算法；字符串的加密算法。 河北省对口招生考试 计算机类 《算法与程序设计》考点双析卷 第19卷 算法与程序基础（1） 老师讲解卷 时间：45分钟 总分：100分 班级_______ 姓名_______ 学号_______ 成绩_______ 一、单项选择题（本大题共20小题，每题3分，共60分） 1．下列关于程序与算法的关系描述不正确的是（   ） A．算法是对程序的描述 B．算法是程序的灵魂 C．程序是算法一种体现 D．程序是算法的具体实现 2．下列关于程序与算法描述不正确的是（   ） A．算法和程序是计算机科学中两个非常重要的概念 B．算法是一种问题的解决方法，而程序则是算法的具体实现 C．算法可以不满足有穷性而一直运算，而程序不能 D．算法的好坏直接影响程序的效率和质量 3．下列关于程序描述正确的是（   ） A．程序一般由算法自动生成 B．程序一般由程序员根据算法改写的 C．程序就是算法 D．程序语言能被计算机直接识别 4．算法的 “确定性” 指的是（   ） A．必须在有限步骤内终止 B．每一步操作有明确含义 C．可以使用自然语言描述 D．能处理非法输入 5．顺序查找法的时间复杂度是（   ） A．O(n) B．O(log n) C．O(n²) D．O(1) 6．二分查找法要求数组必须是（   ） A．无序的 B．有序的 C．可以无序也可以有序 D．以上都不对 7．以下关于冒泡排序算法的描述，正确的是（   ） A．冒泡排序是一种不稳定的排序算法 B．冒泡排序在最好情况下的时间复杂度为 O (n) C．冒泡排序每次比较相邻的两个元素，将较小的元素交换到后面 D．冒泡排序需要额外的存储空间来完成排序 8．在算法的时间复杂度中，无论输入规模的大小、算法的执行时间都保持不变，这是指(   ) A．常数时间复杂度 B．线性时间复杂度 C．对数时间复杂度 D．指数时间复杂度 9．与算法执行时间相关的因素有（   ） A．问题中数据存储的数据结构 B．算法设计的策略 C．问题的规模 D．以上说法都正确 10．下列问题中，最适合用递归算法解决的是（   ） A．计算 1 到 n 的和 B．求两个数的最大公约数 C．计算斐波那契数列的第 n 项 D．判断一个数是否为素数 11．顺序查找与二分查找相比，下列说法正确的是（   ） A．顺序查找效率总是更低 B．顺序查找适用于有序和无序数组，二分查找仅适用于有序数组 C．顺序查找的时间复杂度为 O (log n)，二分查找为 O (n) D．二分查找不需要遍历元素，顺序查找需要遍历所有元素 12．二分查找（折半查找）的前提条件是（   ） A．被查找的数组必须是无序的 B．被查找的数组必须是有序的 C．被查找的数组元素个数必须为奇数 D．被查找的数组必须包含重复元素 13．下列关于算法和程序的区别，说法错误的是（   ） A．算法必须有明确的终止条件，程序可能无限循环 B．算法强调逻辑的正确性，程序强调语法的正确性 C．算法可以用伪代码描述，程序必须用编程语言实现 D．算法和程序的步骤都必须是有限的 14．关于算法与程序的关系，下列说法正确的是（   ） A．算法就是程序，程序就是算法 B．算法是程序的灵魂，程序是算法的实现 C．算法必须用计算机语言编写，程序可以用自然语言描述 D．算法和程序都不需要考虑输入输出 15．以下空间复杂度中，最低的是（   ） A．O(1) B．O(n) C．O(n²) D．O(2ⁿ) 16．某算法的时间复杂度为 O (n²)，意味着（   ） A．算法需要执行 n² 次语句 B．输入规模为 n 时，算法执行时间与 n² 成正比 C．算法的执行时间固定为 n² 毫秒 D．算法的效率比 O (n) 的算法低，与输入规模无关 17．算法的时间复杂度表示（   ） A．算法执行的实际时间 B．算法执行时间随输入规模增长的趋势 C．算法中语句的数量 D．算法在最坏情况下的执行时间 18．使用自然语言表述算法的缺点不包括(   ) A．容易有歧义性 B．语句太长 C．有串行性很难清晰表示 D．便于翻译成计算机程序 19．算法的可行性是指（   ） A．算法必须能被计算机执行 B．算法必须能解决实际问题 C．算法的每一步都必须是可行的、能有效执行的 D．算法必须有输入和输出 20．算法的确定性是指（   ） A．算法必须有输入 B．算法必须有输出 C．算法的每一步操作都必须是明确无误的 D．算法必须在有限的时间内完成 二、填空题（本大题共8小题，每题5分，共40分） 21．算法的图形化描述工具是__________。 22．二分查找法中，每次查找时，查找区间的大小会变为原来的______。 23．时间复杂度考虑算法执行时间与输入规模之间的关系，_________实际的执行时间。（考虑/不考虑） 24．指数时间复杂度的表示方法为________。 25．算法的执行时间随输入规模的增加而呈平方级增长是指________时间复杂度。 26．算法时间复杂度通常使用________符号表示。 27．斐波那契数列的定义为、F (0)=0，F (1)=1，F (n)=______（n≥2）。 28．若一个算法的步骤是无限的，则它 _______ （填 “能” 或 “不能”）转化为程序，因为程序运行需在有限时间内完成。 试卷第6页，共6页 试卷第5页，共6页 学科网（北京）股份有限公司 $ 编写说明：河北省普通高等学校对口招生考试计算机类《算法与程序设计考点双析卷》，依据《河北省普通高等学校对口招生计算机类专业考试考试大纲》编写。“考点双析卷”即围绕一个考点，一份是老师的讲解卷一份是学生的练习卷。助力师生构建 “讲练结合” 的学习闭环，适用于高考复习教学。 本专辑第19、第20卷精准对标河北省考纲，知识模块（三）算法与程序基础： 1． 掌握算法的概念，理解算法描述方法，理解算法的设计步骤； 2． 理解算法时间复杂度、空间复杂度等算法性能评价基本方法； 3． 理解算法与程序的关系； 4． 掌握下列典型算法：选择法、冒泡法、插入等排序算法，顺序查找、二分法查找等查找算法；递归算法；最值、均值、公约数、素数、累加、累乘、阶乘、回文数、斐波那契数列等数学算法；字符串的加密算法。 河北省对口招生考试 计算机类 《算法与程序设计》考点双析卷 第19卷 算法与程序基础（1） 老师讲解卷 时间：45分钟 总分：100分 班级_______ 姓名_______ 学号_______ 成绩_______ 一、单项选择题（本大题共20小题，每题3分，共60分） 1．下列关于程序与算法的关系描述不正确的是（   ） A．算法是对程序的描述 B．算法是程序的灵魂 C．程序是算法一种体现 D．程序是算法的具体实现 【答案】A 【详解】程序是对算法的描述，所以A错误。 2．下列关于程序与算法描述不正确的是（   ） A．算法和程序是计算机科学中两个非常重要的概念 B．算法是一种问题的解决方法，而程序则是算法的具体实现 C．算法可以不满足有穷性而一直运算，而程序不能 D．算法的好坏直接影响程序的效率和质量 【答案】C 【详解】可以程序不满足有穷性，而算法不能。因此C不正确。 3．下列关于程序描述正确的是（   ） A．程序一般由算法自动生成 B．程序一般由程序员根据算法改写的 C．程序就是算法 D．程序语言能被计算机直接识别 【答案】B 【详解】程序不等于算法，程序是算法用某种程序设计语言的具体实现且需要人依据算法使用程序语言进行编写，所以AC错误，B正确。又因程序语言需要编译为机器语言才能被计算机识别。所以D也是错误的。 4．算法的 “确定性” 指的是（   ） A．必须在有限步骤内终止 B．每一步操作有明确含义 C．可以使用自然语言描述 D．能处理非法输入 【答案】B 【详解】确定性要求算法的每个步骤无歧义。 5．顺序查找法的时间复杂度是（   ） A．O(n) B．O(log n) C．O(n²) D．O(1) 【答案】A 【详解】顺序查找法的时间复杂度是O(n)。 6．二分查找法要求数组必须是（   ） A．无序的 B．有序的 C．可以无序也可以有序 D．以上都不对 【答案】B 【详解】二分查找法的前提是数组必须有序，否则无法通过比较中间元素来缩小查找区间。 7．以下关于冒泡排序算法的描述，正确的是（   ） A．冒泡排序是一种不稳定的排序算法 B．冒泡排序在最好情况下的时间复杂度为 O (n) C．冒泡排序每次比较相邻的两个元素，将较小的元素交换到后面 D．冒泡排序需要额外的存储空间来完成排序 【答案】B 【详解】冒泡排序是稳定排序算法，A 错误；每次比较相邻元素，将较大元素交换到后面，C 错误；冒泡排序空间复杂度为 O (1)，不需要额外大量存储空间，D 错误；在数组已经有序时，冒泡排序只需要遍历一次数组，时间复杂度为 O (n)，B 正确。 8．在算法的时间复杂度中，无论输入规模的大小、算法的执行时间都保持不变，这是指(   ) A．常数时间复杂度 B．线性时间复杂度 C．对数时间复杂度 D．指数时间复杂度 【答案】A 9．与算法执行时间相关的因素有（   ） A．问题中数据存储的数据结构 B．算法设计的策略 C．问题的规模 D．以上说法都正确 【答案】D 10．下列问题中，最适合用递归算法解决的是（   ） A．计算 1 到 n 的和 B．求两个数的最大公约数 C．计算斐波那契数列的第 n 项 D．判断一个数是否为素数 【答案】C 【详解】斐波那契数列的定义为F(n) = F(n-1) + F(n-2)（n>2），适合用递归实现。 11．顺序查找与二分查找相比，下列说法正确的是（   ） A．顺序查找效率总是更低 B．顺序查找适用于有序和无序数组，二分查找仅适用于有序数组 C．顺序查找的时间复杂度为 O (log n)，二分查找为 O (n) D．二分查找不需要遍历元素，顺序查找需要遍历所有元素 【答案】B 【详解】顺序查找通过逐个遍历元素查找目标，对数组是否有序无要求；二分查找依赖数组有序性，通过缩小范围查找。 12．二分查找（折半查找）的前提条件是（   ） A．被查找的数组必须是无序的 B．被查找的数组必须是有序的 C．被查找的数组元素个数必须为奇数 D．被查找的数组必须包含重复元素 【答案】B 【详解】二分查找的核心是通过比较中间元素与目标值，不断缩小查找范围（排除一半元素），因此要求数组必须有序（升序或降序）。 13．下列关于算法和程序的区别，说法错误的是（   ） A．算法必须有明确的终止条件，程序可能无限循环 B．算法强调逻辑的正确性，程序强调语法的正确性 C．算法可以用伪代码描述，程序必须用编程语言实现 D．算法和程序的步骤都必须是有限的 【答案】D 【详解】算法的核心特征之一是 “有穷性”，但程序可能因逻辑错误陷入无限循环。 14．关于算法与程序的关系，下列说法正确的是（   ） A．算法就是程序，程序就是算法 B．算法是程序的灵魂，程序是算法的实现 C．算法必须用计算机语言编写，程序可以用自然语言描述 D．算法和程序都不需要考虑输入输出 【答案】B 【详解】算法是解决问题的逻辑步骤和策略（如 “先排序再查找” 的思路），而程序是算法的具体实现 15．以下空间复杂度中，最低的是（   ） A．O(1) B．O(n) C．O(n²) D．O(2ⁿ) 【答案】A 【详解】上述四项中，经比较空间复杂度最低的是O(1) 。 16．某算法的时间复杂度为 O (n²)，意味着（   ） A．算法需要执行 n² 次语句 B．输入规模为 n 时，算法执行时间与 n² 成正比 C．算法的执行时间固定为 n² 毫秒 D．算法的效率比 O (n) 的算法低，与输入规模无关 【答案】B 【详解】O (n²) 是 “渐进时间复杂度”，表示当 n 足够大时，算法执行时间的增长趋势与 n² 一致。 17．算法的时间复杂度表示（   ） A．算法执行的实际时间 B．算法执行时间随输入规模增长的趋势 C．算法中语句的数量 D．算法在最坏情况下的执行时间 【答案】B 【详解】时间复杂度并非实际运行时间（受硬件、环境影响），而是用数学符号（如 O (n)）描述算法执行时间与输入规模（n）的增长关系，反映算法的效率趋势。 18．使用自然语言表述算法的缺点不包括(   ) A．容易有歧义性 B．语句太长 C．有串行性很难清晰表示 D．便于翻译成计算机程序 【答案】D 【详解】自然语言的缺点是书写较为繁琐，不能被计算机识别和执行。 19．算法的可行性是指（   ） A．算法必须能被计算机执行 B．算法必须能解决实际问题 C．算法的每一步都必须是可行的、能有效执行的 D．算法必须有输入和输出 【答案】C 【详解】算法的可行性指算法中的每个步骤都必须是切实可行的，能够通过基本操作在有限时间内完成。 20．算法的确定性是指（   ） A．算法必须有输入 B．算法必须有输出 C．算法的每一步操作都必须是明确无误的 D．算法必须在有限的时间内完成 【答案】C 【详解】算法的确定性要求每一步操作都必须清晰明确，没有歧义，确保执行时每一步都有确定的结果。 二、填空题（本大题共8小题，每题5分，共40分） 21．算法的图形化描述工具是__________。 【答案】流程图 22．二分查找法中，每次查找时，查找区间的大小会变为原来的______。 【答案】一半 23．时间复杂度考虑算法执行时间与输入规模之间的关系，_________实际的执行时间。（考虑/不考虑） 【答案】不考虑 24．指数时间复杂度的表示方法为________。 【答案】O（2^n） 25．算法的执行时间随输入规模的增加而呈平方级增长是指________时间复杂度。 【答案】平方 26．算法时间复杂度通常使用________符号表示。 【答案】O 27．斐波那契数列的定义为、F (0)=0，F (1)=1，F (n)=______（n≥2）。 【答案】F (n-1) + F (n-2) 【详解】斐波那契数列从第 3 项开始，每一项都等于前两项之和。 28．若一个算法的步骤是无限的，则它 _______ （填 “能” 或 “不能”）转化为程序，因为程序运行需在有限时间内完成。 【答案】不能 【详解】算法的 “有穷性” 要求步骤必须有限，否则无法通过程序实现（程序若无限执行，无实际意义）。 试卷第6页，共6页 试卷第5页，共6页 学科网（北京）股份有限公司 $