250+ TOP MCQs on Bellman-Ford Algorithm and Answers

Data Structures & Algorithms Multiple Choice Questions on “Bellman-Ford Algorithm”.

1. The Bellmann Ford algorithm returns _______ value.
a) Boolean
b) Integer
c) String
d) Double

Answer: a
Clarification: The Bellmann Ford algorithm returns Boolean value whether there is a negative weight cycle that is reachable from the source.

2. Bellmann ford algorithm provides solution for ____________ problems.
a) All pair shortest path
b) Sorting
c) Network flow
d) Single source shortest path

Answer: d
Clarification: Bellmann ford algorithm is used for finding solutions for single source shortest path problems. If the graph has no negative cycles that are reachable from the source then the algorithm produces the shortest paths and their weights.

3. Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not.
a) True
b) False
Answer: a
Clarification: Bellmann Ford algorithm returns true if the graph does not have any negative weight cycles and returns false when the graph has negative weight cycles.

4. How many solution/solutions are available for a graph having negative weight cycle?
a) One solution
b) Two solutions
c) No solution
d) Infinite solutions

Answer: c
Clarification: If the graph has any negative weight cycle then the algorithm indicates that no solution exists for that graph.

5. What is the running time of Bellmann Ford Algorithm?
a) O(V)
b) O(V2)
c) O(ElogV)
d) O(VE)
View Answer

Answer: d
Clarification: Bellmann Ford algorithm runs in time O(VE), since the initialization takes O(V) for each of V-1 passes and the for loop in the algorithm takes O(E) time. Hence the total time taken by the algorithm is O(VE).

6. How many times the for loop in the Bellmann Ford Algorithm gets executed?
a) V times
b) V-1
c) E
d) E-1

Answer: b
Clarification: The for loop in the Bellmann Ford Algorithm gets executed for V-1 times. After making V-1 passes, the algorithm checks for a negative weight cycle and returns appropriate boolean value.

7. Dijikstra’s Algorithm is more efficient than Bellmann Ford Algorithm.
a) True
b) False
Answer: a
Clarification: The running time of Bellmann Ford Algorithm is O(VE) whereas Dijikstra’s Algorithm has running time of only O(V2).

8. Identify the correct Bellmann Ford Algorithm.
a)

for i=1 to V[g]-1
	do for each edge (u,v) in E[g]
		do Relax(u,v,w)
   for each edge (u,v) in E[g]
	do if d[v]>d[u]+w(u,v)
		then return False
   return True

b)

for i=1 to V[g]-1
       for each edge (u,v) in E[g]
	do if d[v]>d[u]+w(u,v)
		then return False
    return True

c)

for i=1 to V[g]-1
	do for each edge (u,v) in E[g]
		do Relax(u,v,w)
   for each edge (u,v) in E[g]
	do if d[v]<d[u]+w(u,v)
		then return true
   return True

d)

for i=1 to V[g]-1
	do for each edge (u,v) in E[g]
		do Relax(u,v,w)
   return True

Answer: a
Clarification: After initialization, the algorithm makes v-1 passes over the edges of the graph. Each pass is one iteration of the for loop and consists of relaxing each edge of the graph once. Then it checks for the negative weight cycle and returns an appropriate Boolean value.

 
 

9. What is the basic principle behind Bellmann Ford Algorithm?
a) Interpolation
b) Extrapolation
c) Regression
d) Relaxation

Answer: d
Clarification: Relaxation methods which are also called as iterative methods in which an approximation to the correct distance is replaced progressively by more accurate values till an optimum solution is found.

10. Bellmann Ford Algorithm can be applied for _____________
a) Undirected and weighted graphs
b) Undirected and unweighted graphs
c) Directed and weighted graphs
d) All directed graphs

Answer: c
Clarification: Bellmann Ford Algorithm can be applied for all directed and weighted graphs. The weight function in the graph may either be positive or negative.

11. Bellmann Ford algorithm was first proposed by ________
a) Richard Bellmann
b) Alfonso Shimbe
c) Lester Ford Jr
d) Edward F. Moore

Answer: b
Clarification: Alfonso Shimbe proposed Bellmann Ford algorithm in the year 1955. Later it was published by Richard Bellmann in 1957 and Lester Ford Jr in the year 1956. Hence it is called Bellmann Ford Algorithm.

12. Consider the following graph. What is the minimum cost to travel from node A to node C?
bellman-ford-algorithm-questions-answers-q12
a) 5
b) 2
c) 1
d) 3
View Answer

Answer: b
Clarification: The minimum cost to travel from node A to node C is 2.
A-D, cost=1
D-B, cost=-2
B-C, cost=3
Hence the total cost is 2.

