最新资料欢迎阅读 D:旅行商问题 答案:
8、以下关于判定问题难易处理的叙述中错误的是 A:可以由多项式时间算法求解的问题是难处理的 B:需要超过多项式时间算法求解的问题是易处理的 C:可以由多项式时间算法求解的问题是易处理的 D:需要超过多项式时间算法求解的问题是不能处理的 答案:
9、下列说法错误的是
A:If X多项式时间归约到Y and Y多项式时间归约到Z, then X多项式时间归约到Z. B:P包含于NP
C:判定问题可多项式时间变换到优化问题
D:如果一个NP完全问题有多项式时间算法，那么NP中的每一个问题都可以有多项式时间算法 答案: 第二章
1、时间复杂度是指算法最坏情况下的运行时间。 答案: 对
2、f(n)=O(g(n)) 则 f(n)2=O(g(n)2) 答案: 对
3、f(n)=3n3+7n2+4nlogn =O(n2)
6
最新资料欢迎阅读 答案: 错
4、如果一个算法是多项式时间算法，该算法是有效的,是好算法。 答案: 对
5、从资源划分，算法的复杂度分为( )和()。 A:时间复杂度 空间复杂度 B: 空间复杂度 平均复杂度 C:最好复杂度 最坏复杂度 D:时间复杂度 平均复杂度 答案: 时间复杂度 空间复杂度
6、算法复杂度分析的两种基本方法为( )和( )。 A:结构化方法 面向对象方法 B:事后统计 事前分析 C:几何复杂度 平均复杂度 D:平摊复杂度 平滑复杂度
答案: 事后统计 事前分析 第三章
1、0-1背包问题的枚举算法的时间复杂度为O(2n) 答案:B
2、增量构造法生成子集前需要对集合中元素从小到大排列。
7
最新资料欢迎阅读 答案:A
3、分块查找一般设分块的长度是n/2. 答案:B
4、枚举法适用于问题的小规模实例。 答案:A
5、便于实现集合操作的子集生成算法是() A:增量构造法 B:位向量法 C:二进制法 答案:C
6、从所有候选答案中去搜索正确的解，这是 ()算法。 A:蛮力 B:枚举 C:递推 答案:B
7、logn2=( )(logn+5) A:θ B:O C:W D:o 答案:A
8、0-1背包问题的枚举算法，如果在百万次每秒的计算机上运
8
最新资料欢迎阅读 行，1年可以计算的问题规模估计是? A:40 B:60 C:30 D:50 答案:A
9、分数拆分问题的枚举算法通过()方法进行了优化。 A:减少枚举变量 B:减少枚举变量的值域 C:优化数据结构 D:优化数学模型 答案:ABD
10、下面那些算法的时间复杂度为O()? A:顺序查找 B:折半查找 C:插入排序 D:冒泡排序 E:折半插入排序
答案:插入排序、折半插入排序、冒泡排序 第四章
1、贪心算法总能找到可行解，但未必是最优解。 答案:A
9
最新资料欢迎阅读 2、贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。 答案:A
3、问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。 答案:A
4、如果图G中每条边的权重都是互不相同的，图G必定只有一颗最小生成树。 答案:A
5、Kruskal算法的贪婪准则是每一次选取不构成环路的最小边。 答案:A
6、贪心算法基本要素有( )和最优子结构性质。 A:分解合并性质 B:独立子问题性质 C:贪心选择性质 D:重叠子问题性质 答案:C
7、下面不是证明贪心算法证明方法的有()。 A:领先 B:优化 C:交换论证
10
2020智慧树知到《算法分析与设计》章节测试完整答案
