对于求取两个长度为n的字符串的最长公共子序列问题，利用(57)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。A．贪心B．分治C．分支—限界D．动态规划

阅读以下程序说明和C程序，将应填入(n)处的子句，写在对应栏内。

【程序说明】

函数int commstr(char * str1，char * str2，int * sublen)从两已知字符串str1和str2中，找出它们的所有最长的公共子串。如果最长公共子串不止1个，函数将把它们全部找出并输出。约定空串不作为公共子串。

函数将最长公共子串的长度送入由参数sublen所指的变量中，并返回字符串str1和str2的最长公共子串的个数。如果字符串str1和str2没有公共子串，约定最长公共子串的个数和最长公共子串的长度均为0。

【程序】

int strlen(char * s)

{char *t=s;

while( * ++);

return t-s-1;

}

int commstr(char) *str1,char *str2,int *sublen

{ char*s1, *s2;

int count=0,len1 ,len2,k,j,i,p;

len1:=strlen(str1)

len2 = strlen(str2);

if(len1＞len2)

{s1=str1 ;s2=str2;}

else {len2 = len1;s1 = str2;s2 = str1;}

for(j=len2;j＞0;j--) /*从可能最长子串开始寻找*/

{for(k=0;(1)＜:len2;k++) /*k为子串s2的开始位置*/

{for(i=0;s1[(2)]!='\0';i++;) /*i为子串s1的开始位置*/

{ /*s1的子串与s2的子串比较*/

for (p=0;p＜j)&&(3);p++);

if ((4)) /*如果两子串相同*/

{for(p=0);p＜j;p++} /*输出子串*/

printf ("%c",s2[k+p]);

printf ("\n");

count++;/*计数增1 */

}

}

}

if (count＞0) break;

*sublen=(count＞0)?(5):0;

return count;

}

对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用(24)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。串 ＜1，0，0，1，O，1，0，1＞和＜0，1，0，1，1,0,1，1＞的最长公共子序列的长度为(25)。

A．分治

B．贪心

C．动态规划

D．分支—限界

对于求取两个长度为n的字符串的最长公共子序列问题，利用(41)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。

A．贪心

B．分治

C．分支-限界

D．动态规划

阅读下列说明和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的元素值。