DAA OBJECTIVE QUESTIONS UNIT-2
1. What operation in the disjoint set data structure is used to merge two disjoint sets?
A . Merge B . Find
C . Union D . Connect
2. Which operation in the disjoint set data structure determines the representative element of
a set?
A . Find B . Merge
C . Connect D . Union
3. Which of the following is true about the time complexity of the Find operation in a disjoint
set data structure with path compression?
A . O(n) B . O(log n)
C . O(n log n) D . O(1)
4. In a disjoint set data structure, what does the "path compression" technique aim to
A . Number of sets
B . Depth of trees
C . Number of elements
D . Number of operations
5. When performing the Union operation in a disjoint set data structure, which set typically
becomes the parent of the other?
A . The node with more descendants
B . The node with less descendants
C . The set with the smaller representative element
D . The set with the larger representative element
6. In a disjoint set data structure, what does the "union by size" heuristic aim to op
A . Number of sets B . Depth of trees
C . Number of elements D . Number of operations
7. What is the primary purpose of the Collapsing Find technique in union-find algorithms?
A . To ensure that the tree height is minimized.
B . To optimize the path compression during the find operation.
C . To assign weights to the nodes in the tree.
D . To balance the trees in the union-find data structure.
8. How does Weighted Union help in improving the efficiency of union-find operations?
A . By collapsing the paths during the find operation.
B . By ensuring that the tree height is minimized.
C . By assigning weights to the nodes in the tree.
D . By balancing the trees in the union-find data structure.
9. Backtracking algorithm is implemented by constructing a tree of choices called as?
A . State-space tree
B . State-chart tree
C . Node tree
D . Backtracking tree
10. In what manner is a state-space tree for a backtracking algorithm constructed?
A . Depth-first search
B . Breadth-first search
C . Twice around the tree
D . Nearest neighbour first
11. In how many directions do queens attack each other?
A. 1 B.2
C.3 D.4
12. How many possible solutions exist for an 8-queen problem?
A . 100 B . 98
C . 92 D . 88
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)
14. 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
15. 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
16. What will be the chromatic number for an empty graph having n vertices?
A. 0 B.1
C.2 D.n
17. What will be the chromatic number for a complete graph having n vertices?
A. 0 B.1
C . Vn D . n!
[Link] of the following is not a backtracking algorithm?
A. Knight tour problem
B. N queen problem
C. Tower of hanoi
D. M coloring problem
18. What is backtracking?
A. search algorithm that finds the shortest path in a graph.
B. An algorithmic paradigm that tries different solutions until the correct one is found.
C. An algorithm for sorting elements in an array.
D. A dynamic programming technique.
[Link] backtracking, what is a solution candidate?
A. The final solution to the problem.
B. A partial solution that may or may not lead to a valid solution
C. A solution obtained through dynamic programming.
D. The optimal solution.
[Link] is the main purpose of backtracking?
A. To find the maximum element in an array.
B. To explore all possible solutions to a problem.
C. To perform sorting on a list of elements.
D. To calculate the average of a set of numbers.
[Link] backtracking, what is a constraint?
A. A condition that a solution must satisfy.
B. A mathematical equation.
C. A decision point.
D. A variable in the algorithm.
21. How does backtracking differ from brute force?
A. Backtracking is a more efficient form of brute force.
B. Backtracking uses pruning, while brute force does not.
C. Backtracking always finds the optimal solution, while brute force may not.
D. Backtracking and brute force are synonymous terms.
[Link] data structure is commonly used to implement backtracking algorithms?
A. Linked list.
B. Stack.
C. Queue.
D. Hash table.
[Link] is a _____________?
A. Tree structure
B. Complete binary tree
C. Binary tree
D. None of the above
24. In a graph of n nodes and n edges, how many cycles will be present?
A. Exactly 1
B. At most 1
C. At most 2
D. Depending on the graph
25. In what manner is a state-space tree for a backtracking algorithm constructed?
A . Depth-first search
B . Breadth-first search
C . Twice around the tree
D . Nearest neighbour first
[Link] how many directions do queens attack each other?
A. 1 B.2
C.3 D.4