Study Glance
☑ MCQ PRACTICE

Design and Analysis of Algorithms Unit 2

Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.

📚 Design and Analysis of Algorithms
📖 Unit 2
🎯 MCQs

Design and Analysis of Algorithms - Unit-2

1
What operation in the disjoint set data structure is used to merge two disjoint sets?
AMerge
BFind
CUnion
DConnect
Correct Answer Union
2
Which operation in the disjoint set data structure determines the representative element of a set?
AFind
BMerge
CConnect
DUnion
Correct Answer Find
3
Which of the following is true about the time complexity of the Find operation in a disjoint set data structure with path compression?
AO(n)
BO(log n)
CO(n log n)
DO(1)
Correct Answer O(1)
4
In a disjoint set data structure, what does the "path compression" technique aim to reduce?
ANumber of sets
BDepth of trees
CNumber of elements
DNumber of operations
Correct Answer Depth of trees
5
When performing the Union operation in a disjoint set data structure, which set typically becomes the parent of the other?
AThe node with more descendants
BThe node with less descendants
CThe set with the smaller representative element
DThe set with the larger representative element
Correct Answer The node with more descendants
6
In a disjoint set data structure, what does the "union by size" heuristic aim to optimize?
ANumber of sets
BDepth of trees
CNumber of elements
DNumber of operations
Correct Answer Number of elements
7
What is the primary purpose of the Collapsing Find technique in union-find algorithms?
ATo ensure that the tree height is minimized.
BTo optimize the path compression during the find operation.
CTo assign weights to the nodes in the tree.
DTo balance the trees in the union-find data structure.
Correct Answer To optimize the path compression during the find operation.
8
How does Weighted Union help in improving the efficiency of union-find operations?
ABy collapsing the paths during the find operation.
BBy ensuring that the tree height is minimized.
CBy assigning weights to the nodes in the tree.
DBy balancing the trees in the union-find data structure.
Correct Answer By ensuring that the tree height is minimized.
9
Backtracking algorithm is implemented by constructing a tree of choices called as?
AState-space tree
BState-chart tree
CNode tree
DBacktracking tree
Correct Answer State-space tree
10
In what manner is a state-space tree for a backtracking algorithm constructed?
ADepth-first search
BBreadth-first search
CTwice around the tree
DNearest neighbour first
Correct Answer Depth-first search
11
In how many directions do queens attack each other?
A1
B2
C3
D4
Correct Answer 3
12
How many possible solutions exist for an 8-queen problem?
A100
B98
C92
D88
Correct Answer 92
13
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)
Correct Answer (3,1,4,2)
14
What is the condition for proper coloring of a graph?
Atwo vertices having a common edge should not have same color
Btwo vertices having a common edge should always have same color
Call vertices should have a different color
Dall vertices should have same color
Correct Answer two vertices having a common edge should not have same color
15
What is a chromatic number?
AThe maximum number of colors required for proper edge coloring of graph
BThe maximum number of colors required for proper vertex coloring of graph
CThe minimum number of colors required for proper vertex coloring of graph
DThe minimum number of colors required for proper edge coloring of graph
Correct Answer The minimum number of colors required for proper vertex coloring of graph
16
What will be the chromatic number for an empty graph having n vertices?
A0
B1
C2
Dn
Correct Answer 1
17
What will be the chromatic number for a complete graph having n vertices?
A0
B1
Cn
Dn!
Correct Answer n
← Back to All MCQs