Category: Data Structures & Algorithms Objective Questions

Data Structure Multiple Choice Questions on “Search an Element in an Array using Recursion – 1”.

1. Which of the following techniques can be used to search an element in an unsorted array?
a) Iterative linear search
b) Recursive binary search
c) Iterative binary search
d) Normal binary search
Answer: a
Clarification: Iterative linear search can be used to search an element in an unsorted array.
Note: Binary search can be used only when the array is sorted.

2. Consider the array {1,1,1,1,1}. Select the wrong option?
a) Iterative linear search can be used to search for the elements in the given array
b) Recursive linear search can be used to search for the elements in the given array
c) Recursive binary search can be used to search for the elements in the given array
d) No method is defined to search for an element in the given array

Answer: d
Clarification: Iterative linear search, Recursive linear search and Recursive binary search can be applied to search for an element in the above given array.

3. What does the following code do?

#include
int search_num(int *arr, int num, int len)
{
     int i;
     for(i = 0; i < len; i++)
     if(arr[i] == num)
      return i;
     return -1;
}
int main()
{
      int arr[5] ={1,2,3,4,5},num=3,len = 5;
      int indx = search_num(arr,num,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

a) Search and returns the index of all the occurrences of the number that is searched
b) Search and returns the index of the first occurrence of the number that is searched
c) Search and returns of the last occurrence of the number that is searched
d) Returns the searched element from the given array

Answer: b
Clarification: The code finds the index of the first occurrence of the number that is searched.

4. What is the output of the following code?

#include
int search_num(int *arr, int num, int len)
{
     int i;
     for(i = 0; i < len; i++)
     if(arr[i] == num)
        return i;
     return -1;
}
int main()
{
      int arr[5] ={1,3,3,3,5},num=3,len = 5;
      int indx = search_num(arr,num,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

a) Index of 3 is 0
b) Index of 3 is 1
c) Index of 3 is 2
d) Index of 3 is 3

Answer: b
Clarification: The program prints the index of the first occurrence of 3, which is 1.

5. What is the time complexity of the following code used to search an element in an array?

#include
int search_num(int *arr, int num, int len)
{
     int i;
     for(i = 0; i < len; i++)
     if(arr[i] == num)
        return i;
     return -1;
}
int main()
{
      int arr[5] ={1,3,3,3,5},num=3,len = 5;
      int indx = search_num(arr,num,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

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

Answer: b
Clarification: The time complexity of the above code used to search an element in an array is O(n).

6. Consider the following recursive implementation of linear search:

#include
int recursive_search_num(int *arr, int num, int idx, int len)
{
     if(idx == len)
     return -1;
     if(arr[idx] == num)
       return idx;
     return __________;
}
int main()
{
      int arr[5] ={1,3,3,3,5},num=2,len = 5;
      int indx = recursive_search_num(arr,num,0,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

Which of the following recursive calls should be added to complete the above code?
a) recursive_search_num(arr, num+1, idx, len);
b) recursive_search_num(arr, num, idx, len);
c) recursive_search_num(arr, num, idx+1, len);
d) recursive_search_num(arr, num+1, idx+1, len);

Answer: c
Clarification: The recursive call “recursive_search_num(arr, num, idx+1, len)” should be added to complete the above code.

7. What is the output of the following code?

#include
int recursive_search_num(int *arr, int num, int idx, int len)
{
     if(idx == len)
     return -1;
     if(arr[idx] == num)
       return idx;
     return recursive_search_num(arr, num, idx+1, len);
}
int main()
{
      int arr[8] ={1,2,3,3,3,5,6,7},num=5,len = 8;
      int indx = recursive_search_num(arr,num,0,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

a) Index of 5 is 5
b) Index of 5 is 6
c) Index of 5 is 7
d) Index of 5 is 8
View Answer

Answer: a
Clarification: The program prints the index of 5, which is 5.

8. How many times is the function recursive_search_num() called when the following code is executed?

