Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Towers of Hanoi using Recursion”.

1. What is the objective of tower of hanoi puzzle?
a) To move all disks to some other rod by following rules
b) To divide the disks equally among the three rods by following rules
c) To move all disks to some other rod in random order
d) To divide the disks equally among three rods in random order
Answer: a
Clarification: Objective of tower of hanoi problem is to move all disks to some other rod by following the following rules-1) Only one disk can be moved at a time. 2) Disk can only be moved if it is the uppermost disk of the stack. 3) No disk should be placed over a smaller disk.

2. Which of the following is NOT a rule of tower of hanoi puzzle?
a) No disk should be placed over a smaller disk
b) Disk can only be moved if it is the uppermost disk of the stack
c) No disk should be placed over a larger disk
d) Only one disk can be moved at a time
Answer: c
Clarification: The rule is to not put a disk over a smaller one. Putting a smaller disk over larger one is allowed.

3. The time complexity of the solution tower of hanoi problem using recursion is _________
a) O(n²)
b) O(2ⁿ)
c) O(n log n)
d) O(n)
Answer: b
Clarification: Time complexity of the problem can be found out by solving the recurrence relation: T(n)=2T(n-1)+c. Result of this relation is found to be equal to 2ⁿ. It can be solved using substitution.

4. Recurrence equation formed for the tower of hanoi problem is given by _________
a) T(n) = 2T(n-1)+n
b) T(n) = 2T(n/2)+c
c) T(n) = 2T(n-1)+c
d) T(n) = 2T(n/2)+n

Answer: c
Clarification: As there are 2 recursive calls to n-1 disks and one constant time operation so the recurrence relation will be given by T(n) = 2T(n-1)+c.

5. Minimum number of moves required to solve a tower of hanoi problem with n disks is __________
a) 2ⁿ
b) 2ⁿ-1
c) n²
d) n²-1

Answer: b
Clarification: Minimum number of moves can be calculated by solving the recurrence relation – T(n)=2T(n-1)+c. Alternatively we can observe the pattern formed by the series of number of moves 1,3,7,15…..Either way it turn out to be equal to 2ⁿ-1.

6. Space complexity of recursive solution of tower of hanoi puzzle is ________
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Answer: b
Clarification: Space complexity of tower of hanoi problem can be found out by solving the recurrence relation T(n)=T(n-1)+c. Result of this relation is found out to be n. It can be solved using substitution.

7. Which of the following functions correctly represent the solution to tower of hanoi puzzle?
a)

void ToH(int n,int a,int b,int c)
{
   If(n>0)
   {
       ToH(n-1,a,c,b);
       cout<<”move a disk from” <<a<<” to”<< c;
       ToH(n-1,b,a,c);
   }
}

b)

void ToH(int n,int a,int b,int c
{
   If(n>0)
   {
       ToH(n-1,a,b,c);
       cout<<”move a disk from” <<a<<” to”<< c;
       ToH(n-1,b,a,c);
   }
}

c)

void ToH(int n,int a,int b,int c)
{
     If(n>0)
     {
         ToH(n-1,a,c,b);
         cout<<”move a disk from” <<a<<” to”<< c;
         ToH(n-1,a,b,c);
     }
}

d)

void ToH(int n,int a,int b,int c)
{
   If(n>0)
   {
       ToH(n-1,b,a,c);
       cout<<”move a disk from” <<a<<” to”<< c;
       ToH(n-1,a,c,b);
   }
}

Answer: a
Clarification: The first recursive call moves n-1 disks from a to b using c. Then we move a disk from a to c. Finally the second recursive call moves n-1 disks from b to c using a.

8. Recursive solution of tower of hanoi problem is an example of which of the following algorithm?
a) Dynamic programming
b) Backtracking
c) Greedy algorithm
d) Divide and conquer

Answer: d
Clarification: The recursive approach uses divide and conquer algorithm as we break the problem into smaller parts and then solve the smaller parts and finally combine their results to get the overall solution.

9. Tower of hanoi problem can be solved iteratively.
a) True
b) False

Answer: a
Clarification: Iterative solution to tower of hanoi puzzle also exists. Its approach depends on whether the total numbers of disks are even or odd.

10. Minimum time required to solve tower of hanoi puzzle with 4 disks assuming one move takes 2 seconds, will be __________
a) 15 seconds
b) 30 seconds
c) 16 seconds
d) 32 seconds

