Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Maximum Flow Problem”.

1. What does Maximum flow problem involve?
a) finding a flow between source and sink that is maximum
b) finding a flow between source and sink that is minimum
c) finding the shortest path between source and sink
d) computing a minimum spanning tree
Answer: a
Clarification: The maximum flow problem involves finding a feasible flow between a source and a sink in a network that is maximum and not minimum.

2. A network can have only one source and one sink.
a) False
b) True

Answer: b
Clarification: A network can have only one source and one sink inorder to find the feasible flow in a weighted connected graph.

3. What is the source?
a) Vertex with no incoming edges
b) Vertex with no leaving edges
c) Centre vertex
d) Vertex with the least weight

Answer: a
Clarification: Vertex with no incoming edges is called as a source. Vertex with no leaving edges is called as a sink.

4. Which algorithm is used to solve a maximum flow problem?
a) Prim’s algorithm
b) Kruskal’s algorithm
c) Dijkstra’s algorithm
d) Ford-Fulkerson algorithm

Answer: d
Clarification: Ford-fulkerson algorithm is used to compute the maximum feasible flow between a source and a sink in a network.

5. Does Ford- Fulkerson algorithm use the idea of?
a) Naïve greedy algorithm approach
b) Residual graphs
c) Minimum cut
d) Minimum spanning tree

Answer: b
Clarification: Ford-Fulkerson algorithm uses the idea of residual graphs which is an extension of naïve greedy approach allowing undo operations.

6. The first step in the naïve greedy algorithm is?
a) analysing the zero flow
b) calculating the maximum flow using trial and error
c) adding flows with higher values
d) reversing flow if required

Answer: a
Clarification: The first step in the naïve greedy algorithm is to start with the zero flow followed by adding edges with higher values.

7. Under what condition can a vertex combine and distribute flow in any manner?
a) It may violate edge capacities
b) It should maintain flow conservation
c) The vertex should be a source vertex
d) The vertex should be a sink vertex
View Answer

Answer: b
Clarification: A vertex can combine and distribute flow in any manner but it should not violate edge capacities and it should maintain flow conservation.

8. Find the maximum flow from the following graph.

a) 22
b) 17
c) 15
d) 20
Answer: c
Clarification: Initially, zero flow is computed. Then, computing flow= 7+1+5+2=15. Hence, maximum flow=15.

9. A simple acyclic path between source and sink which pass through only positive weighted edges is called?
a) augmenting path
b) critical path
c) residual path
d) maximum path
Answer: a
Clarification: Augmenting path between source and sink is a simple path without cycles. Path consisting of zero slack edges is called critical path.

10. In what time can an augmented path be found?
a) O(|E| log |V|)
b) O(|E|)
c) O(|E|²)
d) O(|E|² log |V|)
Answer: b
Clarification: An augmenting path can be found in O(|E|) mathematically by an unweighted shortest path algorithm.

11. Dinic’s algorithm runs faster than the Ford-Fulkerson algorithm.
a) true
b) false

Answer: a
Clarification: Dinic’s algorithm includes construction of level graphs and resLidual graphs and finding of augmenting paths along with blocking flow and is faster than the Ford-Fulkerson algorithm.

12. What is the running time of an unweighted shortest path algorithm whose augmenting path is the path with the least number of edges?
a) O(|E|)
b) O(|E||V|)
c) O(|E|²|V|)
d) O(|E| log |V|)
Answer: c
Clarification: Each augmenting step takes O(|E|) using an unweighted shortest path algorithm yielding a O(|E|2|V|) bound on the running time.

13. Who is the formulator of Maximum flow problem?
a) Lester R. Ford and Delbert R. Fulkerson
b) T.E. Harris and F.S. Ross
c) Y.A. Dinitz
d) Kruskal
Answer: b
Clarification: The first ever people to formulate Maximum flow problem were T.E. Harris and F.S. Ross. Lester R. Ford and Delbert R. Fulkerson formulated Ford- Fulkerson algorithm.

