填空题

1. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）

解析：对于N个元素而言，查找第一个元素需要比较1次，第2个元素需要比较2次，…，第n个元素需要比较n次，所以总的比较次数为，对于N个元素的平均查找长度为。

1. 一个文件包含了200个记录，若采用分块查找法，每块长度为4，则平均查找长度为（）

解析：分块查找，又称为索引顺序查找，吸取了顺序查找和折半查找各自的优点，既有动态结构，又适合快速查找。
基本思想：将查找表分为若干个子块。块内元素可以无序，但块间元素是有序的，即第一个块中的最小关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。在建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中第一个元素的地址，索引表按关键字有序排列。
所以使用分块查找的方式是：先查索引表，确定在那个块，之后在块间顺序查找。块的数量为，块间查找的平均查找长度为，块内查找的平均查找长度为，总的平均查找长度为：。
注意：本题未说明块间和块内是否有序，所以默认按照无序进行计算。如果有序，则可以采用二分查找法。

1. 使用KMP算法在文本串S中找模式串P是一种常见的方法。假设S=P={xyxyyxxyx}，亦即将S对自己进行匹配，匹配过程中正确的next数组是（）。

KMP博文连接：http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html
总结：当j==1或者j>=k>1的时候，next[j]的值为MAX的值+1。MAX值的确定：求出待匹配串的所有前缀和后缀，其中的公共部分为数量为MAX的值。

判断题

1. 对无序表用二分法查找比顺序查找快。

答：错误。二分法只适用于有序的顺序表，对于无序表无法使用二分法进行查找。