Category: Data Structures & Algorithms Objective Questions

Data Structure Multiple Choice Questions on “Kadane’s Algorithm”.

1. Kadane’s algorithm is used to find ____________
a) Longest increasing subsequence
b) Longest palindrome subsequence
c) Maximum sub-array sum
d) Longest decreasing subsequence

Answer: c
Clarification: Kadane’s algorithm is used to find the maximum sub-array sum for a given array.

2. Kadane’s algorithm uses which of the following techniques?
a) Divide and conquer
b) Dynamic programming
c) Recursion
d) Greedy algorithm

Answer: b
Clarification: Kadane’s algorithm uses dynamic programming.

3. For which of the following inputs would Kadane’s algorithm produce the INCORRECT output?
a) {0,1,2,3}
b) {-1,0,1}
c) {-1,-2,-3,0}
d) {-4,-3,-2,-1}

Answer: d
Clarification: Kadane’s algorithm works if the input array contains at least one non-negative element. Every element in the array {-4,-3,-2,-1} is negative. Hence Kadane’s algorithm won’t work.

4. For which of the following inputs would Kadane’s algorithm produce a WRONG output?
a) {1,0,-1}
b) {-1,-2,-3}
c) {1,2,3}
d) {0,0,0}

Answer: b
Clarification: Kadane’s algorithm doesn’t work for all negative numbers. So, the answer is {-1,-2,-3}.

5. Complete the following code for Kadane’s algorithm:

#include
int max_num(int a, int b)
{ 
      if(a > b)
         return a; 
      return b;
}
int kadane_algo(int *arr, int len)
{	
     int ans, sum, idx;
     ans =0;
     sum =0;
     for(idx =0; idx < len; idx++)
     {
         sum = max_num(0,sum + arr[idx]);
         ans = ___________;
     }
     return ans;
}
int main()
{
     int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3},len=7;
     int ans = kadane_algo(arr,len);
     printf("%d",ans);
     return 0;
}

a) max_num(sum, sum + arr[idx])
b) sum
c) sum + arr[idx]
d) max_num(sum,ans)
Answer: d
Clarification: The maximum of sum and ans, is stored in ans. So, the answer is max_num(sum, ans).

6. What is the time complexity of Kadane’s algorithm?
a) O(1)
b) O(n)
c) O(n²)
d) O(5)

Answer: b
Clarification: The time complexity of Kadane’s algorithm is O(n) because there is only one for loop which scans the entire array exactly once.

7. What is the space complexity of Kadane’s algorithm?
a) O(1)
b) O(n)
c) O(n²)
d) None of the mentioned

Answer: a
Clarification: Kadane’s algorithm uses a constant space. So, the space complexity is O(1).

8. What is the output of the following implementation of Kadane’s algorithm?

#include
int max_num(int a, int b)
{
       if(a > b)
	return a;
       return b;
}
int kadane_algo(int *arr, int len)	
{
       int ans, sum, idx;
       ans =0;
       sum =0;
       for(idx =0; idx < len; idx++)
       {
	     sum = max_num(0,sum + arr[idx]);
	     ans = max_num(sum,ans);
       }
       return ans;
}
int main()
{
      int arr[] = {2, 3, -3, -1, 2, 1, 5, -3}, len = 8;
      int ans = kadane_algo(arr,len);
      printf("%d",ans);
      return 0;
}

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

Answer: d
Clarification: Kadane’s algorithm produces the maximum sub-array sum, which is equal to 9.

9. What is the output of the following implementation of Kadane’s algorithm?

#include
int max_num(int a, int b)
{  
      if(a > b)
         return a;
      return b;
}
int kadane_algo(int *arr, int len)	
{
      int ans, sum, idx;
      ans =0;
      sum =0;
      for(idx =0; idx < len; idx++)
      {
	  sum = max_num(0,sum + arr[idx]);
	  ans = max_num(sum,ans);
      }
      return ans;
}
int main()
{
      int arr[] = {-2, -3, -3, -1, -2, -1, -5, -3},len = 8;
      int ans = kadane_algo(arr,len);
      printf("%d",ans);
      return 0;
}

a) 1
b) -1
c) -2
d) 0

Answer: d
Clarification: Kadane’s algorithm produces a wrong output when all the elements are negative. The output produced is 0.

10. Consider the following implementation of Kadane’s algorithm:

