算法选择题初级版 256道.docx

算法选择题初级版 256道.docx

《算法选择题初级版 256道.docx》由会员分享，可在线阅读，更多相关《算法选择题初级版 256道.docx（68页珍藏版）》请在冰点文库上搜索。

算法选择题初级版256道

算法选择题（初级版）256道

1.二分搜索算法是利用（）实现的算法。

[单选题]*

A.分治策略（正确答案）

B.动态规划法

C.贪心法

D.回溯法

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

[单选题]*

A.子集树

B.排列树（正确答案）

C.深度优先生成树

D.广度优先生成树

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

[单选题]*

A.备忘录法

B.动态规划法（正确答案）

C.贪心法

D.回溯法

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

[单选题]*

A.广度优先

B.最小耗费优先

C.最大效益优先

D.深度优先（正确答案）

5.采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为（）。

[单选题]*

A.O（n2^n）

B.O（nlogn）（正确答案）

C.O（2^n）

D.O（n）

6.分支限界法求解最大团问题时，活结点表的组织形式是（）。

[单选题]*

A.最小堆

B.最大堆（正确答案）

C.栈

D.数组

7.下面问题（）不能使用贪心法解决。

[单选题]*

A.单源最短路径问题

B.N皇后问题（正确答案）

C.最小花费生成树问题

D.背包问题

8.下列算法中不能解决0/1背包问题的是（）。

[单选题]*

A.贪心法（正确答案）

B.动态规划

C.回溯法

D.分支限界法

9.背包问题的贪心算法所需的计算时间为（）。

[单选题]*

A.O（n2n）

B.O（nlogn）（正确答案）

C.O（2n）

D.O（n）

10.二分查找是利用（）实现的算法。

[单选题]*

A.分治策略（正确答案）

B.动态规划法

C.分支限界法

D.概率算法

11.下列不是动态规划算法基本步骤的是（）。

[单选题]*

A.找出最优解的性质

B.构造最优解（正确答案）

C.算出最优解

D.定义最优解

12.最大效益优先是（）的一种搜索方式。

[单选题]*

A.分支界限法（正确答案）

B.动态规划法

C.贪心法

D.回溯法

13.在下列算法中有时找不到问题解的是（）。

[单选题]*

A.蒙特卡罗算法

B.拉斯维加斯算法（正确答案）

C.舍伍德算法

D.数值概率算法

14.对于动态规划，下面说法错误的是（）。

[单选题]*

A.动态规划（dynamicprogramming）是运筹学的一个分支

B.动态规划是求解决策过程（decisionprocess）最优化的数学方法

C.虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

D.动态规划类似搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。

（正确答案）

15.衡量一个算法好坏的标准是（）。

[单选题]*

A.运行速度快

B.占用空间少

C.时间复杂度低（正确答案）

D.代码短

16.以下不可以使用分治法求解的是（）。

[单选题]*

A.棋盘覆盖问题

B.选择问题

C.归并排序

D.0/1背包问题（正确答案）

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

[单选题]*

A.分治策略（正确答案）

B.动态规划法

C.贪心法

D.回溯法

18.下列随机算法中运行时有时候成功有时候失败的是（）。

[单选题]*

A.数值概率算法

B.舍伍德算法

C.拉斯维加斯算法（正确答案）

D.蒙特卡罗算法

19.对于分支限界法，下面不属于分支限界法搜索方式的是（）。

[单选题]*

A.广度优先

B.最小耗费优先

C.最大效益优先

D.层次优先（正确答案）

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

[单选题]*

A.备忘录法

B.动态规划法

C.贪心法

D.回溯法（正确答案）

21.备忘录方法是那种算法的变形（）。

[单选题]*

A.分治法

B.动态规划法（正确答案）

C.贪心法

D.回溯法

22.哈夫曼编码的贪心算法所需的计算时间为（）。

[单选题]*

A.O（n2n）

B.O（nlogn）（正确答案）

C.O（2n）

D.O（n）

23.最长公共子序列算法利用的算法是（）。

[单选题]*

A.分支界限法

B.动态规划法（正确答案）

C.贪心法

D.回溯法

24.实现棋盘覆盖算法利用的算法是（）。

[单选题]*

A.分治法（正确答案）

B.动态规划法

C.贪心法

D.回溯法

25.下面是贪心算法的基本要素的是（）。

[单选题]*

A.重叠子问题

B.构造最优解

C.贪心选择性质（正确答案）

D.定义最优解

26.回溯法的效率不依赖于下列哪些因素（）。

[单选题]*

