阅读程序

注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。

第4节：排序算法

第1题【NOIP】2010

#include <iostream>
using namespace std;
void swap(int & a, int & b)
{
    int t;
    t = a;
    a = b;
    b = t;
}
int main()
{
    int a1, a2, a3, x;        
    cin>>a1>>a2>>a3;
14  if (a1 > a2)
        swap(a1, a2);
    if (a2 > a3)
        swap(a2, a3);
    if (a1 > a2)
19      swap(a1, a2);    
    cin>>x;
    if (x < a2)
        if (x < a1)
            cout<<x<<' '<<a1<<' '<<a2<<' '<<a3<<endl;
        else
            cout<<a1<<' '<<x<<' '<<a2<<' '<<a3<<endl;
    else
        if (x < a3)
            cout<<a1<<' '<<a2<<' '<<x<<' '<<a3<<endl;
        else
            cout<<a1<<' '<<a2<<' '<<a3<<' '<<x<<endl;    
    return 0;
}

●判断题

(1)去掉第14行到第19行，不会影响程序的运行结果。

A. 正确 B. 错误

(2)将第一行的iostream改成cstdio会编译错误。

A. 正确 B. 错误

(3)本题输出结果和将四个数从小到大排序一样。

A. 正确 B. 错误

(4)如果输入

91 2 20
77

,输出为2 20 77 91。

A. 正确 B. 错误

●选择题

(5)如果输入

114514 191 810
258

,程序输出()。

A. 114 514 258 191 9810 B. 114514 191 810 258 C. 114514 191 810 258 D. 191 258 810 114514

(6)如果输入1 1 1 2,程序输出()。

A. 1 1 1 2 B. 1 1 2 1 C. 1 2 1 1 D. 2 1 1 1

第2题【NOIP】2010

#include<iostream>
using namespace std;
int main()
{
    const int SIZE=100;
    int na,nb,a[SIZE],b[SIZE],i,j,k;
    cin>>na;
    for(i=1;i<=na;i++)
        cin>>a[i];
    cin>>nb;
    for(i=1;i<=nb;i++)
        cin>>b[i];
13  i=1;
14  j=1;
    while( (i<=na)&&(j<=nb) )
    {
        if(a[i]<=b[j])
        {
            cout<<a[i]<<' ';
            i++;
        }
        else{
            cout<<b[j]<<' ';
            j++;
        }
    }
    if(i<=na)
       for(k=i;k<=na;k++)
           cout<<a[k]<<' ';
    if(j<=nb)
       for(k=j;k<=nb;k++)
           cout<<b[k]<<' ';
    return 0;
}

●判断题

(1)保证a数组和b数组有序，输出的序列一定是一个不降序列。

A. 正确 B. 错误

(2)如果输入0 0,不会输出数。

A. 正确 B. 错误

(3)如果删掉第13行和第14行不影响程序结果

A. 正确 B. 错误

(4)使用C++98不会CE.

A. 正确 B. 错误

●选择题

(5)该程序时间复杂度是( )

A. O(na+nb) B. O(max{na,nb}logmax{na,nb}) C. O(na·nb) D. O($na^{nb}$)

(6)如果输人、

5
1 3 5 7 9
4
2 6 10 14

,输出( )。

A. 1 2 3 5 6 7 9 10 14 B. 14 10 9 7 6 5 3 2 1 C. 1 3 5 7 9 2 6 10 14 D. 5 1 3 5 7 9 4 2 6 10 14

第3题【NOIP】2011

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 100;
int main(){
    int n,i,sum,x,a[SIZE];
    cin>>n;
8   memset(a,0,sizeof(a));
    for(i=1;i<=n;i++){
        cin>>x;
11      a[x]++;
    }
    i=0; sum=0;
14  while(sum<(n/2+1)){
        i++;
        sum+=a[i];
    }
    cout<<i<<endl;
    return 0;
}

●判断题

(1)当第8行的sizeof(a)改为SIZE时，运行结果不会发生改变。

A. 正确 B. 错误

(2)当第11行的a[x]++改成++a[x]时，运行结果不会发生改变。

A. 正确 B. 错误

(3)当第14行的sum<(n/2+1)改为sum<(n+1)/2时，运行结果不会发生改变。

A. 正确 B. 错误

(4)数组a的所有数中的最大值为1。

A. 正确 B. 错误

●选择题

(5)输入11 4 5 6 6 4 3 3 2 3 2 1,输出的结果为()。

A. 3 B. 4 C. 5 D. error

(6)输入5 1 2 3 4 5,输出的结果为()。

A. 2 B. 3 C. 4 D. 5

第4题【NOIP】2014

