高级中学信息技术算法与程序设计章节练习(2019.05.13)

问答题
用贪心算法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。
答案：首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品...
填空题
许多可以用贪心算法求解的问题一般具有2个重要的性质：（）性质和（）性质。
答案：贪心选择；最优子结构
单项选择题
应用Johnson法则的流水作业调度采用的算法是（）
A.贪心算法
B.分支限界法
C.分治法
D.动态规划算法
填空题
以深度优先方式系统搜索问题解的算法称为（）。
答案：回溯法
填空题
算法的复杂性有（）和（）之分，衡量一个算法好坏的标准是（）。
答案：时间复杂性；空间复杂性；时间复杂度高低
单项选择题
以下关于渐进记号的性质是正确的有：（）
A.f（n）=Θ（g（n）），g（n）=Θ（h（n））→f（n）=Θ（h（n））
B.f（n）=O（g（n）），g（n）=O（h（n））→h（n）=O（f（n））
C.O（f（n））+O（g（n））=O（min{f（n），g（n）}）
D.f（n）=O（g（n））→g（n）=O（f（n））
单项选择题
k带图灵机的空间复杂性S（n）是指（）
A.k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数
B.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和
C.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数
D.k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最小方格数
填空题
所谓最优子结构性质是指（）。
答案：问题的最优解包含了其子问题的最优解
问答题
输入某年，某月，某日，判断这一天是这一年的第几天。
答案：#include
void main()
{
int y,m,d;
填空题
某一问题可用动态规划算法求解的显著特征是（）。
答案：该问题具有最优子结构性质