数据结构第四章考试.题库-(含答案~).doc
《数据结构第四章考试.题库-(含答案~).doc》由会员分享,可在线阅读,更多相关《数据结构第四章考试.题库-(含答案~).doc(18页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、|第四章 串一、选择题1下面关于串的的叙述中,哪一个是不正确的?( ) 【北方交通大学 2001 一、5(2 分) 】A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储,也可以采用链式存储2 若串 S1=ABCDEFG, S2=9898 ,S3=#,S4=012345,执行concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)其结果为( ) 【北方交通大学 1999 一、5 (25/7 分) 】AABC#G0123 BABCD#23
2、45 CABC#G2345 DABC#2345EABC#G1234 FABCD#1234 GABC#012343设有两个串 p 和 q,其中 q 是 p 的子串,求 q 在 p 中首次出现的位置的算法称为( )A求子串 B联接 C匹配 D求串长【北京邮电大学 2000 二、4(20/8 分) 】 【西安电子科技大学 1996 一、1 (2 分) 】4已知串 S=aaab,其 Next 数组值为( ) 。 【西安电子科技大学 1996 一、7 (2 分) 】A0123 B1123 C1231 D12115串 ababaaababaa 的 next 数组为( ) 。 【中山大学 1999 一、7】
3、A012345678999 B012121111212 C011234223456 D01230123223456字符串ababaabab 的 nextval 为( )A(0,1,0,1,04,1,0,1) B(0,1,0,1,0,2,1,0,1)C(0,1,0,1,0,0,0,1,1) D(0,1,0,1,0,1,0,1,1 )【北京邮电大学 1999 一、1(2 分) 】7模式串 t=abcaabbcabcaabdab,该模式串的 next 数组的值为( ) ,nextval 数组的值为 ( ) 。 A0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B0 1 1 1 2
4、 1 2 1 1 2 3 4 5 6 1 1 2C0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1【北京邮电大学 1998 二、3 (2 分) 】8若串 S=software,其子串的数目是( ) 。 【西安电子科技大学 2001 应用 一、2(2 分) 】A8 B37 C36 D99设 S 为一个长度为 n 的字符串,其中的字符各不相同,则 S 中的互异的非平凡子串(
5、非空且不同于 S 本身)的个数为( ) 。 【中科院计算所 1997 】A2n-1 Bn2 C(n2/2)+(n/2) D(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其他情况10串的长度是指( ) 【北京工商大学 2001 一、6 (3 分) 】A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数二、判断题1KMP 算法的特点是在模式匹配时指示主串的指针不会变小。 ( ) 【北京邮电大学 2002 一、4 (1 分) 】2设模式串的长度为 m,目标串的长度为 n,当 nm 且处理只匹配一次的模式时,朴素的匹配(即子串定位函
6、数)算法所花的时间代价可能会更为节省。 ( ) 【长沙铁道学院 1998 一、1 (1 分)】3串是一种数据对象和操作都特殊的线性表。 ( ) 【大连海事大学 2001 1、L (1 分)】二、填空题1空格串是指_(1)_,其长度等于_(2)_。 【西安电子科技大学 2001 软件 一、4(2 分) 】2组成串的数据元素只能是_。 【中山大学 1998 一、5 (1 分) 】3一个字符串中_称为该串的子串 。 【华中理工大学 2000 一、3(1 分) 】4INDEX(DATASTRUCTURE , STR )=_。 【福州大学 1998 二、4 (2 分)】5设正文串长度为 n,模式串长度为
7、 m,则串匹配的 KMP 算法的时间复杂度为_。 【重庆大学 2000 一、4】|6模式串 P=abaabcac的 next 函数值序列为_。 【西安电子科技大学 2001 软件 一、6(2 分) 】7字符串ababaaab的 nextval 函数值为_。 【北京邮电大学 2001 二、4 (2 分) 】8设 T 和 P 是两个给定的串,在 T 中寻找等于 P 的子串的过程称为_(1)_,又称 P 为_(2)_。【西安电子科技大学 1998 二、5 (16/6 分) 】9串是一种特殊的线性表,其特殊性表现在_(1)_;串的两种最基本的存储方式是_(2)_、_(3)_;两个串相等的充分必要条件是
8、_(4)_。 【中国矿业大学 2000 一、3 (4 分) 】10两个字符串相等的充分必要条件是_。 【西安电子科技大学 1999 软件 一、1 (2 分) 】11知 U=xyxyxyxxyxy;t=xxy ;ASSIGN(S,U) ;ASSIGN(V,SUBSTR(S,INDEX(s,t) ,LEN(t)+1) ) ;ASSIGN(m, ww)求 REPLACE(S,V,m)= _。 【东北大学 1997 一、1 (5 分)】12实现字符串拷贝的函数 strcpy为:void strcpy(char *s , char *t) /*copy t to s*/ while (_) 【浙江大学
9、1999 一、5 (3 分)】13下列程序判断字符串s 是否对称,对称则返回1,否则返回0;如 f(“abba“)返回1,f(“abab“)返回0; int f(1)_)int i=0,j=0;while (sj)(2)_;for(j-; ilength) THEN index:=i; length:=length1; (3)_; ELSE (4)_;(5) _;END;程序(b)void maxcomstr(orderstring *s,*t; int index, length)int i,j,k,length1,con;index=0;length=0;i=1;|while (ileng
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第四 考试 题库 答案
限制150内