爱迪国际C++章节测试-复杂度分析

*
您的姓名:
*
1.

基于比较的排序时间复杂度的下限是( ),其中N表示待排序的元素个数。

A、O(n)
B、O(nlogn)
C、O(logn)
D. O(n²)
2.
完善程序:(序列重排)全局数组变量a定义如下:
const int SIZE = 100;
int a[SIZE], n;
它记录着一个长度为n的序列 ,a[1],a[2],a[n]现在需要一个函数,以整数p(1≤pn)为参数,实现如下功能:将序列a的前p个数与后np个数对调,且不改变这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(n²)、空间复杂度为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;
}
}问题1:问题2: 问题3:问题4: 问题5:*
*
3.

某算法的计算时间表示为递推关系式 T(n)= T(n-1)+n(n为正整数)T(0)=1,则该算法的时间复杂度为( )

A、 O(logn)

B、 O(nlogn)

C、 O(n)

D 、O(n²)

A、 O(logn)
B、 O(nlogn)
C、 O(n)
D 、O(n²)
*
4.

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

A、 ⌈3N / 2⌉- 2
B、 ⌊3N / 2⌋- 2
C、 2N - 2
D、 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个数用以上冒泡排序算法进行排序,最少需要比较多少次?( )。


A. n²
B. n-2
C. n-1
D. n
*
6.

以比较作为基本运算,在N个数中找出最大数,最坏情况下所需要的最少的比较次数为( )。


A. N²
B.N
C.N-1
D.N+1
问卷星提供技术支持
举报