Category: Data Structures & Algorithms Objective Questions

Data Structure Multiple Choice Questions on “Longest Increasing Subsequence”.

1. The longest increasing subsequence problem is a problem to find the length of a subsequence from a sequence of array elements such that the subsequence is sorted in increasing order and it’s length is maximum. This problem can be solved using __________
a) Recursion
b) Dynamic programming
c) Brute force
d) Recursion, Dynamic programming, Brute force

Answer: d
Clarification: The longest increasing subsequence problem can be solved using all of the mentioned methods.

2. Find the longest increasing subsequence for the given sequence:
{10, -10, 12, 9, 10, 15, 13, 14}
a) {10, 12, 15}
b) {10, 12, 13, 14}
c) {-10, 12, 13, 14}
d) {-10, 9, 10, 13, 14}

Answer: d
Clarification: The longest increasing subsequence is {-10, 9, 10, 13, 14}.

3. Find the length of the longest increasing subsequence for the given sequence:
{-10, 24, -9, 35, -21, 55, -41, 76, 84}
a) 5
b) 4
c) 3
d) 6
View Answer

Answer: d
Clarification: The longest increasing subsequence is {-10, 24, 35, 55, 76, 84} and it’s length is 6.

4. For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.
a) True
b) False

Answer: b
Clarification: For a given sequence, it is possible that there is more than one subsequence with the longest length.
Consider, the following sequence: {10,11,12,1,2,3}:
There are two longest increasing subsequences: {1,2,3} and {10,11,12}.

5. The number of increasing subsequences with the longest length for the given sequence are:
{10, 9, 8, 7, 6, 5}
a) 3
b) 4
c) 5
d) 6

Answer: d
Clarification: Each array element individually forms a longest increasing subsequence and so, the length of the longest increasing subsequence is 1. So, the number of increasing subsequences with the longest length is 6.

6. In the brute force implementation to find the longest increasing subsequence, all the subsequences of a given sequence are found. All the increasing subsequences are then selected and the length of the longest subsequence is found. What is the time complexity of this brute force implementation?
a) O(n)
b) O(n²)
c) O(n!)
d) O(2ⁿ)

Answer: d
Clarification: The time required to find all the subsequences of a given sequence is 2ⁿ, where ‘n’ is the number of elements in the sequence. So, the time complexity is O(2ⁿ).

7. Complete the following dynamic programming implementation of the longest increasing subsequence problem:

#include
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      { 
           tmp_max = 0;
	   for(j = 0; j < i; j++)
	   {
	        if(arr[j] < arr[i])
	        {
		    if(LIS[j] > tmp_max)
		     ___________;  
	        }
           }
	   LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	if(LIS[i] > max)
	   max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

a) tmp_max = LIS[j]
b) LIS[i] = LIS[j]
c) LIS[j] = tmp_max
d) tmp_max = LIS[i]

Answer: a
Clarification: tmp_max is used to store the maximum length of an increasing subsequence for any ‘j’ such that: arr[j] < arr[i] and 0 < j < i.
So, tmp_max = LIS[j] completes the code.

8. What is the time complexity of the following dynamic programming implementation used to find the length of the longest increasing subsequence?

