300+ REAL TIME Data Structures & Algorithms Objective Questions & Answers 2023

250+ TOP MCQs on Depth First Search and Answers

Data Structure Multiple Choice Questions on “Depth First Search”.

1. Depth First Search is equivalent to which of the traversal in the Binary Trees?
a) Pre-order Traversal
b) Post-order Traversal
c) Level-order Traversal
d) In-order Traversal
Answer: a
Clarification: In Depth First Search, we explore all the nodes aggressively to one path and then backtrack to the node. Hence, it is equivalent to the pre-order traversal of a Binary Tree.

2. Time Complexity of DFS is? (V – number of vertices, E – number of edges)
a) O(V + E)
b) O(V)
c) O(E)
d) O(V*E)
Answer: a
Clarification: The Depth First Search explores every node once and every edge once (in worst case), so it’s time complexity is O(V + E).

3. The Data structure used in standard implementation of Breadth First Search is?
a) Stack
b) Queue
c) Linked List
d) Tree
Answer: a
Clarification: The Depth First Search is implemented using recursion. So, stack can be used as data structure to implement depth first search.

4. The Depth First Search traversal of a graph will result into?
a) Linked List
b) Tree
c) Graph with back edges
d) Array

Answer: b
Clarification: The Depth First Search will make a graph which don’t have back edges (a tree) which is known as Depth First Tree.

5. A person wants to visit some places. He starts from a vertex and then wants to visit every vertex till it finishes from one vertex, backtracks and then explore other vertex from same vertex. What algorithm he should use?
a) Depth First Search
b) Breadth First Search
c) Trim’s algorithm
d) Kruskal’s Algorithm

Answer: a
Clarification: This is the definition of the Depth First Search. Exploring a node, then aggressively finding nodes till it is not able to find any node.

6. Which of the following is not an application of Depth First Search?
a) For generating topological sort of a graph
b) For generating Strongly Connected Components of a directed graph
c) Detecting cycles in the graph
d) Peer to Peer Networks
Answer: d
Clarification: Depth First Search is used in the Generation of topological sorting, Strongly Connected Components of a directed graph and to detect cycles in the graph. Breadth First Search is used in peer to peer networks to find all neighbourhood nodes.

7. When the Depth First Search of a graph is unique?
a) When the graph is a Binary Tree
b) When the graph is a Linked List
c) When the graph is a n-ary Tree
d) When the graph is a ternary Tree

Answer: b
Clarification: When Every node will have one successor then the Depth First Search is unique. In all other cases, when it will have more than one successor, it can choose any of them in arbitrary order.

8. Regarding implementation of Depth First Search using stacks, what is the maximum distance between two nodes present in the stack? (considering each edge length 1)
a) Can be anything
b) 0
c) At most 1
d) Insufficient Information

Answer: a
Clarification: In the stack, at a time, there can be nodes which can differ in many levels. So, it can be the maximum distance between two nodes in the graph.

9. In Depth First Search, how many times a node is visited?
a) Once
b) Twice
c) Equivalent to number of indegree of the node
d) Thrice

Answer: c
Clarification: In Depth First Search, we have to see whether the node is visited or not by it’s ancestor. If it is visited, we won’t let it enter it in the stack.

Multiple Choice Questions and Answers.

250+ TOP MCQs on Chromatic Number and Answers

Data Structures & Algorithms Multiple Choice Questions on “Chromatic Number”.

1. What is the definition of graph according to graph theory?
a) visual representation of data
b) collection of dots and lines
c) collection of edges
d) collection of vertices
Answer: b
Clarification: According to the graph theory a graph is the collection of dots and lines. Vertices are also called dots and lines are also called edges.

2. What is the condition for proper coloring of a graph?
a) two vertices having a common edge should not have same color
b) two vertices having a common edge should always have same color
c) all vertices should have a different color
d) all vertices should have same color