#include
int recursive_search_num(int *arr, int num, int idx, int len)
{
     if(idx == len)
     return -1;
     if(arr[idx] == num)
     return idx;
     return recursive_search_num(arr, num, idx+1, len);
}
int main()
{
      int arr[8] ={1,2,3,3,3,5,6,7},num=5,len = 8;
      int indx = recursive_search_num(arr,num,0,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

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

Answer: b
Clarification: The function recursive_search_num() is called 6 times when the above code is executed.

9. What is the time complexity of the following recursive implementation of linear search?

#include
int recursive_search_num(int *arr, int num, int idx, int len)
{
     if(idx == len)
     return -1;
     if(arr[idx] == num)
     return idx;
     return recursive_search_num(arr, num, idx+1, len);
}
int main()
{
      int arr[8] ={1,2,3,3,3,5,6,7},num=5,len = 8;
      int indx = recursive_search_num(arr,num,0,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

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

Answer: b
Clarification: The time complexity of the above recursive implementation of linear search is O(n).

Data Structure MCQs on “Maximum Sum of Continuous Subarray – 2”.

1. Which line should be inserted in the blank to complete the following dynamic programming implementation of the maximum sub-array sum problem?

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

a) max_num(sum[idx – 1] + arr[idx], arr[idx])
b) sum[idx – 1] + arr[idx].
c) min_num(sum[idx – 1] + arr[idx], arr[idx])
d) arr[idx].

Answer: a
Clarification: The array “sum” is used to store the maximum sub-array sum. The appropriate way to do this is by using:
sum[idx] = max_num(sum[idx – 1] + arr[idx], arr[idx]).

2. What is the time complexity of the following dynamic programming algorithm used to find the maximum sub-array sum?

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

a) O(n)
b) O(logn)
c) O(nlogn)
d) O(n²)
View Answer

Answer: a
Clarification: The time complexity of the above dynamic programming algorithm used to solve maximum sub-array sum is O(n).

3. What is the space complexity of the following dynamic programming algorithm used to find the maximum sub-array sum?

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

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

Answer: a
Clarification: The above dynamic programming algorithm uses space equal to the length of the array to store the sum values. So, the space complexity is O(n).

4. Consider the following code snippet. Which property is shown by line 4 of the below code snippet?

1. int sum[len], idx;
2. sum[0] = arr[0];
3. for(idx = 1; idx < len; idx++)
4.	  sum[idx] = max(sum[idx - 1] + arr[idx], arr[idx]);
5. int mx = sum[0];
6. for(idx = 0; idx < len; idx++)
7.	 if(sum[idx] > mx)
8.		mx =sum[idx];
9. return mx;

a) Optimal substructure
b) Overlapping subproblems
c) Both overlapping subproblems and optimal substructure
d) Greedy substructure

Answer: a
Clarification: The current sum (i.e. sum[idx]) uses the previous sum (i.e. sum[idx – 1]) to get an optimal value. So, line 4 shows the optimal substructure property.

5. Consider the following code snippet:

1. int sum[len], idx;
2. sum[0] = arr[0];
3. for(idx = 1; idx < len; idx++)
4.	  sum[idx] = max(sum[idx - 1] + arr[idx], arr[idx]);
5. int mx = sum[0];
6. for(idx = 0; idx < len; idx++)
7.	 if(sum[idx] > mx)
8.		mx =sum[idx];
9. return mx;

Which method is used by line 4 of the above code snippet?
a) Divide and conquer
b) Recursion
c) Both memoization and divide and conquer
d) Memoization

Answer: d
Clarification: The array “sum” is used to store the previously calculated values, so that they aren’t recalculated. So, line 4 uses the memoization technique.

6. Find the maximum sub-array sum for the following array:
{3, 6, 7, 9, 3, 8}
a) 33
b) 36
c) 23
d) 26

Answer: b
Clarification: All the elements of the array are positive. So, the maximum sub-array sum is equal to the sum of all the elements, which is 36.

7. What is the output of the following program?