13. In the given graph, identify the path that has minimum cost to travel from node a to node f.
bellman-ford-algorithm-questions-answers-q13
a) a-b-c-f
b) a-d-e-f
c) a-d-b-c-f
d) a-d-b-c-e-f

Answer: d
Clarification: The minimum cost taken by the path a-d-b-c-e-f is 4.
a-d, cost=2
d-b, cost=-2
b-c, cost=1
c-e, cost= 2
e-f, cost=1
Hence the total cost is 4.

14. Bellmann Ford Algorithm is an example for ____________
a) Dynamic Programming
b) Greedy Algorithms
c) Linear Programming
d) Branch and Bound

Answer: a
Clarification: In Bellmann Ford Algorithm the shortest paths are calculated in bottom up manner which is similar to other dynamic programming problems.

15. A graph is said to have a negative weight cycle when?
a) The graph has 1 negative weighted edge
b) The graph has a cycle
c) The total weight of the graph is negative
d) The graph has 1 or more negative weighted edges

Answer: c
Clarification: When the total weight of the graph sums up to a negative number then the graph is said to have a negative weight cycle. Bellmann Ford Algorithm provides no solution for such graphs.

250+ TOP MCQs on GCD and LCM using Recursion Multiple Choice Questions and Answers (MCQs) and Answers

Data Structures & Algorithms Multiple Choice Questions on “GCD and LCM using Recursion – 1”.

1. Which of the following is not another name for GCD(Greatest Common Divisor)?
a) LCM
b) GCM
c) GCF
d) HCF

Answer: a
Clarification: : LCM (Least Common Multiple) and GCD are not same. GCM (Greatest Common Measure), GCF (Greatest Common Factor), HCF (Highest Common Factor) are other names for GCD.

2. What is the GCD of 8 and 12?
a) 8
b) 12
c) 2
d) 4

Answer: d
Clarification: GCD is largest positive integer that divides each of the integer. So the GCD of 8 and 12 is 4.

3. If GCD of two number is 8 and LCM is 144, then what is the second number if first number is 72?
a) 24
b) 2
c) 3
d) 16

Answer: d
Clarification: As A * B = GCD (A, B) * LCM (A, B). So B = (144 * 8)/72 = 16.

4. Which of the following is also known as GCD?
a) Highest Common Divisor
b) Highest Common Multiple
c) Highest Common Measure
d) Lowest Common Multiple
Answer: a
Clarification: GCM (Greatest Common Measure), GCF (Greatest Common Factor), HCF (Highest Common Factor) and HCF (Highest Common Divisor) are also known as GCD.

5. Which of the following is coprime number?
a) 54 and 24
b) 4 and 8
c) 6 and 12
d) 9 and 28
Answer: d
Clarification: Coprime numbers have GCD 1. So 9 and 28 are coprime numbers. While 54 and 24 have GCD 6, 4 and 8 have GCD 4, 6 and 12 have GCD 6.

6. In terms of Venn Diagram, which of the following expression gives GCD (Given A ꓵ B ≠ Ø)?
a) Multiplication of A U B terms
b) Multiplication of A ꓵ B terms
c) Multiplication of A*B terms
d) Multiplication of A-B terms

Answer: b
Clarification: In terms of Venn Diagram, the GCD is given by the intersection of two sets. So A ꓵ B gives the GCD. While A U B gives the LCM.

7. What is the GCD according to the given Venn Diagram?
gcd-lcm-recursion-multiple-choice-questions-answers-mcqs-q7
a) 2
b) 3
c) 5
d) 6

Answer: c
Clarification: In terms of Venn Diagram, the GCD is given by the intersection of two sets. So A ꓵ B gives the GCD. While A U B gives the LCM. So here A ꓵ B is 5.

8. What is the GCD of a and b?
a) a + b
b) gcd (a-b, b) if a>b
c) gcd (a+b, a-b)
d) a – b

Answer: b
Clarification: As per Euclid’s Algorithm, gcd (a, b) = gcd (a-b, b) if a > b or gcd (a, b) = gcd (a, b-a) if b > a.

9. What is the GCD of 48, 18, 0?
a) 24
b) 2
c) 3
d) 6

Answer: d
Clarification: GCD is largest positive integer that divides each of the integer. So the GCD of 48, 18, 0 is 6.

10. Is 9 and 28 coprime number?
a) True
b) False

Answer: a
Clarification: Coprime numbers have GCD 1. So 9 and 28 are coprime numbers.

11. If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then what is the expression called?
a) Bezout’s Identity
b) Multiplicative Identity
c) Sum of Product
d) Product of Sum

Answer: a
Clarification: If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then the expression is called Bezout’s Identity and p, q can be calculated by extended form of Euclidean algorithm.

12. Is gcd an associative function.
a) True
b) False

