Data Structure II Practice Test 2

1. What is the best case time complexity randomized quick sort?

O(n² log n)

O(n²)

O(n log n)

O(log n)

2. What is the worst case time complexity of cocktail sort?

O(n)

O(log n)

O(n log n)

O(n²)

3. What is a randomized quick sort?

quick sort with random input

quick sort with random output

quick sort with random choice of pivot

quick sort with random partitions

4. What is the advantage of comb sort over merge sort?

Comb sort is a stable sorting algorithm

It has no advantage

Comb sort is more efficient

Comb sort is an in place sorting algorithm

5. Who invented the shell sort algorithm?

Alan Shell

Tony Hoare

John Von Neumann

Donald Shell

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

O(N²)

O(N)

O(log N)

O(N log N)

7. Which of the following code performs the partition operation in QuickSort?

private static int partition(int[] arr, int low, int high)
{
	int left, right, pivot_item = arr[low];
	left = low;
	right = high;
	while(left <= right)
	{
		while(arr[left] > pivot_item)
		{
			left++;
		}
		while(arr[right] <= pivot_item)
		{
			right--;
		}
		if(left < right)
		{
			swap(arr, left, right);
		}
	}
	arr[low] = arr[right];
	arr[right] = pivot_item;
	return right;
}

private static int partition(int[] arr, int low, int high)
{
	int left, right, pivot_item = arr[low];
	left = low;
	right = high;
	while(left <= right)
	{
		while(arr[left] <= pivot_item)
		{
			left++;
		}
		while(arr[right] > pivot_item)
		{
			right--;
		}
		if(left < right)
		{
			swap(arr, left, right);
		}
	}
	arr[low] = arr[right];
	arr[right] = pivot_item;
	return right;
}

private static int partition(int[] arr, int low, int high)
{
	int left, right, pivot_item = arr[low];
	left = low;
	right = high;
	while(left > right)
	{
		while(arr[left] > pivot_item)
		{
			left++;
		}
		while(arr[right] <= pivot_item)
		{
			right--;
		}
		if(left < right)
		{
			swap(arr, left, right);
		}
	}
	arr[low] = arr[right];
	arr[right] = pivot_item;
	return right;
}

private static int partition(int[] arr, int low, int high)
{
	int left, right, pivot_item = arr[low];
	left = low;
	right = high;
	while(left > right)
	{
		while(arr[left] <= pivot_item)
		{
			left++;
		}
		while(arr[right] > pivot_item)
		{
			right--;
		}
		if(left < right)
		{
			swap(arr, left, right);
		}
	}
	arr[low] = arr[right];
	arr[right] = pivot_item;
	return right;
}

8. What is the worst case time complexity of randomized quicksort?

O(n log n)

O(n)

O(n² log n)

O(n²)

9. Which of the following is a disadvantage of cube sort?

Iteration is slow

high memory overhead for any data

balancing is slow

high memory overhead for small data

10. How many loops are required to implement gnome sorting algorithm?

2 nested loops

It does not require any loop

Single loop

3 nested loops