#include
int max_num(int a,int b)
{
     if(a> b)
	return a;
     return b;
}
int maximum_subarray_sum(int *arr, int len)
{
     int sum[len], idx;
     sum[0] = arr[0];
     for(idx = 1; idx < len; idx++)
	sum[idx] = max_num(sum[idx - 1] + arr[idx], arr[idx]);
     int mx = sum[0];
     for(idx = 0; idx < len; idx++)
	if(sum[idx] > mx)
	   mx =sum[idx];
     return mx;
}
int main()
{
     int arr[] = {-20, 23, 10, 3, -10, 11, -5},len = 7;
     int ans = maximum_subarray_sum(arr, len);
     printf("%d",ans);
     return 0;
}

a) 27
b) 37
c) 36
d) 26

Answer: b
Clarification: The program prints the value of maximum sub-array sum, which is 37.

8. What is the value stored in sum[4] after the following program is executed?

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

a) 28
b) 25
c) 22
d) 12

Answer: c
Clarification: After the program is executed the value stored in sum[4] is 22.
Note: You are asked to find the value stored in sum[4] and NOT the output of the program.

and Answers.

Data Structure Multiple Choice Questions on “Dice Throw Problem”.

1. You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem?
a) Brute force
b) Recursion
c) Dynamic programming
d) Brute force, Recursion and Dynamic Programming
Answer: d
Clarification: Brute force, Recursion and Dynamic Programming can be used to solve the dice throw problem.

2. You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together?
a) n*n*n…f times
b) f*f*f…n times
c) n*n*n…n times
d) f*f*f…f times
Answer: b
Clarification: Each die can take f values and there are n dice. So, the total number of permutations is f*f*f…n times.

3. You have 3 dice each having 6 faces. What is the number of permutations that can be obtained when you roll the 3 dice together?
a) 27
b) 36
c) 216
d) 81
Answer: c
Clarification: The total number of permutations that can be obtained is 6 * 6 * 6 = 216.

4. You have 2 dice each of them having 6 faces numbered from 1 to 6. What is the number of ways in which a sum of 11 can be achieved?
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: The sum of 11 can be achieved when the dice show {6, 5} or {5, 6}.

5. There are n dice with f faces. The faces are numbered from 1 to f. What is the minimum possible sum that can be obtained when the n dice are rolled together?
a) 1
b) f
c) n
d) n*f

Answer: c
Clarification: The sum will be minimum when all the faces show a value 1. The sum in this case will be n.

6. There are n dice with f faces. The faces are numbered from 1 to f. What is the maximum possible sum that can be obtained when the n dice are rolled together?
a) 1
b) f*f
c) n*n
d) n*f

Answer: d
Clarification: The sum will be maximum when all the faces show a value f. The sum in this case will be n*f.

7. There are 10 dice having 5 faces. The faces are numbered from 1 to 5. What is the number of ways in which a sum of 4 can be achieved?
a) 0
b) 2
c) 4
d) 8

Answer: a
Clarification: Since there are 10 dice and the minimum value each die can take is 1, the minimum possible sum is 10. Hence, a sum of 4 cannot be achieved.

8. Consider the following dynamic programming implementation of the dice throw problem:

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
     int arr[num_of_dice + 1][S + 1];
     int dice, face, sm;
     for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
     for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
     for(dice = 2; dice <= num_of_dice; dice++)
     { 
         for(sm = 1; sm <= S; sm++)
         {
             for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
         }
     }
     return _____________;
}
int main()
{
     int num_of_dice = 3, num_of_faces = 4, sum = 6;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

Which of the following lines should be added to complete the above code?
a) arr[num_of_dice][S]
b) arr[dice][sm]
c) arr[dice][S]
d) arr[S][dice]

Answer: a
Clarification: The line arr[num_of_dice][S] completes the above code.

