Teaching Aptitude
October 4, 2023Nielit ScentistB [02122018]
October 4, 2023DataStructures
Question 9

The number of possible minheaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ___________.
80


81


82


83

Question 9 Explanation:
–> We have 7 distinct integers {1,2,3,4,5,6,7} and sort it
–> After sorting, pick the minimum element and make it the root of the min heap.
–> So, there is only 1 way to make the root of the min heap.
–> Now we are left with 6 elements.
–> Total ways to design a min heap from 6 elements = C(6,3) ∗ 2! ∗ C(3,3) ∗ 2! = 80
–> After sorting, pick the minimum element and make it the root of the min heap.
–> So, there is only 1 way to make the root of the min heap.
–> Now we are left with 6 elements.
–> Total ways to design a min heap from 6 elements = C(6,3) ∗ 2! ∗ C(3,3) ∗ 2! = 80
Note:
C(6,3)∗2! : Pick up any 3 elements for the left subtree and each left subtree combination can be permuted in 2! ways by interchanging the children and similarly, for right subtree .
Correct Answer: A
Question 9 Explanation:
–> We have 7 distinct integers {1,2,3,4,5,6,7} and sort it
–> After sorting, pick the minimum element and make it the root of the min heap.
–> So, there is only 1 way to make the root of the min heap.
–> Now we are left with 6 elements.
–> Total ways to design a min heap from 6 elements = C(6,3) ∗ 2! ∗ C(3,3) ∗ 2! = 80
–> After sorting, pick the minimum element and make it the root of the min heap.
–> So, there is only 1 way to make the root of the min heap.
–> Now we are left with 6 elements.
–> Total ways to design a min heap from 6 elements = C(6,3) ∗ 2! ∗ C(3,3) ∗ 2! = 80
Note:
C(6,3)∗2! : Pick up any 3 elements for the left subtree and each left subtree combination can be permuted in 2! ways by interchanging the children and similarly, for right subtree .
Subscribe
Login
0 Comments