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

250+ TOP MCQs on Chan’s Algorithm and Answers

Data Structures & Algorithms Multiple Choice Questions on “Chan’s Algorithm”.

1. Chan’s algorithm is used for computing _________
a) Closest distance between two points
b) Convex hull
c) Area of a polygon
d) Shortest path between two points

Answer: b
Clarification: Chan’s algorithm is an output-sensitive algorithm used to compute the convex hull set of n points in a 2D or 3D space. Closest pair algorithm is used to compute the closest distance between two points.

2. What is the running time of Chan’s algorithm?
a) O(log n)
b) O(n log n)
c) O(n log h)
d) O(log h)

Answer: c
Clarification: The running time of Chan’s algorithm is calculated to be O(n log h) where h is the number of vertices of the convex hull.

3. Who formulated Chan’s algorithm?
a) Timothy
b) Kirkpatrick
c) Frank Nielsen
d) Seidel
Answer: a
Clarification: Chan’s algorithm was formulated by Timothy Chan. Kirkpatrick and Seidel formulated the Kirkpatrick-Seidel algorithm. Frank Nielsen developed a paradigm relating to Chan’s algorithm.

4. The running time of Chan’s algorithm is obtained from combining two algorithms.
a) True
b) False
Answer: a
Clarification: The O(n log h) running time of Chan’s algorithm is obtained by combining the running time of Graham’s scan [O(n log n)] and Jarvis match [O(nh)].

5. Which of the following is called the “ultimate planar convex hull algorithm”?
a) Chan’s algorithm
b) Kirkpatrick-Seidel algorithm
c) Gift wrapping algorithm
d) Jarvis algorithm

Answer: b
Clarification: Kirkpatrick-Seidel algorithm is called as the ultimate planar convex hull algorithm. Its running time is the same as that of Chan’s algorithm (i.e.) O(n log h).

6. Which of the following algorithms is the simplest?
a) Chan’s algorithm
b) Kirkpatrick-Seidel algorithm
c) Gift wrapping algorithm
d) Jarvis algorithm

Answer: a
Clarification: Chan’s algorithm is very practical for moderate sized problems whereas Kirkpatrick-Seidel algorithm is not. Although, they both have the same running time. Gift wrapping algorithm is a non-output sensitive algorithm and has a longer running time.

7. What is the running time of Hershberger algorithm?
a) O(log n)
b) O(n log n)
c) O(n log h)
d) O(log h)

Answer: b
Clarification: Hershberger’s algorithm is an output sensitive algorithm whose running time was originally O(n log n). He used Chan’s algorithm to speed up to O(n log h) where h is the number of edges.

8. Which of the following statements is not a part of Chan’s algorithm?
a) eliminate points not in the hull
b) recompute convex hull from scratch
c) merge previously calculated convex hull
d) reuse convex hull from the previous iteration

Answer: b
Clarification: Chan’s algorithm implies that the convex hulls of larger points can be arrived at by merging previously calculated convex hulls. It makes the algorithm simpler instead of recomputing every time from scratch.

9. Which of the following factors account more to the cost of Chan’s algorithm?
a) computing a single convex hull
b) locating points that constitute a hull
c) computing convex hull in groups
d) merging convex hulls
Answer: c
Clarification: The majority of the cost of the algorithm lies in the pre-processing (i.e.) computing convex hull in groups. To reduce cost, we reuse convex hulls from previous iterations.

10. Chan’s algorithm can be used to compute the lower envelope of a trapezoid.
a) true
b) false
Answer: a
Clarification: An extension of Chan’s algorithm can be used for proving solutions to complex problems like computing the lower envelope L(S) where S is a set of ‘n’ line segments in a trapezoid.

250+ TOP MCQs on Vertex Coloring and Answers

Data Structures & Algorithms Multiple Choice Questions on “Vertex Coloring”.

1. Which of the following is not a type of graph in computer science?
a) undirected graph
b) bar graph
c) directed graph
d) weighted graph

Answer: b
Clarification: According to the graph theory a graph is the collection of dots and lines. A bar graph is not a type of graph in computer science.

2. What is vertex coloring of a graph?
a) A condition where any two vertices having a common edge should not have same color
b) A condition where any two vertices having a common edge should always have same color
c) A condition where all vertices should have a different color
d) A condition where all vertices should have same color

Answer: a
Clarification: The condition for vertex coloring of a 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. How many edges will a tree consisting of N nodes have?
a) Log(N)
b) N
c) N – 1
d) N + 1

Answer: c
Clarification: In order to have a fully connected tree it must have N-1 edges. So the correct answer will be N-1.

4. Minimum number of unique colors required for vertex coloring of a graph is called?
a) vertex matching
b) chromatic index
c) chromatic number
d) color number

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. How many unique colors will be required for proper vertex coloring of 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 number of unique colors required for proper coloring of the graph will be 1.

6. How many unique colors will be required for proper vertex coloring of a bipartite graph having n vertices?
a) 0
b) 1
c) 2
d) n
View Answer

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

7. Which of the following is an NP complete problem?
a) Hamiltonian cycle
b) Travelling salesman problem
c) Calculating chromatic number of graph
d) Finding maximum element in an array

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

8. How many unique colors will be required for proper vertex coloring of 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. So the number of unique colors required for proper coloring of the graph will be n.

9. How many unique colors will be required for proper vertex coloring of 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 the number of unique colors required for proper coloring of the graph will be n.

10. Minimum number of colors required for proper edge coloring of a graph is called?
a) Chromatic color
b) Chromatic index
c) Edge matching
d) Color number

Answer: b
Clarification: The minimum number of colors required for proper edge coloring of graph is called chromatic index. It is also known as edge chromatic number.

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

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

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. All nodes will have the same color except the central node.

12. How many unique colors will be required for vertex coloring of the following graph?

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

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

13. How many unique colors will be required for vertex coloring of the following graph?

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

Answer: b
Clarification: The given graph will require 3 unique colors because two diagonal vertex are connected to each other directly. So its chromatic number will be 3.

14. Vertex coloring and chromatic number are one and the same.
a) True
b) False
View Answer

Answer: b
Clarification: Vertex coloring of a graph is an assignment of colors to the vertices of a graph such that no two adjacent vertices have the same color. Whereas chromatic number refers to the minimum number of unique colors required for vertex coloring of the graph.

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.