14. What is the running time of Dinic’s blocking flow algorithm?
a) O(V²E)
b) O(VE²)
c) O(V³)
d) O(E max |f|)

Answer: a
Clarification: The running time of Dinic’s blocking flow algorithm is O(V²E). The running of Ford-Fulkerson algorithm is O(E max |f|).

15. How many constraints does flow have?
a) one
b) three
c) two
d) four
Answer: c
Clarification: A flow is a mapping which follows two constraints- conservation of flows and capacity constraints.

Data Structure Question Bank on “Sum of Digits of a Number using Recursion”.

1. Which of the following methods can be used to find the sum of digits of a number?
a) Recursion
b) Iteration
c) Greedy algorithm
d) Both recursion and iteration

Answer: d
Clarification: Both recursion and iteration can be used to find the sum of digits of a number.

2. What can be the maximum sum of digits for a 4 digit number?
a) 1
b) 16
c) 36
d) 26

Answer: c
Clarification: The sum of digits will be maximum when all the digits are 9. Thus, the sum will be maximum for the number 9999, which is 36.

3. What can be the minimum sum of digits for a 4 digit number?
a) 0
b) 1
c) 16
d) 36

Answer: b
Clarification: The sum of digits will be minimum for the number 1000 and the sum is 1.

4. Consider the following iterative implementation to find the sum of digits of a number:

#include
int sum_of_digits(int n)
{
      int sm = 0;
      while(n != 0)
      {
          _________;
          n /= 10;
      }
      return sm;
}
int main()
{
      int n = 1234;
      int ans = sum_of_digits(n);
      printf("%d",ans);
      return 0;
}

Which of the following lines should be inserted to complete the above code?
a) sm += n
b) sm += n%10
c) sm += n-10
d) sm += n/10

Answer: b
Clarification: The line “sm += n % 10” adds the last digit(LSB) of the number to the current sum. Thus, the line “sm += n%10” should be added to complete the above code.

5. What is the output of the following code?

#include
int sum_of_digits(int n)
{
      int sm = 0;
      while(n != 0)
      {
          sm += n%10;
          n /= 10;
      }
      return sm;
}
int main()
{
      int n = 1234;
      int ans = sum_of_digits(n);
      printf("%d",ans);
      return 0;
}

a) 1
b) 3
c) 7
d) 10

Answer: d
Clarification: The above code prints the sum of digits of the number 1234, which is 10.

6. Consider the following recursive implementation to find the sum of digits of number:

#include
int recursive_sum_of_digits(int n)
{
      if(n == 0)
        return 0;
      return _________;
}
int main()
{
      int n = 1201;
      int ans = recursive_sum_of_digits(n);
      printf("%d",ans);
      return 0;
}

Which of the following lines should be inserted to complete the above code?
a) (n / 10) + recursive_sum_of_digits(n % 10)
b) (n) + recursive_sum_of_digits(n % 10)
c) (n % 10) + recursive_sum_of_digits(n / 10)
d) (n % 10) + recursive_sum_of_digits(n % 10)
View Answer

Answer: c
Clarification: The line “(n % 10) + recursive_sum_of_digits(n / 10)” should be inserted to complete the above code.

7. What is the time complexity of the following recursive implementation to find the sum of digits of a number n?

#include
int recursive_sum_of_digits(int n)
{
      if(n == 0)
        return 0;
      return _________;
}
int main()
{
      int n = 1201;
      int ans = recursive_sum_of_digits(n);
      printf("%d",ans);
      return 0;
}

a) O(n)
b) O(1)
c) O(len(n)), where len(n) is the number of digits in n
d) O(1/2)

Answer: c
Clarification: The time complexity of the above recursive implementation to find the sum of digits of a number is O(len(n)).

8. What is the output of the following code?

