数据结构第4章测试题B.docxVIP

※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※米※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※ ※※※※※※第4章测试题B卷一、选择题1.下面关于串的的表达中，哪一个是不正确的？（） A.串是字符的有限序列B.空串是由空格构成的串 C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式 存储2 假设串 S产ABCDEFG , S2= 9898 ,S3= ### ,S4= 012345，执行 concat(replace(SI,substr(SI,length(S2),length(S3)),S3),substr(S4,index(S2,3. (4. 5. 6. 7. 8 ),length(S2)))其结果为(A. ABC###G0123 B. ABCD###2345E. ABC###(；1234 F. ABCDft##1234) C. G. 设有两个串P和q,其中q是p的子串,ABC###G2345 D. ABC###2345ABC懒#01234求q在P中首次出现的位置的算法称为 ）A.求子串B.联接C.匹配 D.求串长串S= aaab,其Next数组值为（A. 0123B. 1123 C. 1231串 iababaaababaa, 的 next 数组为 字符串ababaabab的 nextval 为 A. (0,1,0,1,04,1,0,1)C. (0,1,0,1,0,0,0,1,1)模式串t= 数组的值为78. ）o）。 D. 1211 C. D. ( )B. (0,1,0,1,0,2,1,0,1)D. (0,1,0,1,0,1,0,1,1 ) abcaabbcabcaabdab,该模式串的next数组的值为()o）,nextval A. 1 2 C. 1 2 E. B. 0D. 0F. 00 1 假设串S= software,其子串的数目是（A. 8B. 37C. 36 )oD. 99. 串设S为一个长度为n的字符串，其中的字符各不相同,（非空且不同于S本身）的个数为A. 2n-l B. n2C. 那么S中的互异的非平凡子 )o(n2/2) + (n/2)D. (n2/2) + (n/2)-l E. （n2/2）-（n/2）-l F.其他情况10.串的长度是指（） A.串中所含不同字母的个数 C.串中所含不同字符的个数B.串中所含字符的个数1）.串中所含非空格字符的个数 二、判断题 TOC \o 1-5 \h \z . KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）.设模式串的长度为m,目标串的长度为n,当且处理只匹配一次的模式时, 朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）.串是一种数据对象和操作都特殊的线性表。（） 三、填空题 [空格串是指 ⑴，其长度等于（2）。 .组成串的数据元素只能是 o. 一个字符串中称为该串的子串. . INDEX （＜DATASTRUCTURE,, STR）=。 .设正文串长度为n,模式串长度为m,那么串记配的KMP算法的时间复杂度为.模式串P=abaabcac的next函数值序列为 四、综合题1、函数void insert（char*s,char*t, int pos）将字符串t插入到字符串s中,插入 位置为pos。请用c语言实现该函数。假设分配给字符串s的空间足够让字符串t插 入。（说明：不得使用任何库函数）2、编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字 符串中的合法字符为A-Z这26个字母和0-9这10个数字）。 3、写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。