Problem A: 查找与排序算法

1、哈希表长m=13哈希函数H(key)=key%13表中已有4个结点：

addr(15)=2；addr(29)=3； addr(17)=4； addr(40)=1；

其余地址为空如果采用线性探测再散列处理冲突关键字为16的结点的地址是（   ）。

      A. 8     B. 3   C. 5 D.7

2、【NOIP2000】某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索(binary search)，在最坏的情況下，需检视(     )个单元。

      A．1000         B．10            C．100          D．500

3、【NOIP2001】在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为（     ）。

      A．2             B．3           C．4              D．5

4. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用(  )查找方法。

     A. 分块    B. 顺序      C. 二分 D. 散列

5、在以下排序算法中，不需要进行关键字比较操作的算法是(    ) 。

     A. 基数排序     B. 昌泡排序   C. 堆排序 D.直接插入排序

6. 如排序算法的稳定性是指关键码相同的记录排序前后相对位置不发生改变。下列哪种排序算法是不稳定的:

    A. 插入排序     B. 昌泡排序   C. 归并排序 D. 快速排序

7. 快速排序最坏情况下的算法复杂度为:

     A. O(log2n)     B. O(n)   C. O(nlog2n) D. O(n2)快速排序

8. 如果不在快速排序中引入随机化，有可能导致的后果是（     ）。

      A.数组访问越界        B.陷入死循环         C.排序结果错误        D.排序时间退化为平方级

9.  快速排序平均情况与最坏情况下的算法复杂度分别为:

     A.平均情况O(nlog2n)，最坏情况O(n2)                  B. A.平均情况O(n)，最坏情况O(n2)

     C. 平均情况O(n)，最坏情况O(nlog2n)                   D. A.平均情况O(log2n)，最坏情况O(n2)

10. 以下时间复杂度不是的O(n2)排序方法是(    ) 。

     A. 插入排序     B. 昌泡排序   C. 归并排序 D. 选择排序