数据结构和算法|集16

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

1、考虑使用数组实现的二进制最大堆。以下哪个数组表示二进制最大堆？ （A） 25,12,16,13,10,8,14 （B） 25,14,13,16,10,8,12 （C） 25,14,16,13,10,8,12 （D） 25,14,12,13,10,8,16

答复（C）

如果树中每个节点的数据都大于或等于其子节点的数据，则树就是最大堆。

在堆树的数组表示中，索引i处的节点的左子节点位于索引2i+1处，右子节点位于索引2i+2处。

           25
        /      
      /          
    14            16
   /             /  
 /             /     
13     10      8       12

2.对上一个问题的正确答案进行两次删除操作后，数组的内容是什么？ （A） 14,13,12,10,8 （B） 14,12,13,8,10 （C） 14,13,8,12,10 （D） 14,13,12,8,10

答复（D）

对于堆树，删除节点包括以下两个操作。

1） 用最后一级的最后一个元素替换根。 2） 从根开始，将整棵树从上到下排列。。

让我们逐个删除这两个节点： 1） 删除25项： 用12代替25

          12
        /    
      /       
    14        16
   /          /
 /           /
13     10    8

由于根违反了heap属性（16大于12），所以将16作为树的根。

           16
        /     
      /        
    14         12
   /          /
  /          /
13     10    8

2） 删除16项： 用8代替16

           8
        /    
       /      
    14         12
   / 
  /   
 13     10

从根到底都是健康的。

           14
         /    
       /       
     8         12
    / 
   /   
 13     10

            14
         /     
        /       
     13         12
    / 
   /   
  8    10

3.在快速排序中，为了对n个元素进行排序，使用O（n）时间算法选择第（n/4）个最小元素作为枢轴。快速排序最糟糕的时间复杂度是什么？ （A） Θ（n） （B） Θ（n logn） （C） Θ（n^2） （D） Θ（n） ^2. 日志（n）

答复（B） 递归表达式变成：

T（n）=T（n/4）+T（3n/4）+cn

求解上述递归后，我们得到Θ（nLogn）。

4.任何具有7个节点的AVL树的最大高度是多少？假设具有单个节点的树的高度为0。 （A） 二, （B） 三, （C） 四, （D） 五,

答复（B） AVL树是具有以下限制的二叉树。 1） 孩子们的身高差异最大为1。 2） 两个孩子都是AVL树

                 a
               /   
             /      
            b        c
          /        /
         /        /
        d     e   g
       /
      /
     h

参考资料： http://en.wikipedia.org/wiki/AVL_tree

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