《数据结构与算法》第四章-串-考研真题.docx

《《数据结构与算法》第四章-串-考研真题.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法》第四章-串-考研真题.docx（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法第四章串考研真题精选一、选择题.下面关于串的的叙述中，哪一个是不正确的？（）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#234

2、5E. 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

3、 ).模式串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

4、/2)-lE. （n2/2）-（n/2）-l F.其他情况10.串的长度是指（）B.串中所含字符的个数D.串中所含非空格字符的个数A.串中所含不同字母的个数C.串中所含不同字符的个数二、判断题1. KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）.设模式串的长度为明目标串的长度为n,当且处理只匹配一次的模式时，朴素的 匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）2 .串是一种数据对象和操作都特殊的线性表。（）二、填空题1 .空格串是指（1）,其长度等于 （2）.2 .组成串的数据元素只能是,. 一个字符串中 称为该串的子串o3 . INDEX (DATASTRUCTU

5、RE, 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, I

6、NDEX (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。-; ij & si=sj; i+,j-)；return(3)I四、应用题.名词解释：串1 .描述以下概念的区别：空格串与空串。2 .两个

7、字符串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

8、,求其next函数值和nextval函数值。8 .已知字符串=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算法有一定改进， 时间复杂度达

9、到。(m+n)。本题也可采用从后面匹配的方法，即从右向左扫描，比较6次 成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模 式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二 个字符开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种 方法，本题比较18次成功。5 . KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部 分匹配时，KMP算法的优点更为突出.6 .模式串的next函数定义如下：nextj=根据此定义，可求解模式串I的next和nextval值如下:j1 2 3 4 5 6 7

10、 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 和 n

11、extval 值分别为: 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) 第：趟匹配：

12、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 的 ne

13、xt 函数值为 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