第一部分 选择题 (共20分)

一、单项选择题 (本大题共8小题，每小题2分，共16分)

  1.某算法的空间花费s(n)=100nlog2n+0.5n1.5+1000n+2000,其空间复杂度为 [   ]
　　A.O(1)                      B.O(n)
    C.O(n1.5)                   D.O(nlog2n)

  2.在单项链表中删除一个指定结点的后继的时间复杂度为 [   ]
　　A.O(n)                      B.O(nlog2n)
    C.O(1)                      D.O(√n)

  3.在n(n>0)个元素的顺序栈中删除1个元素的时间复杂度为 [   ]
　　A.O(1)                      B.O(√n)
    C.O(nlog2n)                 D.O(n)

  4.对长度为n的字符串进行字符定位运算的时间复杂度为 [   ]
    A.O(1)                      B.O(√n)
    C.O(nlog2n)                 D.O(n)

  5.广义表的深度是 [   ]
    A.广义表中子表个数           B.广义表括号个数
    C.广义表展开后所含的括号层数 D.广义表中元素个数

  6.高度为h(h>0)的二叉树最少有________个结点 [   ]
    A.h                          B.h-1
    C.h+1                        D.2h

  7.n个顶点的带权无向连通图的最小生成树包含________个顶点 [   ]
    A.n-1                        B.n
    C.n/2                        D.n+1

  8.冒泡排序在最好情况下时间复杂度为 [   ]
　　A.O(1)                      B.O(nlog2n)
    C.O(n)                      D.O(n2)

   9.采用拉链法解决冲突的散列表中，查找的平均查找长度 [   ]