1. #include
2. int max_num(int a, int b)
3. {
4.     if(a > b)
5.	 return a;
6.     return b;
7. }
8. int kadane_algo(int *arr, int len)	
9. {
10.      int ans = 0, sum = 0, idx;
11.	 for(idx =0; idx < len; idx++)
12.	 {
13.		sum = max_num(0,sum + arr[idx]);
14.		ans = max_num(sum,ans);
15.	 }
16.	 return ans;
17. }
18. int main()
19. {
20. 	  int arr[] = {-2, -3, -3, -1, -2, -1, -5, -3},len = 8;
21.       int ans = kadane_algo(arr,len);
22.	  printf("%d",ans);
23.	  return 0;
24. }

What changes should be made to the Kadane’s algorithm so that it produces the right output even when all array elements are negative?

	Change 1 = Line 10: int sum = arr[0], ans = arr[0]
	Change 2 = Line 13: sum = max_num(arr[idx],sum+arr[idx])

a) Only Change 1 is sufficient
b) Only Change 2 is sufficient
c) Both Change 1 and Change 2 are necessary
d) No change is required

Answer: c
Clarification: Both change 1 and change 2 should be made to Kadane’s algorithm so that it produces the right output even when all the array elements are negative.

Data Structure Multiple Choice Questions on “Counting Boolean Parenthesizations”.

1. You are given a boolean expression which consists of operators &, | and ∧ (AND, OR and XOR) and symbols T or F (true or false). You have to find the number of ways in which the symbols can be parenthesized so that the expression evaluates to true. This is the boolean parenthesization problem. Which of the following methods can be used to solve the problem?
a) Dynamic programming
b) Recursion
c) Brute force
d) Dynamic programming, Recursion and Brute force

Answer: d
Clarification: Dynamic programming, Recursion and Brute force can be used to solve the Boolean parenthesization problem.

2. Consider the expression T & F | T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: The expression can be parenthesized as T & (F | T) and (T & F) | T so that the output is T.

3. Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: The expression can be parenthesized as (T & F) ∧ T or T & (F ∧ T), so that the output is T.

4. Consider the expression T | F ∧ T. In how many ways can the expression be parenthesized so that the output is F (false)?
a) 0
b) 1
c) 2
d) 3

Answer: b
Clarification: The expression can be parenthesized as (T | F) ∧ T, so that the output is F (false).

5. Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms?
a) n factorial
b) n square
c) n cube
d) nth catalan number

Answer: d
Clarification: The nth Catalan number gives the total number of ways of parenthesizing an expression with n + 1 terms.

6. What is the maximum number of ways in which a boolean expression with n + 1 terms can be parenthesized, such that the output is true?
a) nth catalan number
b) n factorial
c) n cube
d) n square

Answer: a
Clarification: The number of ways will be maximum when all the possible parenthesizations result in a true value. The number of possible parenthesizations is given by the nth catalan number.

7. Consider the following dynamic programming implementation of the boolean parenthesization problem:

int count_bool_parenthesization(char *sym, char *op)
{
      int str_len = strlen(sym);
      int True[str_len][str_len],False[str_len][str_len];
      int row,col,length,l;
      for(row = 0, col = 0; row < str_len; row++,col++)
      {
          if(sym[row] == 'T')
          {
              True[row][col] = 1;
              False[row][col] = 0;
          }
          else
          {
              True[row][col] = 0;
              False[row][col] = 1;
          }
      }
      for(length = 1; length < str_len; length++)
      {
          for(row = 0, col = length; col < str_len; col++, row++)
          {
              True[row][col] = 0;
              False[row][col] = 0;
              for(l = 0; l < length; l++)
              {
                  int pos = row + l;
                  int t_row_pos = True[row][pos] + False[row][pos];
                  int t_pos_col = True[pos+1][col] + False[pos+1][col];
                  if(op[pos] == '|')
                  {
                      _______________;
                  }
                  if(op[pos] == '&')
                  {
                      _______________;
                  }
                  if(op[pos] == '^')
                  {
                      _______________;
                  }
              }
          }
      }
      return True[0][str_len-1];
}