Answer: a
Clarification: The condition for proper coloring of graph is that two vertices which share a common edge should not have the same color. If it uses k colors in the process then it is called k coloring of graph.

3. The number of colors used by a proper coloring graph is called?
a) k coloring graph
b) x coloring graph
c) m coloring graph
d) n coloring graph

Answer: a
Clarification: A proper graph ensures that two vertices which share a common edge should not have the same color. If it uses k colors in the process then it is called k coloring of graph.

4. What is a chromatic number?
a) The maximum number of colors required for proper edge coloring of graph
b) The maximum number of colors required for proper vertex coloring of graph
c) The minimum number of colors required for proper vertex coloring of graph
d) The minimum number of colors required for proper edge coloring of graph

Answer: c
Clarification: The minimum number of colors required for proper vertex coloring of graph is called chromatic number whereas the minimum number of colors required for proper edge coloring of graph is called chromatic index of a graph.

5. What will be the chromatic number for an empty graph having n vertices?
a) 0
b) 1
c) 2
d) n
View Answer

Answer: b
Clarification: An empty graph is a graph without any edges. So the chromatic number for such a graph will be 1.

6. What will be the chromatic number for an bipartite graph having n vertices?
a) 0
b) 1
c) 2
d) n

Answer: c
Clarification: A bipartite graph is graph such that no two vertices of the same set are adjacent to each other. So the chromatic number for such a graph will be 2.

7. Calculating the chromatic number of a graph is a
a) P problem
b) NP hard problem
c) NP complete problem
d) cannot be identified as any of the given problem types

Answer: c
Clarification: Chromatic number of an arbitrary graph cannot be determined by using any convenient method. So calculating the chromatic number of a graph is an NP complete problem.

8. What will be the chromatic number for a line graph having n vertices?
a) 0
b) 1
c) 2
d) n

Answer: d
Clarification: A line graph of a simple graph is obtained by connecting two vertices with an edge. A line graph has a chromatic number of n.

9. What will be the chromatic number for a complete graph having n vertices?
a) 0
b) 1
c) n
d) n!

Answer: c
Clarification: A complete graph is the one in which each vertex is directly connected with all other vertices with an edge. So in such a case each vertex should have a unique color. Thus the chromatic number will be n.

10. What will be the chromatic number for a tree having more than 1 vertex?
a) 0
b) 1
c) 2
d) Varies with the structure and number of vertices of the tree
View Answer

Answer: c
Clarification: The minimum number of colors required for proper vertex coloring of graph is called chromatic number. So every tree having more than 1 vertex is 2 chromatic.

11. A graph with chromatic number less than or equal to k is called?
a) K chromatic
b) K colorable
c) K chromatic colorable
d) K colorable chromatic

Answer: b
Clarification: Any graph that has a chromatic number less than or equal to k is called k colorable. Whereas a graph with chromatic number k is called k chromatic.

12. What will be the chromatic number of the following graph?

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

Answer: b
Clarification: The given graph will only require 2 unique colors so that no two vertices connected by a common edge will have the same color. So its chromatic number will be 2.

13. What will be the chromatic number of the following graph?

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

Answer: b
Clarification: The given graph will require 3 unique colors so that no two vertices connected by a common edge will have the same color. So its chromatic number will be 3.

14. What will be the chromatic number of the following graph?

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

Answer: b
Clarification: The given graph will require 3 unique colors so that no two vertices connected by a common edge will have the same color. So its chromatic number will be 3.

15. The chromatic number of star graph with 3 vertices is greater than that of a complete graph with 3 vertices.
a) True
b) False

Answer: b
Clarification: The chromatic number of a star graph is always 2 (for more than 1 vertex) whereas the chromatic number of complete graph with 3 vertices will be 3. So chromatic number of complete graph will be greater.

16. The chromatic number of star graph with 3 vertices is greater than that of a tree with same number of vertices.
a) True
b) False