#include
int recursive_sum_of_digits(int n)
{
      if(n == 0)
        return 0;
      return n % 10 + recursive_sum_of_digits(n/10);
}
int main()
{
      int n = 1234321;
      int ans = recursive_sum_of_digits(n);
      printf("%d",ans);
      return 0;
}

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

Answer: b
Clarification: The above code prints the sum of digits of the number 1234321, which is 16.

9. How many times is the function recursive_sum_of_digits() called when the following code is executed?

#include
int recursive_sum_of_digits(int n)
{
      if(n == 0)
        return 0;
      return n % 10 + recursive_sum_of_digits(n/10);
}
int main()
{
      int n = 1201;
      int ans = recursive_sum_of_digits(n);
      printf("%d",ans);
      return 0;
}

a) 6
b) 7
c) 5
d) 9
Answer: c
Clarification: The function recursive_sum_of_digits() is called 8 times, when the following code is executed.

10. You have to find the sum of digits of a number given that the number is always greater than 0. Which of the following base cases can replace the base case for the below code?

#include
int recursive_sum_of_digits(int n)
{
      if(n == 0)
        return 0;
      return n % 10 + recursive_sum_of_digits(n/10);
}
int main()
{
      int n = 1201;
      int ans = recursive_sum_of_digits(n);
      printf("%d",ans);
      return 0;
}

a) if(n == 0) return 1
b) if(n == 1) return 0
c) if(n == 1) return 1
d) no need to modify the base case
Answer: d
Clarification: None of the above mentioned base cases can replace the base case if(n == 0) return 0.

11. What is the output of the following code?

#include
int recursive_sum_of_digits(int n)
{
      if(n == 0)
        return 0;
      return n % 10 + recursive_sum_of_digits(n/10);
}
int main()
{
      int n = 10000;
      int ans = recursive_sum_of_digits(n);
      printf("%d",ans);
      return 0;
}

a) 0
b) 1
c) runtime error
d) -1
Answer: b
Clarification: The program prints the sum of digits of the number 10000, which is 1.

12. What is the output of the following code?

#include
int cnt =0;
int my_function(int n, int sm)
{
      int i, tmp_sm;
      for(i=1;i<=n;i++)
      {
          tmp_sm = recursive_sum_of_digits(i);
          if(tmp_sm == sm)
            cnt++;
      }
      return cnt;
}
int recursive_sum_of_digits(int n)
{
      if(n == 0)
        return 0;
      return n % 10 + recursive_sum_of_digits(n/10);
}
int main()
{
      int n = 20, sum = 3;
      int ans = my_function(n,sum);
      printf("%d",ans);
      return 0;
}

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

Answer: c
Clarification: The code prints the count of numbers between 1 and 20 such that the sum of their digits is 3. There are only two such numbers: 3 and 12.

Data Structures & Algorithms Multiple Choice Questions on “Master’s Theorem – 2”.

1. Solve the following recurrence using Master’s theorem.
T(n) = 4T (n/2) + n²
a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n²log n)
d) T(n) = O(n²)

Answer: c
Clarification: The given recurrence can be solved by using the second case of Master’s theorem.
T(n) = O(nc log n) = Here nc = n²
So the solution becomes T(n) = O(n²log n).

2. Solve the following recurrence using Master’s theorem.
T(n) = T (n/2) + 2ⁿ
a) T(n) = O(n²)
b) T(n) = O(n² log n)
c) T(n) = O(2ⁿ)
d) cannot be solved

Answer: c
Clarification: The given recurrence can be solved by using the third case (as f(n) > log21) of Master’s theorem.
T(n) = O(f(n)) = Here f(n) = 2n.
So the solution becomes T(n) = O(2n).

3. Solve the following recurrence using Master’s theorem.
T(n) = 16T (n/4) + n
a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n²log n)
d) T(n) = O(n²)
View Answer