Which of the following lines should be added to complete the “if(op[pos] == ‘|’)” part of the code?
a) False[row][col] += True[row][pos] * False[pos+1][col];
True[row][col] += t_row_pos * t_pos_col + False[row][pos] * False[pos+1][col];
b) False[row][col] += False[row][pos] * True[pos+1][col];
True[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];
c) False[row][col] += True[row][pos] * True[pos+1][col];
True[row][col] += t_row_pos * t_pos_col + True[row][pos] * True[pos+1][col];
d) False[row][col] += False[row][pos] * False[pos+1][col];
True[row][col] += t_row_pos * t_pos_col – False[row][pos] * False[pos+1][col];

Answer: d
Clarification: The following lines should be added:
False[row][col] += False[row][pos] * False[pos+1][col];
True[row][col] += t_row_pos * t_pos_col + False[row][pos] * False[pos+1][col];

8. Which of the following lines should be added to complete the “if(op[k] == ‘&’)” part of the following code?

int count_bool_parenthesization(char *sym, char *op)
{
      int str_len = strlen(sym);
      int True[str_len][str_len],False[str_len][str_len];
      int row,col,length,l;
      for(row = 0, col = 0; row < str_len; row++,col++)
      {
          if(sym[row] == 'T')
          {
              True[row][col] = 1;
              False[row][col] = 0;
          }
          else
          {
              True[row][col] = 0;
              False[row][col] = 1;
          }
      }
      for(length = 1; length < str_len; length++)
      {
          for(row = 0, col = length; col < str_len; col++, row++)
          {
              True[row][col] = 0;
              False[row][col] = 0;
              for(l = 0; l < length; l++)
              {
                  int pos = row + l;
                  int t_row_pos = True[row][pos] + False[row][pos];
                  int t_pos_col = True[pos+1][col] + False[pos+1][col];
                  if(op[pos] == '|')
                  {
                      _______________;
                  }
                  if(op[pos] == '&')
                  {
                      _______________;
                  }
                  if(op[pos] == '^')
                  {
                      _______________;
                  }
              }
          }
      }
      return True[0][str_len-1];
}

a) True[row][col] += False[row][pos] * False[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];
b) True[row][col] += True[row][pos] * True[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];
c) True[row][col] += True[row][pos] * False[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];
d) True[row][col] += False[row][pos] * True[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];

Answer: b
Clarification: The following lines should be added:
True[row][col] += True[row][pos] * True[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];

9. What is the time complexity of the following dynamic programming implementation of the boolean parenthesization problem?

int count_bool_parenthesization(char *sym, char *op)
{
      int str_len = strlen(sym);
      int True[str_len][str_len],False[str_len][str_len];
      int row,col,length,l;
      for(row = 0, col = 0; row < str_len; row++,col++)
      {
          if(sym[row] == 'T')
          {
              True[row][col] = 1;
              False[row][col] = 0;
          }
          else
          {
              True[row][col] = 0;
              False[row][col] = 1;
          }
      }
      for(length = 1; length < str_len; length++)
      {
          for(row = 0, col = length; col < str_len; col++, row++)
          {
              True[row][col] = 0;
              False[row][col] = 0;
              for(l = 0; l < length; l++)
              {
                  int pos = row + l;
                  int t_row_pos = True[row][pos] + False[row][pos];
                  int t_pos_col = True[pos+1][col] + False[pos+1][col];
                  if(op[pos] == '|')
                  {
                      False[row][col] += False[row][pos] * False[pos+1][col];
                      True[row][col] += t_row_pos * t_pos_col - False[row][pos] * False[pos+1][col];;
                  }
                  if(op[pos] == '&')
                  {
                     True[row][col] += True[row][pos] * True[pos+1][col];
                     False[row][col] += t_row_pos * t_pos_col - True[row][pos] * True[pos+1][col];
                  }
                  if(op[pos] == '^')
                  {
                     True[row][col] += True[row][pos] * False[pos+1][col] 
                                      + False[row][pos] * True[pos + 1][col];
                     False[row][col] += True[row][pos] * True[pos+1][col] 
                                       + False[row][pos] * False[pos+1][col];
                  }
              }
          }
      }
      return True[0][str_len-1];
}

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

10. What is the space complexity of the following dynamic programming implementation of the boolean parenthesization problem?

