数据结构和算法|集7

在2006门CS考试中提出了以下问题。

1.在包含n个数字的二进制最大堆中，可以及时找到最小的元素（GATE CS 2006） （A） 0（n） （B） O（logn） （C） 0（logn） （D） 0（1）

答复（A） 在最大堆中，最小的元素总是出现在叶节点上。所以我们需要检查所有叶节点的最小值。最坏情况下的复杂性为O（n）

         12
        /  
      /      
    8         7
   /         / 
 /         /     
2      3   4       5

2.在数组X中存储二叉树的方案如下。X的索引从1开始，而不是从0开始。根存储在X[1]处。对于存储在X[i]的节点，左子节点（如果有）存储在X[2i]中，右子节点（如果有）存储在X[2i+1]中。为了能够在n个顶点上存储任何二叉树，X的最小大小应该是。（盖特CS 2006） （A） log2n （B） n （C） 2n+1 （D） 2^n-1

答复（D） 对于右偏二叉树，节点数为2^n–1。例如，在下面的二叉树中，节点“A”将存储在索引1中，“B”存储在索引3中，“C”存储在索引7中，“D”存储在索引15中。

A
 
   
    B
      
        
         C
           
             
              D

3.以下哪种就地排序算法需要最少的交换次数？（盖特CS 2006） （A） 快速排序 （B） 插入排序 （C） 选择排序 （D） 堆排序

答复（C） 对于选择排序，所需的交换数量是最小的（Θ（n））。

4.如果数组X中的一个元素大于其右边的所有元素，则称其为前导。查找数组中所有前导的最佳算法（GATE CS 2006） （A） 使用阵列的从左到右传递在线性时间内求解它 （B） 使用阵列从右向左的过程在线性时间内求解它 （C） 使用时间8中的分而治之（nlogn）解决它 （D） 在时间8（n2）中解决它

答复（B） 请看 这 发帖解释。

5、考虑顶点集{V1，V2，.VN}上的加权完全图G，使得边（VI，VJ）的权重为2πJJ。G的最小生成树的权重为：（GATE CS 2006） （A） n-1 （B） 2n-2 （C） nC2 （D） 二,

答复（B） 这种图的最小生成树是

v1
  
    v2
      
       v3
         
          v4
            .
              .
                .
                 vn
 

最小生成树的权重 = 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2 | n–（n-1）| =2n-2

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

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