Data Structure II Practice Test 2

1. Shell sort is applied on the elements 27 59 49 37 15 90 81 39 and the chosen decreasing sequence of increments is (5,3,1). The result after the first iteration will be

27 59 39 37 15 90 81 49

27 59 49 37 15 90 81 39

27 59 37 49 15 90 81 39

15 59 49 37 27 90 81 39

2. Which of the following sorting algorithm is NOT stable?

Merge sort

Introsort

Bubble sort

Brick sort

3. Tim sort begins sorting the given array by using which of the following sorting algorithm?

selection sort

merge sort

insertion sort

quick sort

4. The worst case running time of shell sort, using Shell’s increments is?

O(log N)

O(N)

O(N²)

O(N log N)

5. What will be the output of the given Java code?

import java.util.Arrays; 
public class SortExample 
{ 
	public static void main(String[] args) 
	{ 
		int[] arr = {10,7,9,5,8,4}; 
		Arrays.sort(arr, 1, 3); 
		System.out.printf(Arrays.toString(arr)); 
	} 
}

[10,5,7,8,9,4]

[4,5,7,8,9,10]

[10,9,8,7,5,4]

[10,7,9,5,8,4]

6. Introsort algorithm is combination of _____________

Heap sort and insertion sort

Quick sort and Shell sort

Quick sort and Heap sort

Heap sort and Merge sort

7. What is the worst case complexity of QuickSort?

O(logn)

O(n²)

O(n)

O(nlogn)

8. Why is Shell sort called as a generalization of Insertion sort?

Insertion is more efficient than any other algorithms

Shell sort performs internal sorting

Shell sort allows an exchange of far items whereas insertion sort moves elements by one position

Improved lower bound analysis

9. Auxiliary space used by gnome sort is _________

O(log n)

O(n log n)

O(1)

O(n)

10. Which one of the following is false?

Heap sort is a comparison-based sorting algorithm

Heap sort has O(nlogn) average case time complexity

Heap sort is stable sort

Heap sort is an in-place algorithm