两道运算题,关于数据结构的

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/09 11:29:13
两道运算题,关于数据结构的

两道运算题,关于数据结构的
两道运算题,关于数据结构的

 


两道运算题,关于数据结构的

(38,24,40,|46|,56,80,95,79)//第一次划分基准46

(24,38,40,46,56,80,95,79)//以38为基准的前半部分,以56为基准的后半部分没变化

(24,38,40,46,56,79,80,95,)//以80为基准

(78(0),15(2),03(3),57(5),45(6),20(7),31(8),23(10),36(11),12(12))

其中HT[1],HT[4],HT[9]空缺.

12的查找长度为1,即HT[12%13] = HT[12] = 12

23的查找长度为1,即HT[23%13] = HT[10] = 23

45的查找长度为1,即HT[45%13] = HT[6] = 45

57的查找长度为1,即HT[57%13] = HT[5] = 57

20的查找长度为1,即HT[20%13] = HT[7] = 20

03的查找长度为1,即HT[03%13] = HT[3] = 03

78的查找长度为1,即HT[78%13] = HT[0] = 78

31的查找长度为4,因为HT[31%13] = HT[5] = 57,线性探查HT[6] = 45,HT[7] = 20, HT[8] = 31,一共找了5,6,7,8这4个长度.

15的查找长度为1,即HT[15%13] = HT[2]

36的查找长度为1,因为HT[36%13] = HT[10] = 23,现行查找 HT[11] = 36

因此,平均查找长度为(1+1+1+1+1+1+1+4+1+1)/10 = 1.3