自己搜的算法题2.0

1、二分搜索算法是利用(A )实现的算法。

A、分治策略B、动态规划法 C、贪心法 D、回溯法

2、下列不是动态规划算法基本步骤的是(A )。

A、找出最优解的性质B、构造最优解C、算出最优解 D、定义最优解

3、最大效益优先是( A )的一搜索方式。

A、分支界限法 B、动态规划法 C、贪心法 D、回溯法

4、在下列算法中有时找不到问题解的是(B )。

A、蒙特卡罗算法 B、拉斯维加斯算法C、舍伍德算法 D、数值概率算法

5、下列算法中不能解决0/1背包问题的是(A)

A贪心法B动态规划C回溯法D分支限界法

6、回溯法搜索状态空间树是按照(C)的顺序。

A中序遍历B广度优先遍历C深度优先遍历D层次优先遍历

7、下列随机算法中运行时有时候成功有时候失败的是(C)

A数值概率算法B舍伍德算法C拉斯维加斯算法D蒙特卡罗算法

8、实现合并排序利用的算法是(A )。

A、分治策略 B、动态规划法 C、贪心法 D、回溯法、

9、算法分析的目的是(D)

A、找出数据结构的合理性B、找出算法中输入和输出之间的关系 C、分析算法的易懂性和可靠性 D、分析算法的效率以求改进

10、如果按index访问item并就地插入或删除数据，这种操作比较频繁，那使用什么结构最节省时间?

A、数组 B、双向链表 C、单独存储 head 指针的双向链表 D、链表

二、填空题(每空2分，共30分)

1、算法是指解决问题的（一种方法）或（一个过程）。

2、从分治法的一般设计模式可以看出，用它设计出的程序一般是（递归算法）。

3、问题的（最优子结构性质），是该问题可用动态规划算法或贪心算法求解的

关键特征。

4、以深度优先方式系统搜索问题解的算法称为（回溯法）。

5、数值概率算法常用于（数值问题）的求解。

6、一个算法的优劣可以用（空间复杂度）和（时间复杂度） 来衡量。

7、直接或间接调用直接的方法称之为（递归技术）。

9贪心算法从初始阶段开始，每一个阶段总是作一个使（局部最优）的贪

心选择。

1. 拉斯维加斯算法找到的解一定是（正确的）

另一个试卷

2、单项选择题(本大题共30分，共 15 小题，母小题2分)

1.算法分析的两个主要方面是(  A )。

A.空间复杂度和时间复杂度

B.正确性和简单性

C.可读性和文档性

D.数据复杂度和程序复杂度

2.计算机算法指的是 (  C  )。

A.算方法

 B.排方法

C.解决问题的方法和过程

D.调度方法

3.多阶段决策问题,就是要在可以选择的那些策略中间,选取一个(  A)  策略、使在预定的标准下达到最好的效果。 A.最优 B.最差 C. 平衡 D. 任意

4.根据排序元素所在位置的不同，排序分(   A )。

A.内排序和外排序

B.首排序和尾排序

C.逆排

D.堆排序和栈排序

5.算法必须具备输入、输出和(  B )等5个特性。

A.可执行性、可移植性和可扩充性

B.可行性、确定性和有穷性

C.确定性、有穷性和稳定性

D.易读性、稳定性和安全性

1. 与分治法不同的是，适合于用动态规划求解的问题(  A)

1. 经分解得到子问题往往不是互相独立的
2. 经分解得到子问题往往是互相独立的
3. 经分解得到子问题往往是互相交叉的

D.经分解得到子问题往往是任意的

1. 二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较:如果( A    )，则只要在数组a的左半部继续搜索x。

 A.x

1. x=a[n/2]
2. x>a[n/2]
3. x>=a[n/2]

1. 活动安排问题就是在所给的活动集合中，选出( C  )的相容活子集。

1. 最小 B.任意 C.最大 D. 一个

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

A.回溯法

B.分支限界法

C.回溯法和分支限界法

D.回溯法求解子集树问题

10.适用动态规划的问题必须满足( D   )

A.优化原理

