Data Structure II Practice Test 3

1. Recursive insertion sort is a comparison based sort.

False

True

2. What is the average time complexity of MSD radix sort (w= bits required to store each key)?

O(n²)

O(n log n)

O(n.w)

O(n + w)

3. There is one small error in the following flip routine. Find out which line it is on.

	1	void flip(int arr[], int i)
	2	{
	3	      int t, init = 0;
	4	      while (init < i)
	5	      {
	6		    t = arr[init];
	7		    arr[i] = arr[init] ;
	8		    arr[i] = t;
	9		    init++;
	10		    i--;
	11	      }
	12	}

Line 3

Line 7

Line 5

Line 9

4. What is the worst space complexity of bucket sort (k = number of buckets)?

O(n log n)

O(n.k)

O(n²)

O(n + k)

5. What will be the order of elements of the array arr = {23, 67, 143, 654, 43} after first iteration of MSD sort is complete?

23, 143, 43, 654, 67

23, 67, 143, 654, 43

23, 43, 67, 143, 654

23, 67, 43, 143, 654

6. Which one of the following sorting algorithm requires recursion?

counting sort

stooge sort

odd even sort

selection sort

7. Which of the following is an alternate name of MSD radix sort?

top down radix sort

bottom up radix sort

forward radix sort

backward radix sort

8. What is the average case time complexity of permutation sort?

O(n*n!)

O(infinity)

O(n²)

O(n log n)

9. LSD radix sort is in-place sorting algorithm.

False

True

10. Which of the following function correctly represents odd-even sort?

void oddEvenSort(int arr[], int n)
{
	bool Sorted = false; 
        while (!Sorted)
	{
		Sorted = true;
	        for (int i=1; i<n-1; i=i+1)
		{
			if (arr[i] < arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = false;
			}
		}
                for (int i=0; i<n-1; i=i+1)
		{
			if (arr[i] < arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = false;
			}
		}
	}
	return;
}

void oddEvenSort(int arr[], int n)
{
	bool Sorted = false; 
        while (!Sorted)
	{
		Sorted = true;
	        for (int i=1; i<n-1; i=i+2)
		{
			if (arr[i] > arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = false;
			}
		}
                for (int i=0; i<n-1; i=i+2)
		{
			if (arr[i] > arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = false;
			}
		}
	}
	return;
}

void oddEvenSort(int arr[], int n)
{
	bool Sorted = false; 
        while (!Sorted)
	{
		Sorted = true;
	        for (int i=1; i<n-1; i=i+2)
		{
			if (arr[i] < arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = true;
			}
		}
                for (int i=0; i<n-1; i=i+2)
		{
			if (arr[i] < arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = true;
			}
		}
	}
	return;
}

void oddEvenSort(int arr[], int n)
{
	bool Sorted = false; 
        while (!Sorted)
	{
		Sorted = true;
	        for (int i=1; i<n-2; i=i+2)
		{
			if (arr[i] > arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = false;
			}
		}
                for (int i=0; i<n-2; i=i+2)
		{
			if (arr[i] > arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = false;
			}
		}
	}
	return;
}