1、请估计一下，如果用合并排序做预排序，用折半查找做查找，要做多少次查找才能使得对一个由 1000个元素构成的数组所做的预排序是有意义的(我们可以假设，所要查 找的都是数组中的元素)。如果是一个由 1000000个元素构成的数组呢？ 2通过连续的插入，为列表5，6,8,3,2,4，7构造一棵平衡二叉树AVL树 3、通过连续的插入， 用9,5,8,3,2,4,7构造一棵2-3树 4， a.用自底向上算法为列表1,8,6,5,3,7，4构造一个堆。 b.用连续的键插入(自顶向下算法)为列表1,8,6,5,3,7,4构造一个堆。 c.这个命题是否永远成立:对于相同的输入，自底向上算法和自顶向下算法产生相同的堆。 5，堆排序是一种稳定的排序算法吗?

1. 对于一个由1000个元素构成的数组，用合并排序做预排序，需要进行log2(1000) = 10次查找才能使得预排序有意义。对于一个由1000000个元素构成的数组，需要进行log2(1000000) = 20次查找才能使得预排序有意义。

2. 将列表5，6，8，3，2，4，7插入到AVL树中，依次插入5、6、8，AVL树为：

    6
   / \
  5   8

再插入3、2、4、7，AVL树为：

      6
     / \
    3   8
   / \
  2   5
   \
    4

3. 将列表9、5、8、3、2、4、7插入到2-3树中，依次插入9、5、8，2-3树为：

       5
     /   \
    3     8
   / \   / \
  2  4  7  9

再插入7、4，2-3树为：

         5
       /   \
      3     7
     / \   / \
    2  4  6  8 9

4. a. 用自底向上算法为列表1、8、6、5、3、7、4构造一个堆：

      1
     / \
    8   6
   / \ / \
  5  3 7  4

b. 用连续的键插入(自顶向下算法)为列表1、8、6、5、3、7、4构造一个堆：

      1
     / \
    5   6
   / \ / \
  8  3 7  4

c. 对于相同的输入，自底向上算法和自顶向下算法产生的堆不一定相同。

5. 堆排序不是一种稳定的排序算法。在堆排序中，元素的交换可能会改变相同元素的相对顺序。