八股文-算法

1.利用动态规划计算以下矩阵连乘：A1(20* 25)、A2(25* 5)、A3(5* 15)、A4(15* 10)、A5(10* 20)、A6(20* 25)下列计算开销最小的是（ ）

A (A1A2A3)((A4A5)A6)

B (A1A2)((A3(A4A5))A6)

C (((A1((A2A3)A4)A5)A6)

D (A1A2)(((A3A4)A5)A6)

A的计算次数：

(A1A2A3)：25 * 20*5+20 * 5 *15=4000

((A4A5)A6)：15 * 10 * 20+15 * 20 * 25=10500

(A1A2A3)((A4A5)A6)：25* 20* 5+20* 5* 15+15* 10* 20+15* 20* 25+20* 15* 25=22000

2.贪心算法包含哪些

单源最短路径 最小生成树 0-1背包

3.线性规划问题又称线性规划，特指 目标函数 和 约束条件 皆为线性的 最优化问题

（1）关于线性规划描述不正确的是（ C ）。

图解法只能用于求解两个变量的线性规划问题

线性规划的最优解一定是可行解

线性规划标准形的决策变量不为零

线性规划可行域有界，则一定有最优解

（2）有关LP问题，（ A ）是错误的 。

当最优解多余一个时，最优解必有无穷多个

当有可行解时，必有最优解

当有最优解时，必有在可行集顶点达到的最优解

当有可行解时，必有可行基解

（3）关于标准形线性规划表述不正确的是（ B ）。

约束条件都为不等式

若存在最优解，则最优解必在可行域顶点上

若存在可行域，则可行域一定是凸集

可行域可以是无界

（4）下列不属于NP问题的是？

P问题： 如：排序问题。

一个问题可以在多项式（O(n^k)）的时间复杂度内解决。

NP问题： 如： 一个问题的解可以在多项式的时间内被验证。

NPH问题：

任意np问题都可以在多项式时间内归约为该问题，但该问题本身不一定是NP问题。归约的意思是为了解决问题A，先将问题A归约为另一个问题B，解决问题B同时也间接解决了问题A。

NPC问题：

既是NP问题，也是NP-hard问题。

如：

SAT问题

0-1整数规划

最大团

(SET PACKING)

最小点覆盖

集合覆盖

反馈节点集

反馈弧集

有向哈密尔顿回路

无向哈密尔顿回路

3SAT

图着色数

恰好覆盖

分团覆盖

(HITTING SET)

斯坦纳树

0-1背包

工作规划

最大割

5.下列描述不正确的是（ C ）。

所有NP问题都可以归约为NPC问题 NPC问题在多项式时间内找不到解 NPH问题在多项式时间内找不到解 P问题也是NP问题

6.设串长为n，模式串长为m，则KMP算法所需的附加空间为（ NLOGM ）