#include
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      { 
           tmp_max = 0;
	   for(j = 0; j < i; j++)
	   {
	        if(arr[j] < arr[i])
	        {
		    if(LIS[j] > tmp_max)
		     tmp_max = LIS[j];  
	        }
           }
	   LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	if(LIS[i] > max)
	   max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

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

Answer: c
Clarification: The time complexity of the above dynamic programming implementation used to find the length of the longest increasing subsequence is O(n²).

9. What is the space complexity of the following dynamic programming implementation used to find the length of the longest increasing subsequence?

#include
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      { 
           tmp_max = 0;
	   for(j = 0; j < i; j++)
	   {
	        if(arr[j] < arr[i])
	        {
		    if(LIS[j] > tmp_max)
		     tmp_max = LIS[j];  
	        }
           }
	   LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	if(LIS[i] > max)
	   max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

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

Answer: b
Clarification: The above dynamic programming implementation uses space equal to the length of the sequence. So, the space complexity of the above dynamic programming implementation used to find the length of the longest increasing subsequence is O(n).

10. What is the output of the following program?

#include
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      {
	    tmp_max = 0;
	    for(j = 0; j < i; j++)
	    {
	        if(arr[j] < arr[i])
	        {
		     if(LIS[j] > tmp_max)
		       tmp_max = LIS[j];
	        }
            }
	    LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	  if(LIS[i] > max)
	      max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

a) 3
b) 4
c) 5
d) 6
Answer: d
Clarification: The program prints the length of the longest increasing subsequence, which is 6.

11. What is the value stored in LIS[5] after the following program is executed?

#include
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      {
	   tmp_max = 0;
	   for(j = 0; j < i; j++)
	   {
	        if(arr[j] < arr[i])
	        {
		     if(LIS[j] > tmp_max)
		     tmp_max = LIS[j];
	        }
	   }
	   LIS[i] = tmp_max + 1;
       }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	 if(LIS[i] > max)
	     max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

a) 2
b) 3
c) 4
d) 5

Answer: c
Clarification: The value stored in LIS[5] after the program is executed is 4.

contest

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Monoalphabetic Cipher”.

1. What is the meaning of cipher in cryptography?
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 is an algorithm for performing encryption or decryption. In cryptography, a set of defined steps are followed to generate ciphers.

2. Which of the following is a type of traditional cipher?
a) transportation cipher
b) transposition cipher
c) transforming cipher
d) vigenere cipher

Answer: b
Clarification: There are two types of a traditional cipher. First is transposition cipher and the second is substitution cipher.

3. Which of the following ciphers are created by shuffling the letters of a word?
a) substitution cipher
b) transposition cipher
c) vigenere cipher
d) hill cipher

Answer: b
Clarification: There are two types of traditional ciphers – Transposition and substitution cipher. In transposition cipher the letters of the given data are shuffled in a particular order, fixed by a given rule.

4. Which of the following is a type of substitution cipher?
a) Mono alphabetic cipher
b) transposition cipher
c) transportation cipher
d) transforming cipher
Answer: a
Clarification: In substitution cipher the plain text is replaced by cipher text according to a fixed rule. There are two types of substitution cipher – Mono alphabetic and Poly alphabetic cipher.

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

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.

6. Which of the following is not a type of poly alphabetic cipher?
a) Auto key cipher
b) Hill cipher
c) Playfair cipher
d) Additive cipher

Answer:d
Clarification: In poly alphabetic cipher each symbol of plain text is replaced by a different cipher text regardless of its occurrence. Out of the given options, only additive cipher is not a poly alphabetic cipher.

7. What will be the ciphered text for the input string “” with key string as “code” to the program of keyword cipher?
a) SCMBNUMERY
b) SSCMBNUMERY
c) NIFO
d) NILO
Answer: a
Clarification: Keyword cipher is type of mono alphabetic cipher. In this algorithm the letters {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z} by
{C,O,D,E,A,B,F,G,H,I,J,K,L,M,N,P,Q,R,S,T,U,V,W,X,Y,Z} respectively.

8. 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 data are shuffled in a particular order, fixed by a given rule. There are two types of transposition cipher – Rail fence cipher and Columnar transposition cipher.

9. What will be output for the given code?

