CMS专题
单选题对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）
Θ（n）和Θ（n）
Θ（n2）和Θ（1）
Θ（n2）和Θ（n）
相似问题和答案
第1题：
（ 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; i
int t=a[i];
int j;
for ( 【 14 】 ; j>0; --j){
if (t>=a[j-1]) break;
a[j]=a[j-1];}
a[j]=t;}}
protected:
int *a, n; // 指针 a 用于存放数组首地址， n 用于存放数组元素个数
};
第2题：
用数组A[0,N-1]存放循环队列的元素值，若其头指针和尾指针分别为front和rear，则循环队列中当前元素的个数为
A．(rear-front+N+1)mod N
B．(rear-front+1)mod N
C．(rear-front-1+N)mod N
D．(rear-front)mod N
第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题：
插入排序算法的主要思想是：每次从未排序序列中取出一个数据，插入到己排序序列中的正确位置。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用于存放数组元素个数
};
j＝i 解析：本题考查的是插入排序算法。在sort()函数中是一个两重循环，外循环从1循环递增到n-1，即遍历未排序序列a[1]…a[n-1]，取未排序序列中的第1个元素a[i] (i初值等于1)与已排序序列中的最后一个元素a[i-1]开始从后往前进行比较。内循环从后往前遍历已排序序列，使循环变量j的初值为i，则a[j-1]是已排序序列的最后一个元素。所以应该填j＝i
第5题：
A.N1=N2、σ1=σ2
B.N1≠N2、σ1=σ2
C.N1=N2、σ1≠σ2
D.N1≠N2、σ1≠σ2
第6题：
插入排序算法的主要思想是：每次从未排序序列中取出一个数据，插入已排序序列中的正确位置。Insert类的成员函数sort()实现了插入排序算法，请填空。
class Insert{
public:
Insert(int*b0,int n0):b(b0),n(n0){};//参数b0是某数组首地址，n是数组元素个数
void sort()
{//此函数假设已排序序列初始化状态只包含b[0]，未排序序列初始为b[1]…b[n-1]
for(int i=1;i＜n;++i)
{
int t=b[i];
int j;
for(______;j＞0;--j)
{
if(t＞=b[j-1])
break;
b[j]=b[j-1];
b[j]=t;
}
}
}
};
j=i 解析：在函数sort()中，外层for循环中依次将数组b中的值赋值给变量t，然后在内层循环中依次与已经排序的数组元素进行比较，并在符合条件的位置插入该元素。“int t=b[i];”语句可知数组中有i个元素已经排序。因此，根据内层循环中的j＞0;--j语句，知道内层循环是将当前的第i个元素与j个元素进行比较，前面已知数组中有i个元素已经排序，根据题干中的要求“插入已排序序列中”，即j=i。
第7题：
函数swap(a, n)可完成对a数组从第1个元素到第n个元素两两交换。其中b[0]=1;b[1]=2; swap(b, 2)。在运行调用函数中的语句后，b[0]和b[1]的值分别为( )。
A．1，1
B．1，2
C．2，2
D．2，1
解析：如果函数实参是数组名，形参也应为数组名，函数swap中形参进行了交换，实际卜也是实参进行了交换。而且数组名代表数组首元素的地址，并不代表数组的全部元素。所以，swap(b，2)是数组b第一个元素与第二个元素进行交换，即b[0]与b[1]，根据题干，知道答案为2，1。
第8题：
插入排序算法的主要思想是：每次从未排序序列中取出一个数据，插入到已排序序列中的正确位置，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] j>0;--j）{
if（t>a[j-1]）break;
a[j]=a[j-1];}
a[j]=t;}}
protected:
int*a,n;//指针a 用于存放数组首地址，n 用于存放数组元素个数
}；
i%2==0
第9题：
A.r-f
B.r-f-1
C.(r-f)%N+1
D.(r-f+N)%N
第10题：
函数swap(arr,n)可完成对arr数组从第1个元素到第n个元素两两交换。在运行调用函数中的语句后，a[0]和a[1]的值分别为【 】。
a[0]=1；a[1]=2；swap(a，2)；
2，1 解析：本题考核函数参数的传递。数组名作为函数参数传递的是数组的首地址，即实参数组名把实参数组的首地址传给了形参数组名，形参数组名就指向了相应的实参数组，就是说形参数组和实参数其实就是同一个数组，对形参数组元素的修改也同样影响到对应的实参数组元素。