Answer: a
Clarification: The gcd function is an associative function as gcd (a, gcd (b, c)) = gcd (gcd (a, b), c).

13. Which is the correct term of the given relation, gcd (a, b) * lcm (a, b) =?
a) |a*b|
b) a + b
c) a – b
d) a / b

Answer: a
Clarification: The gcd is closely related to lcm as gcd (a, b) * lcm (a, b) = |a*b|.

14. Who gave the expression for the probability and expected value of gcd?
a) James E. Nymann
b) Riemann
c) Thomae
d) Euler

Answer: a
Clarification: In the year 1972, James E. Nymann showed some result to show the probability and expected value of gcd.

15. What is the computational complexity of Binary GCD algorithm where a and b are integers?
a) O (log a + log b)2)
b) O (log (a + b))
c) O (log ab)
d) O (log a-b)

Answer: a
Clarification: From the Binary GCD algorithm, it is found that the computational complexity is O (log a + log b)2) as the total number of steps in the execution is at most the total sum of number of bits of a and b.

250+ TOP MCQs on Towers of Hanoi using Recursion and Answers

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

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

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

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

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

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

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

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

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

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

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

b)

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

c)

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

d)

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

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

 
 

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

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

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

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

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

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

& Algorithms.

250+ TOP MCQs on Minimum Number of Jumps and Answers

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

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

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

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

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

3. Consider the following recursive implementation:

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

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

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

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

5. What is the output of the following program?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10. What is the output of the following program?

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

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

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

11. What is the output of the following program?

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

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

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

250+ TOP MCQs on Pigpen Cipher and Answers

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

1. Which of the following cipher replaces letters with symbols?
a) polybius square ciper
b) affine cipher
c) caesar cipher
d) pigpen cipher

Answer: d
Clarification: Pigpen cipher encrypts the plain text by replacing each letter with a corresponding symbol. Pigpen cipher is an example of geometric substitution cipher.

2. Which of the following is not an alternative name of pigpen cipher?
a) pen cipher
b) freemason’s cipher
c) napoleon cipher
d) tic-tac-toe cipher

Answer: a
Clarification: Pigpen cipher is also known by the names like:- freemason’s cipher, napoleon cipher, tic-tac-toe cipher, masonic cipher. It is a cipher which is believed to be used by freemasons in the 18th century.

3. Which of the following cipher was used by freemasons?
a) Vigenere cipher
b) Autokey cipher
c) Pigpen cipher
d) Hill cipher
View Answer

Answer: c
Clarification: Pigpen cipher is believed to be used by freemasons in the 18th century. Pigpen cipher is an example of geometric substitution cipher.

4. Choose the weakest cipher from the following?
a) vigenere cipher
b) rail fence cipher
c) hill cipher
d) pigpen cipher
Answer: d
Clarification: Pigpen cipher is the weakest cipher out of the given options. This is because it is a simple geometric substitution cipher so can be easily cracked using frequency analysis.

5. Which of the following is not a poly alphabetic substitution cipher?
a) vigenere cipher
b) one time pad cipher
c) play fair cipher
d) pigpen cipher

Answer: d
Clarification: Pigpen cipher is the only non poly alphabetic substitution cipher out of the given options. It is an example of geometric substitution cipher.

6. Pigpen cipher is an example of?
a) Mono alphabetic substitution cipher
b) Transposition cipher
c) Poly alphabetic substitution cipher
d) Geometric substitution cipher

Answer: a
Clarification: Pigpen cipher encrypts the plain text by replacing each letter with a corresponding symbol. Pigpen cipher is an example of geometric substitution cipher.

7. Pigpen cipher is less secure than a vigenere cipher.
a) True
b) False
Answer: a
Clarification: Vigenere cipher is more secure as compared to pigpen cipher. It is because pigpen cipher is geometric substitution cipher and vigenere cipher is poly alphabetic substitution cipher.

8. Pigpen cipher is not susceptible to frequency analysis.
a) True
b) False
Answer: b
Clarification: Pigpen cipher is a very weak cipher as it just replaces letters with corresponding symbols. It can be easily broken using frequency analysis.

9. What will be the ciphered text corresponding to plain text “ACT” if pigpen cipher is used for encryption?
a) _| |_ >
b) |_ > |_
c) _| |_<
d) |_< _|
Answer: a
Clarification: Pigpen cipher replaces letters of the plain text with corresponding symbols. These symbols are fragment of a grid.

10. What will be the plain text corresponding to ciphered text “|_ _| >” if pigpen cipher is used for encryption?
a) cat
b) hat
c) dog
d) rat
Answer: a
Clarification: Pigpen cipher replaces letters of the plain text with corresponding symbols. So by using the grid we can replace these symbols by their corresponding letters which are “cat” here.

