一. 选择题
(1)采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为(  ).
a.  n     b.  (n+1)/2    c.  n/2      d.  (n-1)/2
(2)采用折半法查找长度为10的有序线性表时,在表内各元素等概率的情况,下,查找成功所需的平均比较次数为(    ).
– 37/10     b. 31/10      c.  29/10      d. 27/10
(3)采用分块查找时,若线性表中共有361个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块分(  )结点最好
   a. 10     b. 14      c. 17       d. 19
(4)在哈希函数h(key)=key % m 中, m应取大小恰当的(   )
   a. 素数     b. 奇数      c. 偶数       d. 任意数
二 为数列 25,45,90,65,55,10,75,40,30 分别建立二叉排序树 和平衡二叉树.
三.a.给定数组int a[10]={25,15,80,20,70,45,10,60};给出它的极小堆.
   b.给出从上堆中删除堆顶元素后所得堆对应的数列.
   c.给定字符串  char * a=“previous”;  给出它的极大堆.
   d.给出从上堆中添加一个元素t后所得的堆.
四.用快速排序算法对如下数组排序,
  60   55   65   90   20   5    80  100
  a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 
1.  第一轮支点(pivot) 选20,列出第一轮排序后的元素次序.
2.  列出第一轮排序后的高端子列,对这个子列再用快速排序算法排一论.
3. 快速排序的计算复杂性:
  a.平均情况____ b.最坏情况________  c.最好情况________
   (a) o(nlogn)  (b) o(n2)  (c) o(n)   (d) o(1)
五.用hash函数hashf(x)=x%11将整数值映射为hash表的素引.将数据1,23,19,30,14,33,12,22,7插入hash表中.
a)  用开放探测寻址法建立hash表.
b) 用独立链表地址法建立hash表.
c) 分别计算等概率情况下两种方法查找成功的平均查找次数.