Answer: b
Clarification: Number of moves = 2⁴-1=16-1=15
Time for 1 move = 2 seconds
Time for 15 moves = 15×2 = 30 seconds.

& Algorithms.

Data Structure Multiple Choice Questions & Answers (MCQs) on “Minimum Number of Jumps”.

1. You are given an array of elements where each array element represents the MAXIMUM number of jumps that can be made in the forward direction from that element. You have to find the minimum number of jumps that are required to reach the end of the array. Which of these methods can be used to solve the problem?
a) Dynamic Programming
b) Greedy Algorithm
c) Recursion
d) Recursion and Dynamic Programming

Answer: d
Clarification: Both recursion and dynamic programming can be used to solve minimum number of jumps problem.

2. Consider the following array:
{1, 3, 5, 8, 9, 2, 6, 7, 6}
What is the minimum number of jumps required to reach the end of the array?
a) 1
b) 2
c) 3
d) 4

Answer: c
Clarification: The jumps made will be:{1 -> 2 -> 4 -> 9}. So, the number of jumps is three.

3. Consider the following recursive implementation:

#include
#include
int min_jumps(int *arr, int strt, int end)
{
     int idx;
     if(strt == end)
	return 0;
     if(arr[strt] == 0) // jump cannot be made
	return INT_MAX;
     int min = INT_MAX;
     for(idx = 1; idx <= arr[strt] && strt + idx <= end; idx++)
     {
	  int jumps = min_jumps(____,____,____) + 1;
	  if(jumps < min)
	      min  = jumps;
     }
     return min;
}
int main()
{
     int arr[] ={1, 3, 5, 8, 9, 2, 6, 7, 6},len = 9;
     int ans = min_jumps(arr, 0, len-1);
     printf("%dn",ans);
     return 0;
}

Which of these arguments should be passed by the min_jumps function represented by the blanks?
a) arr, strt + idx, end
b) arr + idx, strt, end
c) arr, strt, end
d) arr, strt, end + idx

Answer: a
Clarification: arr, strt + idx, end should be passed as arguments.

4. For a given array, there can be multiple ways to reach the end of the array using minimum number of jumps.
a) True
b) False
Answer: a
Clarification: Consider the array {1,2,3,4,5}. It is possible to reach the end in the following ways: {1 -> 2 -> 3 -> 5} or {1 -> 2 -> 4 -> 5}.
In both the cases the number of jumps is 3, which is minimum. Hence, it is possible to reach the end of the array in multiple ways using minimum number of jumps.

5. What is the output of the following program?

#include
#include
int min_jumps(int *arr, int strt, int end)
{
      int idx;
      if(strt == end)
 	 return 0;
      if(arr[strt] == 0) // jump cannot be made
	 return INT_MAX;
      int min = INT_MAX;
      for(idx = 1; idx <= arr[strt] && strt + idx <= end; idx++)
      {
	   int jumps = min_jumps(arr, strt + idx, end) + 1;
	   if(jumps < min)
	     min  = jumps;
      }
      return min;
}
int main()
{
      int arr[] ={1, 2, 3, 4, 5, 4, 3, 2, 1},len = 9;
      int ans = min_jumps(arr, 0, len-1);
      printf("%dn",ans);
      return 0;
}

a) 4
b) 5
c) 6
d) 7

Answer: a
Clarification: The program prints the minimum number of jumps required to reach the end of the array. One way reach the end using minimum number of jumps is
{1 -> 2 -> 4 -> 8 -> 9}. So, the number of jumps is 4.

6. For any array, given that at most one element is non-zero, it is ALWAYS possible to reach the end of the array using minimum jumps.
a) True
b) False

Answer: b
Clarification: Consider the array {1,0,2,3,4}.
In this case, only one element is 0 but it is not possible to reach the end of the array.

7. Consider the following dynamic programming implementation of the minimum jumps problem:

#include
#include
int min_jump(int *arr, int len)
{
     int j, idx, jumps[len];
     jumps[len - 1] = 0;
     for(idx = len - 2; idx >= 0; idx--)
     {
	  int tmp_min = INT_MAX;
	  for(j = 1; j <= arr[idx] && idx + j < len; j++)
	  {
		 if(jumps[idx + j] + 1 < tmp_min)
		     tmp_min = jumps[idx + j] + 1;
	  }
	  jumps[idx] = tmp_min;
     }
     return jumps[0];
}
int main()
{
      int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
      int ans = min_jump(arr,len);
      printf("%dn",ans);
      return 0;
}