int count_bool_parenthesization(char *sym, char *op)
{
      int str_len = strlen(sym);
      int True[str_len][str_len],False[str_len][str_len];
      int row,col,length,l;
      for(row = 0, col = 0; row < str_len; row++,col++)
      {
          if(sym[row] == 'T')
          {
              True[row][col] = 1;
              False[row][col] = 0;
          }
          else
          {
              True[row][col] = 0;
              False[row][col] = 1;
          }
      }
      for(length = 1; length < str_len; length++)
      {
          for(row = 0, col = length; col < str_len; col++, row++)
          {
              True[row][col] = 0;
              False[row][col] = 0;
              for(l = 0; l < length; l++)
              {
                  int pos = row + l;
                  int t_row_pos = True[row][pos] + False[row][pos];
                  int t_pos_col = True[pos+1][col] + False[pos+1][col];
                  if(op[pos] == '|')
                  {
                      False[row][col] += False[row][pos] * False[pos+1][col];
                      True[row][col] += t_row_pos * t_pos_col - False[row][pos] * False[pos+1][col];;
                  }
                  if(op[pos] == '&')
                  {
                     True[row][col] += True[row][pos] * True[pos+1][col];
                     False[row][col] += t_row_pos * t_pos_col - True[row][pos] * True[pos+1][col];
                  }
                  if(op[pos] == '^')
                  {
                     True[row][col] += True[row][pos] * False[pos+1][col] 
                                       + False[row][pos] * True[pos + 1][col];
                     False[row][col] += True[row][pos] * True[pos+1][col] 
                                       + False[row][pos] * False[pos+1][col];
                  }
              }
          }
      }
      return True[0][str_len-1];
}

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

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

11. What is the output of the following code?

#include
#include
int count_bool_parenthesization(char *sym, char *op)
{
     int str_len = strlen(sym);
     int True[str_len][str_len],False[str_len][str_len];
     int row,col,length,l;
     for(row = 0, col = 0; row < str_len; row++,col++)
     {
         if(sym[row] == 'T')
         {
             True[row][col] = 1;
             False[row][col] = 0;
         }
         else
         {
             True[row][col] = 0;
             False[row][col] = 1;
         }
     }
     for(length = 1; length < str_len; length++)
     {
         for(row = 0, col = length; col < str_len; col++, row++)
         {
             True[row][col] = 0;
             False[row][col] = 0;
             for(l = 0; l < length; l++)
             {
                 int pos = row + l;
                 int t_row_pos = True[row][pos] + False[row][pos];
                 int t_pos_col = True[pos+1][col] + False[pos+1][col];
                 if(op[pos] == '|')
                 {
                     False[row][col] += False[row][pos] * False[pos+1][col];
                     True[row][col] += t_row_pos * t_pos_col - False[row][pos] * False[pos+1][col];
                 }
                 if(op[pos] == '&')
                 {
                     True[row][col] += True[row][pos] * True[pos+1][col];
                     False[row][col] += t_row_pos * t_pos_col - True[row][pos] * True[pos+1][col];
                 }
                 if(op[pos] == '^')
                 {
                     True[row][col] += True[row][pos] * False[pos+1][col] 
                                       + False[row][pos] * True[pos + 1][col];
                     False[row][col] += True[row][pos] * True[pos+1][col] 
                                       + False[row][pos] * False[pos+1][col];
                 }
             }
         }
     }
     return True[0][str_len-1];
}
int main()
{
     char sym[] = "TTTT";
     char op[] = "|^^";
     int ans = count_bool_parenthesization(sym,op);
     printf("%d",ans);
     return 0;
}

a) 1
b) 2
c) 3
d) 4
View Answer

Answer: d
Clarification: The output of the above program is 4.

and Answers.

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

1. What is the significance of indicator block in running key cipher?
a) it helps in encryption
b) it strengthens the cipher
c) it gives information regarding the book/text from where the key is taken
d) it makes encryption easy

Answer: c
Clarification: The purpose of having an indicator block in running key cipher is to give information to the receiver about the source of a key being used. It is usually included in the second last block of the message.

2. Running key cipher is an example of _______________
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher

Answer: b
Clarification: Running key cipher is a substitution cipher. It falls under the category of poly alphabetic cipher as it uses multiple substitutions at different positions in order to cipher the plain text.

3. Encryption in running key cipher is done using _______________
a) running key table
b) vigenere cycle
c) tabula recta
d) any table provided by the person performing the encryption
Answer: c
Clarification: Encryption of plain text in running key cipher is done by making use of tabula recta. The same table is also used for encryption in vigenere cipher.

4. Which of the following cipher uses a key book or a key text instead of a keyword?
a) vigenere cipher
b) autokey cipher
c) running key cipher
d) affine cipher

