1. Which of the followings are TRUE? why?

(A) If there are N numbers in a max heap, finding the 2nd largest number takes no better than O( log N ) time. (B) If there are N numbers in a max heap, using level order traversal on this max heap returns N numbers that are sorted in descending order. (C) If there are N numbers in a min heap, using level order traversal on this min heap returns N numbers that are sorted in ascending order. (D) There exists a max heap (with more than 1 node) that is a binary search tree. (E) If there are N numbers in the array, the Big-O complexity of Heapsort is O(NlogN).

2. Here is a list of 10 numbers that are partially sorted. Which sorting algorithm(s) could have produced the following array after 2 iterations? why? Original sequence: 30,20,40,50,60,10,70,90,80,0 Sequence after 2 iterations: 20 30 40 50 60 10 70 90 80 0

(A) Selection Sort (B) Insertion Sort // (B) (C) Bubble Sort

3. What is the Big-O complexity of the following function isV2inV1()? (A) O( N1 ) // (A) (B) O( N1 + N2 ) (C) O( N2 ) (D) O( N1*N2 )

why?

bool isV2inV1(int v1[], int N1,int v2[], int N2) {

int i = 0, j = 0; while( i < N1 && j < N2 ){

if(v1[ i ] == v2[ j ]) {

i++; j++;

}

else

i++;

}

if( j == N2)

return true;

return false;

}

4.

What is the Big-O complexity of the following program? (A) O( N2 ) (B) O( N3 ) (C) O( N4 ) (D) O( N5 ) why?

#include

using namespace std;

int main() {

int N; cin >> N;

for(int i=1; i <= N ; i++)

for(int j=1; j <= i*i ; j++)

if(j % i == 0)

for(int k = 0 ; k < j ; k++ )

cout << ".";

else

cout << endl;

}