Which of the following “for” loops can be used instead of the inner for loop so that the output doesn’t change?
a) for(j = 1; j < arr[idx] + len; j++)
b) for(j = 0; j < arr[idx] – len; j++)
c) for(j = idx + 1; j < len && j <= arr[idx] + idx; j++)
d) No change is required

Answer: d
Clarification: None of the above mentioned “for” loops can be used instead of the inner for loop. Note, for(j = idx + 1; j < len && j <= arr[idx] + idx; j++) covers the same range as the inner for loop but it produces the wrong output because the indexing inside the loops changes as “j” takes different values in the two “for” loops.

8. What is the time complexity of the following dynamic programming implementation used to find the minimum number of jumps?

#include
#include
int min_jump(int *arr, int len)
{
     int j, idx, jumps[len];
     jumps[len - 1] = 0;
     for(idx = len - 2; idx >= 0; idx--)
     {
	  int tmp_min = INT_MAX;
	  for(j = 1; j <= arr[idx] && idx + j < len; j++)
	  {
		 if(jumps[idx + j] + 1 < tmp_min)
		     tmp_min = jumps[idx + j] + 1;
	  }
	  jumps[idx] = tmp_min;
     }
     return jumps[0];
}
int main()
{
      int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
      int ans = min_jump(arr,len);
      printf("%dn",ans);
      return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) None of the mentioned

Answer: c
Clarification: The time complexity of the above dynamic programming implementation is O(n²).

9. What is the space complexity of the following dynamic programming implementation used to find the minimum number of jumps?

#include
#include
int min_jump(int *arr, int len)
{
     int j, idx, jumps[len];
     jumps[len - 1] = 0;
     for(idx = len - 2; idx >= 0; idx--)
     {
	  int tmp_min = INT_MAX;
	  for(j = 1; j <= arr[idx] && idx + j < len; j++)
	  {
		 if(jumps[idx + j] + 1 < tmp_min)
		     tmp_min = jumps[idx + j] + 1;
	  }
	  jumps[idx] = tmp_min;
     }
     return jumps[0];
}
int main()
{
      int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
      int ans = min_jump(arr,len);
      printf("%dn",ans);
      return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) O(5)

Answer: b
Clarification: The space complexity of the above dynamic programming implementation is O(n).

10. What is the output of the following program?

#include
#include
int min_jump(int *arr, int len)
{
      int j, idx, jumps[len];
      jumps[len - 1] = 0;
      for(idx = len - 2; idx >= 0; idx--)
      {	
	     int tmp_min = INT_MAX;
	     for(j = 1; j <= arr[idx] && idx + j < len; j++)
	     {
		   if(jumps[idx + j] + 1 < tmp_min)
		      tmp_min = jumps[idx + j] + 1;
	     }
	     jumps[idx] = tmp_min;
      }
      return jumps[0];
}
int main()
{
      int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
      int ans = min_jump(arr,len);
      printf("%dn",ans);
      return 0;
}

a) 7
b) 8
c) 9
d) 10

Answer: b
Clarification: The program prints the minimum jumps required to reach the end of the array, which is 8 and so the output is 8.

11. What is the output of the following program?

#include
#include
int min_jump(int *arr, int len)
{
      int j, idx, jumps[len];
      jumps[len - 1] = 0;
      for(idx = len - 2; idx >= 0; idx--)
      {	
	  int tmp_min = INT_MAX;
	  for(j = 1; j <= arr[idx] && idx + j < len; j++)
	  {
	        if(jumps[idx + j] + 1 < tmp_min)
		  tmp_min = jumps[idx + j] + 1;
	  }
	  jumps[idx] = tmp_min;
      }
      return jumps[0];
}
int main()
{
      int arr[] ={9, 9, 9, 9, 9, 9, 9, 9, 9},len = 9;
      int ans = min_jump(arr,len);
      printf("%dn",ans);
      return 0;
}

a) 1
b) 6
c) 2
d) 7

Answer: a
Clarification: The program prints the minimum jumps required to reach the end of the array, which is 1 and so the output is 1.

Data Structures & Algorithms Multiple Choice Questions on “Transposition”.

1. What is the meaning of cipher in computer terminology?
a) an algorithm that performs encryption
b) an algorithm that generates a secret code
c) an algorithm that performs encryption or decryption
d) a secret code

Answer: c
Clarification: Cipher can be defined to be an algorithm that performs encryption or decryption. In cryptography, a set of defined steps are followed to generate ciphers.

2. Which of the following cipher is created by shuffling the letters of a word?
a) substitution cipher
b) transposition cipher
c) mono alphabetic cipher
d) poly alphabetic cipher

Answer: b
Clarification: Types of traditional ciphers- Transposition and substitution cipher. In transposition cipher the letters of the given message are shuffled in a particular order, fixed by a given rule.

3. Which of the following is not a type of transposition cipher?
a) Rail fence cipher
b) Columnar transposition cipher
c) One time pad cipher
d) Route cipher
View Answer

Answer: c
Clarification: Out of the given options only One time pad cipher is not a type of transposition cipher. It is a type of substitution cipher.

4. Which of the following is not a type of mono alphabetic cipher?
a) additive cipher
b) multiplicative cipher
c) afffine cipher
d) hill cipher
View Answer

Answer: d
Clarification: In mono alphabetic cipher each symbol of plain text is replaced by a particular respective symbol in the cipher text. There are three types of mono alphabetic ciphers- additive, multiplicative and affine.

5. Route cipher falls under the category of?
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher

Answer: c
Clarification: Route cipher is a transposition cipher. It falls under the category of transposition cipher as it encrypts the plain text by rearranging its letters.

6. Which of the following ciphered text would have used transposition cipher for encryption of the plain text “”?
a) SSCMBNUMERY
b) TBMGPVOESZ
c) UCNHQWPFTA
d) SNONRAFUDY

Answer: d
Clarification: We know that transposition cipher encrypts the plain text by shuffling the letters of the plain text. So out of the given options, only “SNONRAFUDY” has the same set of letters as “”.

7. Which of the following is a type of transposition cipher?
a) Rail Fence cipher
b) Hill cipher
c) Rotor cipher
d) One time pad

Answer: a
Clarification: In transposition cipher the letters of the given message are shuffled in a particular order, fixed by a given rule. Two types of transposition cipher are – Rail fence cipher and Columnar transposition cipher.

8. In which of the following cipher the plain text and the ciphered text have same set of letters?
a) one time pad cipher
b) columnar transposition cipher
c) playfair cipher
d) additive cipher

Answer: b
Clarification: In transposition cipher, the letters remain same in ciphered and plain text. Their position is only changed whereas in substitution cipher the letters become different in encrypted text. So columnar transposition cipher will be the correct option.

9. Combining transposition cipher with substitution cipher improves its strength?
a) true
b) false

Answer: a
Clarification: Combining transposition cipher with substitution cipher helps in overcoming its weaknesses. But it causes the cipher to become more laborious to decode and it becomes more prone to errors.

10. What will be the encrypted text corresponding to plain text “” using rail fence cipher with key value given to be 2?
a) SNONRAFUDY
b) SORAFUDYNN
c) SNAUDNORFY
d)

Answer: a
Clarification: For encrypting a plain text using rail fence cipher we use a table having a number of rows equal to key value as shown below. Then we read along the rows to get the ciphered text. So the ciphered text will be “SNONRAFUDY”.

11. What will be the encrypted text corresponding to plain text “” using columnar transposition cipher with the keyword as “GAMES”?
a) SNONRAFUDY
b) SORAFUDYNN
c) SNAUDNORFY
d) ANFRSUNDOY

Answer: d
Clarification: For encrypting using columnar cipher we have to arrange the letters of the plain text in a table which has the same number of columns as the letters of the keyword. Then the letters of the keyword are arranged in alphabetical order and we read along each column.
3 1 4 2 5
G A M E S
S A N F O
U N D R Y
So the ciphered text will be “ANFRSUNDOY”.

contest

Data Structures & Algorithms Multiple Choice Questions on “Morse Code – 2”.

1. Which letter of the English alphabet has the shortest code in Morse Code?
a) A
b) C
c) B
d) E
Answer: d
Clarification: Morse code was designed so that the length of each symbol is inverse to the frequency of occurrence in text. Thus the letter in English, “E”, has a single dot.

2. Which word tells a word rate of Morse code’s shorter code durations for common characters such as “e” and “t”.?
a) PARIS
b) CODEX
c) PARCOD
d) SPACE

Answer: a
Clarification: PARIS tells about word rate that is typical of natural language words and reflects the benefits of Morse code’s shorter code durations for common characters such as “e” and “t”.

3. Is Morse code speed measured in words per minute (wpm).
a) True
b) False
Answer: a
Clarification: Morse code speed is measured in words per minute (wpm). The transmission rate of the Morse code is also measured is groups per unit (gpm).

4. Is Morse code speed measured in characters per minute (cpm)?
a) True
b) False

Answer: a
Clarification: Morse code speed is measured in characters per minute (cpm) as well as in words per minute (wpm). The transmission rate of the Morse code is also measured is groups per unit (gpm).

5. Who is the creator of Modern International Morse Code?
a) Samuel F. B. Morse
b) Karl Morse
c) Alexander Morse
d) Friedrich Clemens Gerke
Answer: d
Clarification: It was created by Friedrich Clemens Gerke in 1848 and initially used for telegraphy in Germany. Samuel Morse is the inventor of the telegraph after whom Morse code was named.

6. What is meant by the single dot in Morse code?
a) A
b) C
c) B
d) E
Answer: d
Clarification: The most common letter in English, the letter “E”, has a single dot. Morse code was designed so that the length of each symbol is inverse to frequency of occurrence in text.

7. Which word offers a word rate that is typical of 5-letter code groups?
a) PARIS
b) CODEX
c) PARCOD
d) SPACE
Answer: b
Clarification: CODEX word offers a word rate that is typical of 5-letter code groups. PARIS is a standard word to measure the operator transmission speed of Morse Code.

8. What is the name of special procedural signals that are used to indicate changes in communications protocol status?
a) Prosigns
b) Aldis
c) BIT
d) Asterisk

Answer: b
Clarification: Prosigns are special unwritten procedural signals which are used to show changes in communications protocol status or white space text.

9. Space signal is of how many unit?
a) 1
b) 2
c) 3
d) 4
Answer: a
Clarification: Since the duration of Space Signal is equal to Dot Duration. So, the space signal is of 1 Unit. While a dash is 3 units and space between letters is also three units.

10. The letters of a word are separated by a space of how many units?
a) 1 Unit
b) 2 Units
c) 3 Units
d) 4 Units
View Answer

Answer: c
Clarification: The letters of a word are separated by a space of 3 Unit. The representation of dot symbol has 1 unit, while the dash symbol has 2 units.

11. Which symbol is not defined inside the ITU recommendation on Morse code?
a) $
b) .
c) +
d) ~
Answer: a
Clarification: The symbol $ and & are not defined inside the ITU recommendation on Morse code. International Telecommunication Union is a union that mandated Morse code worldwide.

12. For which symbol there is no standard representation in Morse Code?
a) /
b) .
c) *
d) !

Answer: d
Clarification: There is no standard representation for the exclamation mark (!) in Morse code. The other symbols have been defined by the International Telecommunication Union.

13. In which year the symbol @ was added to the official Morse character set by ITU-R?
a) 2003
b) 2004
c) 2005
d) 2006

Answer: b
Clarification: On May 24, 2004, the symbol @ was added to the official Morse character set by International Telecommunication Union.

14. Which device was used to generate high speed Morse Code?
a) Iambic Paddle
b) Note Paddle
c) Vibrolex
d) KSM Radio

Answer: a
Clarification: Iambic Paddle was used to generate high speed Morse Code in conjunction with an electronic keyer. It was commercially manufactured.

15. Who along with Samuel Morse developed Morse code?
a) Alfred Vail
b) Alan Turing
c) Jedidiah Morse
d) Lucretia Pickering Walker

Answer: a
Clarification: Alfred Vail along with Samuel Morse developed Morse code. While Jedidiah Morse, Lucretia Pickering Walker were his father and spouse respectively.

& Algorithms.

and Answers.

contest

Data Structure Multiple Choice Questions on “Bubble Sort”.

1. What is an external sorting algorithm?
a) Algorithm that uses tape or disk during the sort
b) Algorithm that uses main memory during the sort
c) Algorithm that involves swapping
d) Algorithm that are considered ‘in place’

Answer: a
Clarification: As the name suggests, external sorting algorithm uses external memory like tape or disk.

2. What is an internal sorting algorithm?
a) Algorithm that uses tape or disk during the sort
b) Algorithm that uses main memory during the sort
c) Algorithm that involves swapping
d) Algorithm that are considered ‘in place’

Answer: b
Clarification: As the name suggests, internal sorting algorithm uses internal main memory.

3. What is the worst case complexity of bubble sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)

Answer: d
Clarification: Bubble sort works by starting from the first element and swapping the elements if required in each iteration.

4. Select the appropriate code that performs bubble sort.
a)

for(int j=arr.length-1; j>=0; j--)
{
	for(int k=0; k<j; k++)
	{
		if(arr[k] > arr[k+1])
		{
			int temp = arr[k];
			arr[k] = arr[k+1];
			arr[k+1] = temp;
		}
	}
}

b)

for(int j=arr.length-1; j>=0; j--)
{
	for(int k=0; k<j; k++)
	{
		if(arr[k] < arr[k+1])
		{
			int temp = arr[k];
			arr[k] = arr[k+1];
			arr[k+1] = temp;
		}
	}
}

c)

for(int j=arr.length; j>=0; j--)
{
	for(int k=0; k<j; k++)
	{
		if(arr[k] > arr[k+1])
		{
			int temp = arr[k];
			arr[k] = arr[k+1];
			arr[k+1] = temp;
		}
	}
}

d)

for(int j=arr.length; j>=0; j--)
{
	for(int k=0; k<j; k++)
	{
		if(arr[k] > arr[k+2])
		{
			int temp = arr[k];
			arr[k] = arr[k+1];
			arr[k+1] = temp;
		}
	}
}

View Answer

Answer: a
Clarification: The outer loop keeps count of number of iterations, and the inner loop checks to see if swapping is necessary.

5. What is the average case complexity of bubble sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)

Answer: d
Clarification: Bubble sort works by starting from the first element and swapping the elements if required in each iteration even in the average case.

6. Which of the following is not an advantage of optimised bubble sort over other sorting techniques in case of sorted elements?
a) It is faster
b) Consumes less memory
c) Detects whether the input is already sorted
d) Consumes less time

Answer: c
Clarification: Optimised Bubble sort is one of the simplest sorting techniques and perhaps the only advantage it has over other techniques is that it can detect whether the input is already sorted. It is faster than other in case of sorted array and consumes less time to describe whether the input array is sorted or not. It consumes same memory than other sorting techniques. Hence it is not an advantage.

7. The given array is arr = {1, 2, 4, 3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array?
a) 4
b) 2
c) 1
d) 0

Answer: a
Clarification: Even though the first two elements are already sorted, bubble sort needs 4 iterations to sort the given array.

8. How can you improve the best case efficiency in bubble sort? (The input is already sorted)
a)

        boolean swapped = false;
	for(int j=arr.length-1; j>=0 && swapped; j--)
	{
		swapped = true;
		for(int k=0; k<j; k++)
		{
			if(arr[k] > arr[k+1])
			{
				int temp = arr[k];
				arr[k] = arr[k+1];
				arr[k+1] = temp;
				swapped = false;
			}
		}
	}

b)

        boolean swapped = true;
	for(int j=arr.length-1; j>=0 && swapped; j--)
	{
		swapped = false;
		for(int k=0; k<j; k++)
		{
			if(arr[k] > arr[k+1])
			{
				int temp = arr[k];
				arr[k] = arr[k+1];
				arr[k+1] = temp;
			}
		}
	}

c)

        boolean swapped = true;
	for(int j=arr.length-1; j>=0 && swapped; j--)
	{
		swapped = false;
		for(int k=0; k<j; k++)
		{
			if(arr[k] > arr[k+1])
			{
				int temp = arr[k];
				arr[k] = arr[k+1];
				arr[k+1] = temp;
				swapped = true;
			}
		}
	}

d)

        boolean swapped = true;
	for(int j=arr.length-1; j>=0 && swapped; j--)
	{
		for(int k=0; k<j; k++)
		{
			if(arr[k] > arr[k+1])
			{
				int temp = arr[k];
				arr[k] = arr[k+1];
				arr[k+1] = temp;
				swapped = true;
			}
		}
	}

View Answer

Answer: c
Clarification: A boolean variable ‘swapped’ determines whether any swapping has happened in a particular iteration, if no swapping has occurred, then the given array is sorted and no more iterations are required.

9. What is the best case efficiency of bubble sort in the improvised version?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)

Answer: c
Clarification: Some iterations can be skipped if the list is sorted, hence efficiency improves to O(n).

10. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array with improvised version?
a) 4
b) 2
c) 1
d) 0

