对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下:统计A中-1、0和1的个数,设分别为n1、n2和n3,然后将A中的前n1个元素赋值为-1,第n1+1到n1+n2个元素赋值为0,最后n3个元素赋值为1。该算法的时间复杂度和空间复杂度分别为()。 A.(n)和(1)B.(n)和(n)C.(n2)和(1)D.(n2)和(n)
对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下:统计A中-1、0和1的个数,设分别为n1、n2和n3,然后将A中的前n1个元素赋值为-1,第n1+1到n1+n2个元素赋值为0,最后n3个元素赋值为1。该算法的时间复杂度和空间复杂度分别为()。
A.Θ(n)和Θ(1)
B.Θ(n)和Θ(n)
C.Θ(n2)和Θ(1)
D.Θ(n2)和Θ(n)
相关考题:
在下列对单链表进行的操作中,算法时间复杂度为O(n)的是()。 A、访问第i个元素的前驱(1B、在第i个元素之后插入一个新元素(1≤i≤n)C、删除第i个元素(1≤i≤n)D、对表中元素进行排序
试题四(共15 分)阅读下列说明和C代码,回答问题 1 至问题3,将解答写在答题纸的对应栏内。【说明】某应用中需要对100000 个整数元素进行排序,每个元素的取值在 0~5 之间。排序算法的基本思想是:对每一个元素 x,确定小于等于 x的元素个数(记为m),将 x放在输出元素序列的第m 个位置。对于元素值重复的情况,依次放入第 m-l、m-2、…个位置。例如,如果元素值小于等于4 的元素个数有 10 个,其中元素值等于 4 的元素个数有3个,则 4 应该在输出元素序列的第10 个位置、第 9 个位置和第8 个位置上。算法具体的步骤为:步骤1:统计每个元素值的个数。步骤2:统计小于等于每个元素值的个数。步骤3:将输入元素序列中的每个元素放入有序的输出元素序列。【C代码】下面是该排序算法的C语言实现。(1)常量和变量说明R:常量,定义元素取值范围中的取值个数,如上述应用中 R值应取6i:循环变量n:待排序元素个数a:输入数组,长度为nb:输出数组,长度为nc:辅助数组,长度为R,其中每个元素表示小于等于下标所对应的元素值的个数。(2)函数sort1 void sort(int n,int a[ ],intb[ ]){2 int c[R],i;3 for (i=0;i (1) ;i++){4 c[i]=0;5 }6 for(i=0;in;i++){7 c[a[i]] = (2) ;8 }9 for(i=1;iR;i++){10 c[i]= (3) ;11 }12 for(i=0;in;i++){13 b[c[a[i]]-1]= (4) ;14 c[a[i]]=c[a[i] ]-1;15 }16 }【问题1】(8 分)根据说明和C代码,填充 C代码中的空缺(1)~(4)。【问题2】(4 分)根据C代码,函数的时间复杂度和空间复杂度分别为 (5) 和 (6) (用 O符号表示)。【问题3】(3 分)根据以上C代码,分析该排序算法是否稳定。若稳定,请简要说明(不超过 100 字);若不稳定,请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。从下列的2 道试题(试题五和试题六)中任选 1 道解答。如果解答的试题数超过 道,则题号小的 道解答有效。
阅读下列说明和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)。
阅读下列说明和C代码,回答问题1至问题3【说明】??? 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的第m个位置。对于元素值重复的情况,依次放入第m-l、m-2、…个位置。例如,如果元素值小于等于4的元素个数有10个,其中元素值等于4的元素个数有3个,则4应该在输出元素序列的第10个位置、第9个位置和第8个位置上。算法具体的步骤为:步骤1:统计每个元素值的个数。步骤2:统计小于等于每个元素值的个数。步骤3:将输入元素序列中的每个元素放入有序的输出元素序列。【C代码】下面是该排序算法的C语言实现。(1)常量和变量说明R: 常量,定义元素取值范围中的取值个数,如上述应用中R值应取6i:循环变量n:待排序元素个数a:输入数组,长度为nb:输出数组,长度为nc:辅助数组,长度为R,其中每个元素表示小于等于下标所对应的元素值的个数。(2)函数sort1??? void sort(int n,int a[],int b[]){2??? ???int c[R],i;3?? for (i=0;i4?? ??c[i]=0;5??? ???}6??? ???for(i=0;i7??? ?c[a[i]] = ??(2)? ;8??? ???}9 ??for(i=1;i10??? c[i]= ?(3)11??? ??}12 ?for(i=0;i13??? b[c[a[i]]-1]=? (4)?? ;14??? c[a[i]]=c[a[i]]-1;15??? ??}16??? }【问题1】? 根据说明和C代码,填充C代码中的空缺(1)~(4)。【问题2】根据C代码,函数的时间复杂度和空间复杂度分别为 (5) 和 (6) (用O符号表示)。【问题3】?? 根据以上C代码,分析该排序算法是否稳定。若稳定,请简要说明(不超过100字);若不稳定,请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。
声明一个含7个整型元素的数组a,通过键盘为数组a赋值,并进行如下操作: (1) 将数组a的各个元素反转后输出 (2) 将数组a的元素排序后输出 (3)将数组a的前5个元素赋值给数组b,并输出数组b的各个元素。
对于用一维数组d[0..n-1]顺序存储的线性表,其算法的时间复杂度为O(1)的操作是()。A.将n个元素从小到大排序B.从线性表中删除第i个元素(1≤i≤n)C.查找第i个元素(1≤i≤n)D.在线性表中第i个元素之后插入一个元素
对于用一维数组 d [1..n]顺序存储的线性表,其算法时间复杂度为O(1)的操作是_____ 。A.将n个元素从小到大排序B.从线性表中删除第i个元素(1≤i≤n)C.查找第i个元素(1≤i≤n)D.向线性表的第i个元素之后插入一个元素(0≤i≤n)