B.无前效性

C.优化理和后效

D.最优化原理和无后效性

11.算法的每种运算必须要有确切的定义,不能有二义性,以下符合算法确定性运算的是( B) A.5/0

B.将6或7与x相加

C.未赋值量参与运算

D.f(n)=f(n-1)+2,F(1)=10,n为自然数

12.直接或间接的调用自身的算法称为(B )。

A.贪心算法

B.递归算法

C.迭代算法

D.动态规划算法

13. 二分查找只适用(B )存储结构。

A.堆

B. 顺序 C.任意顺序

D. 栈

14.实现快速排序算法如下:

 

A.quickSort(p,q-1) B.quickSort(p+1q-1) C.quickSort(p,q+1) D.quickSort(p,q-2)

15.应用分治法的两个前提是(  A)。 A.问题的可分性和解的可归并性 B.问题的可分性和解的存在性

C.问题的复杂性和解的可归并性 D.问题的可分性和解的复杂性

二、判断题(本大题共 70分，共 20 小题，每小题 3.5 分)

1.算法就是一组有穷的规则?(  √ )

2.概率算法中蒙特卡罗算法得到的解必是正确的?(  x  )

3.程序和算法一样，都是某种程序设计语言的具体实现。(  x  )

4.合并排序算法是渐近最优算法?   (  √   )

5.递归定义必须是有确切含义是指必须一步比一步简单,最后是有终结的,决不能无限循环下去(  √  )

6.二分搜索方法在最坏的情况下用0(logn)时间完成搜索任务。(  √ )

7.能否利用分治法完全取决于问题是否具有如下特征:利用该问题分解出的子问题的解可以合并为该问题的解。(   √ )

8.分治法的基本思想是将一个规模较大的问题分解成若干个规模较小的子问题，这些子问题之间并不一定相互独立(  x  )

9.递归算法的效率往往很低，费时和费内存空间( √ )

10.当一个问题具有最优子结构性质时只能用动态规划方法求解。(  x )

11.如果一类活动过程一个阶段的决策确定以后，常影响到下一个阶段的决策，则称它为多阶段决策问题。    (   √ )

12.反复应用分治手段,不能使子问题与原问题类型一致而其规模却不断缩小?(   √  ) 

13.裴波那契数列的定义:f(n)=f(n-1)+f(n-2),f(0)=1f(1)=2，其数据的定义形式不是按递归定义。(   x   )

14 0-1背包问题与背包问题这两类问题都可以用贪心算法求解。(  x  )

15.证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。(  x )

16.子问题之间不包含公共的子问题,这个条件涉及到分治法的效率()17.概率算法允许在执行过程中随机地选择下一个计算步骤?(  √  )

18，二分搜索法的二分查找只适用于顺序存储结构。 ( √ )

19.要想在电脑上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度( √ )

20.用回溯法解题一个显著特征是在搜索过程中动态产生问题的解空间(  √ )

2011年12月考试算法设计分析第二次作业

一、单项选择题(本大题共30分，共15 小题，每小题2 分)

1.优先队列的分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。优先队列中规定的结点优先级常用一个与该结点相关的数值p来表示。结点优先级的高低与p值大小相关，根据问题的不同情况，采用(   C   )来描述优先队列。

 A.先进先出队列

B.后进先出的栈

C.最大堆或最小堆

D.随机序列

2.阶乘函数用递归定义 Public static int factorial(intn)

{if(n==O)

return 1;

 return ();

}   B

An*factorial(n) B.n*factorial(n-1) C.n*factorial(n-2) D.n*factorial(n+1)

3.(  B  )能够求得问题的解,但却无法有效地判定解的正确性

A.数值概率算法 B.蒙特卡罗算法 C.拉斯维加斯算法 D全伍得算法

4.对于n个元素的排序问题。n=2时，只要作(   C  )次比较即可排好序

A. 3

B. 2

C.1

 D. 4

5，一般地讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法和备忘录算法相比: (   B   )

A.效果一样动态规划效果好

B.备忘录方法效果好

C.无法判断 D.哪个效果好

