Data Structures MCQs with Answers
Practice important Data Structures MCQs with answers and explanations.
Chapter: 35
Q561:
How does the parent array help in analyzing the number of trees in the forest?
A. By counting the number of elements
B. By counting the number of -1 values
C. By counting the number of roots
D. By counting the number of non-root nodes
Correct Answer:
B
Chapter: 35
Q562:
In the union operation, which tree becomes the root if union(4, 5) is called and 5 is the root?
A. 4
B. 5
C. 3
D. 8
Correct Answer:
B
Chapter: 35
Q563:
What is the time complexity of the union operation in a disjoint set data structure?
A. O(1)
B. O(log n)
C. O(n)
D. O(n^2)
Correct Answer:
A
Chapter: 35
Q564:
In the find operation, what is the role of the for loop in the provided code?
A. To traverse and return the root of the set
B. To merge two sets
C. To initialize the parent array
D. To count the number of elements
Correct Answer:
A
Chapter: 35
Q565:
What happens to the parent array after union(5, 7) if the current parent array is -1 -1 -1 -1 -1 5 -1 7?
A. 5 becomes the parent of 7
B. 7 becomes the parent of 5
C. 5 and 7 are both set to -1
D. The array remains unchanged
Correct Answer:
A
Chapter: 35
Q566:
What is the primary advantage of using a single-dimensional array over a two-dimensional matrix for disjoint sets?
A. Easier to implement
B. Requires less space
C. Faster access time
D. More intuitive structure
Correct Answer:
B
Chapter: 35
Q567:
What is the significance of the parent[i] = -1 initialization?
A. Indicates element i is not part of any set
B. Indicates element i is a root of its own set
C. Indicates element i is a child node
D. Indicates element i is in a disjoint set
Correct Answer:
B
Chapter: 35
Q568:
What does the height of a tree in a disjoint set data structure represent?
A. The number of nodes in the tree
B. The number of levels in the tree
C. The maximum number of child nodes
D. The time complexity of union operations
Correct Answer:
B
Chapter: 36
Q569:
What is the primary goal of Union by Size in disjoint sets?
A. To minimize the time complexity of the union operation
B. To ensure heights of trees stay small
C. To increase the depth of trees
D. To optimize the find operation
Correct Answer:
B
Chapter: 36
Q570:
In the Union by Size method, what does a negative value in the parent array represent?
A. The tree is not a root node
B. The size of the tree
C. The height of the tree
D. The tree has been merged with another tree
Correct Answer:
B
Chapter: 36
Q571:
What is the main advantage of path compression in the find operation?
A. It reduces the height of the tree by merging smaller trees
B. It speeds up the find operation by flattening the tree path to the root
C. It decreases the size of trees
D. It improves the complexity of the union operation
Correct Answer:
B
Chapter: 36
Q572:
How does Union by Height differ from Union by Size?
A. Union by Height maintains tree heights and merges smaller height trees into larger ones
B. Union by Height maintains tree sizes and merges smaller trees into larger ones
C. Union by Height merges trees based on their sizes
D. Union by Height merges trees based on their root node values
Correct Answer:
A
Chapter: 36
Q573:
What is the worst-case time complexity for find operations with Union by Rank and Path Compression?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(α(n))
Correct Answer:
D
Chapter: 36
Q574:
What does the find operation in Union by Size return?
A. The size of the set
B. The parent node of the node
C. The root of the tree containing the node
D. The height of the tree containing the node
Correct Answer:
C
Chapter: 36
Q575:
When merging two trees using Union by Size, which tree becomes the root?
A. The tree with fewer nodes
B. The tree with greater depth
C. The tree with the smaller height
D. The tree with more nodes
Correct Answer:
D
Chapter: 36
Q576:
How does path compression affect future find operations?
A. It requires more time for each find operation
B. It creates a balanced tree for faster find operations
C. It directly connects nodes to the root, reducing future find operation time
D. It increases the depth of the tree
Correct Answer:
C
Chapter: 36
Q577:
In the provided pseudo-code, which line performs the union operation by merging trees of different sizes?
A. Line 3
B. Line 7
C. Line 10
D. Line 14
Correct Answer:
B
Chapter: 36
Q578:
What is the maximum depth of a tree in Union by Size after a series of union operations?
A. n
B. log2(n)
C. n^2
D. O(log n)
Correct Answer:
B
Chapter: 36
Q579:
What operation is performed in line 4 of the pseudo-code for union in Union by Size?
A. Compare sizes of trees and add the smaller tree’s size to the larger one
B. Set the root of one tree as the parent of the other
C. Merge two trees directly without comparison
D. Update the parent node of the root tree
Correct Answer:
A
Chapter: 36
Q580:
In the find operation with path compression, what happens to the nodes' parent values?
A. They are set to -1
B. They are updated to point directly to the root
C. They are left unchanged
D. They are set to point to the parent’s parent
Correct Answer:
B