Answer: d
Clarification: The given recurrence can be solved by using the first case of Master’s theorem. So the solution becomes T(n) = O(n²).

4. Solve the following recurrence using Master’s theorem.
T(n) = 2T (n/2) + n/ log n
a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n²log n)
d) cannot be solved using master’s theorem

Answer: d
Clarification: The given recurrence cannot be solved by using the Master’s theorem. It is because this recurrence relation does not fit into any case of Master’s theorem.

5. Solve the following recurrence using Master’s theorem.
T(n) = 0.7 T (n/2) + 1/n
a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n²log n)
d) cannot be solved using master’s theorem

Answer: d
Clarification: The given recurrence cannot be solved by using the Master’s theorem. It is because in this recurrence relation a < 1 so master’s theorem cannot be applied.

6. Solve the following recurrence using Master’s theorem.
T(n) = 4 T (n/2) + n!
a) T(n) = O(n!)
b) T(n) = O(n! log n)
c) T(n) = O(n²log n)
d) cannot be solved using master’s theorem
Answer: a
Clarification: The given recurrence can be solved by using the third case of Master’s theorem. So the solution becomes T(n) = O(n!).

7. Solve the following recurrence using Master’s theorem.
T(n) = 4T (n/4) + n log n
a) T(n) = O(n (log n)²)
b) T(n) = O(n log n)
c) T(n) = O(n²log n)
d) cannot be solved using master’s theorem

Answer: a
Clarification: The given recurrence can be solved by using the extended second case of Master’s theorem. So the solution becomes T(n) = O(n (log n)²).

8. What will be the recurrence relation of the following code?

Int sum(int n)
{
   If(n==1)
       return 1;
   else
       return n+sum(n-1);
}

a) T(n) = T(n/2) + n
b) T(n) = T(n-1) + n
c) T(n) = T(n-1) + O(1)
d) T(n) = T(n/2) + O(1)
Answer: c
Clarification: As after every recursive call the integer up to which the sum is to be calculated decreases by 1. So the recurrence relation for the given code will be T(n) = T(n-1) + O(1).

9. What will be the recurrence relation of the following code?

int xpowy(int x, int n)
if (n==0) return 1;
if (n==1) return x;
if ((n % 2) == 0)
return xpowy(x*x, n/2);
else
return xpowy(x*x, n/2) * x;

a) T(n) = T(n/2) + n
b) T(n) = T(n-1) + n
c) T(n) = T(n-1) + O(1)
d) T(n) = T(n/2) + O(1)

Answer: d
Clarification: As after every recursive call the integer up to which the power is to be calculated decreases by half. So the recurrence relation for the given code will be T(n) = T(n/2) + O(1). It can be solved by using master’s theorem.

10. What will be the time complexity of the following code?

int xpowy(int x, int n)
{
    if (n==0) 
        return 1;
    if (n==1) 
        return x;
    if ((n % 2) == 0)
        return xpowy(x*x, n/2);
    else
        return xpowy(x*x, n/2) * x;
}

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

Answer: a
Clarification: As the recurrence relation of the code is given by T(n) = T(n/2) + O(1) so it can be solved by using master’s theorem second case.

Data Structure Multiple Choice Questions on “Matrix-chain Multiplication”.

1. Which of the following methods can be used to solve the matrix chain multiplication problem?
a) Dynamic programming
b) Brute force
c) Recursion
d) Dynamic Programming, Brute force, Recursion

Answer: d
Clarification: Dynamic Programming, Brute force, Recursion methods can be used to solve the matrix chain multiplication problem.

2. Which of the following is the recurrence relation for the matrix chain multiplication problem where mat[i-1] * mat[i] gives the dimension of the ith matrix?
a) dp[i,j] = 1 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]}
b) dp[i,j] = 0 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]}
c) dp[i,j] = 1 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].
d) dp[i,j] = 0 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].

