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

《数据结构第4章测试题B.docx》由会员分享，可在线阅读，更多相关《数据结构第4章测试题B.docx（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 米 第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. ABCDf

2、t#1234)C.G.设有两个串P和q,其中q是p的子串,ABC#G2345 D. ABC#2345ABC懒#01234求q在P中首次出现的位置的算法称为）A.求子串B.联接C.匹配D.求串长串S= aaab,其Next数组值为（A. 0123B. 1123C. 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. 1211C. D.( )B. (0,1,0,1,0,2,1,0,1)D. (0,1,0,1,0,1

3、,0,1,1 )abcaabbcabcaabdab,该模式串的next数组的值为()o）,nextvalA.1 2 C.1 2 E.B. 0D. 0F. 00 1假设串S= software,其子串的数目是（A. 8B. 37C. 36)oD. 99.串设S为一个长度为n的字符串，其中的字符各不相同,（非空且不同于S本身）的个数为A. 2n-lB. 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

4、）.串中所含非空格字符的个数二、判断题. KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）.设模式串的长度为m,目标串的长度为n,当且处理只匹配一次的模式时, 朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）.串是一种数据对象和操作都特殊的线性表。（） 三、填空题空格串是指 ，其长度等于（2）。2 .组成串的数据元素只能是 o. 一个字符串中称为该串的子串.3 . INDEX （DATASTRUCTURE, STR）=。4 .设正文串长度为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、写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。