《数据结构与算法》第四章-串-考研真题.docx
数据结构与算法第四章串考研真题精选一、选择题.下面关于串的的叙述中，哪一个是不正确的？（）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储 2 若串 S尸'ABCDEFG' ,S2= '9898' ,S3= '#' ,S4='012345',执行 concat（replace（S 1 ,substr（S 1 ,length（S2）,length（S3）,S3）,substr（S4,index（S2, ' 8' ）,length（S2） 其结果为（）A. ABC#G0123 B. ABCD#2345 C. ABC#G2345 D. ABC#2345E. ABC#G1234 F. ABCD#1234 G. ABC#01234.设有两个串p和q,其中q是p的子串，求q在p中首次出现的位置的算法称为()A.求子串 B.联接 C.匹配D.求串长.已知串S= 'aaab',其next数组值为()。A. 0123 B. 1123C. 1231D. 1211.串 *ababaaababaa* 的 next 数组为()。A. B. C. D. .字符串 4ababaababJ 的 nextval 为()A. (0,1,0,04,1,0/)B. (0,1,0J,0,2,1,0,1)C. (0,101,0,0,0,1,1)D. (0,1,0J,OJA 1,1 ).模式串t= 4abcaabbcabcaabdab5,该模式串的next数组的值为(7 nextval数组的值为 ()。A. C. ()111 0 0 13101 1007018.若串S=' software',其子串的数目是（D. 01 I 1223 1 1234567 12F. 0 110213 1 01 102 1 701)oA. 8 B. 37C. 36A. 8 B. 37C. 36D. 99 .设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子用（非空且不同于S本身）的个数为（）。A. 2n-l B. n2 C. (n2/2)+(n/2) D. (n2/2)+(n/2)-lE. （n2/2）-（n/2）-l F.其他情况10.串的长度是指（）B.串中所含字符的个数D.串中所含非空格字符的个数A.串中所含不同字母的个数C.串中所含不同字符的个数二、判断题1. KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）.设模式串的长度为明目标串的长度为n,当且处理只匹配一次的模式时，朴素的 匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）2 .串是一种数据对象和操作都特殊的线性表。（）二、填空题1 .空格串是指（1）,其长度等于 （2）.2 .组成串的数据元素只能是,. 一个字符串中 称为该串的子串o3 . INDEX ('DATASTRUCTURE', 'STR') =。4 .设正文串长度为n,模式串长度为m,则串匹配的KMP算法的时间复杂度为。5 .模式串P= 4 abaabcacJ的next函数值序列为。6 .字符串'ababaaab'的nextval函数值为。7 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为(1)，又称P为(2)。8 .串是一种特殊的线性表，其特殊性表现在(1):串的两种最基本的存储方式是q_、 (3)：两个串相等的充分必要条件是一(4)。9 .两个字符串相等的充分必要条件是。10 .知 U= 'xyxyxyxxyxy'； t= 'xxy'；ASSIGN (S, U)；ASSIGN (V, SUBSTR (S, INDEX (s, t), LEN (t) +1)；ASSIGN (m, 'ww')求 REPLACE (S, V, m) =。11 .实现字符串拷贝的函数strcpy为：void strcpy(char *s , char *t) /*copy t to s*/ while ().下列程序判断字符串s是否对称，对称则返回1,否则返回0；如f(“abba")返回1, f("abab") 返回0；int f(£D)int i=0,j=0;while (sj)(2);for。-; i<j && si=sj; i+,j-)；return(3)I四、应用题.名词解释：串1 .描述以下概念的区别：空格串与空串。2 .两个字符串S1和S2的长度分别为m和n0求这两个字符串最大共同子串算法的时间复 杂度为T(m,n)。估算最优的T(m,n),并简要说明理由。3 .设主串S= 'xxyxxxyxxxxyxyx',模式串T二'xxyxy'。请问：如何用最少的比较次数找 到T在S中出现的位置？相应的比较次数是多少？4 . KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进？5 .己知模式串t= 4abcaabbabcab,写出用KMP法求得的每个字符对应的next和nextval函 数值。6 .给出字符串1 abacabaaad,在KMP算法中的next和nextval数组。7 .令1= 'abcabaa',求其next函数值和nextval函数值。8 .已知字符串<cddcdccecdea，,计算每个字符的next和nextval函数的值。9 .试利用KMP算法和改进算法分别求pl= 4abaabaa?和p2= *aabbaab,的next函数和 nextval 函数。10 .已知KMP串匹配算法中子串为babababaa,写出next数组改进后的next数组信息值(要 求写出数组下标起点)。11 .求模式串T= 'abcaabbac'的失败函数Nexi(j)值。12 .字符串的模式匹配KMP算法中，失败函数(NEXT)是如何定义的？计算模式串p= 1 aabaabaaabc'中各字符的失败函数值.13 .设字符串 S= 4aabaabaabaac'» P= *aabaac'(1)给出S和P的next值和nextval值：(2)若S作主串，P作模式串，试给出利用BF算法和KMP算法的匹配过程。14 .设目标为 t= 'abcaabbabcabaacbacba',模式为 p= 'abcabaa'(1)计算模式p的naxtval函数值；(5分)(2)不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。(5分) 16.模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m,模 式的长度为n,则在主串中寻找模式的KMP算法的时间复杂性是多少？如果，某一模式P=' abcaacabaca,请给出它的NEXT函数值及NEXT函数的修正值NEXTVAL之值。17 .设目标为$= *abcaabbcaaabababaabca*,模式为 P= 'babab',(1)手工计算模式P的nextval数组的值;(2)写出利用求得的nextval数组，按KMP算法对目标S进行模式匹配的过程。18 .用无回溯的模式匹配法( KMP法)及快速的无回溯的模式匹配法求模式串T的nextj 值，添入下面表中：j1234567ta a b b a a bkmp法求得的nextj值快速无回溯法求得的ncxtj值串答案一、选择题I.B2.E3.C4.A5.C6.A7.ID7.2F8.B9.D10.B二、判断题三.填空题1. (1)由空格字符(ASCII值32)所组成的字符串(2)空格个数2.字符3.任意个连续的字符组成的子序列4. 55.0(m+n)6. 011223127. 010104218.模式匹配 (2)模式串9 . (1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的 字符也相等.两串的长度相等且两串中对应位置的字符也相等。10 .' xyxyxywwy'12. *s+=*t+ 或(*s+=*t+) != '0'(1) charsfl (2)j+(3)i>=j四.应用题1 .串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性 表的特殊性在于串的元素是字符。2 .空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格 的个数。空串是不含任何字符的串，即空串的长度是零。3 .最优的T(m,n)是O (n)。串S2是串SI的子串，且在S1中的位置是I。开始求出最 大公共子串的长度恰是串S2的长度，一般情况下，T(m,n) =O(m*n)o4 .朴素的模式匹配(BruteForce)时间复杂度是。(m*n), KMP算法有一定改进， 时间复杂度达到。(m+n)。本题也可采用从后面匹配的方法，即从右向左扫描，比较6次 成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模 式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二 个字符开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种 方法，本题比较18次成功。5 . KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部 分匹配时，KMP算法的优点更为突出.6 .模式串的next函数定义如下：nextj=根据此定义，可求解模式串I的next和nextval值如下:j1 2 3 4 5 6 7 8 9 10 11 12t串abcaabbab cabncxtjj0 1 1 12 2 3 12 3 4 5nextval j J0 1 10 2 13 0 1 1 0 57 .解法同上题 6,其 next 和 nextval 值分另IJ为 0112123422 和 0102010422。8 .解法同题6, i串的next和nextval函数值分别为0111232和0110132。9 .解法同题 6,其 next 和 nextval 值分别为 011123231 和 。10 . pl 的 next 和 nextval 值分别为：0112234 和 0102102； p2 的 next 和 nextval 值分别为: 0121123 和 0021002。11 . next数组值为011234567改进后的next数组信息值为010101017。12. 011122312。13. nexi定义见题上面6和下面题20.串p的next函数值为：01212345634» S 的 next 与 nextval 值分别为 和 002002002009, p 的 next 与 nextval值分别为012123和002003。(2)利用BF算法的匹配过程:第一趟匹配:aabaabaabaac利用KMP算法的匹配过程： 第一趟匹配：aabaabaabaacaabaac(i=6,j=6) 第：趟匹配：aabaabaabaac (aa)baac 第三趟匹配：aabaabaabaac (成功)(aa)baacaabaac(i=6.j=6) 第.趟匹配：aabaabaabaac aa(i=3j=2) 第三趟匹配：aabaabaabaac a(i=3,j=I) 第四趟匹配：aabaabaabaac aabaac(i=9,j=6) 第五趟匹配：aabaabaabaac aa(i=6j=2) 第六趟匹配：aabaabaabaaca(i=6,j=l)第七趟匹配：aabaabaabaac(成功)aabaac(i=13,j=7)14. (1) p 的 nextval 函数值为 0110132。(p 的 next 函数值为 011 函32)。(2)利用KMP(改进的nexival)算法，每趟匹配过程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=I)第四趟匹配:abcaabbabcabaac bacba(成功)abcabaa(i=15,j=8)KMP算法的时间复杂性是O (m+n)。p 的 next 和 nextval 值分别为 01112212321 和 o(I) p 的 nexival 函数值为 01010。(next 函数值为 01123)(2)利用所得nextval数值，手工模拟对s的匹配过程，与上面16题类似，为节省篇 幅，故略去。15. 模式串T的next和nextval值分别为0121123和00210020