Answer: b
Clarification: Only 2 elements in the given array are not sorted, hence only 2 iterations are required to sort them.

contest

Data Structures & Algorithms Multiple Choice Questions on “Binary Tree Sort”.

1. Consider the original array 17 8 12 4 26. How many comparisons are needed to construct the BST on the original array?
a) 5
b) 4
c) 7
d) 10

Answer: d
Clarification: Original array is 17 8 12 4 26. The BST built on this array is shown in the figure below.

To built the BST, we travel down the tree until a leaf is reached. Therefore, for every element we compare the element with the internal nodes until we the leaves and then once again compare the element with its parent to decide whether it is right child or left child. So, for given array we need to perform 10 comparisons to build the BST.

2. In binary tree sort, we first construct the BST and then we perform _______ traversal to get the sorted order.
a) inorder
b) postorder
c) preorder
d) level order

Answer: a
Clarification: In binary tree sort is a sort algorithm where a binary search tree is built from the elements to be sorted, and then we perform inorder traversal on the BST to get the elements in sorted order.

3. What is the worst case time complexity of the binary tree sort?
a) O(n)
b) O(nlogn)
c) O(n²)
d) O(logn)
Answer: c
Clarification: For the binary tree sort the worst case when the BST constructed is unbalanced. BST gets unbalanced when the elements are already sorted. So, in the worst case, O(n²) time is required to built the BST and O(n) time to traverse the tree. Therefore, the worst case time complexity is O(n²) + O(n) = O(n²).

4. The insert() procedure, given below, builds the BST on the input elements, which is the first step of the binary tree sort. Choose the correct to fill the condition.

void insert(Tree* node, int newElement)
{
	if(node== NULL)
	{
		node = createNewNode();
		node-> value = newElement;
		node -> left = NULL;
		node -> right = NULL;
		return;
	}
	else if(__________________)
	{
		insert(node->left, newElement);
	}
	else
	{
		insert(node->right, newElement);
	}
}

a) newElement > node->value
b) newElement < node->value
c) newElement == root->value
d) newElement != root->value

Answer: b
Clarification: In binary tree sort, the BST is built on the input elements and the tree is traversed in in-order to get the sorted order. While building the BST, we travel down the tree until a leaf is reached. While traveling dawn the tree, we travel on left subtree if the new element is less than the node or to the right if the element is greater or equal to the node. So, correct option is newElement value.

5. What is the best case time complexity of the binary tree sort?
a) O(n)
b) O(nlogn)
c) O(n²)
d) O(logn)

Answer: b
Clarification: The best case occurs when the BST is balanced. So, when tree is balanced we require O(nlogn) time to build the tree and O(n) time to traverse the tree. So, the best case time complexity of the binary tree sort is O(nlogn).

6. Binary tree sort is an in-place sorting algorithm.
a) True
b) False

Answer: b
Clarification: In binary tree sort it is required to reserve one tree node for each array element. Its implementation requires two pointer variables for each node. So, it requires extra memory. The worst case space complexity of binary tree sort is Θ(n). Therefore, binary tree sort is not an in-place sorting algorithm.

7. Which of the following is false?
a) Binary tree sort and quick sort have same running time
b) Binary tree sort used BST as work area
c) As the number of elements to sort gets larger, binary tree sort gets more and more efficient
d) Both quick sort and binary tree are in place sorting algorithms
Answer: d
Clarification: Binary tree sort and quick sort have same running time i.e O(nlogn)
in average case and O(n²) in worst case. Binary tree is not in-place sorting algorithm.

8. Which of the following sorting algorithms can be considered as improvement to the binary tree sort?
a) Heap sort
b) Quick sort
c) Selection sort
d) Insertion sort

Answer: a
Clarification: Heap sort is basically improvement to the binary tree sort. Heap sort builds a heap on the input element by adjusting the position of the elements within the original array, rather than creating nodes as in binary tree sort.

9. Consider the following statements related to the binary tree sort.
I. Element can be added gradually as they become available
II. It needs extra memory space
a) Statement I is true but Statement II is false
b) Both Statement I and Statement II are false
c) Both Statement I and Statement II are true
d) Statement II is true but Statement I is false

Answer: c
Clarification: Binary tree sort is dynamic sorting, that is it gets more efficient as more the elements are added. So, we can add elements gradually as they become available. Binary tree sort requires extra memory space, its worst case space complexity is Θ(n).