问答题
试述顺序查找、二分法查找和分块查找对被查找的表中的元素有什么要求,并求对长度为n的表,分别按这三种方法进行查找时的平均查找长度。
【正确答案】对于顺序查找,表中元素可以按任何方式存放;而采用二分法查找时要求表中元素必须是有序的,而且须以顺序方式进行存储;若要利用分块查找方法,则要求表中元素须“块”间有序,但每一块内的元素可以按任意方式存放。
平均查找长度:顺序查找时查找成功的平均查找长度为(n+1)/2,而采用二分法查找时,平均查找长度为log2(n+1)-1(当n较大时)。分块查找平均查找长度的大小与其确定所在块所采用的查找方法有关。若用顺序查找确定所在块,则平均查找长度为(n/s+s)/2+1(或(s2+2s+n)/2s);若用二分法查找确定所在的块,平均查找长度为log2(n/s+1)+s/2,其中s为每块含有的元素个数。
【答案解析】