Answer: c
Clarification: Running key cipher is a poly alphabetic cipher. It uses a key book or key text instead of a keyword which is agreed by both parties before encryption takes place.

5. Which of the following is a difference between running key cipher and vigenere cipher?
a) they use different tables for encryption
b) vigenere cipher is poly alphabetic whereas running key cipher is mono alphabetic
c) in vigenere cipher the key is repeated whereas in running key cipher key is not repeated
d) vigenere cipher was used in ancient time whereas running key cipher is used in modern world

Answer: c
Clarification: In running key cipher key is not repeated unlike vigenere cipher. They both use the same table for encryption.

6. Tabula recta consists of _______________
a) 26 rows and 26 columns
b) 26 rows and 1 column
c) 1 row and 26 columns
d) 27 rows and 27 columns

Answer: a
Clarification: Encryption of plain text using running key cipher is done by making use of tabula recta. It consists of 26 rows and 26 columns which have alphabets written 26 times. These are shifted towards left after each row.

7. Running key cipher is harder to decipher than keyword cipher.
a) true
b) false

Answer: a
Clarification: Keyword cipher is less secure than running key cipher. It is due to the fact that keyword cipher is mono alphabetic and thus can be cracked using frequency analysis. But running key cipher being a poly alphabetic cipher is harder to crack.

8. What will be the plain text corresponding to cipher text “KEPWSN” if running key cipher is used with keyword as “”?
a) SECRET
b) QWERTY
c) INDIAN
d) FRIEND
Answer: a
Clarification: Running key cipher is a type of poly alphabetic substitution which uses tabula recta for making substitutions in the plain text. Using the table we find the plain text to be “SECRET”.

9. Running key cipher is a transposition cipher.
a) true
b) false
Answer: b
Clarification: Running key cipher is a poly alphabetic substitution cipher. Encryption is done by using tabula recta.

10. Running key cipher is a variation of?
a) vigenere cipher
b) autokey cipher
c) hill cipher
d) route cipher

Answer: a
Clarification: Vigenere cipher is a variation of vigenere cipher. The only difference between them is that in vigenere cipher a random key is chosen whereas in running key cipher key is chosen from a book or a text.

11. What will be the ciphered text corresponding to “” if running key cipher is used for encryption with keyword as “ONCEUPONATIME”?
a) GNPJIJBQRR
b) GNPIJJBRRQ
c) GPNJJOBQRR
d) GJJNPOBQRI

Answer: a
Clarification: Encryption in running key cipher takes place exactly as in vigenere cipher if we don’t include the indicator block. So by using the tabula recta we can find the encrypted text which is “GNPJIJBQRR”.

12. What will be the ciphered text corresponding to “ALGORITHM” if running key cipher is used for encryption with keyword as “DATASTRUCTURE”?
a) LDJOZOBBK
b) DLZOJBKBO
c) ZOLDJBKBO
d) OLZBJDKBO

Answer: b
Clarification: Encryption in running key cipher takes place exactly as in vigenere cipher if we don’t include the indicator block. So by using the tabula recta we can find the encrypted text which is “DLZOJBKBO”.

13. What will be the plain text corresponding to cipher text “IWRWHS” if running key cipher is used with keyword as “”?
a) SECRET
b) QWERTY
c) INDIAN
d) FRIEND
Answer: b
Clarification: Running key cipher is a type of poly alphabetic substitution which uses tabula recta for making substitutions in the plain text. Using the table we find the plain text to be “QWERTY”.

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Square Root Decomposition”.

1. What is the purpose of using square root decomposition?
a) to reduce the time complexity of a code
b) to increase the space complexity of a code
c) to reduce the space complexity of a code
d) to reduce the space and time complexity of a code

Answer: a
Clarification: Square decomposition is mainly used in competitive programming to optimize code. It reduces the time complexity by a factor of √n.

2. By what factor time complexity is reduced when we apply square root decomposition to a code?
a) n
b) √n
c) n²
d) n^-1/2

Answer: b
Clarification: In square root decomposition a given array is decomposed into small parts each of size √n. This reduces the time complexity of the code by a factor of √n.

3. What will be the worst case time complexity of finding the sum of elements in a given range of (l,r) in an array of size n?
a) O(n)
b) O(l+r)
c) O(l-r)
d) O(r-l)
View Answer

