一、单项选择题（每题2分，共20分）

1、递推算法的两个必要条件是？（） {{ select(1) }}

• 递归出口、递归公式
• 初始条件、递推关系
• 队列、方向数组
• 栈、标记数组

2、普通移动路线题目，只能向右、向下走，递推公式正确的是？（） {{ select(2) }}

• a[i][j] = a[i‑1][j] + a[i][j‑1]
• a[i][j] = a[i‑1][j‑1] + a[i‑1][j]
• a[i][j] = a[i‑1][j] - a[i][j‑1]
• a[i][j] = a[i‑1][j] * a[i][j‑1]

3、移动路线问题，第1行、第1列格子的路径数初始值为？（） {{ select(3) }}

• 0
• 1
• 2
• i+j

4、带障碍的路径计数题，用什么值标记障碍格子？（） {{ select(4) }}

• 1
• -1
• 0
• 999

5、带障碍路径计数递推时，如果上方格子是障碍，处理方式是？（） {{ select(5) }}

• 直接跳过程序结束
• 把该位置当作0参与计算
• 直接赋值为1
• 直接赋值为i

6、数字金字塔求从塔顶到底部的最大路径和，递推公式是？（） {{ select(6) }}

• a[i][j] += max(a[i‑1][j‑1], a[i‑1][j])
• a[i][j] += min(a[i‑1][j‑1], a[i‑1][j])
• a[i][j] = a[i‑1][j] + a[i][j‑1]
• a[i][j] = a[i‑1][j‑1] * a[i‑1][j]

7、数字金字塔求最大路径和，最后结果需要取哪里的最大值？（） {{ select(7) }}

• 第一行全部元素
• 最后一行全部元素
• 第一列全部元素
• 对角线元素

8、数字金字塔求最小路径和，数组空白部分要填充什么？（） {{ select(8) }}

• 0
• 1
• 极大值
• -1

9、莱布尼茨三角形，每一行第一个位置的分母初始值为？（） {{ select(9) }}

• 固定等于1
• 等于行号i
• 等于列号j
• i*j

10、网格路径计数，路径数值容易超出int范围，应当选用什么数据类型？（） {{ select(10) }}

• char
• bool
• long long
• short

二、判断题（每题2分，共10分）

11、递推算法是从已知初始条件，依靠递推关系式一步步推出后续结果。（） {{ select(11) }}

• 正确
• 错误

12、移动路线问题，蚂蚁只能向下向右，(1,1)到(1,m)第一行每个格子路径数为1。（） {{ select(12) }}

• 正确
• 错误

13、数字金字塔，贪心每次选当前最大的数字，一定可以得到全局最大路径和。（） {{ select(13) }}

• 正确
• 错误

14、带障碍路径计数，第一行遇到障碍，障碍后面的格子路径数直接为0。（） {{ select(14) }}

• 正确
• 错误

15、莱布尼茨三角形所有分数分子都为1，程序只需要计算分母。（） {{ select(15) }}

• 正确
• 错误