题目内容
（请给出正确答案）
算法设计:设计一个算法,找出给定字符串X的最长重复子串.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出字符串X.
结果输出:将计算出的字符串X的最长重复子串输出到文件output.txt中.
文件的第1行是最长重复子串的长度.文件的第2行是最长重复子串.
如果结果不匹配，请 联系老师 获取答案
更多“问题描述:最长重复子串问题在分子生物学和模式识别中有广泛应用…”相关的问题
算法设计:设计一个算法,找出给定序列x和y的包含s为其子串的最长公共子序列.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x、y和约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.
结果输出:将计算出的x和y的包含s为其子串的最长公共子序列的长度输出到文件output.txt中.
① 系统所要求解决的问题是什么？
② 为解决该问题，系统应干些什么？
③ 系统应该怎么去干？
其中第②个问题在 （25） 阶段解决，第③个问题在 （26） 阶段解决。
（25）
A. 信息系统总体规划
B. 信息系统分析
C. 信息系统设计
D. 信息系统实施
（26）
A. 信息系统总体规划
B. 信息系统分析
C. 信息系统设计
D. 信息系统实施
对于求取两个长度为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．动态规划
A.近端串扰
B.拓扑结构
C.开路或短路
D.错对
下列描述中正确的是
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;
}
intcommstr(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;
}
A.活动资源估算要确定实施项目活动所需资源的使用时问
B.活动资源估算过程必须和成本估算过程相结合
C.进行活动排序时需要考虑活动资源估算问题
D.企业基础设施资源信息可以用于活动资源估算
试题四（共15分）
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。
如果匹配成功，返回s在t中的位置，否则返回-1 。
KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：
1．在串t和串s中，分别设比较的起始下标i=J=O
2．如果串t和串s都还有字符，则循环执行下列操作：
（1）如果j=-l或者t[i]-s[j]，则将i和j分别加1，继续比较t和s的下一个字符；
（2）否则，将j向右滑动到next[j]的位置，即j =next[J]
3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回一1．
其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。
【C代码】
（1）常量和变量说明
t，s：长度为悯铂Is的字符串
next:next数组，长度为Is
（2）C程序
include ＜stdio．h＞
nclude ＜stdliB．h＞
include ＜string．h＞
／*求next【】的值*/
void get_next（int *next, char *s, int Is） {
int i=0，j=-1；
next[0]=-1；/*初始化next[0]*／
while（i＜ ils）{/*还有字符*／
if（j=-1l ls[i]=s[j]）{／*匹配*／
j++；
i++；
if（s[i]一s[jl）
next [i]- next[j];
else
Next[i]=j；
}
else
J= next[j]；
}
}
int kmp（int *next, char *t ,char *s, int.lt, int Is ）
{
inti= 0,j =0 ;
while （i＜lt && （1 ） {
if（j=-1 II 2_） {
i++ ;
j ++ ;
} else
（3） :
}
if （j＞= ls）
Retum （4）
else .
retum-1；
【问题1】（8分）
根据题干说明，填充C代码中的空（1）～（4）.
【问题2】（2分）
根据题干说明和C代码，分析出kmp算法的时间复杂度为 （5）(主串和子的长度分别为It和Is，用O符号表示）。
【问题3】（5分）
根据C代码，字符串“BBABBCAC”的next数组元素值为 （6） (直接写素值，之间用逗号隔开）。若主串为“AABBCBBABBCACCD”，子串为“BBABBCAC则函数Kmp的返回值是 （7）
给定程序MODll．C中函数fun的功能是：在字符串的最前端加入n个*号，形成新串，并且覆盖原串。
注意：字符串的长度最长允许为79。
请改正函数fun中指定部位的错误，使它能得出正确的结果。
注意：不要改动main函数，不得增行或删行，也不得更改程序的结构!
分析该问题，发现问题具有最优子结构。以 L1为例，除了第一个工位之外，经过第j个工位的最短时间包含了经过L1的第j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间，如式(1)。装配后到结束的最短时间包含离开L1的最短时间或者离开L2的最短时间如式（2）。
由于在求解经过L1和L2的第j个工位的最短时间均包含了经过L1的第j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间，该问题具有重复子问题的性质，故采用迭代方法求解。
该问题采用的算法设计策略是（），算法的时间复杂度为（）
以下是一个装配调度实例，其最短的装配时间为（），装配路线为（）
A.分治
B.动态规划
C.贪心
D.回溯
A. O(lgn)
B. O(n)
C. O(n2)
D. O(nlgn)
A.21
B.23
C.20
D.26
A.S11→S12→S13
B.S11→S22→S13
C.S21→S12→S23
D.S21→S22→S23
