算法分析与设计-山东财经大学中国大学mooc课后章节答案期末考试题库2023年

算法分析与设计.山东财经大学中国大学mooc课后章节答案期末考试

题库2023年

1.蒙特卡罗算法的结果未必正确，并且可能难以有效判定是否正确。

答案:

正确

2.T(n)=T(n-l)+1,T(l)=l,则T(n)=Q(_)

答案:

n

3.木板问题：农夫约翰为了修理栅栏，将一块木板切割成N块，N块的长度

和二原木板长度。每次切割木板时的开销为该木板的长度。木板长15,切成

长为1、2、3、4、5的木板。如何切割，使开销最小？(1)该问题最好

使用()算法求解。A枚举B贪心C分治D递推(2)第一次切割成长度为

—和—的两块。(3)切割的策略和一算法相同。AMSTB区间调度C哈

夫曼D区间划分

答案：

B;6;9;C

4.背包问题，背包容量C=20,物品价值p=[4,8,15,1,6,3],物品重量

w=[5,3,2,10,4,8],如果是0-1背包问题，求装入背包的最大价值和相应

装入物品。(1)该问题最好使用()算法求解？A动态规划算法B贪心算法

C枚举算法D分治算法(2)装入背包的最大价值是,(3)最大价值对应的物

品编号为__、_、__、_0(从小到大)

答案:

A;33;l;2;3;5

5.动态规划方程M[i]=min(M[j]+wij),l<i<j<n,则算法的时间复杂度为M2

答案:

正确

6.给定二分图G二中无孤立点，|V|二n,其最大流算法求得最大流f,则G的最

大独立数二n-f

答案:

正确

7.旅行商问题的所有解，可以组织成一棵树，包含了所有城市的排列组合。树

的根结点到任一叶结点的路径，定义了图的一条周游路线。

答案:

正确

8.对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实

例的一个解空间。

答案

正确

9.Floyd算法是动态规划算法，稠密图效果最佳，边权可正可负。

答案：

正确

10.f=O（g）当且仅当g=3⑴

答案：

正确

11.预流推进算法的关键操作有()

答案：

重嬴号.初始化.推进

12.最小费用最大流算法求得解需满足()条件。

答案：

对于任意边eiE:O£f(e)£c(e)_对任意顶点v,顶点的净流量=0_每条边的流

量乘以单位流量费用之和最小

13.给定一分图G=中无孤立点，其最大流算法求得最大流f,则G的最大匹配数

=f

答案：

正确

14.给定G=，G的匹配中任何两条边都没有公共顶点。

答案：

正确

15.循环用于重复性的工作。循环体的特点是：“以不变应万变”。

答案：

正确

16.主方法可以求解满足T(n)=aT(n/b)+f(n)形式的递推方程，则下列关于方

程中的约束中不准确的是？

答案:

17.Kruskal算法的预处理是边权非递减排序。

答案:

正确

18.区间划分问题的预处理方法是按照开始时间递减排序。

答案:

错误

19.Kruskal算法的贪婪准则是每一次选取不构成环路的最小边。

答案:

正确

20.原问题的最优解包含其子问题的最优解是贪心算法的()性质。

答案：

最届子结构性质

21.算法的每一条指令必须要有确切的含义，必须是清楚的、无二义的。

答案:

正确

22.按照霍纳法则，计算p(x)=anxn+an-lxn-1+...+alxl+aO的复杂度为0(n)

答案：

正确

23.N后问题利用()减少搜索。

答案：

对麻性.约束函数一重排原理

24.分支限界法解0-1背包问题时的解空间树是()

答案：

子集树

25.确定第i阶段的收益函数和从第i阶段出发到第n阶段所获得收益的最优值,

建立动态规划基本方程。这种方法是()

答案：

反推

26.备忘录方法使用()的递归方式。

答案：

自顶向下

27.下列算法中通常以自底向上的方式求解最优解的是()o

答案：

动态规划法

28.f(n)=3nA3+7nA2+4nlogn=()(nA3)

答案：

n_o_o

29.f(n)=3nA3+7nA2+4nlogn=0(nA2)

答案：

错误

30.位向量法生成子集，子集或运算可以生成差集

答案：

错误

31.确定性算法的每一计算步骤都确定，求解同一实例用同一算法求解两次，所

得结果完全相同。

答案：

正确

32.给定网络N=(V,E),设f为任意流,(A,B)是任意s-t割.则流值至少是割的容

量

答案：

错误

33.贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最

优解的一部分。

答案:

正确

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

征。

答案：

正确

35.MST中若在树中任意增加一条边，将出现一个回路；若去掉一条边，将变

成非连通图。

答案：

正确

36.从大规模问题逐步化为小规模问题的算法是()

答案：

递归

37.折半查找长度为n的线性表，平均查找长度为()

答案：

logn

38.T(n)=2T(n/2)+nA2,T(l)=l,则T(n)=()

答案：

Q(nA2)

39.分支限界活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

答案:

正确

40.设G是n阶无孤立点的图，则V*是G的顶点覆盖，当且仅当V-V*是G的

独立集。

答案：

正确

41.设f任意流,(A,R)是任意s-t割.则流值至多等于割的容量.

答案：

正确

42.f(n)=6x2An+nA2,f(n)的渐进性态f(n)=OQ

答案：

2An

43.正推是从小规模的问题推解出大规模问题的一种方法

