计算机技术与软件专业技术资格考试(中级软件设计师)
对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）
相似问题和答案
第1题：
设有定义：int n1=0,n2,*p=&n2,*q=&n1;,下列赋值语句中与n2=n1；语句等价的是 ( )。
A．*p=*q；
B．p=q；
C．*p=&n1；
D．p=*q；
解析： 在定义指针变量p和q时，分别把变量n2和n1的地址赋给了指针变量p和q，所以*p和*q中内容就分别是变量n2和n1的值，所以语句*p=*q与语句n2=n1等价。因此选项A)正确。
第2题：
当发生窗体的单击事件时，输出的第二行为( )。 Private Sub Form_click() Dim N1 As Integer,N2 As Integer,N3 As Integer N1=1:N2=1 Print N1;N2 Do N3=N1+N2 Print N3； N1=N2:N2=N3 Loop Until N3＞=5 End Sub
A．1 1 1
B．2 3 5
C．2 5 7
D．2 3 4
解析：此处需注意的是，DO…LoopUntil循环的结束条件是Until后面的表达式值是True。当发生窗体的单击事件时，首先给变量N1和N2赋值为1，然后输出为12并换行。执行循环，N3的值为2，输出2不换行，进行赋值后N1的值为1，N2的值为2，判断条件“2＞=5”为False，重新执行循环：第二次执行循环输出N3的值为3，循环结束条件依旧为False；第三次执行循环输出N3的值为5，循环结束条件为True，循环退出。所以输出的第二行为“235”。
第3题：
A.Θ（n）和Θ（1）
B.Θ（n）和Θ（n）
C.Θ（n2）和Θ（1）
D.Θ（n2）和Θ（n）
本题需要用3个辅助变量n1、n2和n3来保存数组A中-1、0和1的个数，空间复杂度为Θ（1）。在统计时，需要使用一循环语句遍历数组A。统计完成后，再使用一次循环语句遍历数组A，并将A中的前n1个元素赋值为-1，第n1+1到n1+n2个元素赋值为0，最后n个元素赋值为1。数组A的元素个数为n，因此算法的时间复杂度为Θ（n）。
第4题：
阅读下列说明和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）。
【问题1】（8分）
（1）k<=r
（2）arr[k]=right[j]
（3）begin<end
（4）mergeSort(arr,mid+1,end)
【问题2】（5分）
（5）分治
（6）T(n)=2T(n/2)+O(n)
（7）O(nlogn)
（8）O(n)
【问题3】（2分）
（9）n1+n2
第5题：
若长度为n的线性表采用顺序存储结构，在第i≤1≤i≤n+1) 个位置插入一个新元素的算法时间复杂度为(1)。
A．O(0)
B．O (1)
C．O(n)
D．O(n2)
解析：性表上插入元素，时间主要耗费在移动元素上。不失一般性，假定性表上的任何位置插入元素是等概率的，即：Pi=1/(n+1)，那么在插入一个元素时所需要移动元素的次数的平均值为：。因此，在长度为n的线性表中插入一个元素的时间复杂度为。
第6题：
在图示四个轴力N1、N2、N3和N4中，( )。
：(A)N1和N2为正，N3和N4为负。
(B)N1和N4为正，N2和N3为负。
(C)N2和N3为正，N1和N4为负。
(D)N3和N4为正，N1和N2为负
第7题：
函数swap(arr,n)可完成对arr数组从第1个元素到第n个元素两两交换。在运行调用函数中的语句后，a[0]和a[1]的值分别为【 】。
a[0]=1；a[1]=2；swap(a，2)；
2，1 解析：本题考核函数参数的传递。数组名作为函数参数传递的是数组的首地址，即实参数组名把实参数组的首地址传给了形参数组名，形参数组名就指向了相应的实参数组，就是说形参数组和实参数其实就是同一个数组，对形参数组元素的修改也同样影响到对应的实参数组元素。
第8题：
设有定义：int n1=0,n2,*p=&n2,*q=&n1;，以下赋值语句中与n2=n1;语句等价的是（）。A）*p=*q; B）p=q;C）*p=&n1; D）p=*q;
B项是将n1的地址赋给p，使p也指向n1,C项表达式错误，应该p=&n1,和B一样的效果，D项也是表达式错误。
第9题：
对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为（62）；若采用快速排序算法，则时间和空间复杂度分别为（63）。
A.O（n2）和O（n）
B.O（n）和O（n）
C.O（n2）和O（1）
D.O（n）和O（1）
本题考查基本排序算法的时间复杂度与空间复杂度。
第10题：
B.n1 - n2
C.n1 + n2 -1
D.n1 + n2
E.(n1 + n2)／2