阅读程序

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

第4节：排序算法

第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)
• $O({n}\sqrt{n})$
• $O(\frac{n^2}{w})$

(5)如果输入

6
2 6 3 4 5 1

输出()。

{{ select(6-5) }}

• 1
• 2
• 4
• 8

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

{{ select(6-6) }}

• 元素总和
• 逆序列
• 逆序对
• 卷积