11. What is common between affine cipher and pigpen cipher.
a) both are mono alphabetic substitution cipher
b) both are poly alphabetic substitution cipher
c) both can be cracked using frequency analysis
d) both are transposition cipher

Answer: c
Clarification: Both affine cipher and pigpen cipher can be broken using frequency analysis. Pigpen cipher is an example of geometric substitution cipher.

contest

250+ TOP MCQs on Columnar Transposition and Answers

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

1. Which of the following is not a type of traditional cipher?
a) Substitution cipher
b) Transposition cipher
c) Mono alphabetic cipher
d) PKCS cipher

Answer: d
Clarification: There are two types of the traditional cipher. One is transposition cipher and the other is substitution cipher. Whereas PKCS is a modern asymmetric cipher.

2. Which of the following cipher uses two keys to encrypt data?
a) substitution cipher
b) transposition cipher
c) symmetric cipher
d) asymmetric cipher

Answer: d
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. Asymmetric encryption is also known as?
a) Private key cryptography
b) Public key cryptography
c) Public private key cryptography
d) Traditional cryptography

Answer: b
Clarification: Asymmetric encryption is also known as public key cryptography. Asymmetric cipher makes use of 2 keys for the purpose of encryption.

4. Which of the following is an example of asymmetric encryption technique?
a) one-time pad
b) one-time password
c) DSA
d) blowfish

Answer: c
Clarification: Asymmetric cipher makes use of 2 keys for the purpose of encryption. DSA is an example of asymmetric encryption technique.

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

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

6. Which of the following ciphered text would have NOT used transposition cipher for encryption of the plain text “CIPHER”?
a) EPIHRC
b) EHIPCR
c) DTIPRC
d) HRIPEC

Answer: c
Clarification: We know that transposition cipher encrypts the plain text by shuffling the letters of the plain text. So out of the given options, only “DTIPRC” does not have the same set of letters as “CIPHER”.

7. Which of the following cipher is formed by applying columnar transposition cipher twice?
a) Rail Fence cipher
b) Route cipher
c) Double transposition cipher
d) One time pad
View Answer

Answer: c
Clarification: Double transposition cipher is formed by applying columnar transposition cipher twice. For the purpose of encryption, we may use the same key twice or we can use two different keys.

8. In which of the following cipher the plain text and the ciphered text does not have the same set of letters?
a) route cipher
b) columnar transposition cipher
c) myszkowski cipher
d) additive cipher

Answer: d
Clarification: In transposition cipher, the letters remain the same in ciphered and plain text. Their position is only changed whereas in substitution cipher the letters become different in encrypted text. As additive cipher is the only non transposition cipher out of the given options so it will be the correct option.

9. Columnar transposition cipher is harder to crack as compared to double transposition cipher?
a) true
b) false
View Answer

Answer: b
Clarification: Double transposition cipher is formed by applying columnar transposition cipher twice. So it is harder to crack than a simple columnar transposition cipher.

10. How many columns do we need to have in the table, that is used for encryption in columnar transposition cipher when a given keyword is “SECRET” and plain text is “”?
a) 4
b) 5
c) 6
d) 7

Answer: c
Clarification: The number of columns in the table used for the purpose encryption in columnar transposition cipher will always be equal to the number of letters in the keyword. So in this case it will be equal to 6.

11. What will be the encrypted text corresponding to plain text “CLASSIFIED” using columnar transposition cipher with a keyword as “GAMES”?
a) LFDSIASECI
b) SECIAISDFL
c) CILFAISESD
d) LFSECIAISD
Answer: d
Clarification: For encrypting using columnar cipher we have to arrange the letters of the plain text in a table which has the same number of columns as the letters of the keyword. Then the letters of the keyword are arranged in alphabetical order and we read along each column.
3 1 4 2 5
G A M E S
C L A S S
I F I E D
So the ciphered text will be “IFSECIAISD”.

12. How many rows will the letters of the plain text occupy in the table, that is used for encryption in columnar transposition cipher when a given keyword is “SECRET” and plain text is “”?
a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: The number of columns in the table used for the purpose encryption in columnar transposition cipher will always be equal to the number of letters in the keyword.So when we will write the letters of the plain text row wise then there will be 2 rows of plain text in this case. The table is shown below :-
S E C R E T
1 S A N F O U
2 N D R Y

13. Which of the following statement is not true regarding columnar transposition cipher?
a) it is a weak cipher
b) probability of error is high while deciphering
c) it cannot be combined with other ciphers
d) it is a traditional symmetric cipher

Answer: c
Clarification: Although columnar transposition cipher is a weak cipher in itself. But it can be combined with other substitution ciphers so as to improve its security. The probability of error remains high while decoding columnar cipher as it is a lengthy process.

& Algorithms.

Multiple Choice Questions and Answers.