#include <iosteam>
#include <string>
using namespace std;
const int    SIZE    = 100;
int main(){
	string dict[SIZE];
	int    rank[SIZE];
	int    ind[SIZE];
	int    i, j, n, tmp;
	cin>>n;
	for ( i = 1; i <= n; i++ ){
12	    rank [i] = i;
		ind[i] = i;
		cin>>dict[i];
	}
	for ( i = 1; i < n; i++ )
		for ( j = 1; j <= n - i; j++ )
			if ( dict[ind[j]]>dict[ind[j + 1]]){
				tmp = ind[j];
				ind[j] = ind[j + 1];
				ind[j + 1] = tmp;
			}
	for ( i = 1; i <= n; i++ )
		rank[ind[i]] = i;
	for ( i = 1; i <= n; i++ )
		cout<<rank[i]<<" ";
	cout<<endl;
	return 0;
}

●判断题

(1)该程序的本质是按字典序对字符串排序。

A. 正确 B. 错误

(2)如果输人0,没有任何输出

A. 正确 B. 错误

(3)如果使用C++98编译，不会出现编译错误。

A. 正确 B. 错误

(4)如果去掉第12行，不影响。

A. 正确 B. 错误

●选择题

(5)输入

7
aaa
aba
bbb
aaa
aaa
ccc
aa

,输出( )。

A. 2 5 6 3 4 7 1 B. 1 2 3 4 5 6 7 C. 1 7 4 3 6 5 2 D. 7 6 5 4 3 2 1

(6)这个程序使用的是什么排序()。

A. 置泡排序 B. 插人排序 C. 希尔排序 D. 选择排序

第5题【NOIP】2016

#include <iostream> 
using namespace std;
int main(){
    int a[6] ;
    int pi = 0;
    int pj = 5;
    int t, i;
8   while (pi < pj){
        t = a[pi];
        a[pi] = a[pj];
        a[pj] = t;
        pi++;
        pj--;
    }
    for (i = 0; i < 6; i++)
        cout << a[i] << ",";
    cout << endl;
    return 0;
}

●判断题

(1)将第8行改成pi<=pj不影响程序结果。

A. 正确 B. 错误

(2)程序输出六个数，逗号只出现在相邻两个数之间。

A. 正确 B. 错误

(3)如果a[6]={1,2,3,4,5,6},那么输出6,5,4,3,2,1。

A. 正确 B. 错误

●选择题

(4)这个程序在()。

A. 将已知序列翻转 B. 求序列的逆 C. 将原始数列随机打乱 D. 求序列的卷积

(5)这个程序的时间复杂度是()

A. O($n^2$) B. O(n) C. O(nlogn) D. $O({n}\sqrt{n})$

(6)如果a[6]={6,5,4,3,2,1},那么输出()。

A. 6,5,4,3,2,1 B. 6 5 4 3 2 1 C. 1 2 3 4 5 6 D. 1,2,3,4,5,6,

第6题【NOIP】2017

#include <iostream>
using namespace std;
int n, s, a[100005], t[100005], i;
void mergesort(int l, int r) {
	if (l == r)
		return;
7	int mid = (l + r) / 2;
	int p = l;
	int i = l;
10	int j = mid + 1;
	mergesort(l, mid);
	mergesort(mid + 1, r);
	while (i <= mid && j <= r) {
		if (a[j] < a[i]) {
			s += mid - i + 1;
			t[p] = a[j];
			p++;
			j++;
		} else {
			t[p] = a[i];
			p++;
			i++;
		}
	}
	while (i <= mid){
		t[p] = a[i];
		p++;
		i++;
	}
	while (j <= r){
		t[p] = a[j];
		p++;
		j++;
	}
	for (i = l; i <= r; i++)
		a[i] = t[i];
}

int main(){
	cin >> n;
	for (i = 1; i <= n; i++)
		cin >> a[i];
	mergesort(1, n);
	cout << s << endl;
	return 0;
}

●判断题

1)如果将第10行的mid+1改成mid,不会影响程序结果和时间复杂度。 ( )

A. 正确 B. 错误

(2)如果将第7行的(l+r)/2改成(l+r+1)/2不会影响程序结果和时间复杂度

A. 正确 B. 错误

(3)程序输出结果不可能是0。

A. 正确 B. 错误

●选择题

(4)该程序的时间复杂度是( )。

A. O(n) B. O(nlogn) C. $O({n}\sqrt{n})$ D. $O(\frac{n^2}{w})$

(5)如果输入

6
2 6 3 4 5 1

输出()。

A. 1 B. 2 C. 4 D. 8

(6)该程序是求输入序列的()。

A. 元素总和 B. 逆序列 C. 逆序对 D. 卷积