Teaching Aptitude
October 4, 2023Nielit Scentist-B [02-12-2018]
October 4, 2023Data-Structures
| Question 9 |
The number of possible min-heaps 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