Answer: a
Clarification: For a given array of size n we have to traverse all n elements in the worst case. In such a case l=0, r=n-1 so the time complexity will be O(n).

4. What will be the worst case time complexity of finding the sum of elements in a given range of (l,r) in an array of size n when we use square root optimization?
a) O(n)
b) O(l+r)
c) O(√n)
d) O(r-l)

Answer: c
Clarification: When we use square root optimization we decompose the given array into √n chunks each of size √n. So after calculating the sum of each chunk individually, we require to iterate only 3*√n times to calculate the sum in the worst case.

5. Total how many iterations are required to find the sum of elements in a given range of (l,r) in an array of size n when we use square root optimization?
a) √n
b) 2*√n
c) 3*√n
d) n*√n
Answer: c
Clarification: After calculating the sum of each chunk individually we require to iterate only 3*√n times to calculate the sum in the worst case. It is because two of the √n factors consider the worst case time complexity of summing elements in the first and last block. Whereas the third √n considers the factor of summing the √n chunks.

6. What will be the time complexity of update query operation in an array of size n when we use square root optimization?
a) O(√n)
b) O(n)
c) O(1)
d) O(n²)
Answer:c
Clarification: The time complexity of query operation remains the same in both square root optimized code and non optimized code. We simply find the chunk in which the update requires to be performed and then add the new updated value at the desired index.

7. Square root decomposition technique is only applicable when the number of indices in an array is a perfect square.
a) true
b) false

Answer: b
Clarification: Square root decomposition technique can be applied to an array with any number of indices. It does not require this number to be a perfect square.

8. What will be the worst case time complexity of code to find sum in given query range (l,r) in an array of size n with q number of such queries?
a) O(n)
b) O(q)
c) O(n*q)
d) O(n+q)

Answer: c
Clarification: For finding the result of one query the worst case time complexity will be n. So for q queries the time complexity will be O(q*n). This can be reduced by using square root optimization.

9. What will be the worst case time complexity of code to find sum in given query range (l,r) in an array of size n with q number of such queries when we apply MO’s algorithm?
a) O(n*q)
b) O(n)
c) O((q+n)√n)
d) O(q*√n)
Answer: c
Clarification: Mo’s algorithm requires O(q*√n) + O(n*√n) time for processing all the queries. It is better than the naive solution where O(n*q) time is required.

10. Mo’s algorithm can only be used for problems where the query can be calculated from the result of the previous query.
a) true
b) false
Answer: a
Clarification: Mo’s algorithm uses the result of the previous query in order to compute the result of the given query. It cannot be implemented where such a scenario is not possible.

11. What will be the time complexity of the code to find a minimum element from an array of size n and uses square root decomposition(exclude pre processing time)?
a) O(√n)
b) O(n)
c) O(1)
d) O(n²)

Answer: a
Clarification: For finding the minimum element in a given array of size n using square root decomposition we first divide the array into √n chunks and calculate the result for them individually. So for a given query, the result of middle blocks has to be calculated along with the extreme elements. This takes O(√n) time in the worst case.

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

1. Which of the following sorting algorithm is used by C++ internally?
a) quicksort
b) introsort
c) merge sort
d) heap sort

Answer: b
Clarification: Introsort is the in built sorting algorithm used by C++. It is an example of a hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine.

2. Which of the following sorting algorithm is not a constituent of introsort?
a) selection sort
b) quicksort
c) insertion sort
d) heap sort
Answer: a
Clarification: Introsort is a hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine. It may use quick sort or heap sort or insertion sort depending on the given situation.

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

Answer: b
Clarification: Introsort begins sorting any given array by using quick sort. Then it may switch to heap sort or insertion sort or may stick to quick sort depending upon the size of the partition.

4. Which of the following sorting algorithm is NOT stable?
a) Introsort
b) Brick sort
c) Bubble sort
d) Merge sort

Answer: a
Clarification: Out of the given options introsort is the only algorithm which is not stable. As it may use quick sort in some case to perform sorting which is itself not stable. Thus stability of introsort is not guaranteed.

5. Which of the following sorting algorithm is in-place?
a) intro sort
b) merge sort
c) counting sort
d) radix sort

Answer: a
Clarification: Introsort may use quick sort or heap sort or insertion sort internally in order to sort the given input. All of the three algorithms are in place, thus making introsort to be an in-place sorting algorithm.

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

