1. Which of the followings are TRUE? why? (A) If there are N numbers in a max he
ID: 3868106 • Letter: 1
Question
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 <iostream>
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;
}
Explanation / Answer
1.) a.) Finding a maximum no. in max heap takes O(1) but heapifying it takes O(log n) so that second largest element becomes root of the tree and from there, we can extract the second largest element. Hence, option a is true.
b.) No, it willn't result in sorted order as parent element is greater than both of its children but it is not necessary that left child is greater than that value at right child. Hence, option b is not correct.
c.) Same as above. Hence, option c is not correct as well.
d.) Yeah, every max heap having 2 nodes is a binary search tree. Hence, option d is correct.
e.) Heap sort takes O(n logn). Hence, option e is also correct.
Hence, options a, d and e are correct options.
2.) The given list of 10 numbers result in required sequence after 2 iterations, if we apply the insertion sort. Hence, option b is correct.
3.) Since, we are checking that there is an element in V1 same as in V2. Therefore, loop will run for the value of N1. hence, option a is correct.
4.) The most inner loop in the given program runs like
1^3 + 2^3 + ..
which results in O(n^4). Hence, option c is correct.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.