第56卷 算法与程序设计—递归算法—河北省计算机类—考纲百套卷
|
2份
|
18页
|
47人阅读
|
0人下载
内容正文：
编写说明：河北省对口招生计算机类《考纲百套卷》，依据《河北省普通高等学校对口招生考试大纲（2028版专业课）计算机类》编写。本专辑涵盖9门课程，第一部分是专业核心模块训练卷，第二部分为各门课程的综合训练卷。本专辑共98份试卷。
本试卷是第56卷为专业核心模块训练卷，按《算法与程序设计》中"算法程序卷11——递归算法"范围和要求编写。具体内容为：掌握递归算法
河北省对口招生职业技能考试
算法与程序设计 试卷
（算法程序卷11——递归算法）
考试时间：90分钟 满分：100分
一、单项选择题（共20题，每题2分，共40分）
1. 递归方法必须包含（）
A.循环体 B.递归出口（终止条件） C.输出语句 D.输入语句
【答案】B
【解析】递归方法的核心是“自身调用自身”，但必须有明确的递归出口（终止条件），否则会陷入无限递归导致程序崩溃；A错误，递归无需循环体，循环体是迭代的核心；C、D错误，输入输出语句并非递归方法的必需要素。
2. 递归算法的主要缺点是（）
A.代码复杂 B.占用栈空间，可能栈溢出 C.运行速度慢 D.无法处理大数据
【答案】B
【解析】递归调用过程中，每次调用的函数信息（参数、返回地址等）都会存储在栈内存中，若递归调用深度过大，会导致栈内存耗尽，引发栈溢出；A错误，递归代码通常比迭代更简洁；C错误，递归效率不一定低，取决于问题场景；D错误，递归可处理大数据，只是深度过大会有栈溢出风险。
3. 递归算法必须包含的两个要素是（）。
A.输入和输出 B.循环和选择 C.递归调用和递归终止条件 D.顺序和分支
【答案】C
【解析】递归算法的两个核心要素缺一不可：递归调用（将问题分解为更小规模的自身问题）和递归终止条件（递归出口）；A、B、D均不是递归算法的必需要素，输入输出、循环选择等是通用算法的组成部分。
4. 递归算法的空间复杂度通常取决于（）。
A.算法的时间复杂度 B.递归调用的深度 C.问题的输入规模 D.计算机的内存大小
【答案】B
【解析】递归算法的空间复杂度主要由栈内存占用决定，而栈内存占用量与递归调用的深度直接相关：调用深度越大，栈中存储的函数信息越多，空间复杂度越高；A、C、D与递归空间复杂度无直接关联。
5. 下列关于递归与迭代的说法，正确的是（）。
A.能用递归解决的问题通常也能用迭代解决 B.递归算法一定比迭代效率高 C.所有递归都可以改写为尾递归 D.递归不需要额外的栈空间
【答案】A
【解析】A正确，递归与迭代是两种等价的算法实现方式，能用递归解决的问题，通常都能通过循环改写为迭代；B错误，递归因栈内存开销，效率通常低于迭代；C错误，并非所有递归都能改写为尾递归（尾递归要求递归调用在函数最后一步）；D错误，递归必须占用栈空间存储调用信息。
6. 斐波那契数列F(n)的定义是F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)，求F(5)的值（）。
A.5 B.8 C.13 D.3
【答案】A
【解析】根据递归公式逐步计算：F(2)=F(1)+F(0)=1+0=1；F(3)=F(2)+F(1)=1+1=2；F(4)=F(3)+F(2)=2+1=3；F(5)=F(4)+F(3)=3+2=5。
7. 以下问题中，不适合用递归算法解决的是（）。
A.汉诺塔 B.斐波那契数列 C.遍历大型数组（百万级元素） D.树的遍历
【答案】C
【解析】C错误，遍历大型数组属于线性操作，用迭代（循环）效率更高，递归会因调用深度过大导致栈溢出；A、B、D均是递归的典型应用场景，汉诺塔、斐波那契数列、树的遍历均可通过递归简洁实现。
8. 递归算法的终止条件也称为（）。
A.递归出口/base case B.递归入口 C.递归体 D.递归栈
【答案】A
【解析】递归终止条件又称递归出口，英文常称为base case，用于结束递归调用，避免无限递归；B错误，递归入口是递归调用的起始点；C错误，递归体是将问题分解为子问题的部分；D错误，递归栈是存储递归调用信息的内存空间。
9. 下列关于尾递归的说法，正确的是（）。
A.尾递归不需要递归出口 B.尾递归的递归调用在方法最后一步 C.尾递归一定会导致栈溢出 D.尾递归不能转换为迭代
【答案】B
【解析】尾递归的核心特点是递归调用在函数的最后一步，无后续操作，编译器可对其优化，复用栈空间避免溢出；A错误，尾递归仍需递归出口；C错误，尾递归可通过优化避免栈溢出；D错误，尾递归极易转换为迭代。
10. 用递归算法求n!（n的阶乘），其递归出口是（）。
A.n=0或n=1时，返回1 B.n=2时，返回2 C.n>0时，返回n*f(n-1) D.无固定递归出口
【答案】A
【解析】阶乘的递归公式为n! = n × (n-1)!，递归出口需满足“无需再递归”：0!和1!的结果均为1，因此当n=0或n=1时，直接返回1，结束递归；B、C、D均不符合阶乘递归的逻辑。
11. 递归调用的过程中，函数调用信息会存储在（）中。
A.堆内存 B.栈内存 C.磁盘 D.寄存器
【答案】B
【解析】递归调用时，每次函数调用的参数、返回地址、局部变量等信息会被压入栈内存，当函数执行完毕（达到递归出口），这些信息会被弹出栈释放；A错误，堆内存用于存储动态分配的数据；C、D均不用于存储递归调用信息。
12. 以下关于递归算法的说法，错误的是（）。
A.递归算法的代码通常更简洁 B.递归算法的执行效率一定比迭代低 C.递归算法依赖于自身调用 D.递归算法必须有明确的终止条件
【答案】B
【解析】B错误，递归效率并非一定比迭代低，在某些场景（如树的遍历）中，递归与迭代效率相近，且代码更简洁；A、C、D均是递归算法的正确特点。
13. 汉诺塔问题中，若有3个盘子，最少需要移动（）次才能完成转移。
A.3 B.5 C.7 D.9
【答案】C
【解析】汉诺塔问题的最少移动次数公式为2ⁿ - 1（n为盘子数量），当n=3时，2³ - 1 = 7次；该问题是递归的经典应用，n个盘子的移动可分解为n-1个盘子的移动问题。
14. 下列哪种情况会导致递归栈溢出（）。
A.递归出口正确 B.递归调用深度过大 C.递归体逻辑错误 D.输入参数为0
【答案】B
【解析】递归栈溢出的核心原因是递归调用深度过大，栈内存无法容纳更多的函数调用信息；A错误，递归出口正确可避免无限递归，不会导致栈溢出；C错误，递归体逻辑错误会导致结果错误，而非栈溢出；D错误，输入参数为0通常会触发递归出口，不会导致栈溢出。
15. 递归算法中，“递归体”指的是（）。
A.递归终止的条件 B.将问题分解为更小规模的自身问题的部分 C.函数的返回值 D.函数的输入参数
【答案】B
【解析】递归体是递归算法的核心部分，作用是将当前问题分解为与原问题类型相同、规模更小的子问题，并通过自身调用解决子问题；A是递归出口；C、D是函数的基本组成部分，并非递归体。
16. 用递归算法求斐波那契数列，当n=6时，F(6)的值是（）。
A.8 B.13 C.21 D.5
【答案】A
【解析】根据斐波那契递归公式计算：F(2)=1，F(3)=2，F(4)=3，F(5)=5，F(6)=F(5)+F(4)=5+3=8。
17. 下列关于递归算法适用场景的说法，正确的是（）。
A.适合解决可分解为相同子问题的问题 B.适合解决所有数值计算问题 C.适合处理大规模数据 D.适合所有算法设计场景
【答案】A
【解析】递归的核心优势的是解决“可分解为相同子问题”的问题（如汉诺塔、斐波那契数列），通过自身调用复用逻辑；B、C、D错误，递归不适合所有场景，大规模数据处理易导致栈溢出，部分问题用迭代更高效。
18. 递归算法的时间复杂度通常与（）相关。
A.递归调用的次数 B.问题的输入数据类型 C.计算机的CPU性能 D.栈内存大小
【答案】A
【解析】递归算法的时间复杂度取决于递归调用的次数和每次调用的执行时间，调用次数越多，时间复杂度越高；B、C、D与时间复杂度无直接关联，CPU性能影响执行速度，不影响复杂度本身。
19. 下列代码片段中，属于递归算法的是（）。
A.int f(int n){ return n*n; } B.int f(int n){ if(n==1) return 1; return n + f(n-1); } C.int f(int n){ int sum=0; for(int i=1;i<=n;i++) sum+=i; return sum; } D.int f(int n){ return n+1; }
【答案】B
【解析】B选项满足递归的两个要素：有递归出口（n==1时返回1）和递归调用（f(n-1)），用于计算1到n的和；A、D是普通函数，无自身调用；C是迭代算法，通过循环实现求和。
20. 以下关于递归与迭代的区别，说法正确的是（）。
A.迭代不需要循环结构 B.递归不需要终止条件 C.迭代的空间复杂度通常低于递归 D.递归的代码一定比迭代复杂
【答案】C
【解析】C正确，迭代通过循环实现，无需栈内存存储调用信息，空间复杂度通常为O(1)或O(n)，低于递归的O(深度)；A错误，迭代必须依赖循环结构；B错误，递归必须有终止条件；D错误，递归代码通常比迭代更简洁。
二、填空题（共10空，每空1分，共10分）
21. 递归算法的两个核心要素是递归调用和_____。
【答案】递归终止条件（或递归出口）
【解析】递归算法缺一不可的两个核心要素是：递归调用（分解子问题）和递归终止条件（递归出口），缺少后者会导致无限递归。
22. 递归调用过程中，函数的调用信息会暂时存储在_____中，调用结束后释放。
【答案】栈内存（或栈）
【解析】递归调用时，函数的参数、返回地址等信息会被压入栈内存，当函数执行到递归出口、完成调用后，这些信息会被弹出栈，释放内存空间。
23. 斐波那契数列的递归公式中，当n=0时，F(0)=0；n=1时，F(1)=1；n≥2时，F(n)=_____。
【答案】F(n-1)+F(n-2)
【解析】斐波那契数列的递归定义为：从第3项开始，每一项的值等于前两项之和，即F(n)=F(n-1)+F(n-2)（n≥2）。
24. 递归算法中，_____用于结束递归调用，避免无限递归。
【答案】递归终止条件（或递归出口）
【解析】递归终止条件（递归出口）是递归算法的“终止开关”，当满足该条件时，递归调用停止，避免陷入无限循环导致程序崩溃。
25. 若递归调用的深度过大，会导致_____异常，使程序终止。
【答案】栈溢出
【解析】递归调用的信息存储在栈内存中，栈内存空间有限，若调用深度过大，栈内存会被耗尽，引发栈溢出异常，导致程序终止。
26. 能用递归解决的问题，通常具有_____的特点，即问题可分解为相同类型的更小规模问题。
【答案】分治（或可分解为相同子问题）
【解析】递归的核心思想是“分治”，即把一个复杂问题分解为多个与原问题类型相同、规模更小的子问题，通过解决子问题来解决原问题。
27. 尾递归的特点是递归调用在函数的_____，可通过编译器优化避免栈溢出。
【答案】最后一步（或末尾）
【解析】尾递归的定义是：递归调用是函数执行的最后一步，无任何后续操作，编译器可利用这一特点复用栈空间，避免栈溢出。
28. 求n!的递归算法中，递归出口是当n=0或n=1时，返回_____。
【答案】1
【解析】阶乘的定义为：0! = 1，1! = 1，因此求n!的递归出口为n=0或n=1时，返回1，后续通过n×f(n-1)递归计算。
29. 递归算法的代码通常比迭代算法更_____，但空间复杂度更高。
【答案】简洁（或简洁易懂）
【解析】递归算法通过自身调用复用逻辑，无需编写复杂的循环结构，代码通常更简洁、易懂，但因需栈内存存储调用信息，空间复杂度高于迭代。
30. 递归算法的空间复杂度主要由_____决定。
【答案】递归调用的深度
【解析】递归算法的空间复杂度主要取决于栈内存的占用量，而栈内存占用量与递归调用的深度直接相关，调用深度越大，空间复杂度越高。
三、判断题（共5题，每题1分，共5分）
31. 递归算法必须有明确的递归出口，否则会导致无限递归。（ ）
【答案】√
【解析】递归的核心是“自身调用自身”，若没有明确的递归出口，函数会一直调用自身，陷入无限递归，最终导致栈溢出、程序崩溃。
32. 所有能用递归解决的问题，都可以用迭代解决。（ ）
【答案】√
【解析】递归与迭代是两种等价的算法实现方式，递归的本质是“隐式循环”（通过栈实现），所有能用递归解决的问题，都可以通过编写显式循环改写为迭代算法。
33. 递归算法的运行速度一定比迭代算法慢。（ ）
【答案】×
【解析】递归算法的运行速度不一定比迭代慢，在某些场景（如树的遍历）中，递归与迭代的执行效率相近；只有当递归调用深度大、栈内存开销高时，递归效率才会低于迭代。
34. 尾递归不会产生栈溢出问题。（ ）
【答案】×
【解析】尾递归本身仍会占用栈空间，若调用深度过大，仍可能导致栈溢出；只有通过编译器对尾递归进行优化（复用栈空间），才能避免栈溢出，并非尾递归本身不会产生栈溢出。
35. 递归调用的过程是“先调用，后回溯”的过程。（ ）
【答案】√
【解析】递归调用的过程分为两个阶段：① 调用阶段：从原问题开始，不断分解为子问题，逐层调用自身，直到达到递归出口；② 回溯阶段：从递归出口开始，逐层返回结果，最终得到原问题的解，即“先调用，后回溯”。
四、程序分析题（共1题，每题10分，共10分）
36. 阅读下面的C#程序，分析其功能并写出运行结果。
using System;
class Program
{
static void Main()
{
int[] a = { 5, 3, 8, 1, 9, 2 };
for (int i = 0; i < a.Length - 1; i++)
{
for (int j = 0; j < a.Length - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
foreach (int n in a)
Console.Write(n + " ");
}
}
程序运行结果：___________________
【答案】1 2 3 5 8 9
五、写运行结果题（共2题，每题5分，共10分）
37. 分析下面C#程序段的输出结果：
using System;
class Program
{
static void Main()
{
int x = 10;
int y = x++ + ++x;
Console.WriteLine(x);
Console.WriteLine(y);
}
}
程序运行结果：___________________
【答案】12
22
38. 分析下面C#程序段的输出结果：
using System;
class Program
{
static void Main()
{
int n = 100;
int count = 0;
while (n > 1)
{
n /= 2;
count++;
}
Console.WriteLine(count);
}
}
程序运行结果：___________________
【答案】6
六、程序改错题（共1题，每题5分，共5分）
using System;
class Program
{
static void Main()
{
string str = "abc123xyz45";
int count; // 错误1：变量未初始化
foreach (char c in str)
{
if (c >= '0' && c <= '9')
count++;
}
Console.WriteLine("数字个数：" + count);
Console.Read();
}
}
【答案】
1.语法错误：n % i = 0 中赋值号=误用，应改为相等判断符 ==
2.效率 / 逻辑缺陷：for循环条件 i < n 冗余，应改为 i <= Math.Sqrt(n)（素数标准优化写法）
七、程序填空题（共3题，每题5分，共15分）
40. 下面程序用于求数组最大值及其位置，请填写空白处：
using System;
class Program{
static void Main(){
int[] a = {3, 7, 2, 9, 1};
int max = a[0];
int pos = 0;
for(int i = 1; i < a.Length; i++){
if(_____){
max = a[i];
pos = _____;}
}
Console.WriteLine("max=" + max + " pos=" + pos);
}
}
【答案】['a[i] > max', 'i']
41. 下面程序用于计算1到10的累加和，请填写空白处：
using System;
class Program{
static void Main(){
int sum = 0;
for(int i = 1; i <= 10; i++){
sum += _____;}
Console.WriteLine(sum);
}
}
【答案】['i']
42. 下面程序用于判断一个数是否为素数，请填写空白处：
using System;
class Program{
static void Main(){
int n = 17;
bool isPrime = true;
for(int i = 2; i <= Math.Sqrt(n); i++){
if(n % i == 0){
isPrime = _____;
break;
}
}
Console.WriteLine(isPrime);
}
}
【答案】['false']
学科网（北京）股份有限公司
$
编写说明：河北省对口招生计算机类《考纲百套卷》，依据《河北省普通高等学校对口招生考试大纲（2028版专业课）计算机类》编写。本专辑涵盖9门课程，第一部分是专业核心模块训练卷，第二部分为各门课程的综合训练卷。本专辑共98份试卷。
本试卷是第56卷为专业核心模块训练卷，按《算法与程序设计》中"算法程序卷11——递归算法"范围和要求编写。具体内容为：掌握递归算法
河北省对口招生职业技能考试
算法与程序设计 试卷
（算法程序卷11——递归算法）
考试时间：90分钟 满分：100分
一、单项选择题（共20题，每题2分，共40分）
1. 递归方法必须包含（）
A.循环体 B.递归出口（终止条件） C.输出语句 D.输入语句
2. 递归算法的主要缺点是（）
A.代码复杂 B.占用栈空间，可能栈溢出 C.运行速度慢 D.无法处理大数据
3. 递归算法必须包含的两个要素是（）。
A.输入和输出 B.循环和选择 C.递归调用和递归终止条件 D.顺序和分支
4. 递归算法的空间复杂度通常取决于（）。
A.算法的时间复杂度 B.递归调用的深度 C.问题的输入规模 D.计算机的内存大小
5. 下列关于递归与迭代的说法，正确的是（）。
A.能用递归解决的问题通常也能用迭代解决 B.递归算法一定比迭代效率高
C.所有递归都可以改写为尾递归 D.递归不需要额外的栈空间
6. 斐波那契数列F(n)的定义是F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)，求F(5)的值（）。
A.5 B.8 C.13 D.3
7. 以下问题中，不适合用递归算法解决的是（）。
A.汉诺塔 B.斐波那契数列 C.遍历大型数组（百万级元素） D.树的遍历
8. 递归算法的终止条件也称为（）。
A.递归出口/base case B.递归入口 C.递归体 D.递归栈
9. 下列关于尾递归的说法，正确的是（）。
A.尾递归不需要递归出口 B.尾递归的递归调用在方法最后一步
C.尾递归一定会导致栈溢出 D.尾递归不能转换为迭代
10. 用递归算法求n!（n的阶乘），其递归出口是（）。
A.n=0或n=1时，返回1 B.n=2时，返回2 C.n>0时，返回n*f(n-1) D.无固定递归出口
11. 递归调用的过程中，函数调用信息会存储在（）中。
A.堆内存 B.栈内存 C.磁盘 D.寄存器
12. 以下关于递归算法的说法，错误的是（）。
A.递归算法的代码通常更简洁 B.递归算法的执行效率一定比迭代低
C.递归算法依赖于自身调用 D.递归算法必须有明确的终止条件
13. 汉诺塔问题中，若有3个盘子，最少需要移动（）次才能完成转移。
A.3 B.5 C.7 D.9
14. 下列哪种情况会导致递归栈溢出（）。
A.递归出口正确 B.递归调用深度过大 C.递归体逻辑错误 D.输入参数为0
15. 递归算法中，“递归体”指的是（）。
A.递归终止的条件 B.将问题分解为更小规模的自身问题的部分
C.函数的返回值 D.函数的输入参数
16. 用递归算法求斐波那契数列，当n=6时，F(6)的值是（）。
A.8 B.13 C.21 D.5
17. 下列关于递归算法适用场景的说法，正确的是（）。
A.适合解决可分解为相同子问题的问题 B.适合解决所有数值计算问题
C.适合处理大规模数据 D.适合所有算法设计场景
18. 递归算法的时间复杂度通常与（）相关。
A.递归调用的次数 B.问题的输入数据类型 C.计算机的CPU性能 D.栈内存大小
19. 下列代码片段中，属于递归算法的是（）。
A.int f(int n){ return n*n; }
B.int f(int n){ if(n==1) return 1; return n + f(n-1); }
C.int f(int n){ int sum=0; for(int i=1;i<=n;i++) sum+=i; return sum; }
D.int f(int n){ return n+1; }
20. 以下关于递归与迭代的区别，说法正确的是（）。
A.迭代不需要循环结构 B.递归不需要终止条件
C.迭代的空间复杂度通常低于递归 D.递归的代码一定比迭代复杂
二、填空题（共10空，每空1分，共10分）
21. 递归算法的两个核心要素是递归调用和_____。
22. 递归调用过程中，函数的调用信息会暂时存储在_____中，调用结束后释放。
斐波那契数列的递归公式中，当n=0时，F(0)=0；n=1时，F(1)=1；n≥2时，F(n)=_____。
23. 递归算法中，_____用于结束递归调用，避免无限递归。
24. 若递归调用的深度过大，会导致_____异常，使程序终止。
25. 能用递归解决的问题，通常具有_____的特点，即问题可分解为相同类型的更小规模问题。
26. 尾递归的特点是递归调用在函数的_____，可通过编译器优化避免栈溢出。
27. 求n!的递归算法中，递归出口是当n=0或n=1时，返回_____。
28. 递归算法的代码通常比迭代算法更_____，但空间复杂度更高。
29. 汉诺塔问题的递归求解，核心是将n个盘子的问题分解为n-1个盘子的_____问题。
30. 递归算法的空间复杂度主要由_____决定。
三、判断题（共5题，每题1分，共5分）
31. 递归算法必须有明确的递归出口，否则会导致无限递归。（ ）
32. 所有能用递归解决的问题，都可以用迭代解决。（ ）
33. 递归算法的运行速度一定比迭代算法慢。（ ）
34. 尾递归不会产生栈溢出问题。（ ）
35. 递归调用的过程是“先调用，后回溯”的过程。（ ）
四、程序分析题（共1题，每题10分，共10分）
36. 阅读下面的C#程序，分析其功能并写出运行结果。
using System;
class Program
{
static void Main()
{
int[] a = { 5, 3, 8, 1, 9, 2 };
for (int i = 0; i < a.Length - 1; i++)
{
for (int j = 0; j < a.Length - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
foreach (int n in a)
Console.Write(n + " ");
}
}
程序运行结果：___________________
五、写运行结果题（共2题，每题5分，共10分）
37. 分析下面C#程序段的输出结果：
using System;
class Program
{
static void Main()
{
int x = 10;
int y = x++ + ++x;
Console.WriteLine(x);
Console.WriteLine(y);
}
}
程序运行结果：___________________
38. 分析下面C#程序段的输出结果：
using System;
class Program
{
static void Main()
{
int n = 100;
int count = 0;
while (n > 1)
{
n /= 2;
count++;
}
Console.WriteLine(count);
}
}
程序运行结果：___________________
六、程序改错题（共1题，每题5分，共5分）
using System;
class Program
{
static void Main()
{
string str = "abc123xyz45";
int count; // 错误1：变量未初始化
foreach (char c in str)
{
if (c >= '0' && c <= '9')
count++;
}
Console.WriteLine("数字个数：" + count);
Console.Read();
}
}
七、程序填空题（共3题，每题5分，共15分）
40. 下面程序用于求数组最大值及其位置，请填写空白处：
using System;
class Program{
static void Main(){
int[] a = {3, 7, 2, 9, 1};
int max = a[0];
int pos = 0;
for(int i = 1; i < a.Length; i++){
if(_____){
max = a[i];
pos = _____;}
}
Console.WriteLine("max=" + max + " pos=" + pos);
}
}
41. 下面程序用于计算1到10的累加和，请填写空白处：
using System;
class Program{
static void Main(){
int sum = 0;
for(int i = 1; i <= 10; i++){
sum += _____;}
Console.WriteLine(sum);
}
}
42. 下面程序用于判断一个数是否为素数，请填写空白处：
using System;
class Program{
static void Main(){
int n = 17;
bool isPrime = true;
for(int i = 2; i <= Math.Sqrt(n); i++){
if(n % i == 0){
isPrime = _____;
break;
}
}
Console.WriteLine(isPrime);
}
}
学科网（北京）股份有限公司
$
资源预览图
