在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kA、快速排序B、直接插入排序C、二路归并排序D、简单选择排序E、起泡排序F、堆排序
在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<
- A、快速排序
- B、直接插入排序
- C、二路归并排序
- D、简单选择排序
- E、起泡排序
- F、堆排序
相关考题：
若一个栈初始为空,其输入序列是1,2,3,…,n－1,n,其输出序列的第一个元素为k(1≤k≤「n／2」),则输出序列的最后一个元素是()。 A.值为n的元素B.值为1的元素C.值为n-k的元素D.不确定的
● 设有一个初始为空的栈，若输入序列为 1、2、3、…、n（n3），且输出序列的第一个元素是 n-1，则输入序列中所有元素都出栈后，（37）。（37）A.元素 n-2 一定比n-3 先出栈B.元素 1～n-2 在输出序列中的排列是不确定的C.输出序列末尾的元素一定为 1D.输出序列末尾的元素一定为 n
对具有n个元素的有序序列进行二分查找时，(61)。A．元素位置越靠近序列前端，查找该元素所需的比较次数越少B．查找序列中任何一个元素所需要的比较次数不超过[log2(n+1)]C．查找元素所需的比较次数与元素的位置无关D．元素位置越靠近序列后端，查找该元素所需的比较次数越少
假设有一维数组T[O...m*n-1]，其中m＞n。从数组T的第一个元素(T[0])开始，每隔n个元素取出一个元素依次存入数组B[1...m)中，即B[1]=T[0]，B[2]=T[n]，依此类推，那么放入B[k](1≤k≤n)的元素是(120)。A．T[(K-1)*m]B．T[K*n)C．T[(K-1)*n]D．T[K*m]
已知数组a中有n个元素，下列语句将数组a中从下标x1开始的k个元素移动到从下标x2开始的k个元素中，其中O＜=xl＜x2＜n，x2+k＜n，请将下列语句补充完整。For(int i=x1+k-1；i＞=x1；i--)a[______]=a[i]；
对于n个元素的关键字序列K1，K2，…，Kn，若有Ki≤K2i≤且Ki≤2i+1(i=1，2，…，[n/2]，2i+1≤n)，则称其为小根堆。以下关于小根堆及其元素关系的叙述中，错误的是( )。A．关键字序列K1，K2，…，Kn呈非递减排序时一定为小根堆B．小根堆中的序列K1，K2，K4…，K2j(2j≤n)一定为非递减序列C．小根堆中元素K2i与K2i+1(2i≤n，2i+1≤n)之间的大小关系不能确定D．小根堆的最后一个元素一定是序列的最大元素
已知有一维数组T[0...m*n-1]，其中m＞n。从数组T的第一个元素(T[0])开始，每隔n个元素取出一个元素依次存入数组B[1...m]中，即B[1]＝T[0]，B[2)= T[n]，依次类推，那么放入B[k](1≤k≤m)的元素是______。A．T[(k-1)*n]B．T[k*n]C．T[(k-1)*m]D．T[k*m]
阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素（即将元素从小到大排序后，取第k个元素）。 对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序的序列划分为不大于基准值者（称为左子序列）和大于基准值者（称为右子序列），然后再对左子序列和右子序列分别进行快速排序，最终得到非递减的有序序列。 例如，整数序列19, 12, 30, 11,7,53, 78, 25的第3小元素为12。整数序列19,12,7,30,11,11,7,53,78,25,7的第3小元素为7。 函数partition（int a[ ], int low,int high）以a[low]的值为基准，对a[low]、a[low+1]、、 a[high]进行划分，最后将该基准值放入a[i] (lowihigh)，并使得a[low]、a[low+1]、，．．、 A[i-1]都小于或等于a[i]，而a[i+1]、a[i+2]、．．、a[high]都大于a[i]。 函教findkthElem(int a[],int startIdx,int endIdx,inr k)在a[startIdx]、a[startIdx+1]、...、a[endIdx]中找出第k小的元素。【代码】 include stdio.h include stdlib.h Int partition（int a [ ]，int low, int high） {//对 a[low..high]进行划分，使得a[low..i]中的元素都不大于a[i+1..high]中的元素。 int pivot=a[low]； //pivot表示基准元素 Int i=low,j=high; while(（ 1） ){ While(ija[j]pivot)--j; a[i]=a[j] While(ija[i]=pivot)++i; a[j]=a[i] } （2） ； //基准元素定位 return i； } Int findkthElem（int a[ ]，int startIdx，int endIdx, int k） {//整数序列存储在a[startldx..endldx]中，查找并返回第k小的元素。 if (startldx0 ||endIdx0 || startIdxendIdx || k1 ||k-1endIdx ||k-1startIdx) Return-1; //参数错误 if(startIdxendldx){ int loc=partition(a, startIdx, endldx)； ∥进行划分，确定基准元素的位置 if (loc==k-1) ∥找到第k小的元素 return （3） ； if(k-1 loc) //继续在基准元素之前查找 return findkthElem(a, （4） ,k）； else ／／继续在基准元素之后查找 return findkthElem(a， （5） ，k); } return a[startIdx]； } int main() { int i, k; int n; int a[] = {19, 12, 7, 30, 11, 11, 7, 53, 78, 25, 7}; n= sizeof(a)／sizeof(int) //计算序列中的元素个数 for (k=1;k＜n+1；k++){ for(i=0;i＜n;i++){ printf(%d/t,a[i]); } printf(\n); printf(elem %d=%d\n,k,findkthElem(a,0,n-1,k));//输出序列中第k小的元素 } return 0； }
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。[说明]函数int psort(int a[],int n)实现将含n个整数的数组a[]的不同元素按从小到大顺序存于数组a[]中。实现方法是从未确定的元素列中找到最小元素并将a[]的第i最小元素交换至a[i]位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。[C函数]int psort(int a[],int n){int i,J,k,P;for(i=0,k=0;i＜(1);i++){for(j=i+1, (2) ;j＜n; j++)if(a[p]＞a[j])p=j;if(p!=i){t=a[p];a[p]=a[i];a[i]=t;}if( (3) ) k++;else if( (4) ＜a[i])(5)=a[i];}return k;}int a[]={5,7,5,6,4,3,4,6,7};main(){int k,n;for(k=0;k＜(Sizeof a)/Sizeof(int);k++)printf("%5d",a[k]);printf ("\n\n");n=psort(a,(sizeof(a))/sizeof(int));for(k=0;k＜n;k++)printf("%5d",a[k]);printf("\n\n");}
第二题 阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】对n个元素进行简单选择排序的基本方法是：第一趟从第1个元素开始，在n个元素中选出最小者，将其交换至第一个位置，第二趟从第2个元素开始，在剩下的n-1个元素中选出最小者，将其交换至第二个位置，依此类推，第i趟从n-i+1个元素中选出最小元素，将其交换至第i个位置，通过n-1趟选择最终得到非递减排序的有序序列。 问题：2.1 【代码】#include void selectSort(int data[ ],int n)//对 data[0]~data[n-1]中的n个整数按非递减有序的方式进行排列{ int i,j,k; int temp; for(i=0;i for(k=i,j=i+1;（1）;（2）) //k表示data[i]~data[n-1]中最小元素的下标 if(data[j] if(k!=i) { //将本趟找出的最小元素与data[i]交换 temp=data[i]; （4） ;data[k]=temp; } }}int main(){ int arr[ ]={79,85,93,65,44,70,100,57}; int i,m; m=sizeof(arr)/sizeof(int); //计算数组元素的个数，用m表示 （5）; //调用selectSort对数组arr进行非递减排序 for(（6）;i printf(“%d\t”,arr[i]); printf(“\n”); return 0;}
阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】下面的程序利用快速排序中划分的思想在整数序列中找出第 k 小的元素（即 将元素从小到大排序后，取第 k 个元素）。对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数 作为基准值，然后根据基准值进行划分，从而将待排序的序列划分为不大于基准 值者（称为左子序列）和大于基准值者（称为右子序列），然后再对左子序列和 右子序列分别进行快速排序，最终得到非递减的有序序列。例如，整数序列“19, 12, 30, 11,7,53, 78, 25"的第 3 小元素为 12。整数序列“19, 12,7,30, 11, 11,7，53. 78, 25, 7"的第 3 小元素为 7。函数 partition（int a[], int low,int high）以 a[low]的值为基准，对 a[low]、 a[low+l]、…、a[high]进行划分，最后将该基准值放入 a[i] (low≤i≤high)，并 使得 a[low]、a[low+l]、，．．、A[i-1]都小于或等于 a[i]，而 a[i+l]、a[i+2]、．．、 a[high]都大于 a[i]。函 教 findkthElem(int a[],int startIdx,int endIdx,inr k) 在 a[startIdx] 、 a[startIdx+1]、...、a[endIdx]中找出第 k 小的元素。【代码】#include #include Int partition（int a []，int low, int high）{//对 a[low..high]进行划分，使得 a[low..i]中的元素都不大于 a[i+1..high]中的 元素。int pivot=a[low]； //pivot 表示基准元素 Int i=low,j=high;while(（ 1） ){While(ipivot)--j; a[i]=a[ j] While(ipivot)++i; a[ j]=a[i]}（2） ； //基准元素定位 return i；}Int findkthElem（int a[]，int startIdx，int endIdx, int k）{//整数序列存储在 a[startldx..endldx]中，查找并返回第 k 小的元素。if (startldxendIdx || kendIdx||k-1 if (loc==k-1) ∥找到第 k 小的元素return （3） ；if(k-l 小的元素}return 0；}
阅读以下说明和C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。[说明]下面的函数sort(int n,int a[])对保存在数组a中的整数序列进行非递减排序。由于该序列中的元素在一定范围内重复取值，因此排序方法是先计算出每个元素出现的次数并记录在数组b中，再从小到大顺序地排列各元素即可得到一个非递减有序序列。例如，对于序列6，5，6，9，6，4，8，6，5，其元素在整数区间[4，9]内取值，因此使数组元素b[0]～b[5]的下标0～5分别对应数值4～9，顺序地扫描序列的每一个元素并累计其出现的次数，即将4的个数记入b[0]，5的个数记入b[1]，依此类推，9的个数记入b[5]。最后依次判断数组b的每个元素值，并将相应个数的数值顺序地写入结果序列即可。对于上例，所得数组b的各个元素值如下：1.jpg那么在输出序列中写入1个4、2个5、4个6、1个8、1个9，即得4，5，5，6，6，6，6，8，9，从而完成排序处理。[C函数] void sort(int n,int a[]) { int *b; int i, k, number; int minimum=a[0],maximum=a[0]; /*minimum和maximum分别表示数组a的最小、最大元素值*/ for(i=1; i＜n; i++){ if(______) minimum=a[i]; eiSe if (______) maximum=a[i]; } number=maximum-minimum+1; if(number＜=i)return; b=(int*)calloc(number,sizeof(int)); if(!b) return; for(i=0;i＜n; i++){/*计算数组a的每个元素值出现的次数并记入数组b */ k=a[i]-minimum; ++b[k]; } /*按次序在数组a中写入排好的序列*/ i=______; for(k=0; k＜number; k++) for(; ______; --b[k] ) a[i++]=minimum+______; }
若一个栈初始为空，其输入序列是1，2，3，…，n-1，n，其输出序列的第一个元素为k（1≤k≤「n/2」），则输出序列的最后一个元素是（）。A、值为n的元素B、值为1的元素C、值为n-k的元素D、不确定的
单选题已知待排序的n个元素可分为nk个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。AO（nlog₂n）BO（nlog₂k）CO（klog₂n）DO（klog₂k）
单选题下列内部排序算法中在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kA快速排序B直接插入排序C二路归并排序D简单选择排序E.起泡排序F.堆排序