A.满足显约束的值的个数

C.计算限界函数的时间

B.计算约束函数的时间

D.确定解空间的时间（正确答案）

27.下面哪种函数是回溯法中为避免无效搜索采取的策略（）。

[单选题]*

A.递归函数

B.剪枝函数（正确答案）

C.随机数函数

D.搜索函数

28.下面关于NP问题说法正确的是（）。

[单选题]*

A.NP问题都是不可能解决的问题

B.P类问题包含在NP类问题中（正确答案）

C.NP完全问题是P类问题的子集

D.NP类问题包含在P类问题中

29.蒙特卡罗算法是（）的一种。

[单选题]*

A.分支界限算法

B.概率算法（正确答案）

C.贪心算法

D.回溯算法

30.下列哪一种算法不是随机化算法（）。

[单选题]*

A.蒙特卡罗算法

B.拉斯维加斯算法

C.动态规划算法（正确答案）

D.舍伍德算法

31.（）是贪心算法与动态规划算法的共同点。

[单选题]*

A.重叠子问题

B.构造最优解

C.贪心选择性质

D.最优子结构性质（正确答案）

32.矩阵连乘问题的算法可由（）设计实现。

[单选题]*

A.分支界限算法

B.动态规划算法（正确答案）

C.贪心算法

D.回溯算法

33.Strassen矩阵乘法是利用（）实现的算法。

[单选题]*

A.分治策略（正确答案）

B.动态规划法

C.贪心法

D.回溯法

34.使用分治法求解不需要满足的条件是（）。

[单选题]*

A.子问题必须是一样的（正确答案）

B.子问题不能够重复

C.子问题的解可以合并

D.原问题和子问题使用相同的方法求解

35.回溯法搜索状态空间树是按（）的顺序。

[单选题]*

A.中序遍历

B.广度优先遍历

C.深度优先遍历（正确答案）

D.层次优先遍历

36.实现合并排序利用的算法是（）。

[单选题]*

A.分治策略（正确答案）

B.动态规划法

C.贪心法

D.回溯法

37.下列是动态规划算法基本要素的是（）。

[单选题]*

A.定义最优解

B.构造最优解

C.算出最优解

D.子空间重叠性质（正确答案）

38.采用广度优先策略搜索的算法是（）。

[单选题]*

A.分支限界法（正确答案）

B.动态规划法

C.贪心法

D.回溯法

39.在下列算法中得到的解未必正确的是（）。

[单选题]*

A．蒙特卡罗算法（正确答案）

B．拉斯维加斯算法

C．舍伍德算法

D．数值概率算法

40.实现大整数的乘法是利用的算法（）。

[单选题]*

A.贪心法

B.动态规划法

C.分治策略（正确答案）

D.回溯法

41.0/1背包问题的回溯算法所需的计算时间为（）。

[单选题]*

A.O（n2n）（正确答案）

B.O（nlogn）

C.O（2n）

D.O（n）

42.动态规划算法与贪心法的主要区别是（）。

[单选题]*

A.最优子结构（正确答案）

B.贪心选择性质

C.构造最优解

D.定义最优解

43.实现最大子段和利用的算法是（）。

[单选题]*

A.分治策略

B.动态规划法（正确答案）

C.贪心法

D.回溯法

44.优先队列式分支限界法选取扩展结点的原则是（）。

[单选题]*

A.先进先出

B.后进先出

C.结点的优先级（正确答案）

D.随机

45.广度优先是（）的一种搜索方式。

[单选题]*

A.分支限界算法（正确答案）

B.动态规划法

C.贪心算法

D.回溯算法

46.舍伍德算法是（）的一种。

[单选题]*

A.分支界限算法

B.概率算法（正确答案）

C.贪心算法

D.回溯算法

47.对于下列算法，有时找不到问题解的是（）。

[单选题]*

A.蒙特卡罗算法

B.拉斯维加斯算法（正确答案）

C.快速排序算法

D.数值概率算法

48.下列哪一种算法是随机化算法（）。

[单选题]*

A.贪心算法

B.回溯法

C.动态规划算法

D.舍伍德算法（正确答案）

49.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）。

[单选题]*

A.重叠子问题（正确答案）

B.最优子结构性质

C.贪心选择性质

D.定义最优解

50.以深度优先方式系统搜索问题解的算法称为（）。

[单选题]*

A.分支界限算法

B.概率算法

C.贪心算法

D.回溯算法（正确答案）

51.对于最长公共子序列，下面说法错误的是（）。

[单选题]*

A.最长公共子序列，英文缩写为LCS（LongestCommonSubsequence）。

