计数逆序问题将合并计数逆序的时间由n^2减少为n，从而将算法的时间复杂度由n^2减少为nlogn。

问题描述:给定k个排好序的序列用2路合并算法将这k个序列合并成一个序列.假设采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较.

试设计一个算法确定合并这个序列的最优合并顺序,使所需的总比较次数最少.

为了进行比较,还需要确定合并这个序列的最运合并顺序,使所需的总比较次数最多.

算法设计:对于给定的k个待合并序列,计算最多比较次数和最少比较次数合并方案.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数k,表示有k个待合并序列.接下来的1行有k个正整数,表示k个待合并序列的长度.

结果输出:将计算的最多比较次数和最少比较次数输出到文件output.txt.

问题描述:在一个操场的四周摆放着n堆石子.现要将石子有次序地合并成一堆.规定

每次至少选2堆,最多选k堆石子合并成新的一堆,合并的费用为新的一堆的石子数.试设计一个算法,计算出将n堆石子合并成一堆的最大总费用和最小总费用.

算法设计:对于给定的n堆石子,计算合并成一堆的最大总费用和最小总费用.

数据输入:由文件input.txt提供输入数据.文件的第1行有2个正整数n和k,表示有n堆石子,每次至少选2堆最多选k堆石子合并.第2行有n个数,分别表示每堆石子的个数.

结果输出:将计算的最大总费用和最小总费用输出到文件output.txt.

算法2-2：有序线性表的有序合并【线性表】 Description 已知线性表 LA 和 LB 中的数据元素按值非递减有序排列，现要求将 LA 和 LB 归并为一个新的线性表 LC， 且 LC 中的数据元素仍然按值非递减有序排列。例如，设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则 LC=(2,3,5,6,8,8,9,11,11,15,20) 算法描述如下： 从上述问题要求可知，LC中的数据元素或是LA中的数据元素，或是LB中的数据元素，则只要先设LC为空表，然后将LA或LB中的元素逐个插入到LC中即可。为使LC中元素按值非递减有序排列，可设两个指针 i 和 j 分别指向LA和LB中某个元素，若设 i 当前所指的元素为 a，j 所指的元素为 b，则当前应插入到 LC 中的元素 c 为 c = a < b a b i j LC LA LB br/>图：有序列表有序插入算法 Input 有多组测试数据，每组测试数据占两行。第一行是集合A，第一个整数m（0< m="100）代表集合A起始有m个元素，后面有m个非递减排序的整数，代表A中的元素。第二行是集合B，第一个整数n(0<=n<=100)代表集合b起始有n个元素，后面有n个非递减排序的整数，代表b中的元素。每行中整数之间用一个空格隔开。output 2 3 5 6 7 8 9 11 15 每组测试数据只要求输出一行，这一行含有 m+n 个来自集合 a 和集合b 中的元素。结果依旧是非递减的。每个整数间用一个空格隔开。 sample input4 20sample output2>

问题描述:在一个圆形操场的四周摆放着n堆石子.现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分.试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分.

算法设计:对于给定n堆石子,计算合并成一堆的最小得分和最大得分.

数据输入:由文件input.txt提供输入数据.文件的第1行是正整数n(1≤n≤100),表示有n堆石子.第2行有n个数,分别表示每堆石子的个数.

结果输出:将计算结果输出到文件outpur.txt.文件第1行的数是最小得分,第2行中的数是最大得分.

A、O(1)

B、O(logn)

C、O(n)

D、O(n^2)

阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。

[说明]

Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图，令T是由G的顶点构成的于图，Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树：初始时，T中的点互相不连通；考察G的边集E中的每条边，若它的两个顶点在T中不连通，则将此边添加到T中，同时合并其两顶点所在的连通分量，如此下去，当添加了n-1条边时，T的连通分量个数为1，T便是G的一棵最小生成树。

下面的函数void Kruskal(EdgeType edges[],int n)利用Kruskal算法，构造了有n个顶点的图 edges的最小生成树。其中数组father[]用于记录T中顶点的连通性质：其初值为father[i]=-1 (i=0,1,…,n-1)，表示各个顶点在不同的连通分量上；若有father[i]=j，j＞-1，则顶点i，j连通；函数int Find(int father[],int v)用于返回顶点v所在树形连通分支的根结点。

[函数]

define MAXEDGE 1000

typedef struct

{ int v1;

int v2;

}EdgeType;

void Kruskal(EdgeType edges[],int n)

{ int father[MAXEDGE];

int i,j,vf1,vt2;

for(i=0;i＜n;i+ +) father[i]=-1;

i=0;

j=0;

while(i＜MAXEDGE && j＜(1))

{ vf1=Find(father,edges[i].v1);

vf2=Find(father,edges[i].v2);

if((2))

{(3)=vf1;

(4);

printf("%3d%3d\n",edges[i].v1,edges[i].v2);

}

(5);

}

}

int Find(int father[],int v)

{ int t;

t=v;

while(father[t]＞=0) t=father[t];

return(t);

}

下列给定程序中，函数proc的功能是：首先把b所指字符串中的字符按逆序存放，然后将str1所指字符串中的字符和Str2所指字符串中的字符，按排列的顺序交叉合并到str所指数组中，过长的剩余字符接在str所指数组的尾部。例如，当str1所指字符串中的内容为ABCDEFG，str2 所指字符串中的内容为1234时，str所指数组中的内容应该为A483C2D1EFG；而当str1所指字符串中的内容为1234，str2所指字符串中的内容为ABCEDFG时，str所指数组中的内容应该为1G2F31：4DCBA。 请修改程序中的错误，使它能得出正确的结果。 注意：不要改动main函数，不得增行或删行，也不得更改程序的结构。 试题程序： include<stdlib．h> include<conio．h> include<stdio。h> include<string．h> void proc(char*strl，char*str2，char*str) { int i，j；char ch； i=0；j=strleu(str2)-1； //****found**** while(i>j) { ch=str2[i]；str2[i]=str2[j]；str2[j]=ch； i++；j--； } while(*str1||*str2) { if(*str1){*str=*str1；str++；str1++；) if(*str2){*str=*str2；str++；str2++；) } //****found**** *str=0： } void main { char s1[100]，s2[100]，t[200]； system("CLS")； printf("＼nEnter s1 string：")； scanf("％s"，sl)； printf("＼nEnter s2 string：")； scanf("％s"，s2)； proc(s1，s2，t)； printf("＼nThe result is：％s＼n"，t)； }

设有线性表A=(a1，a2，…am)，B=(b1，b2，…bn)。试写一合并A、B为线性表C的算法，使得

假设A．B均以单链表为存储结构(并且m、n显式保存)。要求C也以单链表为存储结构并利用单链表A、B的结点空间。

● 递增序列A（a1，a2，…，an）和B （b1,b2，…，bn）的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为（61）时，归并过程中元素的比较次数最多。

卡诺图合并最小项的个数必须符合()

A.2的n次方

B.2n

C.4n

D.4n