Answer: d
Clarification: The recurrence relation is given by:
dp[i,j] = 0 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].

3. Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?
a) 10*20
b) 20*30
c) 10*30
d) 10*20*30

Answer: d
Clarification: The number of multiplications required is 10*20*30.

4. Consider the matrices P, Q and R which are 10 x 20, 20 x 30 and 30 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the three matrices?
a) 18000
b) 12000
c) 24000
d) 32000

Answer: a
Clarification: The minimum number of multiplications are 18000. This is the case when the matrices are parenthesized as (P*Q)*R.

5. Consider the matrices P, Q, R and S which are 20 x 15, 15 x 30, 30 x 5 and 5 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the four matrices?
a) 6050
b) 7500
c) 7750
d) 12000
Answer: c
Clarification: The minimum number of multiplications required is 7750.

6. Consider the brute force implementation in which we find all the possible ways of multiplying the given set of n matrices. What is the time complexity of this implementation?
a) O(n!)
b) O(n³)
c) O(n²)
d) Exponential
Answer: d
Clarification: The time complexity of finding all the possible ways of multiplying a set of n matrices is given by (n-1)^th Catalan number which is exponential.

7. Consider the following dynamic programming implementation of the matrix chain problem:

#include
#include
int mat_chain_multiplication(int *mat, int n)
{
      int arr[n][n];
      int i,k,row,col,len;
      for(i=1;i<n;i++)
          arr[i][i] = 0;
      for(len = 2; len < n; len++)
      {
           for(row = 1; row <= n - len + 1; row++)
           {
               col = row + len - 1;
               arr[row][col] = INT_MAX;
               for(k = row; k <= col - 1; k++)
               {
                    int tmp = ________________________;
                    if(tmp < arr[row][col])
                    arr[row][col] = tmp;
               }
           }
      }
      return arr[1][n - 1];
}
int main()
{
     int mat[6] = {20,5,30,10,40};
     int ans = mat_chain_multiplication(mat,5);
     printf("%d",ans);
     return 0;
}

Which of the following lines should be inserted to complete the above code?
a) arr[row][k] – arr[k + 1][col] + mat[row – 1] * mat[k] * mat[col];
b) arr[row][k] + arr[k + 1][col] – mat[row – 1] * mat[k] * mat[col];
c) arr[row][k] + arr[k + 1][col] + mat[row – 1] * mat[k] * mat[col];
d) arr[row][k] – arr[k + 1][col] – mat[row – 1] * mat[k] * mat[col];

Answer: c
Clarification: The line arr[row][k] + arr[k + 1][col] + mat[row – 1] * mat[k] * mat[col] should be inserted to complete the above code.

8. What is the time complexity of the following dynamic programming implementation of the matrix chain problem?

#include
#include
int mat_chain_multiplication(int *mat, int n)
{
      int arr[n][n];
      int i,k,row,col,len;
      for(i=1;i<n;i++)
          arr[i][i] = 0;
      for(len = 2; len < n; len++)
      {
           for(row = 1; row <= n - len + 1; row++)
           {
               col = row + len - 1;
               arr[row][col] = INT_MAX;
               for(k = row; k <= col - 1; k++)
               {
                    int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
                    if(tmp < arr[row][col])
                    arr[row][col] = tmp;
               }
           }
      }
      return arr[1][n - 1];
}
int main()
{
     int mat[6] = {20,5,30,10,40};
     int ans = mat_chain_multiplication(mat,5);
     printf("%d",ans);
     return 0;
}

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

Answer: d
Clarification: The time complexity of the above dynamic programming implementation of the matrix chain multiplication is O(n³).

9. What is the space complexity of the following dynamic programming implementation of the matrix chain problem?

