Data Structure II Practice Test 3

1. What is the advantage of radix sort over quick sort?

radix sort has lesser space complexity

radix sort is not a comparison based sorting technique

radix sort performs better than quick sort when we have log n bits for every digit

radix sort has better cache performance than quick sort

2. What is the auxiliary space complexity of recursive insertion sort?

O(1)

O(n)

O(n²)

O(n log n)

3. Which of the following is a combination of LSD and MSD radix sorts?

Forward radix sort

Trie base radix sort

Flash sort

3-way radix quick sort

4. What is the best case time complexity of recursive bubble sort?

O(n²)

O(log n)

O(n)

O(n log n)

5. The complexity of which of the following sorting algorithms remains to be the same in its best, average and worst case?

pigeonhole sort

quick sort

bubble sort

insertion sort

6. How many recursive statements are used in the algorithm of stooge sort?

7. Which of the following don’t affect the time complexity of bucket sort?

algorithm implemented for sorting individual buckets

distribution of input

input values

number of buckets used

8. MSD radix sort should be preferred over LSD radix sort when we have to maintain the original relative order.

True

False

9. Which of the following code fragment puts sorted values in an array using beads correctly?

for (int i = 0; i < n; i++) 
{ 
         int j;
        for (j = 0; j < max; j++); 
        //max is the maximum value element of given array a[]  
        a[i] = j; 
i}

for (int i = 0; i < n; i++) 
{ 
         int j;
        for (j = 0; j < max && beads[i * max + j]; j++); 
       //max is the maximum value element of given array a[]  
        a[j] = i; 
}

for (int i = 0; i < n; i++) 
{ 
         int j;
        for (j = 0; j < max && beads[i * max + j]; j++); 
        //max is the maximum value element of given array a[]
        a[i] = j; 
}

for (int i = 0; i < n; i++) 
{ 
         int j;
        for (j = 0; j < beads[i * max + j]; j++); 
       //max is the maximum value element of given array a[]  
        a[j] = i; 
}

10. Which of the following is an in-place sorting algorithm?

Counting sort

Merge sort

Radix sort

Permutation sort