问题描述:给定k个排好序的序列用2路合并算法将这k个序列合并成一个序列.假设采用的2路合并算法

●设递增序列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

●设递增序列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

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

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

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

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

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

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。 下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下： arr：待排序数组 p,q,r：一个子数组的位置从p到q，另一个子数组的位置从q+1到r begin,end：待排序数组的起止位置 left,right：临时存放待合并的两个子数组 n1,n2：两个子数组的长度 i,j,k：循环变量 mid：临时变量 【C代码】

inciude<stdio.h> inciude<stdlib.h> define MAX 65536 void merge(int arr[],int p,int q,int r) { int *left, *right; int n1,n2,i,j,k; n1=q-p+1; n2=r-q; if((left=(int*)malloc((n1+1)*sizeof(int)))=NULL) { perror("malloc error"); exit(1); } if((right=(int*)malloc((n2+1)*sizeof(int)))=NULL) { perror("malloc error"); exit(1); } for(i=0;i<n1;i++){ left[i]=arr[p+i]； } left[i]=MAX； for(i=0; i<n2; i++){ right[i]=arr[q+i+1] } right[i]=MAX; i=0; j=0; for(k=p; （1） ; k++) { if(left[i]> right[j]) { （2） ; j++; }else { arr[k]=left[i]； i++； } } } void mergeSort(int arr[],int begin,int end){ int mid; if( （3） ){ mid=(begin+end)/2; mergeSort(arr,begin,mid); （4） ; merge(arr,begin,mid,end); } }

【问题1】 根据以上说明和C代码，填充1-4。 【问题2】 根据题干说明和以上C代码，算法采用了（5）算法设计策略。 分析时间复杂度时，列出其递归式位（6），解出渐进时间复杂度为（7）（用O符号表示）。空间复杂度为（8）（用O符号表示）。 【问题3】 两个长度分别为n1和n2的已经排好序的子数组进行归并，根据上述C代码，则元素之间比较次数为（9）。

外排序中为何采用k路(k>2)合并而不用2路合并?这种技术用于内排序有意义吗?为什么?【东南大学1995三(8分)】

5 集合合并：

给定一个字符串的集合，格式如： {aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh} 要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出 {aaa bbb ccc ddd hhh}，{eee fff}， {ggg}

（1）请描述你解决这个问题的思路；

（2）请给出主要的处理流程，算法，以及算法的复杂度

（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。

5 集合合并：

给定一个字符串的集合，格式如： {aaa bbb ccc}， {bbb ddd}， {eee fff}，

{ggg}，{ddd hhh} 要求将其中交集不为空的集合合并，要求合并完成后的集

合之间无交集，例如上例应输出 {aaa bbb ccc ddd hhh}，{eee fff}， {ggg}

（1）请描述你解决这个问题的思路；

（2）请给出主要的处理流程，算法，以及算法的复杂度

（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。

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

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

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

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

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

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