数据结构和算法|集28

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

1） 让w（n）和A（n）分别表示在大小为n的输入上执行的算法的最坏情况和平均情况下的运行时间。以下哪项总是正确的？ （A） A（n）=Ω（W（n）） （B） A（n）=Θ（W（n）） （C） A（n）=O（W（n）） （D） A（n）=o（W（n））

答复（C） 最坏情况下的时间复杂度总是大于或等于平均情况下的时间复杂度。

2） 在包含n2^n个元素的二元搜索树中，在平衡的搜索树中搜索元素的最坏情况下运行时间为 （A） Θ（n logn） （B） Θ（n2） ^N ) （C） Θ（n） （D） Θ（对数n）

答复（C） 搜索元素所需的时间为Θ（h），其中h是二叉搜索树（BST）的高度。平衡BST的高度增长与节点数成对数关系。所以搜索一个元素的最坏情况是Θ（Log（n*2^n）），它是Θ（Log（n）+Log（2^n）），它是Θ（Log（n）+n），可以写成Θ（n）。

3） 假设P！=NP，以下哪项是正确的？ （A） NP完全=NP （B） NP完全∩ P=Φ （C） NP-hard=NP （D） P=NP完全

答复（B） 答案是B（不是） 全类 问题可以在多项式时间内解决）。因为，如果一个NP完全问题可以在多项式时间内求解，那么所有NP问题都可以在多项式时间内求解。如果是这样的话，那么NP和P集变得相同，这与给定的条件相矛盾。

4） 树的高度定义为树中最长路径上的边数。下面的伪代码中显示的函数被调用为height（root），以计算以树指针根为根的二叉树的高度。

两个框B1和B2的适当表达式为 （A） B1:（1+高度（n->右侧）），B2:（1+最大值（h1，h2）） （B） B1:（高度（n->右侧）），B2:（1+最大值（h1，h2）） （C） B1：高度（n->右侧），B2：最大值（h1，h2） （D） B1:（1+高度（n->右侧）），B2:最大值（h1，h2）

答复（A） 当n的左子树为NULL且右子树不为NULL时，将执行框B1。在这种情况下，n的高度将是右子树的高度加上1。 当n的左子树和右子树都不为空时，将执行框B2。在这种情况下，n的高度将是n的左子树和右子树的最大高度加1。

5） 一个由n个字符串组成的列表，每个字符串的长度为n，使用合并排序算法按字典顺序排序。这种计算的最坏运行时间是 （A） O（n日志n） （B） O（n） ^2. 日志（n） （C） O（n^2+对数n） （D） O（n^2）

答复（B） 合并排序的递归树将具有高度Logn。和O（n） ^2. )将在递归树的每个级别上完成工作（每个级别涉及n个比较，在最坏的情况下，一个比较需要O（n）个时间）。所以这种合并排序的时间复杂度为O（n） ² 日志n）。

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

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