算法设计与分析 知到智慧树答案2024 z28027

第一章 单元测试

1、 程序运行结果往往与输入相关，所以程序可以不满足确定性（ ）

A:错
B:对
答案: 错

2、 有关算法分析的事后统计法正确的是（ ）。

A:从理论上讲，在各种软硬件环境下进行算法测试，得到的资源耗费都是一样的。
B:测试的结果与程序的编译和运行环境有关
C:结果是面向机器，面向程序员，面向语言的
D:结果与测试的样本数据有关
答案: 测试的结果与程序的编译和运行环境有关
,结果是面向机器，面向程序员，面向语言的
,结果与测试的样本数据有关

3、 下面哪些内容是算法设计之前要完成的内容? ( )

A:证明算法的正确性。
B:确定合适的数据结构
C:使用何种计算机语言设计程序
D:是求精确解还是近似解
答案: 确定合适的数据结构
,是求精确解还是近似解

4、 函数10logn3+5logn2的渐近表达式为（ ）：

A:O(nlogn)
B:O（logn2）
C:O(logn3)
D:O(logn)
答案: O(logn)

5、 下列函数根据渐近阶从低到高顺序是（ ）

A:n1/2 ＜ logn ＜2n ＜n3 ＜3n ＜n!
B:n1/2 ＜ logn ＜2n ＜n3 ＜ n! ＜ 3n
C:logn ＜n1/2＜2n ＜n3 ＜ n! ＜ 3n
D:logn ＜ n1/2 ＜2n ＜n3 ＜3n ＜n!
答案: logn ＜ n1/2 ＜2n ＜n3 ＜3n ＜n!

6、 研究NPC 问题的意义: 一旦某个NPC问题找到了多项式时间复杂性的算法，那么所有的NP问题都找到了多项式时间算法。( )

A:对
B:错
答案: 对

第二章 单元测试

1、 直接或间接的调用自身的算法称为（ ）。

A:贪心算法
B:动态规划算法
C:递归算法
D:迭代算法
答案: 递归算法

2、 Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（ ）

A:

B:

C:

D:

答案:

3、 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题分别解决子问题最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（ ）。

A:问题规模不同，问题性质不同
B:问题规模相同，问题性质相同
C:问题规模相同，问题性质不同
D:问题规模不同，问题性质相同
答案: 问题规模不同，问题性质相同

4、 利用二分搜索，最坏情况下的计算时间复杂性为（ ）。

A:O (n2)
B:O（n）
C:O (logn)
D:O (2n)
答案: O (logn)

5、 二分搜索算法只适用（ ）存储结构。

A:堆
B:任意顺序
C:栈
D:顺序
答案: 顺序

6、 使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数为（ ）。

A:10
B:1000
C:500
D:11
答案: 10

7、 线性时间选择的时间复杂度为（ ）。

A:O(n)
B:O （nlogn）
C:O(n2)
D:O(logn)
答案: O(n)

8、 利用合并排序，其辅助空间为（ ）：

A:O(logn)
B:O(nlogn)
C:O（n）
D:O(n2)
答案: O（n）

9、 利用快速排序，对数的序列{16, 27, 13, 2, 15,38}，选择基准16，进行一次划分，结果为（ ）：

A:{2, 13, 15} 16 {38, 27}
B:{13, 2, 15} 16 {27, 38}
C:{15, 13, 2} 16 {27, 38}
D:{13, 2, 15} 16 {38,27}
答案: {13, 2, 15} 16 {27, 38}

10、 分治策略解决棋盘覆盖问题是一个渐近意义下最优的算法.（ ）

A:对
B:错
答案: 对

第三章 单元测试

1、 设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，若xm=yn则（ ）。

A:zk≠xm=yn，且zk是Xm-1和Yn-1的最长公共子序列。
B:zk=xm=yn，且zk是Xm-1和Yn-1的最长公共子序列。
C:zk≠xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。
D:zk=xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。
答案: zk=xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。

2、 当(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10)=(-1, 5, -2, 1, -7, -4, 2, 3, -1, 2)时，最大子段和为( ).

A:7
B:10
C:6
D:9
答案: 6

3、 设有四个矩阵A,B,C,D,它们的维数分别是A=5010, B=1040, C=4030, D=3050,，则计算其乘积至少需要（ ）次乘法

A:87500
B:10500,
C:16000,
D:36000,
答案: 10500,

4、 下面关于动态规划解题的步骤内容描述正确的是哪些？（ ）

A:计算最优值：以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值。
B:分析最优解的结构：将一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质。
C:构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造。
D:建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。
答案: 分析最优解的结构：将一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质。
,构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造。
,建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。

5、 问题用动态规划算法求解效率较高的原因？( )

A:最优子结构性质
B:子问题重叠性质
C:贪心选择性质
D:递归性质.
答案: 子问题重叠性质

6、 对0-1背包问题，n=5，c=12，w={3,7,5,4，4}，v={6,3, 5,4，6 }，则其最优解为（ ）

A:（1，0，1，0，1）
B:（0，1，0，1，1）
C:（0，1，1，1，1）
D:（1，1，1，1，1）
答案: （1，0，1，0，1）

7、 一般来说解同一个问题，动态规划法的效率高于分治算法（ ）

A:错
B:对
答案: 错

8、 图象的变位压缩存储采用数据头和数据存储的编码式存储方式，节省存储空间，实现压缩。（ ）

A:对
B:错
答案: 对

下方是付费阅读内容：本平台商品均为虚拟商品，无法用作二次销售，不支持退换货，请在购买前确认您需要购买的资料准确无误后再购买，望知悉！

完整答案需点击上方按钮支付5元购买,所有答案均为章节测试答案，无期末答案。购买后上方矩形框将出现已付费的隐藏内容。

不知道怎么购买？点此查看购买教程！