当前没有测试数据。

1. 基于比较的排序时间复杂度的下限是（ ），其中n表示待排序的元素个数？ {{ select(1) }}

• $O(n)$
• $O(n log n)$
• $O(log n)$
• $O(n^2)$
  
  

2. 完善程序：

（序列重排）全局数组变量 a 定义如下：

const int SIZE = 100;
int a[SIZE], n;

它记录着一个长度为n的序列 a[1],a[2],⋯,a[n]。 现在需要一个函数，以整数p(1≤p≤n)为参数，实现如下功能：将序列a 的前p个数与后n–p 个数对调，且不改变这p 个数（或n–p个数）之间的相对位置。例如，长度为 5 的序列 1, 2, 3, 4, 5，当p=2 时重排结果为3, 4, 5, 1, 2 。 有一种朴素的算法可以实现这一需求，其时间复杂度为$O(n)$、空间复杂度为 $O(n)$：

void swap1( int p )
{
	int i, j, b[SIZE];
	for ( i = 1; i <= p; i++ )
		b[①] = a[i];     
	for ( i = p + 1; i <= n; i++ )
		b[i - p] = ②;     
	for ( i = 1; i <= ③; i++ ) 
		a[i] = b[i];
}

我们也可以用时间换空间，使用时间复杂度为$O(n2)$、空间复杂度为$O(1)$的算法：

void swap2(int p)
{
	int i, j, temp;
	for ( i = p + 1; i <= n; i++ )
	{
		temp = a[i];
		for ( j = i; j >= ④; j-- ) 
			a[j] = a[j - 1];
		⑤ = temp;   
	}
}

第一空：{{ input(2) }}
第二空：{{ input(3) }}
第三空：{{ input(4) }}
第四空：{{ input(5) }}
第五空：{{ input(6) }}

3. 某算法的计算时间表示为递推关系式 $T(n)=T(n−1)+n$(n 为正整数)及$T(0)=1$，则该算法的时间复杂度为？ {{ select(7) }}

• $O(logn)$
• $O(nlogn)$
• $O(n)$
• $O(n^2)$
  
  

4. 给定一个含N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要 N−1 次比较操作。则最坏情况下，在该数组中同时找最大与 最小的数至少需要（ ）次比较操作。（⌈ ⌉表示向上取整，⌊ ⌋表示向下取整） {{ select(8) }}

• ⌈3N / 2⌉ - 2
• ⌊3N / 2⌋ - 2
• 2N - 2
• 2N - 4
  
  

5. 冒泡排序算法的伪代码如下：

输入：数组L, n ≥ k。输出：按非递减顺序排序的 L。
算法 BubbleSort：
   1. FLAG ← n //标记被交换的最后元素位置
   2. while FLAG > 1 do
   3. k ← FLAG -1
   4. FLAG ← 1
   5. for j=1 to k do
   6.   if L(j) > L(j+1) then do
   7.    L(j)  ? L(j+1)
   8.    FLAG ← j

对 n 个数用以上冒泡排序算法进行排序，最少需要比较多少次?

{{ select(9) }}

• $n^2$
• $n-2$
• $n-1$
• $n$
  
  

6. 以比较作为基本运算，在N个数中找出最大数，最坏情况下所需要的最少的比较次数为？ {{ select(10) }}

• $N^2$
• $N$
• $N - 1$
• $N + 1$