1、对于一个有n个元素的线性表,若采用顺序查找方法时的平均查找长度是什么?若结点是有序的,则采用折半查找法时的平均查找长度是什么?

  顺序查找方法的平均查找长度为 $\frac{n+1}{2}$。
  折半查找方法的平均查找长度为 $\log_2(n+1)-1$。

2、设查找表采用单链表存储,请分别写出对该表进行顺序查找的静态查找和动态查找的算法。

  静态查找:

SSTable* StaticSearch(SSTable *ST, KeyType key){
    SSTable *p = ST;
    while(p != NULL){
        if(p->data == key) return p;
        else p = p->next;
    }
    return NULL;
}

  动态查找:

SSTable* DymamicSearch(SSTable *ST, KeyType key){
    SSTable *p = ST;
    while(p != NULL){
        if(p->data == key) return p;
        else p = p->next;
    }
    SSTable *newST = new SSTable(key, NULL);
    ST.insert(newST);
    return NULL;
}

3、试比较哈希表构造时几种冲突处理方法的优点和缺点。

①开放地址法
  线性探测法:优点:只要散列表未满,总能找到一个不冲突的散列地址。
        缺点:产生冲突的记录被散列到离冲突最近的空地址上,从而又增加了更多的冲突机会。
  二次探测法:优点:探测序列跳跃式地散列到整个表中,不易产生冲突的“聚集”现象。
        缺点:不能保证探测到散列表的所有地址。
②再哈希法
  优点:不易产生冲突的“聚集”现象。
  缺点:计算时间增加。
③链地址法
  优点:不产生冲突的“聚集”现象;删除记录也很简单。
  缺点:指针需要额外的空间。
④建立公共溢出区
  优点:不产生冲突的“聚集”现象。
  缺点:需要建立额外的溢出表。

4、设关键字序列是(19,14,23,01,68,84,27,55,11,34,79),散列表长度是11,散列函数是H(key) = key MOD 11。

①采用开放地址法的线性探测方法解决冲突,请构造该关键字序列的哈希表。

②采用开放地址法的二次探测方法解决冲突,请构造该关键字序列的哈希表。

①哈希表如下:

012345678910
5523011468271184193479

 $H(19) = 19 \ mod \ 11 = 8;$
 $H(14) = 14 \ mod \ 11 = 3;$
 $H(23) = 23 \ mod \ 11 = 1;$
 $H(01) = 01 \ mod \ 11 = 1,冲突; H_1(01) = 2;$
 $H(68) = 68 \ mod \ 11 = 2,冲突; H_1(68) = 3,又冲突; H_2(68) = 4;$
 $H(84) = 84 \ mod \ 11 = 7;$
 $H(27) = 27 \ mod \ 11 = 5;$
 $H(55) = 55 \ mod \ 11 = 0;$
 $H(11) = 11 \ mod \ 11 = 0,冲突; H_1(11) \sim H_5(11)均冲突; H_6(11) = 6;$
 $H(34) = 34 \ mod \ 11 = 1,冲突; H_1(34) \sim H_7(34)均冲突; H_8(34) = 9;$
 $H(79) = 79 \ mod \ 11 = 2,冲突; H_1(79) \sim H_7(79)均冲突; H_8(79) = 10;$

②哈希表如下:

012345678910
5523011434276884197911

 $H(19) = 19 \ mod \ 11 = 8;$
 $H(14) = 14 \ mod \ 11 = 3;$
 $H(23) = 23 \ mod \ 11 = 1;$
 $H(01) = 01 \ mod \ 11 = 1,冲突; H_1(01) = 2;$
 $H(68) = 68 \ mod \ 11 = 2,冲突; H_1(68) = 3,又冲突; H_2(68) = 1,又冲突; H_3(68) = 6;$
 $H(84) = 84 \ mod \ 11 = 7;$
 $H(27) = 27 \ mod \ 11 = 5;$
 $H(55) = 55 \ mod \ 11 = 0;$
 $H(11) = 11 \ mod \ 11 = 0,冲突; H_1(11) = 1,又冲突; H_2(11) = 10;$
 $H(34) = 34 \ mod \ 11 = 1,冲突; H_1(34) \sim H_8(34)均冲突; H_9(34) = (34+5^2) \ mod \ 11 = 4;$
 $H(79) = 79 \ mod \ 11 = 2,冲突; H_1(79) \sim H_3(79)均冲突; H_4(79) = (79-2^2) \ mod \ 11 = 9;$

5、设关键字序列是(19,24,23,17,38,04,27,51,31,34,69),散列表长度是11,散列函数是H(key) = key MOD 11。

①采用开放地址法的线性探测方法解决冲突,请构造该关键字序列的哈希表。

②求出在等概率情况下,该方法的查找成功和不成功的平均查找长度ASL。

①哈希表如下:

地址012345678910
key6923243404381727195131
比较次数91131113132

 $H(19) = 19 \ mod \ 11 = 8;$
 $H(24) = 24 \ mod \ 11 = 2;$
 $H(23) = 23 \ mod \ 11 = 1;$
 $H(17) = 17 \ mod \ 11 = 6;$
 $H(38) = 38 \ mod \ 11 = 5;$
 $H(04) = 04 \ mod \ 11 = 4;$
 $H(27) = 27 \ mod \ 11 = 5,冲突; H_1(27) = 6,又冲突; H_2(27) = 7;$
 $H(51) = 51 \ mod \ 11 = 7,冲突; H_1(51) = 8,又冲突; H_2(51) = 9;$
 $H(31) = 31 \ mod \ 11 = 9,冲突; H_1(31) = 10;$
 $H(34) = 34 \ mod \ 11 = 1,冲突; H_1(34) = 2,又冲突; H_2(34) = 3;$
 $H(69) = 69 \ mod \ 11 = 3,冲突; H_1(69) \sim H_7(69)均冲突; H_8(69) = 0;$
②查找成功平均查找长度 $ASL_{succ}=\frac{9+1+1+3+1+1+1+3+1+3+2}{11} = \frac{26}{11}$
 查找失败平均查找长度 $ASL_{unsucc} = 11$