数据结构习题及答案

第4～5章串和数组

一、填空题

01、称为空串；称为空格串。

02、两个串相等的充分必要条件是。

03、设S="A:/document/Mary.doc"，则strlen(s)= ,"/"的字符定位的位置为。

04、子串的定位运算称为串的模式匹配；称为目标串，称为模式。

05、设目标T="abccdcdccbaa"，模式P=“cdcc”，则第次匹配成功。

06、若n为主串长，m为子串长，则串的匹配算法最坏的情况下需要比较字符的总次数为。

07、假设有二维数组A(6×8)，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置(基地址)为1000，则数组A的体积(存储量)为；末尾元素A(5,7)的第一个字节地址为；若按行存储时，元素A(1,4)的第一个字节地址为；若按列存储时，元素A(4,7)的第一个字节地址为。

08、设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为。

09、三元组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。

10、二维数组A[c1..d1,c2..d2](c1≤d1,c2≤d2)共含有个元素。

11、二维数组A[m][n]采用行序为主的方式存储，每个元素占k 个存储单元，且第1个元素的存储地址是Loc(A[0][0])，则A[i][j]的地址是Loc(A[i][j])= 。

12、有一个10阶对称矩阵A，采用压缩存储方式(以行序为主存储，且A[0][0]的地址为1)，则A[8][5]的地址是。13、稀疏矩阵的稀疏因子为0.05，若采用三元组方式存储，且三元组数组中最多存储20个元素，则该三元组可表示的最大二维方阵的维界是。

二、判断题

( )01、如果两个串含有相同的字符，则这两个串相等。

( )02、数组可以看成线性结构的一种推广，因此存储着大量的插入和删除的运算。

( )03、若采用三元组压缩技术存储稀疏矩阵，则只要将每个元素的行下标与列下标互换，则完成对矩阵的转置运算。

三、单项选择题

( )01、串是任意有限个___。

A)符号构成的序列 B)符号构成的集合

C)字符构成的序列 D)字符构成的集合

( )02、串是一种特殊的线性表，其特殊性体现在___。

A)只有顺序存储结构 B)数据元素是一个字符

C)数据元素是整个串 D)串操作受限只能为子串操作

( )03、___是C语言中的"ABcd123abCD"的子串。A)"ABCD" B)"abcd" C)"AB123" D)"123ab"

( )04、主串S="abc123def123gh123ij"，若对子串T="123"执行定位操作Index(S,T,9)，则操作的结果是___。

A)2 B)3 C)4 D)10

( )05、设有两个串p和q，求q在p中首次出现的位置的运算称作___。

A)连接 B)模式匹配 C)求子串 D)求串长

( )06、设串s1="ABCDEFG"，s2="PQRST"，函数con(x,y)返回

x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j 个字符组成的子串，len(s)返回串s的长度，则下面表达式的结果串是：___。

con(subs(s1,2,len(s2)),subs(s1,len(s2),2))

A)BCDEF B)BCDEFG C)BCPQRST D)BCDEFEF

( )07、若串s="software"，其真子串(不含自身)的个数是___。

A)8 B)37 C)36 D)9

( )08、多维数组的数组元素之间的关系是___的。

A)线性 B)树形 C)图状 D)非线性

( )09、二维数组M由5行6列的元素组成(下标由0开始)，则按行存储时M[3][5]元素与按列存储时的___元素的起始地址是相同的。

A)M[2][4] B)M[3][4] C)M[3][5] D)M[5][3]

( )10、设有一个10阶的对称矩阵A，采有压缩存储方式，以行序为存储主序，若a(1,1)为第一个元素，其存储地址为1，且每个元素占用1个地址空间，则a(8,5)元素的地址为___。

A)13 B)33 C)18 D)40

( )11、设矩阵A是一个对称矩阵(下标从1开始)，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，则下三角部分中任一元素a i,j(i≤j), 在一维数组B中下标k的值是___。

A)i(i-1)/2+j-1 B)i(i-1)/2+j

C)i(i+1)/2+j-1 D)i(i+1)/2+j

( )12、n*n的对称方阵，若以行或列为主序放入内存中，则容量为___。

A)n*n B)n*n/2 C)n*(n+1)/2 D)n*(n-1)/2

四、综合题

01、设s="I AM A STUDENT", t="GOOD", q="WORKER", 求以下

表达式的结果。

(1) Replace(s,"STUDENT",q)

(2) Concat(SubString(s,6,2),

Concat(t,SubString(s,7,8)))

02、若采用按行存储方式，用三元组存储方式表示下面的稀疏

矩阵。

03、下面是4*4稀疏矩阵转置后的三元组表，画出原稀疏矩阵。

i j e

1 2 3

3 1 2

3 3 1

4 3 5

五、算法设计题

01、编写子串查找的算法Index(String S, String T, int pos)。

02、编写删除子串的算法StrDelete(String &S, int pos, int

len)。

03、编写算法求一个子串在主串中出现的次数，若不出现为0。

04、编写一个实现串的置换操作Replace(&S, T, V)的算法。

05、先利用C程序写出二维矩阵的转置一般算法，再写出课本

中稀疏矩阵采用三元组存储后转置算法的2种思路。

1