9. What is time complexity of the following dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
     int arr[num_of_dice + 1][S + 1];
     int dice, face, sm;
     for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
     for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
     for(dice = 2; dice <= num_of_dice; dice++)
     { 
         for(sm = 1; sm <= S; sm++)
         {
             for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
         }
     }
     return arr[num_of_dice][S];
}
int main()
{
     int num_of_dice = 3, num_of_faces = 4, sum = 6;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

a) O(n*f)
b) O(f*s)
c) O(n*s)
d) O(n*f*s)

Answer: d
Clarification: The time complexity of the above dynamic programming implementation is O(n*f*s).

10. What is space complexity of the following dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
     int arr[num_of_dice + 1][S + 1];
     int dice, face, sm;
     for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
     for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
     for(dice = 2; dice <= num_of_dice; dice++)
     { 
         for(sm = 1; sm <= S; sm++)
         {
             for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
         }
     }
     return arr[num_of_dice][S];
}
int main()
{
     int num_of_dice = 3, num_of_faces = 4, sum = 6;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

a) O(n*f)
b) O(f*s)
c) O(n*s)
d) O(n*f*s)

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

11. What is the output of the following code?

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
     int arr[num_of_dice + 1][S + 1];
     int dice, face, sm;
     for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
     for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
     for(dice = 2; dice <= num_of_dice; dice++)
     {
         for(sm = 1; sm <= S; sm++)
         {
             for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
         }
     }
     return arr[num_of_dice][S];
}
int main()
{
     int num_of_dice = 3, num_of_faces = 4, sum = 6;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

a) 10
b) 12
c) 14
d) 16

Answer: a
Clarification: The output of the above code is 10.

12. What will be the value stored in arr[2][2] when the following code is executed?

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
      int arr[num_of_dice + 1][S + 1];
      int dice, face, sm;
      for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
      for(sm = 1; sm <= S; sm++)
           arr[1][sm] = 1;
      for(dice = 2; dice <= num_of_dice; dice++)
      {
          for(sm = 1; sm <= S; sm++)
          {
              for(face = 1; face <= num_of_faces && face < sm; face++)
                  arr[dice][sm] += arr[dice - 1][sm - face];
          }
      }
      return arr[num_of_dice][S];
}
int main()
{
      int num_of_dice = 3, num_of_faces = 4, sum = 6;
      int ans = get_ways(num_of_dice, num_of_faces, sum);
      printf("%d",ans);
      return 0;
}

a) 0
b) 1
c) 2
d) 3
Answer: b
Clarification: The value stored in arr[2][2] is 1.

13. What is the output of the following code?

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
     int arr[num_of_dice + 1][S + 1];
     int dice, face, sm;
     for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
     for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
     for(dice = 2; dice <= num_of_dice; dice++)
     {
         for(sm = 1; sm <= S; sm++)
         {
             for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
         }
     }
     return arr[num_of_dice][S];
}
int main()
{
     int num_of_dice = 4, num_of_faces = 6, sum = 3;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

a) 0
b) 1
c) 2
d) 3
Answer: a
Clarification: The minimum possible sum is 4. So, the output for sum = 3 is 0.

14. What is the output of the following code?

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
      int arr[num_of_dice + 1][S + 1];
      int dice, face, sm;
      for(dice = 0; dice <= num_of_dice; dice++)
          for(sm = 0; sm <= S; sm++)
            arr[dice][sm] = 0;
      for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
      for(dice = 2; dice <= num_of_dice; dice++)
      {
          for(sm = 1; sm <= S; sm++)
          {
              for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
          }
      }
      return arr[num_of_dice][S];
}
int main()
{
      int num_of_dice = 2, num_of_faces = 6, sum = 5;
      int ans = get_ways(num_of_dice, num_of_faces, sum);
      printf("%d",ans);
      return 0;
}

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

Answer: c
Clarification: The output of the above code is 4.

Data Structures & Algorithms Multiple Choice Questions on “Polybius Square”.

1. Polybius square is also known by the name of?
a) Polybius checkboard
b) Polybius table
c) Ploybius board
d) Ploybius keypad

