算法设计与分析知到智慧树章节测试课后答案2024年秋山东科技大学

算法设计与分析知到智慧树章节测试课后答案2024年秋山东科技大学第一章单元测试

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

A:错B:对

答案:错有关算法分析的事后统计法正确的是（）。

A:从理论上讲，在各种软硬件环境下进行算法测试，得到的资源耗费都是一样的。

B:测试的结果与程序的编译和运行环境有关

C:结果与测试的样本数据有关

D:结果是面向机器，面向程序员，面向语言的

答案:测试的结果与程序的编译和运行环境有关

；结果与测试的样本数据有关

；结果是面向机器，面向程序员，面向语言的

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

A:确定合适的数据结构

B:使用何种计算机语言设计程序

C:证明算法的正确性。

D:是求精确解还是近似解

答案:确定合适的数据结构

；是求精确解还是近似解

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

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

答案:O(logn)

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

A:logn＜n1/2＜2n＜n3＜n!＜3n

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

答案:logn＜n1/2＜2n＜n3＜3n＜n!研究NPC问题的意义:一旦某个NPC问题找到了多项式时间复杂性的算法，那么所有的NP问题都找到了多项式时间算法。()

A:错B:对

答案:对

第二章单元测试

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

A:递归算法

B:动态规划算法

C:贪心算法

D:迭代算法

答案:递归算法

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

A:

B:

C:

D:

答案:

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

A:问题规模不同，问题性质不同

B:问题规模不同，问题性质相同

C:问题规模相同，问题性质不同

D:问题规模相同，问题性质相同

答案:问题规模不同，问题性质相同

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

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

答案:O(logn)二分搜索算法只适用（）存储结构。

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

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

A:1000

B:500C:11D:10

答案:10线性时间选择的时间复杂度为（）。

A:O(logn)B:O(n2)C:O(n)

D:O（nlogn）

答案:O(n)

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

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

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

A:{15,13,2}16{27,38}

B:{13,2,15}16{27,38}

C:{13,2,15}16{38,27}

D:{2,13,15}16{38,27}

答案:{13,2,15}16{27,38}

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

A:错B:对

答案:对

第三章单元测试

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

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

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

C:zk=xm=yn，且zk是Xm-1和Yn-1的最长公共子序列。

D:zk=xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。

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

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

A:10B:6C:9

D:7

答案:6设有四个矩阵A,B,C,D,它们的维数分别是A=50*10,B=10*40,C=40*30,D=30*50,，则计算其乘积至少需要（）次乘法

A:87500

B:10500,C:16000,D:36000,

答案:10500,下面关于动态规划解题的步骤内容描述正确的是哪些？（）

A:建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。

B:构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造。

C:计算最优值：以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值。

D:分析最优解的结构：将一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质。

答案:建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。

；构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造。

；分析最优解的结构：将一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质。

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

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

答案:子问题重叠性质对0-1背包问题，n=5，c=12，w={3,7,5,4，4}，v={6,3,5,4，6}，则其最优解为（）

A:（0，1，0，1，1）B:（1，0，1，0，1）

C:（1，1，1，1，1）

D:（0，1，1，1，1）

答案:（1，0，1，0，1）

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

A:错B:对

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

A:错B:对

答案:对

第四章单元测试

在某通讯系统中用到了a，b，c，d，e，f8个字符，字符频度（百分比）为45，13，12，16，9，5则字符a的编码为()：

A:0B:.111C:1100

答案:0活动安排问题利用贪心法求解，则其复杂度为（）

A:O(nlogn)B:O(logn)

C:O(n)D:O(n2)

答案:O(nlogn)在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。()

A:对B:错

答案:对背包问题与0-1背包问题求解方法类似，都能用贪心法或动态规划方法得到最优解（）

A:错B:对

答案:错有关分治法、贪心算法和动态规划算法的描述，正确的是（）

A:问题能用动态规划法解的不一定能用贪心算法解；

B:适用三种方法所解的问题都是可分解成子问题的；

C:用贪心法一定能用动态规划法，但是，动态规划法的效率一般高于贪心算法。

D:贪心算法和动态规划算法共同特征为最优子结构性质;

答案:问题能用动态规划法解的不一定能用贪心算法解；

；适用三种方法所解的问题都是可分解成子问题的；

；贪心算法和动态规划算法共同特征为最优子结构性质;

下列哪些问题能适用贪心法高效求解？（）

A:最小生成树问题

B:0-1背包问题C:哈夫曼编码问题D:单源最短路径问题

答案:最小生成树问题

；哈夫曼编码问题；单源最短路径问题

第五章单元测试

使用回溯法求解0-1背包问题时，计算右子树上界的方法是通过贪心策略求得上界（）

A:错B:对

答案:对适用回溯法解旅行售货员问题，只有当搜索到最后一个城市时，才能判断当前路径是否是该问题的一个解。（）

A:错B:对

答案:错下面关于用回溯法解题说法，正确的是().

A:这种方法适用于解一些组合数相当大的问题。

B:解空间树有子集树与排列树两种;

C:显式地存储整个解空间；

D:在搜索过程中动态产生问题的解空间；

答案:这种方法适用于解一些组合数相当大的问题。

；解空间树有子集树与排列树两种;

；在搜索过程中动态产生问题的解空间；

回溯法中的剪枝函数包括()。

A:随机数生成函数

B:约束函数

C:限界函数

D:递归函数

答案:约束函数

；限界函数

回溯法解题步骤,正确的是（）

A:确定易于搜索的解空间结构;

B:以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索;

C:确定最优子结构的性质;

D:针对所给问题，定义问题的解空间;

答案:确定易于搜索的解空间结构;

；以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索;

；针对所给问题，定义问题的解空间;

四色定理是第一个主要由计算机证明的理论（）

A:对B:错

答案:对

第六章单元测试

在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是()。

A:回溯法求解子集树问题B:回溯法C:回溯法和分支限界法

D:分支限界法

答案:分支限界法分支限界法与回溯