Data Structure II Practice Test 1

1. Which among the following is the best cut-off range to perform insertion sort within a quick sort?

N=0-5

N=20-30

N=5-20

N>30

2. Which of the following is not in place sorting algorithm by default?

quick sort

merge sort

heap sort

insertion sort

3. What is the disadvantage of selection sort?

It takes linear time to sort the elements

It requires auxiliary memory

It is not scalable

It can be used for small keys

4. What is the average time complexity of bottom up merge sort?

O(n log n²)

O(n² log n)

O(n²)

O(n log n)

5. Which of the following code correctly represent exponential search?

int expSearch(int arr[], int n, int x) 
{ 
	if (arr[0] == x) 
		return 0; 
	
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i*2; 

return binarySearch(arr, i/2, max(i, n-1), x); 
//applies binary search in the calculated range
}

int expSearch(int arr[], int n, int x) 
{ 
	if (arr[0] == x) 
		return 0; 
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i*2; 
	return binarySearch(arr, i, min(i, n-1), x);
//applies binary search in the calculated range
}

int expSearch(int arr[], int n, int x) 
{ 
	
	if (arr[0] == x) 
		return 0; 

	
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i/2; 

return binarySearch(arr, i/2, min(i, n-1), x);
//applies binary search in the calculated range
}

int expSearch(int arr[], int n, int x) 
{ 
	if (arr[0] == x) 
		return 0; 
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i*2; 

return binarySearch(arr, i/2, min(i, n-1), x);
//applies binary search in the calculated range
}

6. Linear search(recursive) algorithm used in _____________

When the dataset is unordered

When the size of the dataset is large

When the size of the dataset is low

Never used

7. Choose the code snippet which uses recursion for linear search.

public void linSearch(int[] arr, int first, int last, int key)
{
	if(first == last)
        {
		System.out.print("-1");
	}
	else
        {
		if(arr[first] == key)
                {
			System.out.print(last);
		}
		else
                {
			linSearch(arr, first+1, last, key);
		}
	}
}

      public void linSearch(int[] arr, int first, int last, int key)
      {
		if(first == last)
                {
			System.out.print("-1");
		}
		else
                {
			if(arr[first] == key)
                        {
				System.out.print(first);
			}
			else
                        {
				linSearch(arr, first+1, last-1, key);
			}
		}
      }

public void linSearch(int[] arr, int first, int last, int key)
{
	if(first == last)
        {
		System.out.print("-1");
	}
	else
        {
		if(arr[first] == key)
                {
			System.out.print(first);
		}
		else
                {
			linSearch(arr, first+1, last, key);
		}
	}
}

public void linSearch(int[] arr, int first, int last, int key)
{
	if(first == last)
        {
		System.out.print("-1");
	}
	else
        {
		if(arr[first] == key)
                {
			System.out.print(first);
		}
		else
                {
			linSearch(arr, first+1, last+1, key);
		}
	}
}

8. What is the space complexity of in place merge sort?

O(n log n)

O(log n)

O(1)

O(n)

9. Choose the incorrect statement about merge sort from the following?

standard merge sort has greater space complexity than in-place merge sort

standard merge sort has greater time complexity than in-place merge sort

in place merge sort has O(log n) space complexity

both standard merge sort and in-place merge sort are stable

10. What is the formula used for calculating the position in interpolation search?
(x = element being searched, A[] = input array, low and high are the leftmost and rightmost index of A[] respectively)

high + ((x - A[low]) * (high - low)) / (A[high] - A[low])

((x - A[low]) * (high - low)) / (A[high] - A[low])

x + ((x - A[low]) * (high - low)) / (A[high] - A[low])

low + ((x - A[low]) * (high - low)) / (A[high] - A[low])