6分支限界法与回溯法都是在问题的解空间树T上搜索问题的解,二者(  B   )

1. 求解目标不同,搜索方式相同
2. 求解目标不同,搜索方式也不同
3. 求解目标相同,搜索方式不同

D.求解目标相同,搜索方式也相同

1. 递归算法不能适用以下场合(  D  )

A.数据的定义形式按递归定义

B.数据之间的关系(即数据结构)按递归定义

C.问题解法按递归算法实现

D，概率问题

8.当子问题之间包含公共的子子问题则分治法要做许多不必要的工作,重复地解公共的子问题，此时一般用(  A  )法较好

A.动态规划 

B.分治

C.贪心

D. 概率

9.分治法所能解决的问题应具有的关键特征是(   C  )。

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

B。该问题可以分解为若干个规模较小的相同问题

C.用该问题分解出的子问题的解可以合并为该问题的解

 D.该问题所分解出的各个子问题是相互独立的

10.对于货箱装船问题,根据贪心策略,首先选择(  A  )的货箱,然后选 ()的货箱，如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱

A.最轻次轻

B.最重次重

C.最轻重

D.最重次轻

11.用回溯法解n后问题时，用完全n叉树表示解空间。可行性约束place剪去不满足行、列和斜线约束的子树，place的if判断条件应为(  A  )

 A.(Math.abs(k-j)==Math.abs(x[j]-x[k]))(x[j]==x[k])

