网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
阅读下列说明和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＜stdio, h＞?? ?#include＜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" );?? ?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);?? ?}?? ?}
参考答案
参考解析
解析： 11、k＜=r arr[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
更多 “阅读下列说明和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＜stdio, h＞?? ?#include＜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" );?? ?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);?? ?}?? ?}” 相关考题
考题
插入排序算法的主要思想是：每次从未排序序列中取出一个数据，插入到已排序序列中的正确位置，InsertSort 类的成员函数sort（）实现了插入排序算法，请将画线处缺失的部分补充完整。class InsertSort{public:InsertSort（int*a0,int n0）:a（a0）,n（n0）{}//参数组首地址，n 是数组元素个数void sort（）{//此函数假设已排离序列初始化状态只包含a[0]，未排序序列初始为a[1]?a[n-1]for （int i=1;iint j;for（ [14] j0;--j）{if（ta[j-1]）break;a[j]=a[j-1];}a[j]=t;}}protected:int*a,n;//指针a 用于存放数组首地址，n 用于存放数组元素个数}；
考题
已知函数 void－ sort(int Array[－1 int N的功能:采用选择排序法将具有N元素的整型数组Aray按由大到小排序元素,排序好的元素仍然放在数组Aray里面。例如:如果原来数组为”1432567,则排序后为”7654321″。編写该函数的实现代码,并要求编写main()函数,对实现函数的进行测试
请帮忙给出正确答案和分析，谢谢
考题
（ 14 ） 插入排序算法的主要思想是 ： 每次从未排序序列中取出一个数据 ， 插入到已排序序列中的正确位置 。InsertSort 类的成员函数 sort() 实现了插入排序算法。请将画线处缺失的部分补充完整。class InsertSort{public:InsertSort(int* a0, int n0) :a(a0), n(n0) {} // 参数 a0 是某数组首地址， n 是数组元素个数void sort( ){// 此函数假设已排序序列初始化状态只包含 a[0] ，未排序序列初始为 a[1]...a[n-1]for (int i=1; iint t=a[i];int j;for ( 【 14 】 ; j0; --j){if (t=a[j-1]) break;a[j]=a[j-1];}a[j]=t;}}protected:int *a, n; // 指针 a 用于存放数组首地址， n 用于存放数组元素个数};
考题
阅读下列说明、流程图和算法，将应填(n)处的字句写在对应栏内。[说明]下面的流程图(如图3所示)用N - S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为 low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：[流程图][算法说明]将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[]，int low，int hieh)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，int L，int H)的功能是实现数组A中元素的递增排序。[算法]void sort(int A[]，int L，int H) {if (L＜H) {k=p(A，L，R)； //p()返回基准数在数组A中的下标sort((4))； //小于基准敷的元素排序sort((5))； //大于基准数的元素排序}}
考题
插入排序算法的主要思想是：每次从未排序序列中取出一个数据，插入到己排序序列中的正确位置。InsertSort类的成员函数sort()实现了插入排序算法。请将画线处缺失的部分补充完整。class InsertSort{public：InsertSort(int* a0，int n0)：a(a0)，n(n0){}//参数a0是某数组首地址，n是数组元素个数void sort(){//此函数假设已排序序列初始化状态只包含a[0]，未排序序列初始为a[1]…a[n-1]for(int i=1；i＜n；++i){int t=a[i]；int j；for(【 】;j＞0；--j){if(t＞=a[j-1])break；a[j]=a[j-1]；}a[j]==t；}}protected：int*a，n；//指针a用于存放数组首地址，n用于存放数组元素个数};
考题
阅读以下算法说明，根据要求回答问题1～问题3。[说明]快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。1．分解：选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1]中的每个元素，小于A[q+1..r]中的每个元素。q的值在划分过程中计算。2．递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。3．合并：快速排序在原地排序，故无需合并操作。下面是快速排序的伪代码，请将空缺处(1)～(3)的内容填写完整。伪代码中的主要变量说明如下。A：待排序数组p,r：数组元素下标，从p到rq：划分的位置x：枢轴元素i：整型变量，用于描述数组下标。下标小于或等于i的元素的值，小于或等于枢轴元素的值j：循环控制变量，表示数组元素下标
考题
阅读以下说明和流程图，填补流程图中的空缺(1)～(9)，将解答填入对应栏内。【说明】假设数组A中的各元素A(1)，A(2)，…，A(M)已经按从小到大排序(M≥1)；数组B中的各元素B(1)，B(2)，…，B(N)也已经按从小到大排序(N≥1)。执行下面的流程图后，可以将数组A与数组B中所有的元素全都存入数组C中，且按从小到大排序 (注意：序列中相同的数全部保留并不计排列顺序)。例如，设数组A中有元素：2，5， 6，7，9；数组B中有元素2，3，4，7：则数组C中将有元素：2，2，3，4，5，6，7， 7， 9。【流程图】
考题
●用插入排序和归并排序算法对数组3，1，4，1，5，9，6，5进行从小到大排序，则分别需要进行 (65) 次数组元素之间的比较。(65)A．12,14B．10,14C．12,16D．10,16
考题
通过设置基准(枢轴)元素将待排序的序列划分为两个子序列,使得其一个子序列的元素均不大于基准元素,另一个子序列的元素均不小于基准元素,然后再分别对两个子序列继续递归地进行相同思路的排序处理,这种排序方法称为()。
A、快速排序B、冒泡排序C、简单选择排序D、归并排序
考题
阅读下列说明、流程图和算法，将应填入(n)处的字句写在对应栏内。【流程图说明】下图所示的流程图5.3用N-S盒图形式描述了数组Array中的元素被划分的过程。其划分方法；以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于Array[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。【算法说明】将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int Array[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组Ar ray中的下标。递归函数void sort(int Array[]，int L，int H)的功能是实现数组Array中元素的递增排序。【算法】void sort(int Array[]，int L，int H){if (L＜H) {k=p(Array，L，H)；/*p()返回基准数在数组Array中的下标*/sort((4))；/*小于基准数的元素排序*/sort((5))；/*大于基准数的元素排序*/}}
考题
F. 归并排序{a为序列表，tmp为辅助数组}procedure merge(var a:listtype; p,q,r:integer);{将已排序好的子序列a[p..q]与a[q+1..r]合并为有序的tmp[p..r]}var I,j,t:integer;tmp:listtype;
考题
若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n)，且是稳定的（即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置不变），则可选择的排序方法是（ ）。A.快速排序 B.归并排序 C.堆排序 D.冒泡排序
考题
阅读下列说明和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代码】inciudestdio.h inciudestdlib.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;in1;i++){ left[i]=arr[p+i]； } left[i]=MAX； for(i=0; in2; 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）。
考题
●试题二阅读下列说明、流程图和算法，将应填入(n)处的字句写在答题纸的对应栏内。【说明】下面的流程图(如图3所示)用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：【流程图】图3流程图【算法说明】将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，int L，int H)的功能是实现数组A中元素的递增排序。【算法】void sort (int A[]， int 1，int H){if ( LH){k=p(A，L，R)；//p()返回基准数在数组A中的下标sort( (4) )；//小于基准数的元素排序sort( (5) )；//大于基准数的元素排序}}
考题
试题一（共 15 分）阅读以下说明和流程图，填补流程图中的空缺（1）～（9） ，将解答填入答题纸的对应栏内。[说明]假设数组 A 中的各元素 A(1)，A(2) ，…，A(M)已经按从小到大排序（M≥1） ；数组 B 中的各元素 B(1)，B(2)，…，B(N)也已经按从小到大排序（N≥1） 。执行下面的流程图后， 可以将数组 A 与数组 B 中所有的元素全都存入数组 C 中， 且按从小到大排序 （注意：序列中相同的数全部保留并不计排列顺序） 。例如，设数组 A 中有元素：2，5，6，7，9；数组B 中有元素：2，3，4，7；则数组 C 中将有元素：2，2，3，4，5，6，7，7，9。[流程图]
考题
阅读下列说明和流程图，填补流程图中的空缺（1）~（9），将解答填入答题纸的对应栏内。【说明】假设数组A中的各元素A⑴，A (2)，…，A (M)已经按从小到大排序(M>1):数组B中的各元素B(1) , B (2) . B (N)也已经按从小到大排序(N≥1)。执行下面的流程图后，可以将数组A与数组B中所有的元素全都存入数组C中，且按从小到大排序(注意：序列中相同的数全部保留并不计排列顺序)。例如，设数组A中有元素： 2,5,6,7,9;数组B中有元素： 2,3,4,7;则数组C中将有元素： 2,2,3,4,5,6,7，7,9.
考题
快速排序算法是，在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 （ ） 算法设计策略。已知确定着基准元素操作的时间复杂度为O(n)，则快速排序算法的最好和最坏情况下的时间复杂度为 （请作答此空） 。A.O(n)和O(nlgn)
B.O(n)和O(n2)
C.O(nlgn)和O(nlgn)
D.O(nlgn)和O(n2)
考题
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（ ）算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n)，则快速排序算法的最好和最坏情况下的时间复杂度为（请作答此空）。
考题
通过设置基准(枢轴)元素将待排序的序列划分为两个子序列，使得其一个子序列的元素均不大于基准元素，另一个子序列的元素均不小于基准元素，然后再分别对两个子序列继续递归地进行相同思路的排序处理，这种排序方法称为（ ）。A.快速排序
B.冒泡排序
C.归并排序
D.简单选择排序
考题
若要求对大小为n的数组进行排序的时间复杂度为O（n^2），且是稳定的（即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置不变），则可选择的排序方法是（ ）A.快速排序
B.归并排序
C.堆排序
D.直接插入排序
考题
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（61）算法设计策略。已知确定着基准元素操作的时间复杂度为O（n），则快速排序算法的最好和最坏情况下的时间复杂度为（62）。A.O（n）和O（nlgn）
B.O（n）和O（n2）
C.O（nlgn）和O（nlgn）
D.O（nlgn）和O（n2）
考题
若要求对大小为n的数组进行排序的平均时间复杂度为O（n^2）??，且是不稳定的（即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置有可能发生改变），则可选择的排序方法是（ ）A.快速排序
B.归并排序
C.直接选择排序
D.冒泡排序
考题
若要求对大小为n的数组进行排序的时间复杂度为，且是稳定的（即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置不变），则可选择的排序方法是（ ）A.快速排序
B.归并排序
C.堆排序
D.冒泡排序
考题
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（）算法设计策略。A、分治B、动态规划C、贪心D、回溯
考题
对用数组存储的线性表（16，15，32，11，6，30），用快速排序算法进行由小到大排序，若排序下标范围为0~5，选择元素16作为支点，调用一趟快速排序算法后，元素16在数组中的下标位置为（）
考题
冒泡排序算法中降序排序指的是（）A、从高到低排列数组元素值B、从低到高排列数组元素的值C、由横向到纵向排列数组元素的值D、由纵向到横向排列数组元素的值
热门标签
最新试卷