其定义是，一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。

B.最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”。

C.最长公共子串和最长公共子序列是不同的

D.最长公共子串和最长公共子序列是相同的（正确答案）

52.当一个算法的空间复杂度与问题的规模n成正比时，则表示为（）。

[单选题]*

A.O

（1）

B.O（n）（正确答案）

C.O（n*n）

D.O1

53.当一个算法的时间复杂性与问题的规模n大小无关时，则表示为（）。

[单选题]*

A.1

B.O

（1）（正确答案）

C.O（n）

D.O（0）

54.算法分析的两个主要方面是（）。

[单选题]*

A.空间复杂度和时间复杂度（正确答案）

B.正确性和简单性

C.可读性和文档性

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

55.计算机算法指的是（）。

[单选题]*

A.计算方法

B.排序方法

C.解决问题的方法和过程（正确答案）

D.调度方法

56.多阶段决策问题就是要在可以选择的那些策略中间选取一个（）策略使在预定的标准下达到最好的效果。

[单选题]*

A.最优（正确答案）

B.最差

C.平衡

D.任意

57.根据排序元素所在位置的不同，排序分（）。

[单选题]*

A.内排序和外排序（正确答案）

B.首排序和尾排序

C.顺序排序和逆序排序

D.堆排序和栈排序

58.算法必须具备输入、输出和（）等5个特性。

[单选题]*

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

B.可行性、确定性和有穷性（正确答案）

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

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

59.与分治法不同的是，适合于用动态规划求解的问题（）。

[单选题]*

A.经分解得到子问题往往不是互相独立的（正确答案）

B.经分解得到子问题往往是互相独立的

C.经分解得到子问题往往是互相交叉的

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

60.二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较：

如果（），则只要在数组a的左半部继续搜索x。

[单选题]*

A.x＜a[n/2]（正确答案）

B.x=a[n/2]

C.x>a[n/2]

D.x>=a[n/2]

61.活动安排问题就是在所给的活动集合中，选出（）的相容活子集。

[单选题]*

A.最小

B.任意

C.最大（正确答案）

D.一个

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

[单选题]*

A.回溯法

B.分支限界法（正确答案）

C.回溯法和分支限界法

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

63.适用动态规划的问题必须满足（）。

[单选题]*

A.最优化原理

B.无前效性

C.最优化原理和后效性

D.最优化原理和无后效性（正确答案）

64.算法的每种运算必须要有确切的定义不能有二义性，以下符合算法确定性运算的是（）。

[单选题]*

A.5/0

B.将6或7与x相加（正确答案）

C.未赋值变量参与运算

D.

f（n）=f（n-1）+2，F

（1）=10，n为自然数

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

[单选题]*

A.贪心算法

B.递归算法（正确答案）

C.迭代算法

D.动态规划算法

66.二分查找只适用（）存储结构。

[单选题]*

A.堆

B.顺序（正确答案）

C.任意次序

D.栈

67.应用分治法的两个前提是（）。

[单选题]*

A.问题的可分性和解的可归并性（正确答案）

B.问题的可分性和解的存在性

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

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

68.优先队列的分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。

优先队列中规定的结点优先级常用一个与该结点相关的数值p来表示。

结点优先级的高低与p值大小相关，根据问题的不同情况，采用（）来描述优先队列。

[单选题]*

A.先进先出队列

B.后进先出的栈

C.最大堆或最小堆（正确答案）

D.随机序列

69.阶乘函数用递归定义Publicstaticintfactorial（intn）{if（n==0）return1；return（）：

}[单选题]*

A.n*factorial（n）

B.n*factorial（n-1）（正确答案）

C.n*factorial（n-2）

D.n*factorial（n+1）

70.（）能够求得问题的解但却无法有效地判定解的正确性。

[单选题]*

A.数值概率算法

B.蒙特卡罗算法（正确答案）

C.拉斯维加斯算法

D.舍伍得算法

71.对于n个元素的排序问题。

n＝2时只要作（）次比较即可排好序。

[单选题]*

A.3

B.2

C.1（正确答案）

D.4

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

（）。

[单选题]*

A.效果一样

B.动态规划效果好（正确答案）

C.备忘录方法效果好

D.无法判断哪个效果好

73.分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者（）。

[单选题]*

A.求解目标不同搜索方式相同

B.求解目标不同搜索方式也不同（正确答案）

C.求解目标相同搜索方式不同

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

74.递归算法不适用以下场合（）。

[单选题]*

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

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

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

D.概率问题（正确答案）