#include
#include
int mat_chain_multiplication(int *mat, int n)
{
      int arr[n][n];
      int i,k,row,col,len;
      for(i=1;i<n;i++)
          arr[i][i] = 0;
      for(len = 2; len < n; len++)
      {
           for(row = 1; row <= n - len + 1; row++)
           {
               col = row + len - 1;
               arr[row][col] = INT_MAX;
               for(k = row; k <= col - 1; k++)
               {
                    int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
                    if(tmp < arr[row][col])
                    arr[row][col] = tmp;
               }
           }
      }
      return arr[1][n - 1];
}
int main()
{
     int mat[6] = {20,5,30,10,40};
     int ans = mat_chain_multiplication(mat,5);
     printf("%d",ans);
     return 0;
}

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

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

10. What is the output of the following code?

#include
#include
int mat_chain_multiplication(int *mat, int n)
{
     int arr[n][n];
     int i,k,row,col,len;
     for(i=1;i<n;i++)
         arr[i][i] = 0;
     for(len = 2; len < n; len++)
     {
          for(row = 1; row <= n - len + 1; row++)
          {
               col = row + len - 1;
               arr[row][col] = INT_MAX;
               for(k = row; k <= col - 1; k++)
               {
                    int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
                    if(tmp < arr[row][col])
                    arr[row][col] = tmp;
               }
           }
     }
     return arr[1][n - 1];
}
int main()
{
     int mat[6] = {20,30,40,50};
     int ans = mat_chain_multiplication(mat,4);
     printf("%d",ans);
     return 0;
}

a) 64000
b) 70000
c) 120000
d) 150000

Answer: a
Clarification: The program prints the minimum number of multiplications required, which is 64000.

11. What is the value stored in arr[2][3] when the following code is executed?

#include
#include
int mat_chain_multiplication(int *mat, int n)
{
     int arr[n][n];
     int i,k,row,col,len;
     for(i=1;i<n;i++)
         arr[i][i] = 0;
     for(len = 2; len < n; len++)
     {
          for(row = 1; row <= n - len + 1; row++)
          {
               col = row + len - 1;
               arr[row][col] = INT_MAX;
               for(k = row; k <= col - 1; k++)
               {
                     int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
                     if(tmp < arr[row][col])
                     arr[row][col] = tmp;
               }
          }
     }
     return arr[1][n - 1];
}
int main()
{
     int mat[6] = {20,30,40,50};
     int ans = mat_chain_multiplication(mat,4);
     printf("%d",ans);
     return 0;
}

a) 64000
b) 60000
c) 24000
d) 12000

Answer: b
Clarification: The value stored in arr[2][3] when the above code is executed is 60000.

12. What is the output of the following code?

#include
#include
int mat_chain_multiplication(int *mat, int n)
{
     int arr[n][n];
     int i,k,row,col,len;
     for(i=1;i<n;i++)
         arr[i][i] = 0;
     for(len = 2; len < n; len++)
     {
          for(row = 1; row <= n - len + 1; row++)
          {
               col = row + len - 1;
               arr[row][col] = INT_MAX;
               for(k = row; k <= col - 1; k++)
               {
                    int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
                    if(tmp < arr[row][col])
                    arr[row][col] = tmp;
               }
          }
     }
     return arr[1][n-1];
}
int main()
{
     int mat[6] = {10,10,10,10,10,10};
     int ans = mat_chain_multiplication(mat,6);
     printf("%d",ans);
     return 0;
}

a) 2000
b) 3000
c) 4000
d) 5000
View Answer

Answer: c
Clarification: The program prints the minimum number of multiplications required to multiply the given matrices, which is 4000.

13. What is the output of the following code?

#include
#include
int mat_chain_multiplication(int *mat, int n)
{
     int arr[n][n];
     int i,k,row,col,len;
     for(i=1;i<n;i++)
         arr[i][i] = 0;
     for(len = 2; len < n; len++)
     {
          for(row = 1; row <= n - len + 1; row++)
          { 
               col = row + len - 1;
               arr[row][col] = INT_MAX;
               for(k = row; k <= col - 1; k++)
               {
                    int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
                    if(tmp < arr[row][col])
                    arr[row][col] = tmp;
               }
          }
     }
     return arr[1][n-1];
}
int main()
{
     int mat[6] = {20,25,30,35,40};
     int ans = mat_chain_multiplication(mat,5);
     printf("%d",ans);
     return 0;
}

