北语17春《算法与数据分析》作业1答案

发布 2022-07-08 06:39:28 阅读 2400

一、单选题(共10道试题,共50分。)

1.下列算法中通常以自底向上的方式求解最优解的是。

a.备忘录法。

b.动态规划法。

c.贪心法。

d.回溯法正确答案:b

2.回溯法解旅行售货员问题时的解空间树是。

a.子集树。

b.排列树。

c.深度优先生成树。

d.广度优先生成树正确答案:a

3.下列算法中通常以深度优先方式系统搜索问题解的是。

a.备忘录法。

b.动态规划法。

c.贪心法。

d.回溯法正确答案:d

4.实现最大子段和利用的算法是。

a.分治策略。

b.动态规划法。

c.贪心法。

d.回溯法正确答案:b

5.下面不是分支界限法搜索方式的是。

a.广度优先。

b.最小耗费优先。

c.最大效益优先。

d.深度优先正确答案:d

6.最大效益优先是下列哪项的一种搜索方式。

a.分支界限法。

b.动态规划法。

c.贪心法。

d.回溯法正确答案:a

7.分治法所能解决的问题一般具有的几个特征不包括。

a.该问题的规模缩小到一定的程度就可以容易地解决。

b.该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。

c.利用该问题分解出的子问题的解不可以合并为该问题的解。

d.原问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题正确答案:c

8.用分支限界法设计算法的第二步是。

a.针对所给问题,定义问题的解空间(对解进行编码。

b.确定易于搜索的解空间结构(按树或图组织解)

c.以广度优先或以最小耗费(最大收益)优先的方式搜索解空间。

d.在搜索过程中用剪枝函数避免无效搜索正确答案:b

9.以下不可以使用分治法求解的是。

a.棋盘覆盖问题。

b.选择问题。

c.归并排序。

d. 0/1背包问题正确答案:d

10.实现循环赛日程表利用的算法是。

a.分治策略。

b.动态规划法。

c.贪心法。

d.回溯法正确答案:a

17春《算法与数据分析》作业1

二、判断题(共10道试题,共50分。)

1.从分治法的一般设计模式可以看出,用它设计出的程序一般是递归算法。

a.错误。b.正确正确答案:b

2.以深度优先方式系统搜索问题解的算法称为回溯法。

a.错误。b.正确正确答案:b

3.拉斯维加斯算法找到的解不一定是正确解。

a.错误。b.正确正确答案:a

4.算法的复杂性没有时间复杂性和空间复杂性之分。

a.错误。b.正确正确答案:a

5.矩阵连乘问题的算法可由动态规划设计实现。

a.错误。b.正确正确答案:b

6.问题的最优子结构性质是该问题不可用动态规划算法或贪心算法求解的关键特征。

a.错误。b.正确正确答案:a

7.数值概率算法常用于数值问题的求解。

a.错误。b.正确正确答案:b

8.利用概率的性质计算近似值的随机算法是数值概率算法,运行时以一定的概率得到正确解的随机算法是蒙特卡罗算法。

a.错误。b.正确正确答案:b

9.程序是算法用某种程序设计语言的具体实现。

a.错误。b.正确正确答案:b

10.计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步。

a.错误。b.正确正确答案:b

北语17春《算法与数据分析》作业1答案

一 单选题 共 10 道试题,共 50 分。1.下列算法中通常以自底向上的方式求解最优解的是。a.备忘录法。b.动态规划法。c.贪心法。d.回溯法。正确答案 b 2.回溯法解旅行售货员问题时的解空间树是。a.子集树。b.排列树。c.深度优先生成树。d.广度优先生成树。正确答案 a 3.下列算法中通常...

北语17春《算法与数据分析》作业2答案

一 单选题 共 10 道试题,共 50 分。1.分支限界法解最大团问题时,活结点表的组织形式是。a.最小堆。b.最大堆。c.栈。d.数组。正确答案 b 2.贪心算法与动态规划算法的共同点是。a.重叠子问题。b.构造最优解。c.贪心选择性质。d.最优子结构性质。正确答案 d 3.蒙特卡罗算法是以下的哪...

北语17春《数据结构》作业

一 单选题 共 20 道试题,共 100 分。1.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为 a.24b.71 c.48d.53 正确答案 b 2.数组的逻辑结构不同于下列 的逻辑结构。a.线性表。b.栈。c.队列。d.树。正确答案 d 3.设有以下四种排序方法,...