Answer: a
Clarification: Polybius square is similar to substitution cipher. It is also known by the name of Polybius checkboard.

2. How many keys are required for encryption and decryption of data when we use asymmetric cipher?
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: Asymmetric cipher makes use of 2 keys for the purpose of encryption. One is known as public key whereas other is called private key.

3. Which of the following is made possible by the use of Polybius square?
a) To represent the plain text by smaller set of symbols
b) To represent the plain text by larger set of symbols
c) To represent the plain text by the letters of some other language
d) To represent the plain text by the same set of symbols

Answer: a
Clarification: Polybius square is similar to substitution cipher. Polybius square allows us to cipher the plain text in such a way that a minimum number of symbols are used in the encrypted text.

4. What is the usual size of polybius square used for encrypting English alphabets?
a) 5 X 5
b) 6 X 6
c) 26 X 26
d) 25 X 25

Answer: a
Clarification: The usual size of poybius square for encrypting English alphabets is 5 X 5. Usually, I and J are combined so as to fit all English letters in this table.

5. Polybius square cipher is most closely related to?
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher

Answer: a
Clarification: Polybius square cipher is much like any mono alphabetic cipher. It is because it applies a fixed substitution to the letters present in plain text.

6. Which two English letters are usually combined in polybius table?
a) A and B
b) Y and Z
c) I and J
d) J and K

Answer: c
Clarification: The usual size of poybius square for encrypting English alphabets is 5 X 5. Usually, I and J are combined so as to fit all English letters in this table.

7. Auto key cipher is more secure than polybius square cipher?
a) true
b) false

Answer: a
Clarification: Polybius square is closely related to mono alphabetic substitution cipher and thus is more vulnerable to frequency analysis. Whereas polybius square being a poly alphabetic cipher is less vulnerable to frequency analysis and so is more secure.

8. Polybius square cipher is less susceptible to frequency analysis.
a) true
b) false

Answer: b
Clarification: Polybius square cipher is closely related to mono alphabetic cipher. Thus it is quite vulnerable to frequency analysis much like any other mono alphabetic cipher.

9. Which of the following cipher uses polybius square cipher in its first step of encrypting data?
a) Autokey cipher
b) One time pad cipher
c) ADFGVX cipher
d) Rail fence cipher

Answer: c
Clarification: ADFGVX cipher uses polybius square cipher in its first step of encrypting data. It uses a 6 X 6 version of polybius square.

10. What will be the plain text corresponding to ciphered text “134325” if standard polybius square cipher is used for encryption?
a) SRH
b) CSK
c) RCB
d) KKR

Answer: b
Clarification: For decoding ciphered text we have to use the polybius square in and find out the letters corresponding to each pair of coordinate. So in this case the plain text is found to be “CSK”.

11. What will be the encrypted text corresponding to plain text “SAN” using standard polybius square cipher?
a) 431133
b) 341133
c) 441133
d) 114433
Answer: a
Clarification: For encrypting using polybius square cipher we have to use the table which is shown below and write (row, col) coordinates corresponding to each letter.
1 2 3 4 5
1 A B C D E
2 F G H I/J K
3 L M N O P
4 Q R S T U
5 V W X Y Z
So the ciphered text will be “431133”.

12.What will be the output of the following C++ code?

#include  
#include  
using namespace std; 
void Cipher(string str) 
{ 
    int r, c; 
    for (int i = 0; str[i]; i++) 
    { 
 
	r = ceil((str[i] - 'a') / 5) + 1; 
 
 
	c = ((str[i] - 'a') % 5) + 1; 
 
 
	if (str[i] == 'k') 
        { 
	    r = r - 1; 
	    c = 5 - c + 1; 
	} 
 
 
	else if (str[i] >= 'j') 
        { 
	    if (c == 1) 
            { 
		c = 6; 
		r = r - 1; 
	    } 
	    c = c - 1; 
	} 
	cout << r << c; 
    } 
    cout << endl; 
} 
 
int main() 
{ 
    string str = "nsit"; 
    Cipher(str); 
}