75.若当子问题之间包含公共的子子问题时，则分治法要做许多不必要的工作，重复地解公共的子问题，此时一般用（）法较好。

[单选题]*

A.动态规划（正确答案）

B.分治

C.贪心

D.概率

76.分治法所能解决的问题应具有的最关键特征是（）。

[单选题]*

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

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

C.利用该问题分解出的子问题的解可以合并为该问题的解（正确答案）

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

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

[单选题]*

A.最轻次轻（正确答案）

B.最重次重

C.最轻次重

D.最重次轻

78.用回溯法解n后问题时，用完全n叉树表示解空间。

可行性约束place剪去不满足行、列和斜线约束的子树，place中的if判断条件应为（）。

[单选题]*

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.以上都不正确

79.分支限界法的搜索策略是：

在扩展结点处，先生成其（）儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。

为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

[单选题]*

A.一个

B.二个

C.任意多个

D.所有的（正确答案）

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

[单选题]*

A.子问题的可求解性

B.子问题的独立性

C.子问题的可合并性

D.子问题的重叠性（正确答案）

81.在任何一个

的棋盘覆盖中，用到的L型骨牌个数恰为（）。

[单选题]*

A.（4^k-1）/3（正确答案）

B.（4^k-1）/2

C.（2^k-1）/3

D.（2^k-1）/2

82.以Bitonic旅行路线问题为例，动态规划的时间复杂度为（）。

[单选题]*

A.O（n）

B.O（n!

）

C.O（n2）（正确答案）

D.O（n3）

83.一个算法应该包含如下几条性质除了（）。

[单选题]*

A.二义性（正确答案）

B.有限性

C.正确性

D.可终止性

84.解决一个问题通常有多种方法。

若说一个算法“有效”是指（）。

[单选题]*

A.这个算法能在一定的时间和空间资源限制内将问题解决

B.这个算法能在人的反应时间内将问题解决

C.这个算法比其他已知算法都更快地将问题解决

D.A和C（正确答案）

85.当输入规模为n时算法增长率最小的是（）。

[单选题]*

A.5n

B.20log2n（正确答案）

C.2n

D.3nlog3n

86.渐进算法分析是指（）。

[单选题]*

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

B.当规模逐步往极限方向增大时对算法资源开销“增长率”上的简化分析（正确答案）

C.数据结构所占用的空间

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

87.当上下限表达式相等时我们使用下列哪种表示法来描述算法代价（）。

[单选题]*

A.大O表示法

B.大Ω表示法

C.Θ表示法（正确答案）

D.小o表示法

88.采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素，以下对顺序搜

索法分析正确的是（）。

[单选题]*

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

B.最佳情况的渐进代价要好于最差情况和平均情况的渐进代价（正确答案）

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

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

89.递归通常用（）来实现。

[单选题]*

A.有序的线性表

B.队列

C.栈（正确答案）

D.数组

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

这要求原问题和子问题（）。

[单选题]*

A.问题规模相同，问题性质相同

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

C.问题规模不同，问题性质相同（正确答案）

D.问题规模不同，问题性质不同

91.在寻找n个元素中第k小元素问题中如快速排序算法思想运用分治算法对n个元素进行划分如何选择划分基准下面（）[单选题]*

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

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

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

D．以上皆可行。

但不同方法算法复杂度上界可能不同（正确答案）

92.对于0/1背包问题和背包问题的解法下面（）[单选题]*

A．0/1背包问题和背包问题都可用贪心算法求解

B．0/1背包问题可用贪心算法求解但背包问题则不能用贪心算法求解

C．0/1背包问题不能用贪心算法求解但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解（正确答案）

D．因为0/1背包问题不具有最优子结构性质所以不能用贪心算法求解

93.关于回溯搜索法的介绍，下面（）是不正确描述。

[单选题]*

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

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

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

D．回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径（正确答案）

94.关于回溯算法和分支限界法以下（）是不正确描述。

[单选题]*

A.回溯法中每个活结点只有一次机会成为扩展结点（正确答案）

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

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

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

95.优先队列通常用以下（）数据结构来实现。

[单选题]*

A．栈

B．堆（正确答案）

C．队列

D．二叉查找树

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

[单选题]*

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

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

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

D.以上都常用针对具体问题可以选择采用其中某种更为合适的方式（正确答案）

97.对布线问题以下（）是不正确描述。

[单选题]*

A.布线问题的解空间是一个图

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

C.采用广度优先的标号法找到从起点到终点的布线方案，这个方案如果存在的话不一定是最短的（正确答案）

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

9