A*算法求解问题时，出现重复扩展节点问题的原因（）A、如果h函数定义不合理，则当扩展一个节点时，不一定就找到了从初始节点到该节点的最优路径，就有可能被多次扩展。B、特别是如果这样的节点处于问题的最优解路径上时，则一定会被多次扩展。C、h（n）≤h*（n）。D、A*算法效率低。

第1题：

正确答案：(6)能或可以、行及其他含义相同的词语 (7)不能或不可以、不行及其他含义相同的词语
(6)能，或可以、行及其他含义相同的词语 (7)不能，或不可以、不行及其他含义相同的词语 解析：本题考查的是算法的设计和分析技术。
问题1考查的是贪心算法的流程图。第(1)空表示第2个作业到第n个作业的主循环，i是循环控制变量，故第(1)空填入i<=n。
应注意到数组／中的作业J[i](1≤i≤k)是在其期限之前完成的作业，且d[J[i]]≤d[J[i+1]] (1≤id[i]。另一方面， J[D[R]]与r的关系只有两种：J[d[r]]>r，表示还可能在J[1]与J[r]之间插入作业i；J[d[r]]=r，表示不可能在J[1]～J[r]之间插入作业i。J[d[r]]问题2是本题算法的一个实例。6个作业的收益已经按降序排好序。根据流程图，将作业1，2，4和5放入数组J中，并得到总收益为220，具体过程如表4-1所示。

问题3考查算法策略。对于该题，贪心策略可以求得最优解。但不是所有的问题都能通过贪心策略来求得最优解，一个典型的例子是0-1背包问题。举例如下，有三件物品，背包可容纳50磅重的东西，每件物品的详细信息如表4-2所示，问如何装包使得其价值最大?

如果按贪心策略求解该问题，优先选择单位价值最大的物品，则先选择物品1，然后选择物品2。由于此时背包容量还剩下50-10-20=20，不足以容纳物品3，故总价值为 60+100=160美元。但若选择物品2和物品3，容量总和为20+30，小于等于总容量50，得到总价值为100+120=220，会得到更优解。此时用贪心策略不能得到最优解。

第2题：

Dijkstra算法可用于求解有负权的网络最短路问题。

第3题：

A*算法中，如果h满足单调条件，就一定不会出现重复扩展节点问题。

第4题：

对于0－1背包问题和背包问题的解法，下面（）答案解释正确。

• A、0－1背包问题和背包问题都可用贪心算法求解
• B、0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
• C、0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
• D、因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解

第5题：

动态规划算法的基本思想是将待求解问题分解成若干（），先求解（），然后从这些（）的解得到原问题的解。

第6题：

问题的（）是该问题可用动态规划算法或贪心算法求解的关键特征。

第7题：

动态规划算法有一个变形方法（）。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。

第8题：

设计算法就是寻求解决问题的方法，并进行精确描述。

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

修正的A*算法有可能会减少重复节点的扩展，而又不会比A*多扩展节点。

第15题：

Prim算法利用（）策略求解（）问题，其时间复杂度是（）。

第16题：

通过程序设计活动求解问题时，通常可分为问题建模、算法设计、编写代码和编译调试4个阶段。（）阶段的工作与所选择的程序语言密切相关。

• A、问题建模和算法设计
• B、算法设计和编写代码
• C、问题建模和编译调试
• D、编写代码和编译调试

第17题：

应用匈牙利算法求解工作指派问题时，对不打勾的行和打钩的列画横线。

第18题：

一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）。

• A、重叠子问题
• B、最优子结构性质
• C、贪心选择性质
• D、定义最优解

第19题：

算法与程序不同，算法是问题求解规则的一种过程描述。

第20题：

运用遗传算法处理供应链库存优化问题时，其求解的速度和质量都比常规算法要好。

第21题：

第22题：

第23题：

第24题：