a) 33344244
b) 44332434
c) 33432444
d) 11444323

Answer: c
Clarification: The given code implements polybius square cipher on a given plain text. So here as the plain text is “nsit” so the output of the code should be “33432444”.

& Algorithms.

and Answers.

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Co-ordinate Compression”.

1. What is co-ordinate compression?
a) process of reassigning co-ordinates to remove gaps
b) inserting gaps in a co-ordinate system
c) removing redundant co-ordinates
d) adding extra gaps

Answer: a
Clarification: Co-ordinate compression is the process of reassigning co-ordinates in order to remove gaps. This helps in improving efficiency of a solution.

2. What is the need for co-ordinate compression?
a) for improving time complexity
b) for improving space complexity
c) for improving both time and space complexity
d) for making code simpler

Answer: c
Clarification:Co-ordinate compression is the process of reassigning co-ordinates in order to remove gaps. This helps in improving both time and space complexity of a solution.

3. What is the output for the following code?

#include  
using namespace std;  
void convert(int a[], int n) 
{ 	
	vector <pair<int, int> > vec;	
	for (int i = 0; i < n; i++) 
		vec.push_back(make_pair(a[i], i)); 
	sort(vec.begin(), vec.end()); 	
	for (int i=0; i<n; i++) 
		a[vec[i].second] = i; 
} 
void printArr(int a[], int n) 
{ 
	for (int i=0; i<n; i++) 
		cout << a[i] << " "; 
} 
int main() 
{ 
	int arr[] = {10,8,2,5,7}; 
	int n = sizeof(arr)/sizeof(arr[0]);  
	convert(arr , n); 
   	printArr(arr, n); 
	return 0; 
}

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

Answer: a
Clarification: The given code converts the elements of the input array. They are replaced with their respective position number in the sorted array.

4. What will be the time complexity of given code?

#include  
using namespace std;  
void convert(int a[], int n) 
{ 	
	vector <pair<int, int> > vec; 	
	for (int i = 0; i < n; i++) 
		vec.push_back(make_pair(a[i], i)); 	
	sort(vec.begin(), vec.end()); 	
	for (int i=0; i<n; i++) 
		a[vec[i].second] = i; 
} 
void printArr(int a[], int n) 
{ 
	for (int i=0; i<n; i++) 
		cout << a[i] << " "; 
} 
int main() 
{ 
	int arr[] = {10,8,2,5,7}; 
	int n = sizeof(arr)/sizeof(arr[0]); 	
	convert(arr , n); 
   	printArr(arr, n); 
	return 0; 
}

a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: b
Clarification: The time complexity of the given code will be governed by the time complexity of the sorting algorithm used. As this code uses in built sorting of C++ so it will take O(n log n) time.

5. What is the auxiliary space complexity of the given code?

#include  
using namespace std;  
void convert(int a[], int n) 
{ 	
	vector <pair<int, int> > vec; 	
	for (int i = 0; i < n; i++) 
		vec.push_back(make_pair(a[i], i)); 	
	sort(vec.begin(), vec.end()); 
	for (int i=0; i<n; i++) 
		a[vec[i].second] = i; 
} 
void printArr(int a[], int n) 
{ 
	for (int i=0; i<n; i++) 
		cout << a[i] << " "; 
} 
int main() 
{ 
	int arr[] = {10,8,2,5,7}; 
	int n = sizeof(arr)/sizeof(arr[0]);  
	convert(arr , n); 
   	printArr(arr, n); 
	return 0; 
}

a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Answer: b
Clarification: The given code uses an auxiliary space of O(n). It is used by a vector which pairs each element of the array with their respective index number of the original array.

6. What will be the output of the following code?

