第四章 串
一、 选择题
1、设串s1=‘ABCDEFG‘，s2=‘PQRST‘，函数Concat(x,y)返回x和y串的连接串，Substr(s,i,j)返回串s从序号
I
开始的
j
个字符组成的子串，length(s)返回串
s
的长度，则
Concat(Substr(s1,2,length(s2)),Substr(s1,length(s2),2))的结果串是（ ）。
A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 2、空串和空格是相同的（ ）。A、正确 B、错误
3、若串S1=‘ABCDEFG‘，S2=‘9898‘，S3=‘###‘，S4=‘012345‘，则执行
replace(s1,Substr(s1,4,length(s3)),s3),Concat(s1,Substr(s4,index(s2,‘8‘),length(s2)))后，其结果为（ ）。
A、ABC###G0123 B、ABCD###2345 C、ABC###G2345
D、ABC###2345 E、ABC###G1234 F、ABCD###1234 G、ABC###01234 4、串是一种特殊的线性表，其特殊性体现在（ D ）。
A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符
5、设有两个串p和q，求q在p中首次出现的位置的运算称为（ ）。
A、连接 B、模式匹配 C、求子串 D、求串长 6、下面关于串的的叙述中，哪一个是不正确的？（ ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 7、串的长度是指（ ）
A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数
二、 判断题
1、 子串定位函数的时间复杂度在最坏的情况下为O（n*m），因此子串定位函数没有实际利用价值。 2、 设有两个串p和q，其中q是p的子串，把q在p中首次出现的位置作为子串q在p中的位置的
算法称为匹配。
3、 KMP算法的最大特点是指示主串的指针不需要回朔。
三、 填空题
1、设s=‘I_AM_A_TEACHER‘，其长度为（ ）。 2、空串是（零个字符的串 ），其长度为（ ）。
3、设S1=‘GOOD‘，S2=‘︼‘，S3=‘BYE!‘，则S1、S2和S3连接后的结果是（ ）。
20
4、两个串相等的充分必要条件是（
）。
5、串的两种最基本的存储方式是（ 顺序存储方式和链接存储方式 ）。 6、空格串是_________，其长度等于_________。
7、设有两个串q和p，求q在p中首次出现的算法叫_________。 8、串的连接运算不满足_________，满足_________。交换律、结合律
四、 简答题
1、 已知下列字符串（假设采用定长存储结构）
a=‘this‘,b=‘ ?, c=‘good‘, d=‘ne‘, f=‘a sample‘,g=‘is‘
顺序执行以下操作后，S、T、U、V、Length(s)、Index(v,g)、Index(u,g)各是什么？ S=Concat(a,concat(Substr(f,2,7),Concat(b,Substr(a,3,2)))) T=Replace(f,Substr(f,3,6),c) U=Concat(Substr(c,3,1),d)
V=Concat(S,Concat(b,Concat(T,Concat(b,U)))) 2、 执行以下函数会产生怎样的输出结果？
Void demonstrate() {Strassign(s,‘this is a book‘); Replace(s,Substring(s,3,7),‘ese are‘); Strassign(t,Concat(s,‘s‘)); Strassign(u,‘xyxyxyxyxyxy‘); Strassign(v,Substring(u,6,3)); Strassign(w,‘w‘);
Printf(?t=‘,t,‘v=‘,v,‘u=‘,Replace(u,v,w))}
3、 设s=‘I am a student‘，t=‘good‘，q=‘worker‘。求strlength(s)，strlength(t)，substr(s,8,7)，substr(t,2,1)，
index(s,‘a‘)，index(s,t)，replace(s,‘student‘,q)，concat(substr(s,6,2),concat(t,substr(s,7,8)))。 4、 已知s=‘(xyz)+*‘，t=‘(x+z)*y‘，利用连接、求子串和置换等基本操作，将s转化为t。
4.
s1=substr(s,1,5) //s1=‘(xyz)‘ s2=substr(s,3,1) //s2=‘y‘ s3=substr(s,6,1) //s3=‘+‘ s4=substr(s,7,1) //s4=‘*‘ replace(s1,3,1,s3) //s1=‘(x+y)‘ s=s1||s4||s2
21
五、 算法设计题
1、 串s和t采用堆存储，设计一个函数，求第一个在s而不在t中的字符的序号。 2、 采用堆存储串s，设计函数删除s中第I个字符开始的j个字符。 3、 若x和y是采用堆存储的串，设计一个比较两个串是否相等的函数。
一、int search(Hstring s,Hstring t)
{int I=0,flag=1;
while(I {if(s.ch[i]!=t.ch[i])flag=0;I++} if(flag) return –1; else return I-1; } 二、int delij(Hstring &s,int I,int j) {int k; if(I<0||j<0) return 0 if(I+j>s.length)j=s.length-I; for(k=I+j;k 三、int compare(Hstring x,Hstring y) {int I=0,flag=1; if(x.length!=y.length)return 0; else {while(I {if(x.ch[i]!=y.ch[i])flag=0; I++;} Return flag; } } 22 第五章 数组与广义表 一、 选择题 1、在以下讲述中，正确的是（ ）。 A、 线性表的现行存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出 2、若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ ）。 A、正确 B、错误 3、二维数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（ ）。 A、SA+141 B、SA+180 C、SA+222 D、SA+225 4、数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（ ）。 A、80 B、100 C、240 D、270 5、常对数组进行的两种基本操作是（ ）。 A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引 6、将一个A[15][15]的下三角矩阵（第一个元素为A[1][1]），按行优先存入一维数组B[120]中，A中元素A[6][5]在B数组中的位置K为（ ）。 A、19 B、26 C、21 D、15 7、若广义表A满足Head(A)=Tail(A)，则A为（ ）。 A、（） B、（（）） C、（（），（）） D、（（），（），（）） 8、广义表（（a）,a）的表头是（ ），表尾是（ ）。 A、a B、b C、(a) D、((a)) 9、广义表（（a,b）,c,d）的表头是（ ），表尾是（ ）。 A、a B、b C、(a,b) D、(c,d) 10、广义表（（a））的表头是（ ），表尾是（ ）。 A、a B、(a) C、() D、((a)) 11、广义表（a,b,c,d）的表头是（ ），表尾是（ ）。 A、a B、(a) C、(a,b) D、(b,c,d) 12、广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。 A、a B、() C、(a,b,c,d) D、((a,b,c,d)) 13、下面结论正确的是（ ）。 A、一个广义表的表头肯定不是一个广义表 B、一个广义表的表尾肯定是一个广义表 C、广义表L=（（），（A，B））的表头为空表 D、广义表中原子个数即为广义表的长度 23 14、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=( ) A、(G) B、(D) C、C D、 D 15、已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出原子项t的操作是（ ）。 A、Head(Head(Tail(Tail(L)))) B、Tail(Head(Head(Tail(L)))) C、Head(Tail(Head(Tail(L)))) D、Head(Tail(Head(Tail(Tail(L))))) 16、设A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))=( ) A. (g) B.(d) C.c D.d 17、对矩阵压缩存储是为了（ ） A、方便运算 B、节省空间 C、方便存储 D、提高运算速度 18、稀疏矩阵一般的压缩存储方法有两种，即（ ） A、二元数组和三元数组 B、三元组和散列 C、三元组和十字链表 D、散列和十字链表 二、 判断题 1． 数组是同类型值的集合。x 2． 数组的存储结构是一组连续的内存单元。v 3． 数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。 4． 插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。 5． 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。 6． 广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。 7． 线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。v 8． 广义表中原子个数即为广义表的长度。 9． 广义表中元素的个数即为广义表的深度。 三、 填空题 1、设a是含有N个分量的整数数组，则求该数组中最大整数的递归定义为（ ），最小整数的递归定义为（ ）。 最大整数的递归定义为：f(k)=a[0](k=0时)||f(k)=max(f(k-1),a[k])(k>0时) 最小整数的递归定义为：f(k)=a[0](k=0时)||f(k)=min(f(k-1),a[k])(k>0时) 2、二维数组A[10][5]采用行序为主方式存储，每个元素占4个存储单元，并且A[5][3]的存储地址是1000，则A[8][2]的地址是（ ）。 3、二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是Loc(A[0][0])，则A[i][j]的地址是（ ）。 4、广义表的（ ）定义为广义表中括弧的重数。 5、设广义表L=（（ ），（ ）），则Head(L)=（ ）；Tail(L)=（ ）；L的长度是（ ）；L的深度是（ ）。 6、广义表中的元素可以是（ 原子或子表 ），其描述宜采用程序设计语言中的（ 链表 ）表示。 24