答案：

正确

44.堆排序的时间复杂度是0()o

答案：

0(nlogn)

45.堆排序的时间复杂度是()

答案：

nlogn

46.分治与递归都是从大规模问题逐步化为小规模问题，因此分治算法经常使用

递归实现。

答案：

正确

47.两个有序数组合并的时间不会超过两个数组的长度和。

答案：

正确

48.最短路算法中适用于稀疏图的是()

答案：

SPFA算法_Bellman算法

49.动态规划方程中子问题个数为M3依赖的子问题个数为Me,则算法的时

间复杂度为M(t+e)

答案:

正确

50.分治法将原问题分解为若干个规模较小、相互独立、完全相同的子问题。

答案:

错误

51.任务安排问题：某公司有5个工作岗位，每个岗位需要1个人，现接到5

位待业者申请。A申请岗位1、2、3,B申请1、4,C和D申请4、5,E

申请5。最多一人就业？最多就业安排是：A安排—或_«B安排—该问

题可以转化为二分图的()问题A最大匹配B完美匹配C完备匹配D最小

匹配

答案：

4;2;3;1;A

5乙T(n)=ZT(n/Z)+nlogn,贝UT(n)二Q(__)

答案：

n(logn)A2##%_YZPRLFH_%##nlog(A2)n

53.找n个元素的中位数的分治算法的时间复杂度为0(_).

答案：

n

54.最高标号预流推进算法的时间复杂度为0()

答案：

nA2mAl/2

55.常见的分支限界法为()

答案：

优区队列式分支限界_FIFO分支限界一队列式分支限界

56.备忘录算法的特点()

答案：

从二到小计算_自顶向下计算

57.最优子结构是问题能用动态规划算法求解的前提。

答案:

正确

58.DAG图最长路的反推关系是L(i)=1+max{L(j)：(i,j)为边}

答案:

正确

59.Bellman算法在求解过程中，每次循环都要检查修改所有顶点的路径，也就

是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定卜来

答案:

正确

60.动态规划计算树上的最大独立集时，从叶子开始，先计算子树，逐步计算到

根节点。

答案:

正确

61.回溯法的两种解空间树为

答案：

排歹谪_子集树

62.对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为

()O

答案：

2An

63.回溯法搜索解空间时，在搜索试探时选取x[i]的值顺序是任意的，顺序对于

计算量没有差别。

答案：

错误

64.队列式分支限界法以最小耗费优先的方式搜索解空间树。

答案：

错误

65.确定性算法的每一计算步骤都确定，求解同一实例用同一算法求解两次，所

用时间和所得结果可能不同。

答案：

错误

66.时间复杂度是指算法最坏情况下的运行时间。

答案:

正确

67,以空间换时间的方法有()

答案：

动家规划一预构造.预处理

68.回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但是，当探

索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，

这种走不通就退回再走的技术，称为回溯法。

答案：

正确

69.从资源划分，算法的复杂度分为0和0。

答案：

时间复杂度空间复杂度

70.分支限界法与回溯法，都是在问题的解空间树上搜索问题解。

答案：

正确

71.装载问题的剪枝函数有()

答案：

可行性约束函数：.上界函数：Cw+r£bestw

72.随机抽取数组元索k次，从最接近搜索元素x的位力顺序搜索,顺序搜索的平

均比较次数为O(n/(k+l)).

答案：

正确

73.(logn)A2=()(logn+5)

答案：

W

74.下面有关递归与递推的说法错误的是()

答案：

一般来说，递归的效率高于递推

75.下面不是影响回溯算法效率的主要因素的是()

答案：

x[k]的优先级

76.给定n个整数，n个数的取值范围为下面有关计数排序的说法正确的

是()

答案：

台数排序最好情况下的时间复杂度为0(n+k)_计数排序的复杂度为0

