回 帖 发 新 帖 刷新版面

主题:一写二叉树的问题要求助大家

下面的一些题,看不明白
不知道什么是二叉搜索树,什么堆,时间复杂度的问题


1. 从二叉搜索树中查找一个元素时,其时间复杂度大致为__ O(log2n)______。
        A、 O(n)      B、 O(1)      C、 O(log2n)      D、 O(n2)
    2. 向二叉搜索树中插入一个元素时,其时间复杂度大致为___B_____。
        A、 O(1)      B、 O(log2n )      C、 O(n)      D、 O(nlog2n)
    3. 根据n个元素建立一棵二叉搜索树时,其时间复杂度大致为___D_____。
        A、 O(n)      B、 O(log2n )      C、 O(n2)      D、 O(nlog2n)
    4. 从堆中删除一个元素的时间复杂度为___C____。
        A、 O(1)      B、 O(n)      C、 O(log2n)      D、 O(nlog2n)
    5. 向堆中插入一个元素的时间复杂度为_____A___。
        A、 O(log2n)      B、 O(n)      C、 O(1)     D、 O(nlog2n)
2.对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个___按升序排列的有序序列_____。

3.从一棵二叉搜索树中查找一个元素时,若元素的值等于根结点的值,则表明___找到____,若元素的值小于根结点的值,则继续向__左子树______查找,若元素的大于根结点的值,则继续向__右子树______查找。

4.在一个堆的顺序存储中,若一个元素的下标为i,则它的左孩子元素的下标为__2i+1____,右孩子元素的下标为__2i+2______。
    5. 在一个小根堆中,堆顶结点的值是所有结点中的__最小值______,在一个大根堆中,堆顶结点的值是所有结点中的__最大值_____。
    6.当从一个小根堆中删除一个元素时,需要把___堆尾_____元素填补到堆顶位置,然后再按条件把它逐层__向下______调整。

回复列表 (共1个回复)

沙发

二叉搜索树就是二叉树吧,就是说一个树上的任意节点最多2个儿子
堆是一棵特殊的满二叉搜索树,有大根堆、小根堆等等,大根堆即树的任意节点的值都比它儿子节点的值大
时间复杂度一般指的是最高阶的时间复杂度,具体我说不清楚,举两个例子:
for (i=0;i<n;i++) sum++; 的复杂度是O(n)的
for (i=0;i<=2*n;i++)
  for (j=0;j<3*n+5;j++){
    sum++;
    sum+=2;
  }
复杂度是O(  (2*n+1)*(3*n+5)  ) , 即 O( 6*n^2 ), 即 O( n^2 )
其中O( 6*n^2 )的6叫 常数因子

我来回复

您尚未登录,请登录后再回复。点此登录或注册