Answer: a
Clarification: Quicksort, heap sort and insertion sort are comparison based sorts. Thus overall introsort also becomes a comparison based sort.

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

Answer: b
Clarification: Introsort is mainly governed by heap sort and quick sort. As the best case of both heap sort and quick sort is O(n log n) so the best case of introsort also becomes O(n log n).

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

Answer: b
Clarification: Worst case time complexity of quicksort is avoided when we implement introsort. Introsort switches to heap sort when there is a possibility of crossing the maximum depth limit.

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

Answer: b
Clarification: Average time complexity of introsort remains to be O(n log n) as for most of the cases quick sort and heap sort are used which have O(n log n) time complexity for an average case.

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

Answer: d
Clarification: Introsort is a hybrid of quick sort, heap sort and insertion sort. So like quick sort it may use O(log n) auxiliary space in the stack to store call statements.

11. Why is heap sort preferred over merge sort for introsort implementation?
a) Because heap sort is faster
b) Because heap sort requires less space
c) Because heap sort is easy to implement
d) Because heap sort is easy to understand
Answer: b
Clarification: Both heap sort and merge sort have the same time complexity. But heap sort is an in-place sorting algorithm whereas merge sort requires O(n) auxiliary space which makes heap sort a more preferable option.

12. Why is insertion sort preferred over other sorting algorithms (like selection sort, bubble sort etc.) for introsort 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. What is the cut-off for switching from quick sort to insertion sort in the implementation of introsort?
a) 4
b) 8
c) 16
d) 32

Answer: c
Clarification: When small arrays needs to be sorted then insertion sort proves to be the best choice. So when the size of the partition is less than 16 introsort switches to insertion sort. This particular value has been deduced experimentally.

14. What is the cut-off for switching from quick sort to heap sort in the implementation of introsort?
a) 16
b) n²
c) n log(n)
d) 2 log (n)

Answer: d
Clarification: Quicksort has a worst case time complexity of O(n²) which is not preferable. So in order to avoid worst case of quicksort, introsort switches to heap sort when the depth is greater than 2 log(n). This particular value has been deduced experimentally.

15. Which of the following sorting algorithm will be preferred when the size of partition is between 16 and 2 log(n) while implementing introsort?
a) quick sort
b) insertion sort
c) heap sort
d) merge sort

Answer: a
Clarification: Quicksort proves to be the best sorting algorithm for mid sized arrays as it has low space and time complexity. Thus quick sort is preferred when size of partition is between 16 and 2 log(n).

16. What will be the output of the given C++ code?

#include  
using namespace std; 
int main() 
{ 
    int arr[] = {1,3,4,2,5}; 
    int n = sizeof(arr)/sizeof(arr[0]);  
    sort(arr, arr+n, greater<int>());   
    int a; 
    for (a = 0; a < n; a++) 
        cout << arr[a] << " ";   
    return 0; 
}

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

Answer: c
Clarification: The given program sorts the input in descending order. It is due to the third parameter i.e. greater() which is passed to the function sort().

17. What will be the output of the given C++ code?

#include  
using namespace std; 
int main() 
{ 
    int arr[] = {1, 3,4,2,5}; 
    int n = sizeof(arr)/sizeof(arr[0]);   
    sort(arr, arr+n); 
    int a;
    for ( a = 0; a< n; a++) 
        cout << arr[a] << " ";  
    return 0; 
}

a) 1 2 3 4 5
b) 1 3 4 2 5
c) 5 4 3 2 1
d) error
Answer: a
Clarification: The given program sorts the input in ascending order. Function sort() uses two parameters in the form of address of the first and last element of the array to sort the array.

18. What will be the output of the given C++ code?

#include  
using namespace std; 
int main() 
{ 
	int arr[] = {1, 3,4,2,5}; 
	int n = sizeof(arr)/sizeof(arr[0]);
	sort(arr+2, arr+n, greater<int>()); 
        int a;
	for (int a = 0; a < n; a++) 
		cout << arr[a] << " "; 
	return 0; 
}

a) 1 2 3 4 5
b) 1 5 4 3 2
c) 5 4 3 2 1
d) 1 3 5 4 2
Answer: d
Clarification: As the first parameter to function sort() is arr+2 so the sorting begins from the third element i.e. 4. Also as there is a third argument greater () to the function sort() so the sorting will be done in descending order.

& Algorithms.