数据结构和算法|集合26

2011门考试提出了以下问题。

1） 最大堆是指每个父级的值大于或等于其子级的值的堆。以下哪项是最大堆？

答复：（B） 如果一棵二叉树是一棵完整的二叉树（完整的二叉树是一棵二叉树，其中除最后一棵外，每一层都被完全填满，所有节点都尽可能地位于最左边），并且它遵循最大堆属性（每个父级的值大于或等于其子级的值），那么它就是最大堆。

A） 不是最大堆，因为它不是一个完整的二叉树 B） 是最大堆，因为它是完整的二叉树，并且遵循最大堆属性。 C） 不是最大堆，因为8在此树中是5的整数，因此违反了最大堆属性。 D） 不是最大堆，因为8在此树中是5的整数，因此违反了最大堆属性。此树中还有许多其他节点违反了此树中的最大堆属性。

2） 四个矩阵M1、M2、M3和M4的维数分别为pxq、qxr、rxs和sxt，它们可以通过多种方式相乘，总的标量乘法次数不同。例如，当乘以（（M1 X M2）X（M3 X M4））时，乘法总数为pqr+rst+prt。当乘以（（M1 X M2）X M3）X M4时，标量乘法的总数为pqr+prs+pst。

A） 248000 B） 44000 C） 19000 D） 25000

答复（C） 我们使用（（M1 X（M2 X M3））X M4）得到最小乘法数。

乘法总数=100x20x5（对于M2 x M3）+10x100x5+10x5x80=19000。

3） 以下哪个选项提供了函数f1、f2、f3和f4的渐进复杂度的递增顺序？ f1（n）=2^n f2（n）=n^（3/2） f3（n）=nLogn f4（n）=n^（Logn）

A） f3、f2、f4、f1 B） f3、f2、f1、f4 C） f2、f3、f1、f4 D） f2、f3、f4、f1

答复（A） 看见 http://geeksquiz.com/algorithms-analysis-of-algorithms-question-9/ 请解释。

4） 我们得到了一个由n个不同元素组成的集合和一个有n个节点的未标记二叉树。我们可以用多少种方式将给定的集合填充到树中，使其成为二叉搜索树？ A） 0 B） 一, C） n！ D） （1/（n+1））.2nCn

答复（B）

看见 这 PeddaBoku的解释。

5） 下面给出了求数组A[0:n-1]中最长单调递增数列长度的算法。 设Li表示数组中从索引i开始的最长单调递增序列的长度 以下哪项陈述是正确的？ （A） 该算法采用动态规划范式 （B） 该算法具有线性复杂度，并使用分支定界范式 （C） 该算法具有非线性多项式复杂度，并使用分支定界范式 （D） 该算法采用分治范式。

答：（A）

请看 门角 所有上一年的论文/解决方案/解释、教学大纲、重要日期、笔记等。

如果您发现任何答案/解释不正确，或者您想分享有关上述主题的更多信息，请发表评论。