#include  
using namespace std; 
void convert(int arr[], int n) 
{ 
	int temp[n]; 
	memcpy(temp, arr, n*sizeof(int)); 
	sort(temp, temp + n); 	
        unordered_map<int, int> map; 	
	int sort_index = 0; 
	for (int i = 0; i < n; i++) 
		map[temp[i]] = sort_index++; 	
	for (int i = 0; i < n; i++) 
		arr[i] = map[arr[i]]; 
} 
void printArr(int arr[], int n) 
{ 
	for (int i=0; i<n; i++) 
		cout << arr[i] << " "; 
} 
int main() 
{ 
	int arr[] = {3,5,2,4}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	convert(arr , n); 	
	printArr(arr, n); 
	return 0; 
}

a) 0 2 3 4
b) 1 3 0 2
c) 2 4 1 3
d) 1 2 3 4

Answer: b
Clarification: The given code converts the elements of input array. They are replaced with their respective position number in the sorted array.

7. What is the time complexity of the following code?

#include  
using namespace std; 
void convert(int arr[], int n) 
{ 	
	int temp[n]; 
	memcpy(temp, arr, n*sizeof(int)); 
	sort(temp, temp + n); 	
        unordered_map<int, int> map; 	
	int sort_index = 0; 
	for (int i = 0; i < n; i++) 
		map[temp[i]] = sort_index++; 	
	for (int i = 0; i < n; i++) 
		arr[i] = map[arr[i]]; 
} 
void printArr(int arr[], int n) 
{ 
	for (int i=0; i<n; i++) 
		cout << arr[i] << " "; 
} 
int main() 
{ 
	int arr[] = {10, 20, 15, 12, 11, 50}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	convert(arr , n); 	
	printArr(arr, n); 
	return 0; 
}

a) O(n)
b) O(1)
c) O(n log n)
d) O(n²)
Answer: c
Clarification: The time complexity of the given code will be governed by the time complexity of the sorting algorithm used. As this code uses inbuilt sorting of C++ so it will take O(n log n) time.

8. What will be the auxiliary space complexity of the following code?

#include  
using namespace std; 
void convert(int arr[], int n) 
{ 	
	int temp[n]; 
	memcpy(temp, arr, n*sizeof(int)); 
	sort(temp, temp + n); 	
        unordered_map<int, int> map; 	
	int sort_index = 0; 
	for (int i = 0; i < n; i++) 
		map[temp[i]] = sort_index++; 	
	for (int i = 0; i < n; i++) 
		arr[i] = map[arr[i]]; 
} 
void printArr(int arr[], int n) 
{ 
	for (int i=0; i<n; i++) 
		cout << arr[i] << " "; 
} 
int main() 
{ 
	int arr[] = {10, 20, 15, 12, 11, 50}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	convert(arr , n); 	
	printArr(arr, n); 
	return 0; 
}

a) O(n)
b) O(1)
c) O(log n)
d) O(n log n)

Answer: a
Clarification: The given code uses an auxiliary space of O(n). It is used by a vector which pairs each element of the array with their respective index number of the original array.

9. Co-ordinate compression reduces the number of squares in a graph.
a) true
b) false
View Answer

Answer: a
Clarification: The idea behind co-ordinate compression is to reduce the number of squares in a graph by converting them into rectangles of viable size. This reduces the time complexity of traversal.

10. Co-ordinate compression can only be applied in a co-ordinate system problem.
a) true
b) false
View Answer

Answer: b
Clarification: Co-ordinate compression technique can be applied where such optimization is suitable. It does not require to co-ordinate system problem only.

Data Structures & Algorithms Multiple Choice Questions on “Substring Searching Algorithm”.

1. Which of the following is a sub string of “”?
a) SANO
b) FOUND
c) SAND
d) FOND
Answer: b
Clarification: A sub string is a subset of another string. So “FOUND” is the only possible sub string out of the given options.

2. What will be the output of the following code?

#include 
using namespace std; 
 
void func(char* str2, char* str1) 
{ 
	int m = strlen(str2); 
	int n = strlen(str1); 
	for (int i = 0; i <= n - m; i++) 
        { 
		int j; 
 
 
		for (j = 0; j < m; j++) 
			if (str1[i + j] != str2[j]) 
				break; 
 
		if (j == m) 
			cout << i << endl; 
	} 
} 
 