B.(Math.abs(k-j)==Math.abs(x[j]-x[k])

 C.(x[j]==x[k]) D，以上都不正确

12.分支限界法的搜索策略是:在扩展结点处，先生成其(   D )儿子结点(分支)，然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值(限界)，并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

A.一个 B.二个

C.任意多个 D. 所有的

13.能够用动态规划解决的问题还有一个显著特征(  D  )这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。

A.子问题的可求解性

B.子问题的独立性

C.子问题的可合并性

D.子问题的重叠性

 A

1. 动态规划的时间复杂度为(  C  )

A.0(n) B.0(n!) C. 0(n) D. O(n')

二、判断题(本大题共 70分，共 20小题，每小题35 分)

1.从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此，分治法的计算效率通常可以用递归方程来进行分析。(  √  )

2.多阶段决策问题中，每一个阶段可能有若干个决策可供选择(  √  )

3.拉斯维加斯算法不会得到不正确的解，但有时找不到解。 (  √  )

4.在通往边界条件的递归调用过程中，系统用堆栈保存的每次调用的中间结果是局部变量和返回地址值。(    √    )

5.要想在电脑上扩大所处理问题的规模,有效的途径是提高算法的计算复杂度。(  x  )

6.程序必须满足算法具有数据输出的性质(  √  )

7.反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小(  √ )

8.一个算法产生一个或多个输出，它们是同输入有某种特定关系的量(  √  )

9.最优子结构性质特征反映了递归思想的应用()10.递归边界本身并不使用递归的定义(  √ )

1. 用分治法求解一个问题，所需的时间是由子问题的个数、大小以及把这个问题分解为子问题所需的工作总量来确定的。( √   )

12.用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个(最优)解。(  √  )

13.好的约束函数能显著地减少所生成的结点数，但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。  √

1. 一个递归定义必须是有确切含义的，必须一步比一步简单，最后是有终结的，不能无限循环下去( √  )。

15.最优子结构性质是应用分治法的前提( √  )

1. 操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。( √ )

17，有些数据结构如二叉树等，由于其本身的递归特性、特别适合用递归的形式来描述。( √ )

18.概率算法的一个基本特征是，对所求问题的同一个实例用同一个算法求解两次一定能得到完全相同的效果。(  x)

19.问题可以分解为若干个规模较小的相同问题，即称该问题具有最优子结构性质(  x  )

20.递推是从内边界条件出发，通过递推式达到边界条件。( √ )

2011年12月考试算法设计分析第三次作业

一、填空题(本大题共30分，共5小题，每小题6分)

1.分支限界法的求解目标 是   (找出满足约束条件的一个解）

2.贪心算法和（动态规划）算法都要求问题具有最优子结构性质。

3.动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现（大量的重复） 。

5.动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决（最优化问题）的算法策略。

二、改错题(本大题共30分，共5小题，每小题6分)

1.好的约束函数能显著地减少所生成的结点数，但这样的约束函数往往计算量较大。(  对)

2.能够用动态规划解决的问题有一个显著特征:子问题的重叠性。(   对)

3.与分治法不同的是，适合于用动态规划求解的问题经分解得到子问题往往是互相不独立的(   错)  解析： 往往相互独立

4.分限界法不仅通过约束条件,而且可通过目标函数的限界来减少无效搜索(  对)

5.贪心算法所做的选择都是目前最佳的(  对)

 

4、渐进算法分析是指 B

(A)算法在最佳情况、最差情况和平均情况下的代价

(B)当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析

(C)数据结构所占用的空间

(D)在最小输入规模下算法的资源代价

 

6、采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素。以下对顺序搜索法分析正确的是。   B

(A)最佳情况、最差情况和平均情况下，顺序搜索法的渐进代价都相同

(B)最佳情况的渐进代价要好于最差情况和平均情况的渐进代价

(C)最佳情况和平均情况的渐进代价要好于最差情况的渐进代价

(D)最佳情况的渐进代价要好于平均情况的渐进代价，而平均情况的渐进代价要好于最差情况的渐进代价

7、递归通常用来实现。  C

(A)有序的线性表 (B)队列 (C)栈 (D)数组

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

(A)问题规模相同，问题性质相同

(B)问题规模相同，问题性质不同

(C)问题规模不同，问题性质相同

(D)问题规模不同，问题性质不同

9、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准?下面 答案解释最合理。  D

(A)随机选择一个元素作为划分基准 

(B)取子序列的第一个元素作为划分基准

(C)用中位数的中位数方法寻找划分基准

(D)以上皆可行。但不同方法，算法复杂度上界可能不同

1. 对于0-1背包问题和背包问题的解法，下面答案解释正确。  C

(A)0-1背包问题和背包问题都可用贪心算法求解   

(B)0-1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解

(C)0-1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解

(D)因为0-1背包问题不具有最优子结构性质，所以不能用含心算法求解

11、关于回溯搜索法的介绍，下面是不正确描述。  D

(A)回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解

(B)回溯法是一种既带系统性又带有跳跃性的搜索算法

(C)回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯

(D)回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径

12、关于回溯算法和分支限界法，以下 是不正确描述。  A

(A)回溯法中，每个活结点只有一次机会成为扩展结点

(B)分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中

(C)回溯法采用深度优先的结点生成策略

(D)分支限界法采用广度优先或最小耗费优先(最大效益优先)的结点生成策略

1. 优先队列通常用以下数据结构来实现。  B

(A)栈(B)堆(C)队列

(D)二叉查找树

14、在分支限界算法中，根据从活结点表中选择下一扩展结点的不同方式可有几种常用分类，以下描述最为准确   D

(A)采用FIFO队列的队列式分支限界法

(B)采用最小值堆的优先队列式分支限界法

(C)采用最大值堆的优先队列式分支限界法

(D)以上都常用，针对具体问题可以选择采用其中某种更为合适的方式

15、对布线问题，以下是不正确描述   C

(A)布线问题的解空间是一个终 

(B)可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定

(C)采用广度优先的标号法找到从起点到终点的布线方案(这个方案如果存在的话)不一定是最短的

(D)采用先入先出的队列作为活结点表，以终点b为扩展结点或活结点队列为空作为算法结束条件

二、填空题(20分，每空2分)

2、一个直接或间接调用自身的算法称为_ 递归_算法。

出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致（  相等） 。

3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O(   )，在最坏情况下，搜索的时间复杂性为0(   )。

 

4、动态规划算法的基本要素是 （最优子结构性质）  和（子问题重叠性质）

5、动态规划算法有一个变形方法-（  备忘录方法  ）。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。

6、贪心算法的基本要素是  （贪心选择性质） 和最优子结构性质。