#include 
using namespace std; 
string encrypter(string keyword) 
{ 
	string encoded = ""; 	
	bool arr[26] = {0}; 
	for (int i=0; i<keyword.size(); i++) 
	{ 
		if(keyword[i] >= 'A' && keyword[i] <= 'Z') 
		{ 		
			if (arr[keyword[i]-65] == 0) 
			{ 
				encoded += keyword[i]; 
				arr[keyword[i]-65] = 1; 
			} 
		} 
		else if (keyword[i] >= 'a' && keyword[i] <= 'z') 
		{ 
			if (arr[keyword[i]-97] == 0) 
			{ 
				encoded += keyword[i] - 32; 
				alpha[keyword[i]-97] = 1; 
			} 
		} 
	} 
	for (int i=0; i<26; i++) 
	{ 
		if(arr[i] == 0) 
		{ 
			arr[i]=1; 
			encoded += char(i + 65); 
		} 
	} 
	return encoded; 
} 
string ciphertxt(string msg, string encoded) 
{ 
	string cipher=""; 
	for (int i=0; i<msg.size(); i++) 
	{ 
		if (msg[i] >='a' && msg[i] <='z') 
		{ 
			int pos = msg[i] - 97; 
			cipher += encoded[pos]; 
		} 
		else if (msg[i] >='A' && msg[i] <='Z') 
		{ 
			int pos = msg[i] - 65; 
			cipher += encoded[pos]; 
		} 
		else
		{ 
			cipher += msg[i]; 
		} 
	} 
	return cipher; 
} 
int main() 
{ 
	string keyword; 
	keyword = "cipher"; 	
	string encoded = encrypter(keyword); 
	string message = "hello"; 
	cout  << ciphertxt(message,encoded) << endl; 
	return 0; 
}

a) bejjm
b) LFPDAR
c) BEJJM
d) lfpdar

Answer: c
Clarification: The given code is the implementation of keyword cipher. It is an example of mono alphabetic cipher. The given string is always converted into an uppercase ciphered text.

10. What will be output for the given code taking input string as “”?

package com..setandstring;
import java.util.Scanner;
public class MonoalphabeticCipher
{
      public static char p[]  = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
                                  'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
                                  'u', 'v', 'w', 'x', 'y', 'z' };
      public static char ch[] = { 'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P',
                                  'A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L', 'Z',
                                  'X', 'C', 'V', 'B', 'N', 'M' };
      public static String doEncryption(String s)
      { 
           char c[] = new char[(s.length())];
           for (int i = 0; i < s.length(); i++)
           {
                for (int j = 0; j < 26; j++)
                { 
                     if (p[j] == s.charAt(i))
                     {
                         c[i] = ch[j];
                          break;
                     }
                }
            }  return (new String(c));
        }   
        public static void main(String args[])
        {
             Scanner sc = new Scanner(System.in);
             System.out.println("Enter the message: ");
             String en = doEncryption(sc.next().toLowerCase());
             System.out.println("Encrypted message: " + en);
             sc.close();
         }
}

a) Encrypted message: LQFYGXFRKN
b) Encrypted message: NKRFXGYFQL
c) Encrypted message: lqfygxfrkn
d) Encrypted message: nkrfxgyfql

Answer: a
Clarification: The given code is an example of mono-alphabetic cipher. The code replaces the letters of the input string by corresponding keyboard letters.

11. In which of the following cipher the plain text and the ciphered text does not have same number of letters?
a) keyword cipher
b) vigenere cipher
c) transposition cipher
d) additive cipher
View Answer

Answer: b
Clarification: In transposition cipher and mono alphabetic cipher the number of letters in the plain text and ciphered text remain same. But in poly alphabetic cipher the number of letters change. So here as vigenere cipher is the only poly alphabetic cipher so it will be the answer.

and Answers.

Data Structures & Algorithms Multiple Choice Questions on “Bifid Cipher”.

1. What is the period in bifid cipher?
a) length of blocks in which the plain text is divided before encryption
b) number of letters after which the key is repeated
c) number of blocks into which the plain text is divided before encryption
d) number of keys used for encryption
Answer: a
Clarification: Polybius square is similar to substitution cipher. It is also known by the name of Polybius checkboard.

