资源简介

第七单元 《了解更多的算法》
一、选择题（每题 3 分，共 30 分）
1. 在“多人过河巧安排”问题中，主要运用的算法思想是（ ）
A. 穷举法 B. 把大问题分解成小问题解决 C. 贪心算法 D. 回溯法
2. “有趣的七桥问题” 中，实现一笔画判断的关键在于（ ）
A. 计算桥的数量 B. 抽取问题中的关键要素并简化
C. 统计岛屿个数 D. 分析行走路线
3. 寻找最短路径时，把全局问题分解成局部问题解决，这体现了（ ）
A. 分治法思想 B. 枚举思想 C. 递归思想 D. 迭代思想
4. 网页排名算法的主要作用是（ ）
A. 提升网页制作技术 B. 规范网络使用
C. 确定网页在搜索结果中的先后顺序 D. 保障信息安全
5. 对于“多人过河巧安排”问题，若有 3 人过河，船每次最多载 2 人，以下哪种过河策略可能不是最优的（ ）
A. 先让用时最短的两人过河，再让其中一人返回
B. 先让用时较长的两人过河，再让用时短的人返回
C. 先让用时短和时长适中的人过河，再让用时短的人返回
D. 先让用时最短的人分别和另外两人过河
6. 在“有趣的七桥问题”所抽象出的图形中，若某点连接的线条数为 3，则该点是（ ）
A. 偶点 B. 奇点 C. 孤立点 D. 交点
7. 寻找最短路径算法中，以下哪种数据结构常用于存储图的信息（ ）
A. 数组 B. 栈 C. 队列 D. 邻接矩阵
8. 网页排名算法考虑的因素不包括（ ）
A. 网页的更新时间 B. 网页的内容质量
C. 网页的制作工具 D. 网页的链接数量
9. 当处理大规模“寻找最短路径”问题时，以下哪种算法效率相对较高（ ）
A. 深度优先搜索算法 B. 广度优先搜索算法
C. Dijkstra 算法 D. 冒泡排序算法
10. 在解决“多人过河巧安排”问题时，以下哪项不属于需要考虑的约束条件（ ）
A. 船的载人数量限制 B. 每个人的过河时间
C. 河两岸的地形 D. 来回划船的人员安排
二、填空题（每题 4 分，共 20 分）
1. “多人过河巧安排” 中，通过合理规划算法，能够有效解决人员过河的______问题。
2. 七桥问题中，若一个图形要能够一笔画成，奇点的个数应该为______。
3. 寻找最短路径算法中，常见的用于描述路径的方式有______。
4. 网页排名算法通过对网页的各种因素进行分析，赋予每个网页一个______，以确定其在搜索结果中的位置。
5. 在“多人过河巧安排”问题里，若有两人过河时间分别为a和b（a < b），则他们一起过河的时间为______。
简答题（每题 15 分，共 30 分）
1. 简述在“有趣的七桥问题”中，如何抽取关键要素并进行简化来判断能否一笔画。
2. 请阐述网页排名算法对提升网页价值有哪些意义。
四、算法设计题（20 分）
假设有 4 个人要过河，分别是 A、B、C、D，他们单独过河的时间分别为 1 分钟、2 分钟、5 分钟、10 分钟。只有一艘船，每次最多能载 2 个人，且以较慢者的速度为准。请设计一个算法，规划出这 4 个人过河的最短时间安排，并说明算法思路。
参考答案：
一、选择题答案及解析
1. 答案：C
解析：“多人过河”问题中，每次选择当前最优策略（如让最快的人来回划船），体现贪心算法“局部最优”的思想。
2. 答案：B
解析：七桥问题通过将陆地抽象为点、桥抽象为线，简化问题后判断是否能一笔画，关键在于要素抽取与模型简化。
3. 答案：A
解析：分治法将全局问题分解为子问题求解，如最短路径中拆分路径分段计算。
4. 答案：C
解析：网页排名算法（如PageRank）的核心是根据网页权重确定搜索结果排序。
5. 答案：B
解析：让用时较长的两人先过河可能增加总时间，最优策略通常优先让最快的人往返。
6. 答案：B
解析：连接线条数为奇数的点称为奇点，七桥问题中奇点数量决定能否一笔画。
7. 答案：D
解析：邻接矩阵常用于存储图的节点连接关系，适合表示最短路径问题中的图结构。
8. 答案：C
解析：网页排名与制作工具无关，主要考虑内容质量、链接数量、更新时间等。
9. 答案：C
解析：Dijkstra算法是经典的最短路径算法，处理大规模问题时效率高于深度/广度优先搜索。
10. 答案：C
解析：河两岸地形不影响过河策略的规划，属于无关约束条件。
二、填空题答案及解析
1. 答案：最优时间（或顺序规划）
解析：“多人过河”问题需通过算法规划过河顺序，使总时间最短，核心是解决时间优化或顺序安排问题。
2. 答案：0 或 2
解析：七桥问题中，若图形能一笔画成，奇点（连接奇数条线的点）数量必须为0（起点与终点重合）或2（起点与终点不同）。
3. 答案：路径长度（或节点序列）
解析：最短路径算法中，常用“路径总长度”表示最优结果，也可用经过的“节点顺序”描述具体路线。
4. 答案：权重（或排名分数）
解析：网页排名算法通过分析链接数量、内容质量等因素，为每个网页赋予权重值，权重越高搜索结果越靠前。
5. 答案：b
解析：两人过河时，过河时间由较慢者决定（如a < b，则总时间为b），这是“多人过河”问题的基本约束条件。
三、简答题
1. 答案：在“有趣的七桥问题”中，首先把陆地看作点，桥看作连接点的线，将实际的地理场景抽象成几何图形。然后统计每个点连接线条的数量，也就是度数。如果一个点连接的线条数为奇数，这个点就是奇点；线条数为偶数就是偶点。若图形中奇点个数为 0 或 2 ，则可以一笔画成；若奇点个数超过 2 个，则不能一笔画成 。
2. 答案：网页排名算法对提升网页价值意义重大。一方面，它能让优质、相关度高的网页在搜索结果中靠前展示，吸引更多用户访问，增加网页流量。流量提升后，网页的知名度和影响力会扩大，进而吸引更多资源投入，如广告投放等，带来经济效益。另一方面，促使网页制作者不断优化内容和结构，提升网页质量，以在排名算法中获得优势，推动整个网络内容生态向更好方向发展 。
四、算法设计题
答案：
- 算法思路：为使总时间最短，让用时短的人来回送船，同时尽量让用时较长的两人一起过河，避免多次让用时较长的人单独过河浪费时间 。
- 过河安排：
- 第一步：A 和 B 一起过河，用时 2 分钟，然后 A 单独回来，用时 1 分钟。这一步共花费 2 + 1 = 3 分钟。
- 第二步：C 和 D 一起过河，用时 10 分钟，然后 B 回来，用时 2 分钟。这一步共花费 10 + 2 = 12 分钟。
- 第三步：A 和 B 再一起过河，用时 2 分钟。 - 所以总共花费的时间是 3 + 12 + 2 = 17 分钟 。

展开更多......

收起↑