题型判断（20*1）+选择（10*2）+简答（含树和森林的转化，时间复杂度，二叉排序树，平衡二叉树，KMP，Hash表，程序输出等）+证明（15*1）+编程（15*1）
KMP排序
这种类型的题不难，掌握了方法就没问题，主要是注意细心，以及要有足够的熟练度。例题
编号j写成Next前两个，无论什么字段，都记为0，1
第三个，aaa，前两位aa，重复字段a，（即前N-1位的重复字段长度+1），2
第四个，aaad，前三位aaa，重复的字段aa（不可将aaa视为和自身重合），3
第五个，aaade，前四位aaad，重复的字段空，0+1=1
第六个，aaadea，前五位aaade，重复的字段空，0+1=1
第七个，aaadeaa，前六位aaadea，重复的字段a，2
第八个，aaadeaaa，前七位aaadeaa，重复的字段aa，3
第九个，aaadeaaaad，前八位aaadeaaa，重复的字段aaa，4
往下就不一一写了，方法就是这样。重复字段：从前往后与从后往前的字段相同。
3.NextVal
核心：相同就写别人的NextVal，不同就写自己的Next。
1.第一位，都写0
2.第二位，Next=1，T=a=T，相同，
写T对应的NextVal，即NextVal=0
3.第三位，Next=2，T=T=a=T，相同，
写T对应的NextVal，即NextVal=0
注：这里一定要回溯到首位，即T1
4.第四位，Next=3，T=a≠d=T，不同，
写T对应的Next，即NextVal=3
5.第五位，Next=1，T=a≠e=T，不同，
写T对应的Next，即NextVal=1
下同，写一下第九个
6.第九位，Next=4，T=d=T，相同，
写T对应的NextVal，即NextVal=3
4.匹配过程
1.比较失败后，失败数值对应的NextVal为几，就表示下次比较从第几位开始。
2.前面的未比较的也写上，建议用括号括起来，这些是不用比较的。
3.每一行未在括号里面的，就是比较的次数。
4.有几行就是比较了几次，建议写在每行后面，用j=来表示。
结语：KMP属于必考题，但每年的题型固定，难度较小。
有一年考的是从第n位开始匹配，不是第一位，这是可能出现的坑。
做这种题，一是，保持熟练度；二是，认真仔细。