阅读程序-排序算法
阅读程序
注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。
第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行，不会影响程序的运行结果。
{{ select(1-1) }}
- 正确
- 错误
(2)将第一行的iostream改成cstdio会编译错误。
{{ select(1-2) }}
- 正确
- 错误
(3)本题输出结果和将四个数从小到大排序一样。
{{ select(1-3) }}
- 正确
- 错误
(4)如果输入
91 2 20
77
,输出为2 20 77 91。
{{ select(1-4) }}
- 正确
- 错误
●选择题
(5)如果输入
114514 191 810
258
,程序输出()。
{{ select(1-5) }}
- 114 514 258 191 9810
- 114514 191 810 258
- 114514 191 810 258
- 191 258 810 114514
(6)如果输入1 1 1 2,程序输出()。
{{ select(1-6) }}
- 1 1 1 2
- 1 1 2 1
- 1 2 1 1
- 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数组有序，输出的序列一定是一个不降序列。
{{ select(2-1) }}
- 正确
- 错误
(2)如果输入0 0,不会输出数。
{{ select(2-2) }}
- 正确
- 错误
(3)如果删掉第13行和第14行不影响程序结果
{{ select(2-3) }}
- 正确
- 错误
(4)使用C++98不会CE.
{{ select(2-4) }}
- 正确
- 错误
●选择题
(5)该程序时间复杂度是( )
{{ select(2-5) }}
- O(na+nb)
- O(max{na,nb}logmax{na,nb})
- O(na·nb)
- O()
(6)如果输人、
5
1 3 5 7 9
4
2 6 10 14
,输出( )。
{{ select(2-6) }}
- 1 2 3 5 6 7 9 10 14
- 14 10 9 7 6 5 3 2 1
- 1 3 5 7 9 2 6 10 14
- 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时，运行结果不会发生改变。
{{ select(3-1) }}
- 正确
- 错误
(2)当第11行的a[x]++改成++a[x]时，运行结果不会发生改变。
{{ select(3-2) }}
- 正确
- 错误
(3)当第14行的sum<(n/2+1)改为sum<(n+1)/2时，运行结果不会发生改变。
{{ select(3-3) }}
- 正确
- 错误
(4)数组a的所有数中的最大值为1。
{{ select(3-4) }}
- 正确
- 错误
●选择题
(5)输入11 4 5 6 6 4 3 3 2 3 2 1,输出的结果为()。
{{ select(3-5) }}
- 3
- 4
- 5
- error
(6)输入5 1 2 3 4 5,输出的结果为()。
{{ select(3-6) }}
- 2
- 3
- 4
- 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)该程序的本质是按字典序对字符串排序。
{{ select(4-1) }}
- 正确
- 错误
(2)如果输人0,没有任何输出
{{ select(4-2) }}
- 正确
- 错误
(3)如果使用C++98编译，不会出现编译错误。
{{ select(4-3) }}
- 正确
- 错误
(4)如果去掉第12行，不影响。
{{ select(4-4) }}
- 正确
- 错误
●选择题
(5)输入
7
aaa
aba
bbb
aaa
aaa
ccc
aa
,输出( )。
{{ select(4-5) }}
- 2 5 6 3 4 7 1
- 1 2 3 4 5 6 7
- 1 7 4 3 6 5 2
- 7 6 5 4 3 2 1
(6)这个程序使用的是什么排序()。
{{ select(4-6) }}
- 置泡排序
- 插人排序
- 希尔排序
- 选择排序
第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不影响程序结果。
{{ select(5-1) }}
- 正确
- 错误
(2)程序输出六个数，逗号只出现在相邻两个数之间。
{{ select(5-2) }}
- 正确
- 错误
(3)如果a[6]={1,2,3,4,5,6},那么输出6,5,4,3,2,1。
{{ select(5-3) }}
- 正确
- 错误
●选择题
(4)这个程序在()。
{{ select(5-4) }}
- 将已知序列翻转
- 求序列的逆
- 将原始数列随机打乱
- 求序列的卷积
(5)这个程序的时间复杂度是()
{{ select(5-5) }}
- O()
- O(n)
- O(nlogn)
(6)如果a[6]={6,5,4,3,2,1},那么输出()。
{{ select(5-6) }}
- 6,5,4,3,2,1
- 6 5 4 3 2 1
- 1 2 3 4 5 6
- 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,不会影响程序结果和时间复杂度。 ( )
{{ select(6-1) }}
- 正确
- 错误
(2)如果将第7行的(l+r)/2改成(l+r+1)/2不会影响程序结果和时间复杂度
{{ select(6-2) }}
- 正确
- 错误
(3)程序输出结果不可能是0。
{{ select(6-3) }}
- 正确
- 错误
●选择题
(4)该程序的时间复杂度是( )。
{{ select(6-4) }}
- O(n)
- O(nlogn)
(5)如果输入
6
2 6 3 4 5 1
输出()。
{{ select(6-5) }}
- 1
- 2
- 4
- 8
(6)该程序是求输入序列的()。
{{ select(6-6) }}
- 元素总和
- 逆序列
- 逆序对
- 卷积