题目内容
（请给出正确答案）
算法设计:设计一个算法,找出给定序列x和y的包含s为其子串的最长公共子序列.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x、y和约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.
结果输出:将计算出的x和y的包含s为其子串的最长公共子序列的长度输出到文件output.txt中.
![问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及一个长度为p](https://img2.soutiyun.com/ask/2021-01-05/97870096903162.png)
![问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及一个长度为p](https://img2.soutiyun.com/ask/2021-01-05/978700980362268.png)
如果结果不匹配，请 联系老师 获取答案
更多“问题描述:给定2个长度分别为n和m的序列x[0...n-1]…”相关的问题
.m处理器问题要求的是
,将数据包序列划分为m段:
使
达到最小.式中,
是序列
的负载量.
的最小值称为数据包序列
的均衡负载量.
算法设计:对于给定的数据包序列,计算m个处理器的均衡负载量.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.n表示数据包个数,m表示处理器数.接下来的1行中有n个整数,表示n个数据包的大小.
结果输出:将计算的处理器均衡负载量输出到文件output,txt,且保留2位小数.
算法设计:对于给定的I和k,计算I的最大k乘积.
数据输入:由文件input.txt提供输入数据.文件的第1行中有2个正整数n和k.正整数n是序列的长度,正整数k是分割的段数.接下来的一行中是一个n位十进制整数(n≤10).
结果输出:将计算结果输出到文件output.txt.文件第1行中的数是计算出的最大k乘积.
问题描述:给定一个赋权无向图G=(V,E),每个顶点
都有权值w(v).如果
,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.
算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).
结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.
算法设计:给定平面上n个点,计算这n个点的最短双调TSP回路.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示给定的平面上的点数.在接下来的n行中,每行2个实数,分别表示点的x坐标和y坐标.
结果输出:将计算的最短双调TSP回路的长度(保留2位小数)输出到文件output.txt.
A.当A的最大元素大于B的最大元素时
B.当A的最大元素小于B的最小元素时
C.当A的最小元素大于B的最小元素时
D.当A的最小元素小于B的最大元素时
问题描述:给定一条有向直线L及L上的n+1个点
.有向直线L上的每个点x都有权值w(xi),每条有向边
都有一个非负边长
.有向直线L上的每个点x可以看作客户,其服务需求量为w(xi)e每条边
的边长可以看作运输费用.如果在点xi处未设置服务机构,则将点xi处的服务需求沿有向边转移到点xj处服务机构需付出的服务转移费用为
.在点x0处已设置了服务机构,现在要在直线L上增设2处服务机构,使得整体服务转移费用最小.
算法设计:对于给定的有向直线L,计算在直线L上增设2处服务机构的最小服务转移费用.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数m,表示有向直线L上除了点x0还有n个点
接下来的n行中,每行有2个整数.第i+1行的2个整数分别表示
和
.
结果输出:将计算的最小服务转移费用输出到文件output.txt.
试题四（共15 分）
阅读下列说明和C代码，回答问题 1 至问题3，将解答写在答题纸的对应栏内。
【说明】
某应用中需要对100000 个整数元素进行排序，每个元素的取值在 0～5 之间。排序算法的基本思想是：对每一个元素 x，确定小于等于 x的元素个数(记为m)，将 x放在输出元素序列的第m 个位置。对于元素值重复的情况，依次放入第 m-l、m-2、…个位置。例如，如果元素值小于等于4 的元素个数有 10 个，其中元素值等于 4 的元素个数有3个，则 4 应该在输出元素序列的第10 个位置、第 9 个位置和第8 个位置上。
算法具体的步骤为：
步骤1：统计每个元素值的个数。
步骤2：统计小于等于每个元素值的个数。
步骤3：将输入元素序列中的每个元素放入有序的输出元素序列。
【C代码】
下面是该排序算法的C语言实现。
(1)常量和变量说明
R:常量，定义元素取值范围中的取值个数，如上述应用中 R值应取6i：循环变量
n：待排序元素个数
a：输入数组，长度为n
b：输出数组，长度为n
c：辅助数组，长度为R，其中每个元素表示小于等于下标所对应的元素值的个数。
(2)函数sort
1 void sort(int n,int a[ ]，intb[ ]){
2 int c[R]，i；
3 for (i=0；i＜ (1) ；i++){
4 c[i]=0；
5 }
6 for(i=0；i＜n；i++）{
7 c[a[i]] = (2) ；
8 }
9 for(i=1；i＜R；i++）{
10 c[i]= （3） ；
11 }
12 for(i=0；i＜n；i++）{
13 b[c[a[i]]-1]= (4) ；
14 c[a[i]]=c[a[i] ]-1；
15 }
16 }
【问题1】（8 分）
根据说明和C代码，填充 C代码中的空缺(1)～(4)。
【问题2】（4 分）
根据C代码，函数的时间复杂度和空间复杂度分别为 (5) 和 (6) （用 O符号
表示）。
【问题3】（3 分）
根据以上C代码，分析该排序算法是否稳定。若稳定，请简要说明（不超过 100 字）；
若不稳定，请修改其中代码使其稳定（给出要修改的行号和修改后的代码）。
从下列的2 道试题（试题五和试题六）中任选 1 道解答。
如果解答的试题数超过 道，则题号小的 道解答有效。
●设递增序列A为a1，a2，？，an，递增序列 B为b1，b2，？，bm，且m＞n，则将这两
个序列合并为一个长度为m+n的递增序列时，当 (38) 时，归并过程中元素的比较次
数最少。
(38)
A. an ＞bm
B.an ＜b1
C.a1＞b1
D.a1＜bm
对于长度为m(m>1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是()
A.若入栈和入队的序列相同，则出栈序列和出队序列可能相同
B.若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序
C.入队序列与出队序列关系为1:1，而入栈序列和出栈序列关系是1：n(n>=1)
D.入栈序列和出栈序列关系为1:1，而入队序列与出队序列关系是1：n(n>=1)
对于长度为m(m＞1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是(60)。
A.若入栈和入队的序列相同，则出栈序列和m队序列可能相同
B.若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序
C.入队序列与出队序列关系为1：1，而入栈序列与出栈序列关系是1：n(n≥1)
D.入栈序列与出栈序列关系为1：1，而入队序列与出队序列关系是1：n(n≥1)