a) 32000
b) 28000
c) 64000
d) 70000
View Answer

Answer: c
Clarification: The output of the program is 64000.

and Answers.

Data Structures & Algorithms Multiple Choice Questions on “Vigenère Cipher”.

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

Answer: c
Clarification: Cipher is an algorithm for performing encryption or decryption. In cryptography, a set of defined steps are followed to generate ciphers. These are necessary to prevent data breach.

2. Vigenere cipher is an example of ______________
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher
Answer: b
Clarification: Vigenere cipher is a substitution cipher. It falls under the category of poly alphabetic cipher as it uses multiple substitution at different positions in order to cipher the plain text.

3. Encryption in Vigenere cipher is done using _________
a) vigenere formula
b) vigenere cycle
c) vigenere square
d) vigenere addition

Answer: c
Clarification: Encryption of plain text using vigenre cipher is done by making use of vigenere table. It is also known as vigenere square.

4. Which of the following correctly defines poly alphabetic cipher?
a) a substitution based cipher which uses multiple substitution at different positions
b) a substitution based cipher which uses fixed substitution over entire message
c) a transposition based cipher which uses multiple substitution at different positions
d) a transposition based cipher which uses fixed substitution over entire message

Answer: a
Clarification: Poly alphabetic cipher is a type of substitution cipher. It uses multiple substitution at different positions in order to cipher the plain text.

5. Which of the following is not a type of poly alphabetic cipher?
a) Rotor cipher
b) Hill cipher
c) One time pad cipher
d) Multiplicative cipher

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

6. Vigenere table 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 vigenre cipher is done by making use of vigenere table. It consists of 26 rows and 26 columns which have alphabets written 26 times. These are shifted towards left after each row.

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

Answer: a
Clarification: Keyword cipher is less secure than vigenere cipher. It is due to the fact that keyword cipher is mono alphabetic and thus can be cracked using frequency analysis. But vigenere cipher being a poly alphabetic cipher cannot be deciphered using this method.

8. What will be the plain text corresponding to cipher text “PROTO” if vigenere cipher is used with keyword as “HELLO”?
a)
b) WORLD
c) INDIA
d) AMERICA
Answer: c
Clarification: Vigenere cipher is a type of poly alphabetic substitution which uses vigenere table for making substitutions in the plain text. Using the table we find the plain text to be “INDIA”.

9. Which cipher is represented by the following function?

public class Cipher
{
    public static String encrypt(String text, final String key)
    {
        String res = "";
        text = text.toUpperCase();
        for (int i = 0, j = 0; i < text.length(); i++)
        {
            char c = text.charAt(i);
            if (c < 'A' || c > 'Z')
                continue;
            res += (char) ((c + key.charAt(j) - 2 * 'A') % 26 + 'A');
            j = ++j % key.length();
        }
        return res;
    }

a) vigenere cipher
b) hill cipher
c) keyword cipher
d) rotor cipher
Answer: a
Clarification: The given function represents the function of hill cipher. It is a type of poly alphabetic substitution which makes use of the vigenere table for making substitutions in the plain text.

10. In which of the following cipher the plain text and the ciphered text does not have a same number of letters?
a) affine cipher
b) vigenere cipher
c) columnar cipher
d) additive cipher

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

11. What will be the ciphered text if the string “” is given as input to the code of vigenere cipher with keyword as “HELLO”?
a) UEWIIDKLL
b) ZEYQCOCM
c) ZEYQCBROCM
d) ZEYQCBROCMJDH

