设计一个O（n²)时间的算法,找出由n个数组成的序列的最长单调递增子序列.

问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及d个约束字符串多子串排斥约束的最长公共子序列问题就是要找出x和y的不含为其子串的最长公共子序列

算法设计:设计一个算法,找出给定序列x和y的不含为其子串的最长公共子序列.

数据输入:重文件input.txt提供输入数据.文件的第1行中给出正整数d,表示约束字符串个数.接下来的2行分别给出序列x和y.最后d行的每行给出一个约束字符串.

结果输出:将计算出的x和y的不含为其子串的最长公共子序列输出到文件output.txt中.文件的第1行输出最长公共子序列.第2行输出最长公共子序列的长度.

问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及一个长度为p的约束字符串S[0...p-1].带有子串包含约束的最长公共子序列问题就是要找出x和y的包含s为其子串的最长公共子序列.例如,如果给定的序列x和y分别为AATGCCTAGGC和CGATCTGGAC,字符串s=GTA时,子序列ATCTGGC是x和y的一个无约束的最长公共子序列,而包含s为其子串的最长公共子序列是GTAC.

算法设计:设计一个算法,找出给定序列x和y的包含s为其子串的最长公共子序列.

数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x、y和约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.

结果输出:将计算出的x和y的包含s为其子串的最长公共子序列的长度输出到文件output.txt中.

A、快速排序

B、插入排序

C、冒泡排序

D、归并排序

A、

B、

C、

D、

问题描述:给定n个整数组成的序列,现在要求将序列分割为m段,每段子序列中的数在原序列中连续排列.如何分割才能使这m段子序列的和的最大值达到最小?

算法设计:给定n个整数组成的序列,计算该序列的最优m段分割,使m段子序列的和的最大值达到最小.

数据输入:由文件input.txt提供输入数据.文件的第1行中有2个正整数n和m.正整数n是序列的长度:正整数m是分割的段数.接下来的一行中有n个整数.

结果输出:将计算结果输出到文件output.txt.文件的第1行中的数是计算出的m段子序列的和的最大值的最小值.

A、满二叉树

B、完全二叉树

C、单支树

D、只有根结点的二叉树

问题描述:最长重复子串问题在分子生物学和模式识别中有广泛应用,可以具体表述如下.给定1个长度为n的DNA序列X,最长重复子串问题就是要找出在X中出现2次以上且长度最长的子串.例如,给定的DNA序列为X=AGCATGCATGCAT,则子串GCATGCAT是X的一个最长重复子串,它在X的位置1和5处出现(第1个字符的位置为0).

算法设计:设计一个算法,找出给定字符串X的最长重复子串.

数据输入:由文件input.txt提供输入数据.文件的第1行中给出字符串X.

结果输出:将计算出的字符串X的最长重复子串输出到文件output.txt中.

文件的第1行是最长重复子串的长度.文件的第2行是最长重复子串.

问题描述:最优求幂问题:给定一个正整数n和一个实数x,如何用最少的乘法次数计算出xⁿ.例如,可以用6次乘法逐步计算x²³如下:.可以证明,计算x²³最少需要6次乘法.计算x23的幂序列中各幂次1、2、3、5、10、20、23组成了一个关于整数23的加法链.一般情况下,计算xⁿ的幂序列中各幂次组成正整数n的一个加法链:

上述最优求幂问题相应于正整数n的最短加法链问题,即求n的一个加法链,使其长度r达到最小.正整数n的最短加法链长度记为l(n).

算法设计:对于给定的正整数n,计算相应于正整数n的最短加法链.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数n.

结果输出:将计算的最短加法链长度l(n)和相应的最短加法链输出到文件output.txt.