int main() 
{ 
	char str1[] = "1253234"; 
	char str2[] = "323"; 
	func(str2, str1); 
	return 0; 
}

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

Answer: c
Clarification: The given code describes the naive method of finding a pattern in a string. So the output will be 3 as the given sub string begins at that index in the pattern.

3. What will be the worst case time complexity of the following code?

#include 
using namespace std; 
 
void func(char* str2, char* str1) 
{ 
	int m = strlen(str2); 
	int n = strlen(str1); 
	for (int i = 0; i <= n - m; i++) 
        { 
		int j; 
 
 
		for (j = 0; j < m; j++) 
			if (str1[i + j] != str2[j]) 
				break; 
 
		if (j == m) 
			cout << i << endl; 
	} 
} 
 
int main() 
{ 
	char str1[] = "1253234"; 
	char str2[] = "323"; 
	func(str2, str1); 
	return 0; 
}

a) O(n)
b) O(m)
c) O(m * n)
d) O(m + n)

Answer: c
Clarification: The given code describes the naive method of pattern searching. By observing the nested loop in the code we can say that the time complexity of the loop is O(m*n).

4. What will be the auxiliary space complexity of the following code?

#include 
using namespace std; 
 
void func(char* str2, char* str1) 
{ 
	int m = strlen(str2); 
	int n = strlen(str1); 
	for (int i = 0; i <= n - m; i++) 
        { 
		int j; 
 
		for (j = 0; j < m; j++) 
			if (str1[i + j] != str2[j]) 
				break; 
 
		if (j == m) 
			cout << i << endl; 
	} 
} 
 
int main() 
{ 
	char str1[] = "1253234"; 
	char str2[] = "323"; 
	func(str2, str1); 
	return 0; 
}

a) O(n)
b) O(1)
c) O(log n)
d) O(m)

Answer: b
Clarification: The given code describes the naive method of pattern searching. Its auxiliary space requirement is O(1).

5. What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?
a) O(n)
b) O(n*m)
c) O(m)
d) O(log n)

Answer: c
Clarification: KMP algorithm is an efficient pattern searching algorithm. It has a time complexity of O(m) where m is the length of text.

6. What will be the best case time complexity of the following code?

#include 
using namespace std; 
void func(char* str2, char* str1) 
{ 
	int m = strlen(str2); 
	int n = strlen(str1); 
 
	for (int i = 0; i <= n - m; i++) 
        { 
		int j; 
 
 
		for (j = 0; j < m; j++) 
			if (str1[i + j] != str2[j]) 
				break; 
 
		if (j == m) 
			cout << i << endl; 
	} 
} 
 
int main() 
{ 
	char str1[] = "1253234"; 
	char str2[] = "323"; 
	func(str2, str1); 
	return 0; 
}

a) O(n)
b) O(m)
c) O(m * n)
d) O(m + n)

Answer: b
Clarification: The given code describes the naive method of pattern searching. The best case of the code occurs when the first character of the pattern does not appear in the text at all. So in such a case, only one iteration is required thus time complexity will be O(m).

7. What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
a) O(n + m)
b) O(m)
c) O(n)
d) O(m * n)

Answer: a
Clarification: Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It has a time complexity of O(m + n) where m is the length of text and n is the length of the pattern.

8. What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
a) O(n + m)
b) O(m)
c) O(n)
d) O(m * n)

Answer: b
Clarification: Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It an auxiliary space of O(m) for maintaining Z array.

9. The naive pattern searching algorithm is an in place algorithm.
a) true
b) false

Answer: a
Clarification: The auxiliary space complexity required by naive pattern searching algorithm is O(1). So it qualifies as an in place algorithm.

10. Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.
a) true
b) false

Answer: a
Clarification: The worst case time complexity of Rabin Karp algorithm is O(m*n) but it has a linear average case time complexity. So Rabin Karp and naive pattern searching algorithm have the same worst case time complexity.