Answer: c
Clarification: Vigenere cipher is a type of poly alphabetic substitution which uses vigenere table for making substitutions in the plain text. Using the table we find the solution to be ZEYQCBROCM.

& Algorithms.

here is

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

1. Which of the following cipher makes use of linear algebra for encrypting data?
a) polybius square cipher
b) affine cipher
c) caesar cipher
d) rail fence cipher

Answer: b
Clarification: Affine cipher is the only cipher out of the given options that make use of linear algebra for the purpose of encryption. It is a type of mono alphabetic cipher.

2. Which of the following cipher requires only one key for decoding the ciphered text?
a) Affine cipher
b) RSA
c) DSA
d) PKCS

Answer: a
Clarification: Asymmetric cipher makes use of 2 keys for the purpose of encryption. As affine cipher is the only symmetric cipher out of the given options so it requires only one key.

3. Choose the weakest cipher from the following?
a) Vigenere cipher
b) Autokey cipher
c) Affine cipher
d) Hill cipher

Answer: c
Clarification: Affine cipher is the weakest cipher out of the given options as it is a mono alphabetic cipher and other options are poly alphabetic ciphers. So it is quite vulnerable to frequency analysis.

4. What is the formula used for encryption of data using affine cipher(a,b are constants and x is the numerical equivalent of a letter to be encrypted)?
a) ax+b
b) (ax+b)%26
c) ax²+bx
d) (ax²+bx)%26
View Answer

Answer: b
Clarification: Affine cipher uses linear algebra for the purpose of encryption. It uses the formula (ax+b)%26 for this purpose.

5. What is the formula used for decoding the ciphered text using affine cipher(a,b are constants and x is the numerical equivalent of a letter to be encrypted)?
a) a^-1(x-b)%26
b) (ax+b)%26
c) b^-1(x-a)%26
d) b^-1(x-a)

Answer: a
Clarification: Affine cipher uses linear algebra for the purpose of encryption. It uses the formula a^-1(x-b)%26 for decryption of ciphered text.

6. Affine cipher is an example of?
a) Mono alphabetic cipher
b) Poly alphabetic cipher
c) Transposition cipher
d) Asymmetric cipher

Answer: a
Clarification: Affine cipher falls in the category of mono alphabetic substitution cipher. It uses linear algebra for encrypting the plain text.

7. Affine cipher is less secure than caesar cipher.
a) true
b) false
Answer: b
Clarification: Affine cipher is more secure as compared to caesar cipher. But affine cipher is a very weak cipher as it can be easily broken using frequency analysis.

8. Affine cipher is not susceptible to frequency analysis.
a) true
b) false

Answer: b
Clarification: Affine cipher is a very weak cipher as it can be easily broken using frequency analysis. It can be easily cracked even if 2 characters are known.

9. What will be the ciphered text corresponding to plain text “” if an affine cipher is used with key values as a=5, b=10?
a) wkxjcgxzra
b) gkxteuxfzw
c) ukxhmyxdfg
d) rfsexbsumv
Answer: a
Clarification: Affine cipher uses linear algebra for the purpose of encryption. It uses the formula (ax+b)%26 for this purpose. So the ciphered text will be “wkxjcgxzra”.

10. What will be the plain text corresponding to ciphered text “rmw ” if an affine cipher is used with key values as a=5, b=10?
a) csk
b) kkr
c) srt
d) msd

Answer: c
Clarification: Affine cipher uses linear algebra for the purpose of encryption It uses the formula a^-1(x-b)%26 for decryption of ciphered text. So the plain text will be “srt”.

11. While choosing the value of a and m (m is the no. of alphabets) in affine cipher it must be ensured that?
a) a and m are prime numbers
b) a and m are odd numbers
c) a and m are coprime
d) a and m are even numbers

Answer: c
Clarification: While choosing the values of a and m it should be ensured that a and m are coprime. Otherwise decoding the ciphered text would be difficult.

contest