2. Which of the following cipher uses polybius square?
a) bifid cipher
b) beaufort cipher
c) trithemius cipher
d) gronsfeld cipher

Answer: a
Clarification: Bifid cipher uses polybius square for encrypting the plain text. Bifid cipher combines polybius square cipher with transposition.

3. Bifid cipher combines transposition with which of the following cipher?
a) Polybius square cipher
b) Playfair cipher
c) gronsfeld cipher
d) trifid cipher

Answer: a
Clarification: Bifid cipher combines polybius square cipher with transposition. It uses fractionation to obtain diffusion.

4. What will be the key square in bifid cipher for the key “”?
a)

b)

c)

d)

Answer: a
Clarification: For forming the key square from the given key we first add the letters of the key in the square by omitting the repeated letters and then we add the remaining letters of the English alphabet. Usually, I and J are combined together.

5. Trifid cipher encrypts the plain text by using bifid cipher twice.
a) true
b) false

Answer: b
Clarification: Trifid cipher is a variation of bifid cipher. The only difference between them is that trifid cipher uses a 3×3 key square instead of 5×5 square.

6. Bifid square combines autokey square with transposition.
a) true
b) false

Answer: b
Clarification: Bifid square combines polybius square with transposition. So the given statement is false.

7. What will be the ciphered text corresponding to “” if bifid cipher is used for encryption with key as “KEY” with period as 5?
a) SBPISZTKZH
b) PLNSOWGKQM
c) SELFQEXBHM
d) YFSGWNFBW

Answer: b
Clarification: For encrypting the plain text using bifid cipher we first form the polybius square with the help of given key. After this, the plain text is divided into blocks of length 5 and corresponding coordinates are noted. So the corresponding cipher text would be “PLNSOWGKQM”.

8. What will be the ciphered text corresponding to “ALGORITHM” if bifid cipher is used for encryption with key as “KEY” with a period as 5?
a) SBPISZTKZH
b) PLNSOWGKQM
c) SELFQEXBHM
d) YFSGWNFBW

Answer: d
Clarification: For encrypting the plain text using bifid cipher we first form the polybius square with the help of given key. After this, the plain text is divided into blocks of length 5 and corresponding coordinates are noted. So the corresponding cipher text would be “YFSGWNFBW”.

9. What will be the plain text corresponding to cipher text “XKS” if the bifid cipher is used with key as “KEY” and period as 5?
a) IND
b) USA
c) RSA
d) AUS

Answer: b
Clarification: The decryption in bifid cipher begins identically to encryption. Then we find the corresponding coordinates and then we get the plain text. So the plain text is “USA”.

10. What will be the plain text corresponding to ciphered text “BKC” if the bifid cipher is used for encryption with key as “KEY” and period 5?
a) MSD
b) SRT
c) KVK
d) VVS
View Answer

Answer: c
Clarification: The decryption in bifid cipher begins identically to encryption. Then we find the corresponding coordinates and then we get the plain text. So the plain text is “KVK”.

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

1. Which of the following is Python’s standard sorting algorithm?
a) quick sort
b) introsort
c) merge sort
d) tim sort

Answer: d
Clarification: Tim sort has been python’s standard sorting algorithm since its version 2.3. It is an example of hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine.

2. Which of the following sorting algorithm is a constituent of tim sort?
a) selection sort
b) quick sort
c) merge sort
d) heap sort
Answer: c
Clarification: Tim sort is a hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine. It is derived from insertion sort and merge sort.

3. Tim sort begins sorting the given array by using which of the following sorting algorithm?
a) selection sort
b) quick sort
c) insertion sort
d) merge sort

Answer: c
Clarification: Tim sort begins sorting any given array by using insertion sort for each run. The array is divided into smaller parts for this purpose, each part having a size equal to value of run. Then these small parts called runs are merged in order to obtain sorted array.

4. Which of the following sorting algorithm is stable?
a) Tim sort
b) Introsort
c) Quick sort
d) Heap sort