Answer: b
Clarification: The chromatic number of a star graph and a tree is always 2 (for more than 1 vertex). So both have the same chromatic number.

and Answers.

250+ TOP MCQs on Matrix Multiplication using Recursion and Answers

Data Structures & Algorithms Multiple Choice Questions on “Matrix Multiplication using Recursion”.

1. If Matrix A is of order X*Y and Matrix B is of order M*N, then what is the order of the Matrix A*B given that Y=M?
a) Y*N
b) X*M
c) X*N
d) Y*M
Answer: c
Clarification: The Matrix A*B is of order X*N as it is given that Y=M i.e. number of columns in Matrix A is equal to total number of rows in matrix B. So the Matrix A*B must have X number of rows and N number of columns.

2. How many recursive calls are there in Recursive matrix multiplication through Simple Divide and Conquer Method?
a) 2
b) 6
c) 9
d) 8

Answer: d
Clarification: For the multiplication two square matrix recursively using Simple Divide and Conquer Method, there are 8 recursive calls performed for high time complexity.

3. What is the time complexity of matrix multiplied recursively by Divide and Conquer Method?
a) O(n)
b) O(n²)
c) O(n³)
d) O(n!)

Answer: c
Clarification: The time complexity of recursive multiplication of two square matrices by the Divide and Conquer method is found to be O(n³) since there are total of 8 recursive calls.

4. What is the time complexity of matrix multiplied recursively by Strassen’s Method?
a) O(n^log7)
b) O(n²)
c) O(n³)
d) O(n!)

Answer: a
Clarification: The time complexity of recursive multiplication of two square matrices by Strassen’s Method is found to be O(n^log7) since there are total 7 recursive calls.

5. How many recursive calls are there in Recursive matrix multiplication by Strassen’s Method?
a) 5
b) 7
c) 8
d) 4

Answer: b
Clarification: For the multiplication two square matrix recursively using Strassen’s Method, there are 7 recursive calls performed for high time complexity.

6. Matrix A is of order 3*4 and Matrix B is of order 4*5. How many elements will be there in a matrix A*B multiplied recursively.
a) 12
b) 15
c) 16
d) 20

Answer: b
Clarification: The resultant matrix will be of order 3*5 when multiplied recursively and therefore the matrix will have 3*5=15 elements.

7. If Matrix X is of order A*B and Matrix Y is of order C*D, and B=C then the order of the Matrix X*Y is A*D?
a) True
b) False

Answer: a
Clarification: Given that B=C, so the two matrix can be recursively multiplied. Therefore, the order of the Matrix X*Y is A*D.

8. What is the time complexity of the fastest known matrix multiplication algorithm?
a) O(n^log7)
b) O(n^2.37)
c) O(n³)
d) O(n!)

Answer: b
Clarification: The Coppersmith-Winograd algorithm multiplies the matrices in O(n^2.37) time. Several improvements have been made in the algorithm since 2010.

9. Is Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity?
a) True
b) False

Answer: a
Clarification: Since The Coppersmith-Winograd algorithm multiplies the matrices in O(n^2.37) time. The time complexity of recursive multiplication of two square matrices by Strassen’s Method is found to be O(n^2.80). Therefore, Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity.

and Answers.

250+ TOP MCQs on N Queens Problem and Answers

Data Structures & Algorithms Multiple Choice Questions on “N Queens Problem”.

1. In how many directions do queens attack each other?
a) 1
b) 2
c) 3
d) 4

Answer: c
Clarification: Queens attack each other in three directions- vertical, horizontal and diagonal.

2. Placing n-queens so that no two queens attack each other is called?
a) n-queen’s problem
b) 8-queen’s problem
c) Hamiltonian circuit problem
d) subset sum problem

Answer: a
Clarification: Placing n queens so that no two queens attack each other is n-queens problem. If n=8, it is called as 8-queens problem.

