阅读下列说明和C代码，回答下列问题。[说明] 采用归并排序对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
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" ); exit11 } If((right = (int *)malloc((n2+1) * sizeof(int)))=NULL) Perror("malloc error"); exit 11; } 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;______;k++){ If(left[i]小于right[j] { ______ j++; }else{ arr[k1]=left[i]; i++; } } } Void merge Sort(int arr[ ], int begin, int end) { int mid; if(______){ mid=(begin + end)/2; merge Sort(arr,begin,mid); ______; Merge(arr,begin,mid,end); } }
正确答案及解析
正确答案
解析
k大于=rarr[k]=right[j] begin大于end mergeSort(arr,mid+1,end)[解析] 首先，函数void merge(int arr[],int P,int q,int r)的意思是：对子数组arr[P…q]和子数组arr[q+L..r]进行合并。因此第一空为k大于=q；由于是采用归并排序对n个元素进行递增排序，所以第二空是将left[i]和right[j]的小者存放到arr[k]中去，即arr[k]=right[j]：当数组长度为1时，停止递归，因为此时该数组有序，则第三空为begin大于end，即数组至少有两个元素才进行递归。合并了begin到mid之间的元素，继续合并mid+1到end之间的元素，则第四空为mergeSort(arr,mid+1,end)。12、分治 T(n)=2T(n/2)+O(n) O(nlogn) O(n)[解析] 归并算法实际上就是将数组一直往下分割，直到分割到由一个元素组成的n个子数组，再往上两两归并。将数组进行分割需要logN步，因为每次都是讲数组分割成两半(2x=N，x=logN)。 合并N个元素，需要进行N步，也就是O(N)，则总的时间复杂度为O(NlogN)。合并过程中，使用了”个中间变量存储，left=(int*)malloc((n1+1)*sizeof(int))。所以空间复杂度为O(n)。推导递归式：假设n个元素进行归并排序需要T(n)，可以将其分割成两个分别有n/2个元素的数组分别进行归并，也就是2T(n/2)，在将这两个合并，需要O(n)的时间复杂度，则推导公式为T(n)=2T(n/2)+O(n)。13、n1+n2
你可能感兴趣的试题
一台主机的IP地址为202.123.25.36，掩码为255.255.254.0。如果该主机需要在该网络进行直接广播，那么它应该使用的目的地址为（ ）
-
- A.202.123.25.0
- B.202.123.25.255
- C.202.123.24.0
- D.202.123.24.255
- 查看答案
在计算机系统的日常维护工作中，应当注意硬盘工作时不能__(2)__。另外，需要防范病毒，而__(3)__是不会被病毒感觉的。
-
- A.电子邮件
- B.硬盘
- C.U盘
- D.ROM
- 查看答案
有 4 个 IP 地址：201.117.15.254、201.117.17.01、201.117.24.5 和 201.117.29.3，如果子网掩码为 255.255.248.0，则这 4 个地址分别属于3个子网；其中属于同一个子网的是（）
-
- A.201.117.15.254 和 201.117.17.01
- B.201.117.17.01 和 201.117.24.5
- C.201.117.15.254 和 201.117.29.3
- D.201.117.24.5 和 201.117.29.3
- 查看答案
在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶位和1位终止位，每秒钟传送200个字符，采用4相位调制，则码元速率为（）。
-
- A.50波特
- B.500波特
- C.550波特
- D.1000波特
- 查看答案
在 Windows 中，运行（ ）命令得到下图所示结果。以下关于该结果的叙述中，错误的是（ ）。
Pinging 59.74.111.8 with 32 bytes of data:
Reply from 59.74.111.8: bytes=32 time=3ms TTL=60
Reply from 59.74.111.8: bytes=32 time=5ms TTL=60
Reply from 59.74.111.8: bytes=32 time=3ms TTL=60
Reply from 59.74.111.8: bytes=32 time=5ms TTL=60
Ping statistics for 59.74.111.8:
Packets: Sent = 4, Received = 4, Lost = 0 (0% loss),
Approximate round trip times in milli-seconds:
Minimum = 3ms, Maximum = 5ms, Average = 4ms
-
- A.该命令使得本地主机向目标主机发送了 4 个数据包
- B.本地主机成功收到了目标主机返回的 4 个数据包
- C.本地主机与目标主机连接正常
- D.该命令用于查看目标主机的 IP 地址
- 查看答案