GATE | GATE CS 2018 |问题57

包含来自{1,2,3,4,5,6,7}的每个值的可能最小堆的数量正好是_________________。

注—— 这是数字型问题。 （A） 80 （B） 8. （C） 20 （D） 210 答复: （A） 说明： 将最小元素设置为根（即 1. )，现在剩下6个元素，左子树将有3个元素，每个左子树组合可以在2中排列！方式。

使用7个元素设计最小堆的总体方法= *2! * 2! = 20*2*2 = 80

替代方法—— 包含1到N个元素的最小或最大堆树使用递归关系的总数：

T(N) =(N-1)Ck * T(k) * T(N-k-1), where k = number of nodes on left subtree

T(1) = 1
T(2) = 1
T(3) = 2
T(4) = 3C2 * T(2) * T(1) = 3
T(5) = 4C3 * T(3) * T(1) = 8
T(6) = 5C3 * T(3) * T(2) = 20
T(7) = 5C3 * T(3) * T(3) = 80

答案是80。

这个问题的小测验