(n+k)_计数排序的平均时间复杂度是0(n+k1计数排序最好情况下的

空间复杂度为0(n+k)

77.回溯算法的效率在很大程度上依赖的因素有()：

答案：

剪底时间：计算可行性约束函数constraint和上界函数bound的时间。.

产生x[k]的时间.满足可行性约束函数和上界函数的所有x[k]的个数.满足

显约束的x[k]值的个数

78.nA(l/logn}=0(l)

答案：

正确

79.对近似递增序列的线性表从小到大排序，使用合并排序比较好。

答案：

错误

80.给定图G,BFS形成的层次网络图，是从起点到其它点的最短路。

答案：

正确

81.分析下列程序的上界0和下界W。for(i=1;i<n;i++)key=a[i];intj=i-l

while(j>=0&&a[j]>key)a[j+l]=a[j]j--a[j+l]=key该程序时间宜杂鹿的上

界是0(一)、下界是W(一

答案：

nA2;n

82.顺序查找长度为n的线性表，平均查找长度为()

答案：

(n+l)/2

83.Iogl0=()(10)

答案：

0

84.lognA3=()⑵ogn+5)

答案：

0

85.下面程序的时间复杂度为()i=lwhile(i<=n)doi=i*2

答案：

O(logn)

86.算法复杂度分析的两种方法是()

答案：

事露分析和事后统计

87.下面关于算法的说法错误的是()o

答案：

高一算法只有一种形式描述。

88.舍伍德算法设法消除最坏情况和特定实例的关联性，达到平均实例的性能.

答案：

正确

89.增加拉斯维加斯算法的反复求解次数,可使求解无效的概率任意小。

答案：

正确

96如果

p是一个素数，且0

答案

错误

91.给定连通图G,BFS遍历得到层次图，同一层中存在连接两个结点的边，则

G是二分图.

答案：

错误

92.剩余网络中后向边(v,w)的费用为cost(v,w).

答案：

错误

93.有下界的流通问题一定有可行流。

答案：

错误

94.将有顶点容量限制的顶点u用一条边(u,v)代替，顶点u的入边仍为u的入

边，顶点U的出边变为顶点V的出边。(u,v)的容量等于原先顶点U的容量。

变换后网络的最大流等于原网络的最大流

答案:

正确

95.给定二分图G二中无孤立点，其最大流算法求得最大流f,则G的()=f

答案：

最大匹配数.最小顶点覆盖

96.设G是n阶无孤立点的图，V*是G的最小顶点覆盖，则V-V*是G的()。

答案：

最大独立集

97.FF算法的时间复杂度是()

答案：

mnC

98.分支限界法在对问题的解空间树进行搜索的方法中，一个结点有多次机会成

为活结点

答案：

错误

99.回溯法和分支限养法的主要区别在于，回溯法求取问题的一个解或所有解。

答案:

正确

100.分支限界法不能解决0/1背包问题

答案:

错误

101.分支界限法搜索方式包含（）O

答案：

广度优先.最大效益优先.最小耗费优先

102.用分支限界法设计算法的步骤是：

答案：

针对所给问题，定义问题的解空间（对解进行编码）以广度优先或以最

小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数

避免无效搜索。.确定易于搜索的解空间结构（按树或图组织解）

103.优先队列分支限界法解旅行商问题时，活结点表的组织形式是（）

答案：

最小堆

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

答案：

结金的优先级

105.装载问题，当所给的问题规模为n时，通常有2、个叶结点。

答案：

正确

106.下列哪个结点属于回溯法的结点类型？()

答案：

活结点.死结点.扩展结点

107.回溯法的效率依赖于下列哪些因素()

答案：

计算约束函数的时间.满足显约束的值的个数一计算限界函数的时间

108.旅行商问题的回溯算法所需的计算时间为0()

答案：

n!

109.SPFA算法计算时，如果一个顶点入队列的次数超过n,则存在负权回路。

答案：

正确

110.矩阵连乘问题的不同子问题个数为0(nA2)

答案：

正确

111.贪心和递推算法是线性解决问题，动态规划则是全面分阶段地解决问题。

答案:

正确

112.Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出,

则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。

答案:

正确

113.下面哪些问题的动态规划算法的时间复杂度为Q(mn)?

答案：

LCS万列比对.SPFA算法

114.分治算法与动态规划算法的相同点是()

答案：

递服关系.最优子结构

115.Floyd算法的复杂度为0()

答案：

nA3

116.0PT[i][w]=max{0PT[i-l][w],0PT[i][w-w[i]]+v[i]},这是0问题的递推关系。

答案：

完全0・1背包

117.给定n个元素，找其中位数的时间是。(n)

答案:

正确

118.建立n个元素的最大堆的时间为0(n)

答案:

正确

119.减治法是把一个问题转化成一个子问题来解决，从子问题的解得到原问题的

解。

答案:

正确

120.分治法在每一层递归上有三个步骤()

答案：

分解一合并—解决

121.对线性表进行折半查找最方便的数据结构是()

答案：

有序顺序表

122.大整数乘法分治算法的时间为0()

答案：

nAlog3

123.一般来说，递推的效率高于递归，因此将递归转化为递推

答案:

正确

124.有些问题采用倒布法，容易理解和解决。

答案:

正确

125.递推是从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问

题。

答案:

错误

126.递归算法是直接或间接地调用自身的算法。

答案:

正确

127.T(n)=T(n-l)+n,T(l)=l,则T(n)=()

答案：

Q(nA2)_n(n+l)/2_W(nA2)_(nA2)

128.递归变为非递归的方法有()

答案：

递也模拟栈一尾递归

129.下面有关递归与迭代的说法错误的是()

答案：

每本递归算法原则上总可以转换成与它等价的迭代算法

130.区间选点问题的预处理方法是按照区间的终点递增排序

答案：

正确

131,贪心算法总能找到可行解，并且是最优解。

答案：

错误

132.贪心算法的思想是寻求局部最优解，逐步达到全局最优解

答案：

正确

133.问题的可行解是满足约束条件的解

答案：

正确

134.下面不是证明贪心算法证明方法的有()o

答案：

优化

135.蛮力法适用于问题的小规模实例。

答案:

正确

136.在某些问题实例中枚举是唯一的解决方法。

答案：

正确

137.0-1背包问题的枚举算法，如果在百万次每秒的计算机上运行，1年可以计

算的问题规模估计是？

答案：

40

138.从小规模问题推解出大规模问题的算法是()

答案：

递推

139.使用合适的数据结构可以同时减少时间和空间

答案：

正确

140.时间复杂度就是算法运行的时间的度量，衡量算法的效率。

答案:

正确

141.f(n)=0(g(n))则f(nr2=0(g(n)八2)

答案：

正确

142.顺序查找适合的数据结构是()

答案：

顺序存储一链式存储

143.下面程序的时间复杂度是()i=lwhile(i〈=n)doi=i*5

答案：

Q(logn)

144.设f(N)、g(N)是定义在正数集上的正函数，如果存在正的常数C和自

然数NO,使得当N>N0时有f(N)>Cg(N),则称函数f(N)当N充分

大时有下界g(N),记作f(N)=W(g(N))，即f(N)的阶()g(N)

的阶。

答案：

不低于

145.算法复杂度分析的两种基本方法为()和()

答案：

事后统计事前分析

146.问题的两个要素是输入和实例。

答案：

错误

147.一个问题的同一实例可以有不同的表示形式。

答案：

正确

148.同•数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。

答案：

正确

149.计算机每次求解是针对问题的每个实例求解。

答案：

错误

150.最大独立集问题和()问题等价。

答案：

最小顶点覆盖.最大团

151问题变换的方法有()

答案：

表达变换.问题均简一实例简单化

152.描述算法的基本方法有()。(1)自然语言(2)流程图(3)伪代码(4)机器语言

答案：

B.⑴(2)(3)

153.按照霍纳法则，计算p(x)=anxn+an-lxn・l+...+alxl+aO的数量级为()

答案：

154.问题变换的目的有()。(1)复杂变简单(2)未知变已知(3)隐式变显式(4)难

解变易解(5)以上都是。

答案：

(5)

155.算法与程序的区别是()

答案：

有穷性

156.解决问题的基本步骤是()o(1)算法设计(2)算法实现(3)数学建模

(4)算法分析(5)正确性证明

答案：

⑶⑴⑸(4)(2)

157.下面说法关于算法与问题的说法错误的是()。

答案：

证明算法不正确，需要证明对任意实例算法都不能正确处理。

158.下面关于程序和算法的说法正确的是()o

答案：

算上是一个过程，计算机每次求解是针对问题的一个实例求解_算法的每一

步骤必须要有确切的含义，必须是清楚的、无二义的。一程序是算法用某种

程序设计语言的具体实现。

159,给定两张喜欢列表，稳定匹配问题的输出是()

答案：

最二匹配.没有不稳定配对_完美匹配.稳定匹配

160.给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。

答案：

错误

161.证明算法不正确，只需给出一个反例，算法不能正确处理即可。

答案：

正确

162.同一算法只有一种形式描述

答案:

错误

163.算法必须在有穷时间终止

答案：

正确

164.一个问题的算法必须在有穷时间终止，并且对一切合法的输入都能得出满足

要求的结果。

答案：

正确

165.下面程序的时间复杂度为()x=lfori=ltondoforj=ltoidofork=ltojdo

x++

答案：

nA3

166.对近似递增序列的线性表从小到大排序，使用哪种方法好?

答案：

插入排序

167.给定图G=(V,E),|V|二n,|E|二m,遍历其邻接表的时间复杂度为0()

答案：

n+m

168.两个n*n的矩阵相加的时间复杂度是()

答案：

0(nA2)_0(nA2)_W(nA2)

169.f(n)=O(g(n))且g(n)=O(h(n)),则h(n)=O(f(n))

答案:

错误

170.如果一个算法是多项式时间算法，该算法是有效的，是好算法。

答案：

正确

171.n!=o(2An)

答案：

错误

172.常数阶算法的运行时间与规模n无关。

答案：

正确

173.A公司处理器速度是B公司的100倍。对于复杂度为M2的算法，B公司

的计算机可以在1小时内处理规模为n的问题，A公司的计算机在1小时

能处理的问题规模是0

答案：

10n

174.直接插入排序的时间复杂度是（）。

答案：

0(nA2)

175.选择排序的时间复杂度是0(一)

答案：

nA2

176.分数拆分问题的枚举算法通过()方法进行了优化。

答案：

减3枚举变量的值域.优化数学模型.减少枚举变量

177.枚举算法的优化方法有()

答案：

优化算法.减少枚举变量.优化数学模型_减少枚举变量的值域

178.冒泡排序的时间复杂度为W(nA2)

答案：

错误

179.0-1背包问题的枚举算法的时间复杂度为0(2、)

答案:

错误

180.增量构造法生成子集前需要对集合中元素从小到大排列。

答案：

正确

181.二进制法生成子集，子集与运算可以生成并集

答案：

错误

182.分块查找一般设分块的长度是n/2.

答案：

错误

183.未来与过去无关指的是()的性质

答案：

无后效性

184.使目标函数最大(小)的解是问题的()

答案：

最优解

185.对于稠密图，使用()算法计算MST更适合

答案:

Prim

186.区间调度问题贪心算法的时间复杂度是()

答案：

O(nlogn)

187.区间问题包含0

答案：

区间调度一区间覆盖.区间划分一区间选点

188.贪心算法总能找到可行解，但未必是最优解。

答案：

正确

189.如果图G中每条边的权重都是互不相同的，图G必定只有一颗最小生成树。

答案：

正确

190.任意变长码的平沟码长最小

答案：

错误

191.哈夫曼编码的贪婪准则是从队列中选择频率最小的两个。

答案:

正确

192.哈夫曼编码给出现频率高的字符较短的编码，出现频率较低的字符以较长的

编码，可以大大缩短总码长。

答案：

正确

193.求解高阶递推方程一般使用()迭代方法

答案：

差消迭代

194.递归一般用于解决问题有()：

答案：

易据的结构形式是按递归定义的一数据的定义是按递归定义的。.问题解法按

递归实现。

195.求解快速排序时间复杂度使用的方法有()

答案：

迭A法.递归树.主定理_归纳法

196.尾递归中的递归调用是整个函数体中最后执行的语句且它的返回值不属于表

达式的一部分。

答案：

正确

197.一般来说，递归的效率高于递推。

答案:

错误

198.每个递归算法原则上总可以转换成与它等价的迭代算法，反之不然。

答案：

错误

199.由结果倒过来推解前提条件是倒推方法的一种。

答案：

正确

200.迭代法从原始递布方程出发，反复将对应方程左边的函数用右边等式带入,

直至得到初值，然后将所得的结果化简。

答案：

正确

201.快速排序和插入徘序最好情况卜的时间复杂度是0(nlogn)

答案：

错误

202.设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元

素，最好选用()法。

答案：

冒泡排序

203.军事上迂回包围、穿插分割、各个歼灭是（）思想。

答案:

分治

204.矩阵C中每一行选一个元素，使选择的元素不同列，并且元素之和最小。

Job1Job2Job3Job4Persona9568Personb6437Personc5818Persond7

694最小元素和为最小元素和对应的安拉•是a安排job、b安排job

_、c安排job一、d安排job_如果人数和任务数为n,时间复杂度是

答案：

16;2;l;3;4;n!

205.给定•个数字三角形，从顶至底有多条路径，每•步可沿左斜线向下或沿右

斜线向下，路径所经过的数字之和为路径得分，请求出最小路径得分和相应

路径。738840274445265⑴该问题最好使用（）算法求解？A动态规

划算法B贪心算法C枚举算法D分治算法（2）最小路径得分是_（相应路径

经过的数字为__、—、—、—、—。［从顶到底）

答案：

A;20;7;3;4;4;2

2O6.T(n)=4T(n/2)+n,T(l)=l,则T(n)=Q(_)

答案：

nA2

207.下面程序的时间复杂度为0()k=lwhilen>=ldofori=ltondok=k+l

n=n/2returnk

答案:

208.调用一个偏真的蒙特卡罗算法，只要返回一次true,就可得到正确解。重复

调用4次，正确率从55%提高到95%,调用6次，提高到99%.

答案：

正确

209.增加蒙特卡罗算法的求解次数，可使求解错误的概率任意小。

答案：

正确

210.当最坏和平均情况差别较大时,舍伍德算法可.以消除好坏实例的差别，达到

平均实例的性能.

答案：

正确

211.现实计算机上无法产生真正的随机数

答案：

正确

212.拉斯维加斯算法肯定得到正确解或找不到解，一旦找到一个解，一定是正确解。

答案：

正确

213.分支限界算法的活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

答案:

正确

214.使用限界函数作优先级，第一个加入队列的□•子就是最优解

答案：

错误

215.分支限界法以深度优先的方式搜索解空间树。

答案：

错误

216.活结点是自身已生成，但其儿子还没有全部生成的结点

答案：

正确

217.DAG动态规划算法中反推的开始点是无山边的顶点

答案：

正确

218.最大权独立集包含结点u,不可能包含其儿子结点。

答案：

正确

219.不基于元素比较的排序算法可以在线性时间实现。

答案:

正确

220.递归方程是递归函数的要素之一

答案：

正确

221.递归是从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问

题。

答案：

正确

222.把目标函数作为贪婪准则得到的解不一定是问题的最优解

答案：

正确

223.最小生成树是唯一的。

答案：

错误

224.如果图G中每条边的权重都是互不相同的，图G可能存在多颗最小生成树。

答案：

错误

225.子集生成算法中一般需要对集合元素进行定序。

答案：

正确

226.减少枚举变量的值域可以减少枚举算法的时间复杂度。

答案：

正确

227.求101og3An的渐进表达式是6(n)

答案：

正确

228.21+1/n的渐进表达式是0(1)

答案：

正确

229.f=o(g)且g=o(h)则f=o(h)

答案：

正确

23O.T(n)=l+l/2+l/3...+l/n=Q(lnn)

答案：

正确

231.好算法具有如下特性:当输入规模加倍时，算法降低C倍，C为常数。

答案:

正确

232.f(n)=3nA3+7nA2+4nlogn=W(nA2)

答案:

正确

233.时间复杂度是指算法最好情况下的运行时间。

答案:

错误

234.通过减少子问题个数，降低分治算法时间复杂度的有（）

答案：

Strassen矩阵乘法大整数乘法

235.三分法的判定树是三义树

答案

正确

236.减治法减一个常量就是每次迭代减去一个相同的常数因子（一般为2）

答案:

错误

237.改进子问题合并的时间复杂度可以减少分治算法的时间。

答案:

正确

238.任何基于元素比较的排序算法的时间复杂度＞=61ogn!立二Q(nlogn)

答案：

正确

239,给定n个元素，使用分治算法找k小元素，如果保证分治的两个子数组中

最小的数组是原数组的£倍，时间复杂度可.以由nlogn降低为n

答案：

正确

240.问题A的实例可以变换为另一个问题B的实例。如果问题B的求解算法是

已知的，那么问题A也可以求解。

答案：

正确

241.证明算法不正确，需要证明对任意实例算法都不能正确处理。

答案：

错误

242.如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法

解答了该问题。

答案:

正确

243.同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。

答案：

正确

244.肯定获得解，但不一定是准确解的算法是()o

答案：

数值随机算法.蒙特卡罗算法

245.下列算法中能解决0/1背包问题的是()

答案：

动会规划.分支限界法一回溯法

246.()肯定获得最优解。

答案：

枚举算法.回溯算法

247.关于带需求的流通下面说法正确的是()o

答案：

对于任意边eiE:O£f(e)£c(e)_供给和二需求和

248.给定二分图G=中无孤立点，|V|=n,其最大流算法求得最大流f,则G的（）

答案：

最余顶点覆盖.最大匹配数

249.0PTQ,w）:从1-i种物品中选择，放入容量为w的背包时的最大价值。这

是（）问题动态规划算法的递推函数。

答案：

多重0/1背包.完全0/1背包

250.动态规划算法的特点（）

答案：

子问题重叠一自底向上计算

251.动态规划算法的基本要素有（）和最优子结构性质。

答案：

重叠子问题性质

252.下面不是动态规划的基本方法有（）。

答案：

舍入

253.动态规划方法使用（）计算方式。

答案：

自底向上

254.0PT(i,w):从1-i个物品中选择，放入容量为w的背包时的最大价值。这

是()问题动态规划算法的递推函数。

答案：

0/1、背包.恰好装满的0/1背包

255.区间动态规划的计算次序是()

答案：

先小规模后大规模.先小区间后大区间

256.给定n个报告(编号1-n)和一个报告厅，每人报告的开始时间si和结束时间

fi,(si,fi)I{(1,2)、(1,3)、(1,4)、(2,5)、(3,7)、(4,9)、

(5,6)、(6,8：、(7,9)},求最多可以安排的报告数和相应报告。⑴

该问题最好使用()算法求解。A枚举B贪心C分治D动态规划(2)最多可

以安排的报告是_、__、

答案：

B;l;4;7;8

257.部分背包问题，背包容量c=20,物品1,2...n,对应的物品价值p=[4,8,

15,1,6,3],对应的物品重量w=[5,3,2,10,4,8],求装入背包的最大价值

和装入物品。(1)该问题最好使用()算法求解。A枚举B贪心C分治D

递推(2)装入背包的最大价值是一(3)装入背包的最大价值对应的完整

物品是—、—、—、—O(编号从小到大)

答案：

B;35.25;l;2;3;5

258.T(n)=3T(n/4)+nlogn,T(l)=l,则T(n)=Q(_)

答案:

nlogn

259.设G=中无孤立点，|V|=n,则边覆盖数+匹配数=n

答案:

正确

260.给定网络N=(V,E)的一个流f,任意一个节点满足流出量等于流入量

答案:

错误

261,队列式分支限界以最大效益优先方式产生状态空间树的结点。

答案:

错误

262.如果解空间树中，从根结点到叶结点的最长路径的长度为h(n),则回溯法

所需的计算空间通常为O(h(n))。显式地存储整个解空间则需要0(2八h(n))

或O(h(n)!)内存空间。

答案:

正确

263.回溯法为了避免生成那些不可能产生最佳解的问题状态，不断地利用限界函

数来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。

答案:

正确

264.回溯法搜索解空间时，在其它条件相当的前提下，让可取值最少的x[i]优先,

可以减少计算。

答案:

正确

265.对于稠密图，Floyd算法的效率要高于执行n次Dijkstra算法，也要高于执

行n次SPFA算法

答案:

正确

266.DAG动态规划算法中正推的开始点是无入边的顶点

答案：

正确

267.一般来说，迭代的效率高于递归

答案：

正确

268.每个迭代算法原则上总可以转换成与它等价的递归算法；反之不然

答案:

正确

269.f=n(g)且g=C(h)则f=n(h)

答案:

正确

270.两个n*n的矩阵相乘的时间复杂度是W(n9)

答案:

错误

271.分块查找适应于分块有序的顺序存储结构或线性链表。

答案:

正确

272.计算机每次求解只是针对一个实例求解，问题的描述针该问题的所有实例。

答案:

正确

273.动态规划算法的基本要素有()。

答案：

无后效性.最优子结构性质.重叠子问题性质

274.下面描述分治算法正确的是()

答案：

最小堆中每个元素调整的次数不超过树高Q(logn)。_二分法子问题不独立

的情况可以使用分治算法计算，但计算量大。一三分法的判定树是三叉树

275.求解递推方程的方法有()

答案：

迭府法.递归树一归纳法.主定理

276.贪心算法的常用证明方法有()o

答案：

反证.交换论证_界.领先

277.对于含有n个元素的排列树问题，最坏情况下其解空间的叶结点数目为

()O

答案：

n!

278.下面分治算法的说法正确的是()

答案：

分治法的设计思想是大事化小，各个击破，分而治之。一减治法是把一个问

题转化成一个子问题来解决。一每次都将问题分解为原问题规模的一半进行

求解，称为二分法

279.改进分治算法的方法有()

答案：

改进分治的均衡度.减少子问题的个数.减少合并的时间

280.分治算法的适用条件有()o

答案:

小规模子问题可解_问题可以分解为规模较小的子问题一子问题相互独立一子

问题可合并为问题的解

281.最好情况下，时间复杂度为0(n)的排序算法有()

答案：

插入排序.冒泡排序.计数排序

282.时间复杂度为0(M2)的排序算法有()

答案：

直接选择排序.冒泡排序.快速排序.插入排序

283.时间复杂度为O(nlogn)的排序算法有()

答案：

堆排序_合并排序

284.通过降低子问题合并时间，降低分治算法时间复杂度的有()

答案：

大整数乘法.最接近点对—计数逆序

285.贪心算法的基本要素是()

答案：

贪心选择的性质.无后效性性质.最优子结构性质

286.子集生成方法有()

答案：

增量构造法.二进制法一位向量法

287.下面时间复杂度的描述正确的是()

答案：

从n个数中查找最小值的时间复杂度为O(n)_k)gn!=e(nlogn)

288.问题变换的目的和方式有()o

答案：

复,变简单.未知变已知_难解变易解.隐式变显式

289.算法的性质有()

答案：

确定性_有穷性.输出一输入

290.动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解,

合并为原问题的解。

答案:

正确

291.0/1背包问题的动态规划算法是多项式时间算法。

答案:

错误

292.通常不同的子问题个数随问题规模呈多项式增长。动态规划算法对于每个子

问题求解一次，并保存子问题结果，因此只需要多项式时间。

答案:

正确

293.0-1背包问题的动态规划算法可以使用一维数组实现。

答案:

正确

294.矩阵乘法满足结合律，所以计算矩阵连乘，不同的计算次序计算量相同。

答案:

错误

295.回溯算法和分支限界法的问题的解空间树不会是（）。

答案：

无序树

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

答案：

递后函数

297.备忘录与递归算法的不同点是（）

答案：

子问题重叠

298.Bellman算法的时间复杂度为0()

答案：

mn

299.随机快速排序的时间复杂度是()o

答案：

0(nlogn)

300.下面有关递归与循环的说法错误的是()

答案：

递后方法相比循环方法大大地减少了算法的计算量。

301.给定图G=(V,E),|V|=n,|E|=m,其邻接表的空间复杂度为0()

答案：

m+n

3O2.nA2/3=()(n+nlogn)

答案：

3O3.(6n+5)=()(nA2-n)/2

答案：

o

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

答案：

回溯法

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

答案：

剪枝函数

306.装载问题的回溯算法所需的计算时间为。（）

答案：

2An

307.下面有关动态规划算法错误的是

答案：

0-1、背包问题的动态规划算法是多项式时间算法。

308.可能获得解，且一定是准确解的算法是（）o

答案：

拉加维加斯算法

309.下面说法错误的是()

答案：

舍后德算法总是有解，且解总是正确的，改进了算法的平均性能。

310.备忘录与动态规划算法的不同点是()

答案：

自而向下计算

311.动态规划和分治算法的共同点是

答案：

最届子结构性质

312.动态规划方程M[i,j]=min(M[i,k]+M[k,j]+wij),l<i<k<j<n,则算法的则算法

的时间复杂度为()。

答案：

nA3

313.Floyd算法的时间复杂度为0()

答案：

nA3

314.减少子问题合并的时间，就是减少时间复杂度函数T(n)-aT(n/b)+f(n)中的

()值。

答案:

f(n)

315.Strassen矩阵乘法分治算法的时间为()

答案：

nAlog7

316.中印战争西山口战役刘伯承提出的“打头、截尾、剖腹、击背”是()思想。

答案：

分治

317.两个n/2长度的有序数组合并为新的有序数组的时间为()

答案：

n

318.插入排序的时间复杂度是()o

答案：

0(nA2)

319.未来与过去无关，指的是无()性质。

答案：

无后效性

320.原问题的最优解包含其子问题的最优解，这是()性质

答案•

最加子结构

321.0-1背包问题的枚举算法，如果在万亿次每秒的计算机上运行，1年可以计

算的问题规模估计是？

答案：

60

322.()生成子集，便于实现集合的操作。

答案：

二进制法

323.分块查找256个元素的数组，每块的最佳长度是

答案：

16

324.假设算法A的计算时间为T(n)=n^2在计算机A上输入规模为n时算法A

的运行时间为t秒。计算机B的运行速度是A的64倍，在t秒时间计算机

B运行算法A的输入规模是一

答案：

8n

325.哈夫曼编码的平沟码长最小

答案：

正确

326.假设算法A的计算时间为T(n)=2=,在计算机A上输入规模为n时算法A

的运行时间为t秒。计算机B的运行速度是A的64倍，在t秒时间计算机

B运行算法A的输入规模是一

答案：

n+6

327.下面不是以空间浜时间的方法有()

答案•

数据压缩

328.下面描述错误的是()

答案：

空间复杂度是算法执行所需所有空间的资源量。

329.f(n)=Q(g(n)),则g(n)为f(n)的()

答案：

下界

330.给定n个元素的数组A,n=l(T3,使用折半查找比使用顺序查找大约快一倍。

答案：

100

331.待排序文件基本有序时，下面哪种排序方法，效率最差?

答案：

快速排序

332.待排序文件基本有序时，下面哪种排序方法，效率最高?

答案：

冒泡排序

333.(logn!)=()(nA3/2)

答案：

334.1ognA2=()(nAl/2)

答案：

o

335.从长度为n的数组中多次查找数据，使用（）方法好?

答案：

排谆后折半查找

336.设p是一个实数，且1/2

答案：

正确

337.蒙特卡罗算法的结果肯定是•个正确解。

答案：

错误

338.借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌,

可收到舍伍德算法的效果。

答案：

正确

339.对于给定的正整数n,判定n是一个素数的充要条件是(41)坞-l(modn)。

答案：

正确

340.在一般输入数据的程序里，输入多少会影响到算法的计算复杂度，为了消除

这种影响可用()对输入进行预处理。

答案：

舍伍德算法

341.我们讲的时间复杂度是()情况下的时间复杂度。

答案：

最坏

342.问题的状态生成法有。

答案：

深展优先生成法.宽度优先生成法

343.回溯法解题步骤:

答案：

针对所给问题，定义问题的解空间一确定易于搜索的解空间结构.以深度优先

方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索。

344.回溯法是按广度优先策略搜索解空间树。

答案:

错误

345.回溯法中，如果解空间树是子集树，当所给的问题规模为n时，通常有

2人n个叶结点，遍历子集树需0(2?)计算时间。

答案:

正确

346.回溯法不适用于解一些组合数相当大的问题。

答案:

错误

347.回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。

答案:

正确

348.旅行商问题的限界函数是当前路＞已记录最小路程bestc

答案:

正确

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

答案：

贪心法

350.FIFO是()的搜索方式。

答案：

分支限界

351.采用最大效益优先搜索方式的算法是()o

答案.

分壬界限法

352.分支限界法与回溯法的不同点是什么？

答案：

搜索方式不同_存储空间的要求不同.对扩展结点的扩展方式不同一求解目标

不同

353.设G二中无孤立点，M是G的最大匹配，N为G的最小边覆盖，贝ijMnN=0

答案：

错误

354.层次网络为剩氽图基础上的最短路径图。从源点出发，到达终点，肯定是最

短路径。

答案：

正确

355.设G=中无孤立点。W为G的最小边覆盖，若G中存在相邻边就移去其中一

条。设移去的边集为N,则W-N是G的最大匹配。

答案:

正确

356.有下界的流通问题不一定有可行流。

答案:

正确

3S7.存在割（A,用使流值v（Q=割的容量cap（A,B）.,贝I」割（A,R）是最小割。

答案:

正确

358.改进FF网络流算法，可以通过选择（）增广路，降低时间复杂度。

答案：

最去容量一最大瓶颈容量.最短路径一边数最少

359.使用限界函数作优先级，第一个扩展的叶子就是坡优解

答案:

正确

360.分支限界法在对问题的解空间树进行搜索的方法中，一个结点有多次机会成

为活结点。

答案：

错误

361.分支限界法解旅行商问题时的解空间树是（）。

答案：

排列树

362.扩展结点是所有儿子已经产生的结点。

答案：

错误

363.死结点是正在产生儿子的结点

答案：

错误

364.旅行商问题使用（）进行剪枝。

答案：

下界函数一剪枝函数.约束函数

365.剪枝函数包括（）和约束函数。

答案：

限界函数

366.状态转移方程表示状态间的递推关系，也是子问题间的递推关系。

答案：

正确

367.DAG图最长路的递推函数d⑴表示从某个顶点i出发的最长路长度。

答案：

正确

368.确定第i阶段的收益函数和从第1阶段出发到第i阶段末所获得收益的最优

值，建立动态规划基本方程。这种方法是()

答案：

正推

369.存在O(n2.376)时间的矩阵乘法分治算法

答案：

正确

370.最小堆中每个元素调整的次数不超过树高Q(logn)。

答案：

正确

371.N个元素排序的时间复杂度不可能是线性时间。

答案：

错误

372.分治法分解的子问题与原问题形式相同。

答案：

正确

373.减治法常见的形式有()

答案：

减可变规模一减一个常量一减一个常量因子

374.减少子问题个数，就是减少时间复杂度函数T(n)=aT(n/b)+f(n)中的()值。

答案：

a

375.合并排序的时间复杂度是()

答案：

nlogn

376.递归是从简单问题出发，一步步的向前发展，最终求得问题，是正向的。

答案：

错误

377递归函数的要素是()

答案：

边界条件.递归方程

378.下面说法正确的是()

答案：

用限界函数剪去得不到最优解的子树。一回溯和分支限界都是动态生成解空

间树用约束函数在扩展结点处剪去不满足约束的子树

379.优先队列式分支限界法按照优先队列中规定的优先级，选取优先级最高的结

点，成为当前扩展结点。

答案:

正确

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

方式不同，但求解目标相同。

答案:

错误

381.解决旅行商问题，采用的是优先队列式分支限界法。

答案:

正确

382.优先队列式分支限界为了加速搜索的进程，按照优先队列中规定的优先级,

选取优先级最高的结点，成为当前扩展结点

答案:

正确

383.贪心法处理问题的核心是贪婪准则的选取

答案:

正确

384.设C是一个环，f是C中的最大边，那么最小生成树中肯定包含f.

答案：

错误

385.分支界限法采用深度优先策略搜索。

答案：

错误

386.Dinic算法的时间复杂度为()

答案：

mnA2

387.如果每条边的最大容量为1,则时间复杂度是0(nm)的网络流算法有()

答案：

FF算法

388,有下界的流通问题，转换为带需求的流通问题有可行的流通，下面错误的是

()

答案：

每翥边的流量不变

389.改进FF网络