徐镜春数据结构习题.docx

9.1(1)无序表：顺序查找不成功时，查找长度为n+1；成功时，平均查找长度为1/(n+1)*(1+2+(n+1)=(n+2)/2；两者不相同。（2）表中只有一个关键字等于给定值k的记录，无序表、有序表：顺序查找成功时，平均查找长度均为1/(n)*(1+2+n)=(n+1)/2；两者相同。（3）表中只有m个关键字等于给定值k的记录，无序表：ASL=n+1；有序表：ASL=（n+1）/2+m；两者不相同。9.3ASL=1/10（1+2*2+4*3+3*4）=2.99.119.14删除50后删除68后9.192267413053461301012345678910ASL=（4*1+2*2+3+6）/8=17/89.25int Search-Seq(SSTable ST