3. Where is the n-queens problem implemented?
a) carom
b) chess
c) ludo
d) cards
Answer: b
Clarification: N-queens problem occurs in chess. It is the problem of placing n- queens in a n*n chess board.

4. Not more than 2 queens can occur in an n-queens problem.
a) true
b) false

Answer: b
Clarification: Unlike a real chess game, n-queens occur in a n-queen problem since it is the problem of dealing with n-queens.

5. In n-queen problem, how many values of n does not provide an optimal solution?
a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: N-queen problem does not provide an optimal solution of only three values of n (i.e.) n=2,3.

6. Which of the following methods can be used to solve n-queen’s problem?
a) greedy algorithm
b) divide and conquer
c) iterative improvement
d) backtracking

Answer: d
Clarification: Of the following given approaches, n-queens problem can be solved using backtracking. It can also be solved using branch and bound.

7. Of the following given options, which one of the following is a correct option that provides an optimal solution for 4-queens problem?
a) (3,1,4,2)
b) (2,3,1,4)
c) (4,3,2,1)
d) (4,2,3,1)

Answer: a
Clarification: Of the following given options for optimal solutions of 4-queens problem, (3, 1, 4, 2) is the right option.

8. How many possible solutions exist for an 8-queen problem?
a) 100
b) 98
c) 92
d) 88
Answer: c
Clarification: For an 8-queen problem, there are 92 possible combinations of optimal solutions.

9. How many possible solutions occur for a 10-queen problem?
a) 850
b) 742
c) 842
d) 724

Answer: d
Clarification: For a 10-queen problem, 724 possible combinations of optimal solutions are available.

10. If n=1, an imaginary solution for the problem exists.
a) true
b) false
Answer: b
Clarification: For n=1, the n-queen problem has a trivial and real solution and it is represented by

11. What is the domination number for 8-queen’s problem?
a) 8
b) 7
c) 6
d) 5

Answer: d
Clarification: The minimum number of queens needed to occupy every square in n-queens problem is called domination number. While n=8, the domination number is 5.

12. Of the following given options, which one of the following does not provides an optimal solution for 8-queens problem?
a) (5,3,8,4,7,1,6,2)
b) (1,6,3,8,3,2,4,7)
c) (4,1,5,8,6,3,7,2)
d) (6,2,7,1,4,8,5,3)

Answer: b
Clarification: The following given options for optimal solutions of 8-queens problem, (1,6,3,8,3,2,4,7) does not provide an optimal solution.

and Answers.

250+ TOP MCQs on Catalan Number using Dynamic Programming

Data Structure Multiple Choice Questions & Answers on “Catalan Number using Dynamic Programming”.

1. Which of the following is NOT a Catalan number?
a) 1
b) 5
c) 14
d) 43

Answer: d
Clarification: Catalan numbers are given by: (2n!)/((n+1)!n!).
For n = 0, we get C0 = 1.
For n = 3, we get C3 = 5.
For n = 4, we get C4 = 14.
For n = 5, we get C3 = 42.

2. Which of the following numbers is the 6th Catalan number?
a) 14
b) 429
c) 132
d) 42

Answer: d
Clarification: Catalan numbers are given by: (2n!)/((n+1)!n!).
First Catalan number is given by n = 0.
So the 6th Catalan number will be given by n = 5, which is 42.

3. Which of the following is not an application of Catalan Numbers?
a) Counting the number of Dyck words
b) Counting the number of expressions containing n pairs of parenthesis
c) Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines
d) Creation of head and tail for a given number of tosses

Answer: d
Clarification: Counting the number of Dyck words, Counting the number of expressions containing n pairs of parenthesis, Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines are the applications of Catalan numbers where as creation of head and tails for a given number of tosses is an application of Pascal’s triangle.

4. Which of the following methods can be used to find the nth Catalan number?
a) Recursion
b) Binomial coefficients
c) Dynamic programming
d) Recursion, Binomial Coefficients, Dynamic programming

Answer: d
Clarification: All of the mentioned methods can be used to find the nth Catalan number.