Answer: a
Clarification: Out of the given options Tim sort is the only algorithm which is stable. As both constituents of Tim sort (I.e insertion sort and merge sort) are stable so Tim sort also becomes stable.

5. Which of the following sorting algorithm is not in-place?
a) insertion sort
b) tim sort
c) quick sort
d) intro sort

Answer: b
Clarification: Tim sort is not an in-place sorting algorithm as it requires auxiliary space. It is because it requires to merge sorted runs which requires a third array of the size equal to the sum of the two runs.

6. Tim sort is a comparison based sort.
a) true
b) false

Answer: a
Clarification: Merge sort and insertion sort are comparison based sorts. Thus overall Tim sort also becomes a comparison based sort.

7. What is the best case time complexity of Tim sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: a
Clarification: Best case time complexity of Tim sort occurs when the input array is already sorted. In such a case only one run will be required.

8. What is the worst case time complexity of Tim sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: b
Clarification: Worst case time complexity of Tim sort is O(n log n). It is because the worst complexity of merge sort is O(n log n) and insertion sort is only applied for small arrays.

9. What is the average time complexity of Tim sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: b
Clarification: Average time complexity of Tim sort remains to be O(n log n). It is the same as the average case complexity of merge sort.

10. What is the auxiliary space requirement of Tim sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)
View Answer

Answer: a
Clarification: Tim sort is a hybrid of merge sort and insertion sort. It requires to merge sorted runs which require a third array of the size equal to the sum of the two runs. So in worst case the auxiliary space requirement will be O(n).

11. Which of the following algorithm is implemented internally in java when we use function arrays.sort()?
a) intro sort
b) quick sort
c) tim sort
d) merge sort

Answer: c
Clarification: Java makes use of Tim sort internally for implementing arrays.sort(). It is mainly due to the fastness of this algorithm in comparison to other comparison based sorts.

12. Why is insertion sort preferred over other sorting algorithms (like selection sort, bubble sort etc.) for Tim sort implementation?
a) Because insertion sort is faster and adaptive
b) Because insertion sort requires less space
c) Because insertion sort is easy to implement
d) Because insertion sort is easy to understand

Answer: a
Clarification: When small arrays need to be sorted then insertion sort proves to be the best choice. Also, it is adaptive so it performs better than others when the given array is fully/partially sorted.

13. In which case will tim sort will work as an insertion sort?
a) when no. of elements are less than 64
b) when no. of elements are greater than 64
c) when no. of elements are less than size of run
d) when no. of elements are less than 32
Answer: c
Clarification: Tim sort uses a hybrid of insertion and merge sort. It reduces to insertion sort when the size of array is less than the size of run as insertion sort is efficient in sorting small arrays.

14. What is the usual size of a run in tim sort?
a) 32
b) less than 32
c) 32-64 depending on size of the array
d) 64

Answer: c
Clarification: Usually the size of the run is chosen somewhere between 32 and 64. The size of run is preferably chosen in powers of 2 in order to maintain balance while merging the sorted runs.

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

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

a) [4,5,7,8,9,10]
b) [10,9,8,7,5,4]
c) 4,5,7,8,9,10
d) error

Answer: a
Clarification: The given program sorts the input in ascending order by using the function Arrays.sort(). It uses Tim sort internally.

16. 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)); 
	} 
}

a) [4,5,7,8,9,10]
b) [10,9,8,7,5,4]
c) [10,5,7,8,9,4]
d) [10,7,9,5,8,4]

Answer: d
Clarification: The given program sorts only a portion of the input array. It is done by passing two extra arguments to the function Arrays.sort(). It sorts the elements between index 1 and 2.

& Algorithms.

and Answers.

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

1. Bead sort is also known as _________
a) gravity sort
b) strand sort
c) abacus sort
d) counting sort
Answer: a
Clarification: Bead sort is also known as gravity sort. It is because this algorithm was designed by keeping the natural phenomenon of falling objects in mind.

