###### Teaching Aptitude

October 4, 2023###### Nielit Scentist-B [02-12-2018]

October 4, 2023# Data-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