5. The recursive formula for Catalan number is given by Cn = ∑Ci*C(n-i).
Consider the following dynamic programming implementation for Catalan numbers:

#include
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
           ______________________;
     }
     return arr[n-1];
 
}
int main()
{
     int ans, n = 8;
     ans = cat_number(n);
     printf("%dn",ans);
     return 0;
}

Which of the following lines completes the above code?
a) arr[i] = arr[j] * arr[k];
b) arr[j] += arr[i] * arr[k];
c) arr[i] += arr[j] * arr[k].
d) arr[j] = arr[i] * arr[k];

Answer: c
Clarification: The line arr[i] += arr[j] * arr[k] reflects the recursive formula Cn = ∑Ci*C(n-i).

6. Which of the following implementations of Catalan numbers has the smallest time complexity?
a) Dynamic programming
b) Binomial coefficients
c) Recursion
d) All have equal time complexity

Answer: b
Clarification: The time complexities are as follows:
Dynamic programming: O(n²)
Recursion: Exponential
Binomial coefficients: O(n).

7. What is the output of the following code?

#include
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
         arr[i] += arr[j] * arr[k];
     }
     return arr[n-1];
}
int main()
{
     int ans, n = 8;
     ans = cat_number(n);
     printf("%dn",ans);
     return 0;
}

a) 42
b) 132
c) 429
d) 1430

Answer: c
Clarification: The program prints the 8th Catalan number, which is 429.

8. Which of the following implementations of Catalan numbers has the largest space complexity(Don’t consider the stack space)?
a) Dynamic programming
b) Binomial coefficients
c) Recursion
d) All have equal space complexities

Answer: a
Clarification: The space complexities are as follows:
Dynamic programming: O(n)
Recursion: O(1)
Binomial coefficients: O(1).

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

#include
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
          arr[i] += arr[j] * arr[k];
     }
     return arr[n-1];
}
int main()
{
     int ans, n = 10;
     ans = cat_number(n);
     printf("%dn",ans);
     return 0;
}

a) 14
b) 42
c) 132
d) 429

Answer: b
Clarification: The 6th Catalan number will be stored in arr[5], which is 42.

10. Which of the following errors will occur when the below code is executed?

#include
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
           arr[i] += arr[j] * arr[k];
     }
     return arr[n-1];
}
int main()
{
     int ans, n = 100;
     ans = cat_number(n);
     printf("%dn",ans);
     return 0;
}

a) Segmentation fault
b) Array size too large
c) Integer value out of range
d) Array index out of range

Answer: c
Clarification: The 100th Catalan number is too large to be stored in an integer. So, the error produced will be integer value out of range.(It will be a logical error and the compiler wont show it).

250+ TOP MCQs on Playfair Cipher and Answers

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

1. What is the alternative name of playfair cipher?
a) Wadsworth’s cipher
b) Wheatstone playfair cipher
c) Playfair rectangle
d) Wheatstone cipher
View Answer

Answer: b
Clarification: Playfair cipher is also known by the name of Wheatstone playfair cipher. It is because it was discovered by Charles Wheatstone but was promoted by Lord Playfair.

2. Playfair cipher is an example of __________
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher

Answer: b
Clarification: Playfair 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 Autokey cipher is done using __________
a) a 5×5 table
b) a 13×2 table
c) vigenere table
d) a 6×6 table

Answer: c
Clarification: Encryption of plain text in playfair cipher is done using a 5×5 table. In this table, all the alphabets of the keyword are arranged row wise by eliminating any duplicates then the remaining letters of the alphabet are placed. One of the alphabet has to be omitted in order to fit all the alphabets in the table.

4. Which of the following correctly defines poly graphic substitution cipher?
a) a substitution based cipher which uses multiple substitutions at different positions
b) a substitution based cipher which uses fixed substitution over entire plain text
c) a substitution based cipher in which substitution is performed over a block of letters
d) a transposition based cipher which uses fixed substitution over entire plain text