2. Which of the following sorting algorithm was inspired by the natural phenomenon of falling objects?
a) bogo sort
b) heap sort
c) bead sort
d) strand sort
Answer: c
Clarification: The algorithm of bead sort was inspired by the natural phenomenon of falling objects. Thus, it is also known by the name of gravity sort.

3. Which of the following sorting algorithm is only applicable to positive integers?
a) quick sort
b) heap sort
c) bead sort
d) strand sort
Answer: c
Clarification: Bead sort algorithm is only applicable to positive integers. This is because it works by placing number of beads equal to key value, in each row.

4. What is the auxiliary space complexity of bead sort?
a) O(n)
b) O(1)
c) O(n²)
d) O(n log n)
Answer: c
Clarification: The auxiliary space complexity of bead sort is O(n²). It is because an array of size maximum_element*n (maximum_element is the maximum element that is present in the array and n is the size of the array) has to be maintained.

5. Which of the following sorting algorithm is not in place?
a) quick sort
b) bead sort
c) cycle sort
d) heap sort

Answer: b
Clarification: Bead sort has an auxiliary space complexity of O(n2). So it is not an in place sorting algorithm.

6. Bead sort is a comparison based sorting algorithm.
a) true
b) false

Answer: b
Clarification: Bead sort is an example of non comparison based sorting algorithm. This is because it does not compare the value of elements present in a list in order to sort them.

7. How many comparisons will be required to sort the array arr={5, 4, 7, 1, 9} using bead sort?
a) 5
b) 4
c) 6
d) 0

Answer: d
Clarification: Bead sort is an example of a non-comparison based sorting algorithm. So no comparison is required to be performed in order to sort the array.

8. What is the average time complexity of bead sort (S = sum of input elements)?
a) O(n)
b) O(S)
c) O(n²)
d) O(n log n)

Answer: b
Clarification: Average case time complexity of bead sort is O(S). It is because we drop each bead as a separate operation.

9. What is the best case time complexity of bead sort (S = sum of input elements)?
a) O(n)
b) O(S)
c) O(n²)
d) O(n log n)

Answer: a
Clarification: Best case time complexity of bead sort is O(n). It is when a row of beads is dropped as a distinct operation and since the number of rows is equal to n.

10. What is the worst case time complexity of bead sort (S= sum of input elements)?
a) O(n)
b) O(S)
c) O(n²)
d) O(n log n)

Answer: b
Clarification: Worst case time complexity of bead sort is O(S). It is because we drop each bead as a separate operation.

11. Which of the following code fragment puts sorted values in an array using beads correctly?
a)

for (int i = 0; i < n; i++) 
{ 
         int j;
        for (j = 0; j < max; j++); 
        //max is the maximum value element of given array a[]  
        a[i] = j; 
i}

b)

for (int i = 0; i < n; i++) 
{ 
         int j;
        for (j = 0; j < max && beads[i * max + j]; j++); 
        //max is the maximum value element of given array a[]
        a[i] = j; 
}

c)

for (int i = 0; i < n; i++) 
{ 
         int j;
        for (j = 0; j < beads[i * max + j]; j++); 
       //max is the maximum value element of given array a[]  
        a[j] = i; 
}

d)

for (int i = 0; i < n; i++) 
{ 
         int j;
        for (j = 0; j < max && beads[i * max + j]; j++); 
       //max is the maximum value element of given array a[]  
        a[j] = i; 
}

Answer: b
Clarification: After sorting the elements in the bead array we finally need to shift them to the original array. So we need to apply the condition j < max && beads[i * max + j] in order to achieve this.

12. Bead sort is only applicable to positive integers.
a) true
b) false

Answer: a
Clarification: Bead sort algorithm is only applicable to positive integers. This is because it works by placing the number of beads equal to key value, in each row.

and Answers.