数据结构习题精编：串和数组
一、选择题
1．下面关于串的的叙述中，不正确的是
A．串是字符的有限序列
B．空串是由空格构成的串
C．模式匹配是串的一种重要运算
D．串既可以采用顺序存储，也可以采用链式存储
2．下面关于串的的叙述中，正确的是
A．空串就是空白串B．串相等指的是串的长度相等
C．串的长度必须大于零D．串是一种特殊的线性表
3．字符串是一种特殊的线性表，它与一般线性表的区别是
A．字符串是一种线性结构
B．字符串可以进行复制操作
C．字符串可以顺序存储也可以链式存储
D．字符串由字符构成并且通常作为整体参与操作
4．串s="Data Structure"中长度为3的子串的数目是
A．9B．11C．12D．14
5．若串S="software"，则S的子串的数目是
A．8 B．35 C．36 D．37
6．已知串S= "string"，T="this"，执行运算StrLength(StrCopy(S,T))的结果是A．2 B．4 C．6 D．10
7．若串S="SCIENCESTUDY"，则调用函数StrCopy(P,SubString(S,1,7))后得到A．P="STUDY" B．P="SCIENCE" C．S="STUDY" D．S="SCIENCE" 8．若字符串采用链式存储，每个字符占用一个字节，每个指针在占用四个字节，则该字符串的存储密度为
A．20%B．25%C．50%D．75%
9．为查某一特定单词在文本中出现的位置，可应用的串运算是
A．串联接B．求子串C．串比较D．子串定位10．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最好情况下字符的比较次数
A．m B．n C．n-m D．n+m
11．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最坏情况下字符的比较次数
A．m B．n C．(n-m+1)*m D．n*m
12．已知串S="aaab"，其Next数组的元素值依次为
A．0、1、2、3 B．1、1、2、3 C．1、2、1、1 D．1、2、3、1 13．串"ababaaababaa" 的next数组为
A．011234223456 B．012121111212 C．0123012322345 D．012345678999 14．字符串"ababaabab" 的nextval 为
A．(0,1,0,1,0,0,0,1,1) B．(0,1,0,1,0,1,0,1,1)
C．(0,1,0,1,0,2,1,0,1)  D．(0,1,0,1,0,4,1,0,1)
15．二维数组A[10][20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[0][0]的存储地址为300，则A[8][10]的地址为
A．660 B．732 C．980 D．1132
16．二维数组A[5][6]采用按列为主序的存储方式，每个元素占3个存储单元，若A[0][0]的存储地址是100，则A[4][3]的存储地址是
A．157 B．166 C．169 D．181
17．二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为
A．470 B．471 C．472 D．473
18．假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，每个元素占4个存储单元，则存储地址为2836的元素是
A．R[3][3][3] B．R[3][3][4] C．R[4][3][4] D．R[4][3][5] 19．设二维数组A[1.. m][1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i][j]在一维数组B中的下标为
A．（i-1）*n+j-1 B．（i-1）*n+j C．i*（j-1）D．j*m+i-1
20．设有二维数组A[8][10]，A[0][0]的存储地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为
A．LOC+26L B．LOC+42L C．LOC+50L D．LOC+84L 21．对矩阵压缩存储是为了
A．方便运算B．方便存储C．提高运算速度D．减少存储空间22．设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a1,1为第一个元素，其存储地址为1，每个元素占一个字节空间，则a8,5的地址为
A．13 B．32 C．33 D．75
23．设有一个对称矩阵A[N][N]，A[1][1]为首元素，将其下三角（包括对角线）元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素
A[i][j] （i<j）存于T[k]中，下标k为
A．i(i-1)／2+j B．i(i+1)／2+j C．j(j-1)／2+i D．j(j+1)／2+i 24．设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组(n+1)/2]中，对上述任一元素aij（1≤i，j≤n，且i≤j）在B中的位置为
A．i(i-l)/2+j-1 B．i(i-l)/2+j C．j(j-l)/2+i-1 D．j(j-l)/2+i 25．设有一5阶上三角矩阵A[5][5]，现将其上三角中的元素按列优先顺序存放在一维数组B[15]中。已知A[1][1]存放在B[1]中，其地址为100，每个元素占用2个存储单元，则A[3][4]的地址为
A．116 B．118 C．120 D．122
26．将一个三对角矩阵A[100][100]，按行优先存入一维数组B[298]中，A[1][1]存放在B[1]中。A中元素A[66][65]，在B数组中的位置K为
A．194 B．195 C．197 D．198
27．有一个100*90的稀疏矩阵，非0元素有10个（均为整数）。设每个整型数占2 个字节，则用三元组表示该矩阵时，所需的字节数是
A．20 B．60 C．66 D．18000
28．下面关于广义表的说法中，不正确的是
A．广义表的表头总是一个广义表B．广义表的表尾总是一个广义表
C．广义表难以用顺序结构存储D．广义表可以是一个多层次的结构29．已知广义表的表头为a，表尾为（b，c），则此广义表为
A．(a,b,c) B．(a,(b,c)) C．((a),b,c) D．((a,b,c)) 30．广义表（a，(b，c)，d，e）的表头为
A．a B．(a) C．a,(b,c) D．(a,(b,c)) 31．设广义表L=（（a，b，c）），则L的长度和深度分别为
A．1和1 B．1和2 C．1和3 D．2和3 32．设广义表L=（a，（b，c）），进行GetTail（L）操作后的结果为
A．c B．b，c  C．（b，c）D．（（b，c））33．对于广义表A，若GetHead(A)等于GetTail(A)，则表A为
A．( ) B．(( )) C．(( ),( )) D．(( ),( ),( )) 34．对广义表L=((a，b)，(c，d)，(e，f))执行操作GetTail(GetTail(L))的结果是A．( ) B．(f) C．(e,f) D．((e,f)) 35．对广义表L=((a，b)，c，d) 执行操作GetTail(GetHead(L))的结果是
A．b B．(b) C．(d) D．（c，d）36．已知广义表A=(a,b)，B=(A,A)，C=(a,(b,A),B)，执行操作GetTail(GetHead(GetTail(C))) 后的结果为
A．b B．(b) C．A D．(A) 37．从广义表LS＝（(p，q)，r，s）中分解出原子q的运算是
A．GetTail (GetHead (LS)) B．GetHead (GetTail (GetHead (LS)))
C．GetHead (GetTail (LS)) D．GetTail (GetTail (GetHead (LS))) 38．已知广义表LS＝((a，b，c)，(d，e，f))，从LS中分离出原子e的运算是A．GetHead(GetTail(LS))
B．GetTail(GetHead(LS))
C．GetHead(GetTail(GetHead(GetTail(LS)))
D．GetHead(GetTail(GetTail(GetHead(LS))))
二、填空题
1．空格串是指_____________，其长度等于_____________。
2．组成串的数据元素只能是________。
3．串是一种特殊的线性表，其特殊性表现在_____________；串的两种最基本的存储方式是__________________________；两个串相等的充分必要条件是_____________。
4．若串S1="ABCDEFG", S2="9876" ,S3="###",S4="012345"，执行
Concat(Replace(S1,SubString(S1,StrLength(S2),StrLength(S3)),S3),SubString(S4,Index(S2, "8"),StrLength(S2)))
5．设T和P是两个给定的串，在T中寻等于P的子串的过程称为___________，又称P为_______________。
6．Index（"DATASTRUCTURE"，"STR"）=________。
7．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。
8．模式串P="abaabcac"的next函数值序列为________。
9．字符串"ababaaab"的nextval函数值序列为________。
10．已知串U="xyxyxyxxyxy"，t=" xxy"；依次执行
StrAssign（S，U）；
StrAssign（V，SubString（S，Index（S，t），StrLength（t）+1））；
StrAssign（m，"ww"）；
Replace（S，V，m）；
后，S= _________________，V=___________。
11．设串S="abcdefgh"，T="xyzw"。依次执行
SubString(X，S，3，StrLength(T))；
SubString(Y，S，StrLength(T)，2)；
Concat(Z，X，Y)；
后，串Z的值为_______________。
12．实现字符串拷贝的函数strcpy可写为：
void strcpy(char *s ，char *t) // copy t to s
{
while (__________________________________)；
}
13．有一个二维数组A[8][5]，每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组第1个元素A[0][0]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是______________。若按行序优先存储，则A[3][4]和A[5][3]的第一个字节的地址是___________和___________。若按列序优先存储，则A[2][4]和A[7][1]的第一个字节的地址是___________和___________。
14．一个10阶对称矩阵A，采用行优先顺序压缩存储上三角元素，设第1个元素a[1][1]的存储地址为0，每个元素占有1个字节的存储空间，则a[4][5]的地址为____________。
15．设一个6阶的下三角矩阵B按行优先顺序压缩存储在一维数组A中，其中A[0]存储矩阵的第一个元素B[1][1]，则A[14]存储的元素是________。若将B按列序优先顺序压缩存储在一维数组A中，则A[14]存储的元素是________。
16．稀疏矩阵一般有两种压缩存储方法，即____________和______________。
17．一个广义表的长度是指__________________，而表的深度是指______________。广义表G=(a，
b，(c，d，(e，f))，G)的长度为___________。广义表L=(a，(b，( )))的深度为________。
18．设广义表L=(()，())，则GetHead(L)是_________，GetTail(L)是_________，L的长度是________；深度是_______。广义表（（a，b），c，d）的表头是__________，表尾是____________。
指针与二维数组
19．用广义表的取表头GetHead和取表尾GetTail的运算，从广义表LS=(b,c,(f),((d)))中分解出原子c的操作为_________。
20. 设广义表A=(a，b，(c，d)，(e，(f，g)))，用广义表的取表头GetHead和取表尾GetTail 运算，从A中分解出原子d的操作为_______________________。
三、解答题
1．设有对称矩阵A[n][n]（行和列下标均从1开始），将其上三角元素逐行存于数组B[n*(n+1)/2]中，使得B[k]=a[i][j]（1<=i，j<=n，0<=k<=n*(n+1)/2-1）。试推导出由i、j和n 计算k的一般公式。
2．在n×n矩阵A中，所有下标值满足关系式i+j＜n+l的元素aij（1<=i，j<=n）的值均为0，现将A中其它元素按行优先顺序依次存储到长度为n(n+1)/2的一维数组sa中，其中元素a1,n存储在sa[0]中。
（1）设n=10，元素a[4][9]存储在sa[p]中，写出下标p的值。
（2）设元素a[i][j]（1<=i，j<=n，且i+j＜n+l）存储在sa[k]中，写出由i、j和n计算k 的一般公式。
3．设有n阶三对角矩阵，将其三条对角线上的元素逐行地存于数组B[1..3n-2]中，使得B[k]=a[i][j]。
（1）设n=100，将一个A[100][100]的三对角矩阵，按行优先存入一维数组]中，试确定m的值，并求A中元素A[77][78]在B数组中的位置K。
（2）求用i、j表示k的下标变换公式。
（3）求用k表示i、j的下标变换公式。
4．设A和B均为n阶下三角矩阵，在下三角区域中各有n（n+1）/2个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中，写出所给出方案的代码段。并给出计算A的矩阵元素a[i][j]和B 的矩阵元素b[i][j]在C中的存放位置下标的公式。设A、B、C三个矩阵的行、列下标均从1开始。
5．设有稀疏矩阵A如下（矩阵元素的行列下标均从1开始）：
（1）若矩阵A采用三元组顺序表存储，试给出其三元组表。
（2）若矩阵采用十字链表存储，试画出该矩阵的十字链表。
6．利用广义表的GetHead和GetTail操作写出函数表达式，把以下各小题中的单元素banana从广义表中分离出来：
（1）L1= （apple，pear，banana，orange）
（2）L2= （（apple，pear），（banana，orange））
（3）L3= （（（（apple））），（（pear）），（banana），orange）
（4）L4= （apple，（pear，（banana），orange））
7．画出广义表((((a)，b))，((( )，d)，(e，f))) 的两种存储结构图示。
8．已知广义表如下：
A=（B，y）
B=（x，L）
L=（a，b）
（1）写出下列操作的结果
GetTail（A）=_______________。
GetHead（B）=______________。
（2）画出广义表A所对应的图形（树形结构）。
四、分析题
1．阅读下列函数，并回答问题。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。