Answer: c
Clarification: Poly graphic cipher is a type of substitution cipher in which substitution is performed over a block of letters. Playfair cipher is an example of poly graphic cipher.

5. Which of the following was the first diagram substitution cipher?
a) autokey cipher
b) hill cipher
c) one time pad cipher
d) playfair cipher

Answer: d
Clarification: Poly graphic cipher is a type of substitution cipher in which substitution is performed over a block of letters. In diagram substitution, two adjacent letters are substituted simultaneously. Playfair cipher was the first diagram substitution cipher.

6. Which of the following is hardest to break using frequency analysis?
a) Vigenere cipher
b) Autokey cipher
c) Playfair cipher
d) Rotor cipher
View Answer

Answer: c
Clarification: Out of the given options playfair cipher is the hardest cipher to break using frequency analysis. It is because it does not substitute letters of the word individually but it encrypts them in pairs of two.

7. Playfair cipher is harder to crack than keyword cipher.
a) True
b) False
View Answer

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

8. What will be the plain text corresponding to cipher text “BPKYFS” if playfair cipher is used with keyword as “SECRET” (assuming j is combined with i)?
a) INDIAN
b) WORLD
c) DOLLAR
d) HELLO

Answer: c
Clarification: To decrypt the message we follow the reverse procedure. The table is formed in the same manner. Applying this we get the plain text to be “DOLLAR”.

9. What is the rule for encryption in playfair cipher if the letters in a pair are identical?
a) then that pair is neglected
b) a null is added in between the letters
c) one of the identical letter is replaced by some other letter
d) then both of the letters are replaced by the letter appearing just next in the row

Answer: b
Clarification: In playfair cipher if the letters in a pair are identical then a null is added in between the letters. Any letter can be used as a null as long as that letter is not the one being repeated.

10. What is the rule for encryption in playfair cipher if the letters in a pair appear in same row?
a) they are replaced by the letter appearing immediately below them respectively
b) they are replaced by the letter appearing immediately right to them respectively
c) they are replaced by the letter at the corner of the row
d) that pair is neglected

Answer: b
Clarification: If the letters in a pair appear in same row then they are replaced by the letters appearing immediately right to them respectively. If the element to be replaced appears at the corner of the row then we wrap around to the left side of that row.

11. What will be the ciphered text if the string “” is given as input to the code of playfair cipher with keyword as “SECRET” (assuming j is combined with i)?
a) ZHQAPNPAFR
b) AHQAPNPAFR
c) HAQAPNPAFR
d) QHAAPNPAFR

Answer: b
Clarification: For encrypting the plain text using playfair cipher we use a 5×5 table that is constructed by using keyword. Then we apply rules for encryption in order to get the ciphered text. Table is given as under-

S E C R T
A B D F G
H I K L M
N O P Q U
V W X Y Z

12. What is the rule for encryption in playfair cipher if the letters in a pair appear in same column?
a) they are replaced by the letter appearing immediately below them respectively
b) they are replaced by the letter appearing immediately right to them respectively
c) they are replaced by the letters at the corner of the row
d) that pair is neglected

Answer: a
Clarification: If the letters in a pair appear in the same column then they are replaced by the letters appearing immediately below them respectively. If the element to be replaced appears at the corner of the column then we wrap around to the top side of that column.

13. What is the rule for encryption in playfair cipher if the letters in a pair does not appear in same row or column?
a) they are replaced by the letter appearing immediately below them respectively
b) they are replaced by the letter appearing immediately right to them respectively
c) they are replaced by the letter of the same row at the corner of the rectangle defined by the original pair respectively
d) that pair is neglected
Answer: c
Clarification: If the letters in a pair does not appear in same row or column then they are replaced by the letters of the same row at the corner of the rectangle defined by the original pair respectively. The order of letters should be maintained.

& Algorithms.