数据结构考研分类复习真题 第四章 答案[6]

四．应用题

１．串是零个至多个字符组成的有限序列从数据结构角度讲串属于线性结构与线性表的特殊性在于串的元素是字符

２．空格是一个字符其ASCII码值是空格串是由空格组成的串其长度等于空格的个数空串是不含任何字符的串即空串的长度是零

３．最优的T(mn)是O（n）串S是串S的子串且在S中的位置是开始求出最大公共子串的长度恰是串S的长度一般情况下T(mn) =O(m*n)

４．朴素的模式匹配（Brute－Force）时间复杂度是Ｏ（m＊n）KMP算法有一定改进时间复杂度达到Ｏ（m＋n）本题也可采用从后面匹配的方法即从右向左扫描比较６次成功另一种匹配方式是从左往右扫描但是先比较模式串的最后一个字符若不等则模式串后移;若相等再比较模式串的第一个字符若第一个字符也相等则从模式串的第二个字符开始向右比较直至相等或失败若失败模式串后移再重复以上过程按这种方法本题比较次成功

５．KMP算法主要优点是主串指针不回溯当主串很大不能一次读入内存且经常发生部分匹配时KMP算法的优点更为突出

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []