分治策略
动态规划法
贪心法
回溯法
第1题:
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用(57)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。串<1,0,0,1,0,1,0,1,>和<0,1,0,1,1,0,1,1,>的最长公共子序列的长度为(58)。
A.分治
B.贪心
C.动态规划
D.分支一限界
第2题:
阅读下列说明和C代码,回答问题l至问题3.将解答写在答题纸的对应栏内。
【说明】
计算一个整数数组a的最长递增子序列长度的方法描述如下:
假设数组a的长度为n,用数组b的元素b[i]记录以a[i](0≤i<n)为结尾元素的最长
递增子序列的长度,则数组a的最长递增子序列的长度为器;其中b[i]满足最优子结构,可递归定义为:
【c代码】
下面是算法的c语言实现。
(1)常量和变量说明
a:长度为n的整数数组,待求其最长递增子序列
b:长度为n的数组,b[i]记录以a[i](0≤i<n)为结尾元素的最长递增子序列的长度,
其中0≤i<n
len:最长递增子序列的长度
i.j:循环变量
temp,临时变量
(2)C程序
include <stdio . h>
int maxL (int *b. int n) {
int i. temp =0;
For(i = 0; i < n; i++){
if (b[i] > temp )
Temp= b[i];
}
Return temp;
【问题l】(8分)
根据说明和C代码,填充C代码中的空(1)~(4)。
【问题2】(4分)
根据说明和C代码,算法采用了(5)设计策略,时间复杂度为(6)(用O符号表示)。
【问题3】(3分)
已知数组a={3,10,5,15,6,8},根据说明和C代码,给出数组b的元素值。
第3题:
A.分治策略
B.动态规划法
C.贪心法
D.回溯法
第4题:
实现最长公共子序列利用的算法是()。
第5题:
第6题:
对于求取两个长度为n的字符串的最长公共子序列问题,利用(41)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。
A.贪心
B.分治
C.分支-限界
D.动态规划
第7题:
第8题:
此题为判断题(对,错)。
第9题:
二分搜索算法是利用()实现的算法。
第10题:
给定一个由n个数组成的序列,要求该序列的最长单调上升子序列,请设计对应的算法并分析其时间复杂度,如果时间复杂度劣于O(nlogn)的,将其优化为O(nlogn)时间复杂度的算法。