第四、五章串、数组和广义表练习题答案
一．填空题c语言二维数组转置
1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。
2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为
3。
3. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。
4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第  6 次匹配成功。
5. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。
6. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A57的第一个字节地址为1282 ；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276 。
(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！)
7. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950 。
答：不考虑0行0列，利用列优先公式：LOC(a ij)=LOC(a c1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950
8. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素
的行下标、列下标和元素值。
9.求下列广义表操作的结果：
（1）GetHead【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号
（2）GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ;
（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】===    b ;
（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d）;
10．C语言规定，字符串常量按_字符数组_____处理，它的值在程序的执行过程中是不能改变的。而串变量与其他变量不一样，不能由_赋值_____语句对其赋值。
11．含零个字符的串称为___空___串，用_ф_____表示。其他串称为_非空_____串。任何串中所含__字符
____的个数称为该串的长度。
12．当且仅当两个串的_长度_____相等并且各个对应位置上的字符都__相同____时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的_子_____串，该串称为它所有子串的__主____串。
13．串的顺序存储有两种方法：一种是每个单元只存一个字符，称为_非紧缩_____格式，另一种是每个单元存放多个字符，称为__紧缩____格式。
14．通常将链串中每个存储结点所存储的字符个数称为_结点大小_____。当结点大小大于1时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域里补上不属于字符集的特殊符号。
15．一般地，一个n维数组可视为其数据元素为__n-1维数组的线性表。数组通常只有___读________和__写_________两种基本运算。、、、、
16，通常采用__顺序_________存储结构来存放数组。对二维数组可有两种存储方法：一种是以__列序_________为主序的存储方式，另一种是以_行序__________为主序的存储方式。C语言数组用的是以______行_____序为主序的存储方法；FORTRAN语言用的是以__列________序为主序的存储方法
17．需要压缩存储的矩阵可分为_特殊矩阵和___稀疏________矩阵两种。
18．对称方阵中有近半的元素重复，若为每一对元素只分配一个存储空间，则可将n2个元素压缩存储到__ n(n+1)/2个元素的存储空间中。
19．假设以一维数组M（1：n(n+1)/2）作为n阶对称矩阵A的存储结构，以行序为主序存储其下三角（包括对角线）中的元素，数组M和矩阵A间对应的关系为__
20．上三角矩阵中，主对角线上的第t行(1<=t<=n)有___________个元素，按行优先顺序存
放上三角矩阵中的元素a
ij 时，a
ij
之前的前i-1行共有___________个元素，在第i行上， a
ij
是该行的第___________个元素，M[k]和a
ij
的对应关系是。
当i>j时，a ij=c,c存放在M[___________]中。
21．下三角矩阵的存储和对称矩阵类似。M[K]和a
ij
的对应关系是___________。
22．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在___________处用适当的句子用以填充。
Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b)
{  (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu;
if(a.tu)
{  q=1;
for(col=1; __ col<=a.nu, ________;col++)
for(p=1;p<=a.tu;p++)
if(a.data[p].j ==col)
{(*b).data[q].i=a.data[p].j;
(*b).data[q].j=a.data[p].i;
(*b).data[q].v=a.data[p].v;
__q++_________;
}
}
23．基于三元组的稀疏矩阵转置的处理方法有两种，以下计算按照矩阵A的三元组a.data 的次序进行转置，请在___________处用适当的句子用以填充。
Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b)
{ (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu=a.tu;
if(a.tu)
{for(col=1; col<=a.nu;col++) num[col]=0;
for(t=1;t<=a,tu;t++) num[a.data[t].j]++;
cpot[1]=1;
for(col=2;col<=a.nu;col++)
cpot[col]=_ cpot[col-1]+num[col-1];
for(p=1;p<=a.tu;p++)
{  col=a.data[p].j;
q=cpot[col];
(*b).data[q].i=a.data[p].j;
(*b).data[q].j=a.data[p].i;
(*b).data[q].v=a.data[p].v;
cpot[col]++;
}
}
}
24．设有二为数组int M[10][20](注：m 为0...10,n 为0...20)，每个元素（整数）栈两个存储单元，数组的起始地址为2000，元素M[5][10]的存储位置为_2230__________，M[8][19]的存储值为__2374_________。
25．数组M 中每个元素的长度是3个字节，行下标i 从1到8，列下标j 从1到0，从首的址EA 开始连续存
放在存储其中。若按行方式存放，元素M[8][5]的起始地址为EA+222___________；若按列优先方式存放，元素M[8][5]的地址为_ EA+117__________。
26．二维数组M 的成员是6个字符（每个字符栈一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要___540________个字节；M 的第8列和第5行共占_108__________个字节；若M 按行方式存储，元素M[8][5]的起始地址与当M 按列优先方式存储时的_,M[3][10]__________元素的起始地址一致。
二．选择题
（ B  ）1.串是一种特殊的线性表，其特殊性体现在：
Ａ．可以顺序存储      Ｂ．数据元素是一个字符
Ｃ．可以链式存储        Ｄ．数据元素可以是多个字符
（ B  ）2.设有两个串p 和q ，求q 在p 中首次出现的位置的运算称作：
Ａ．连接      Ｂ．模式匹配    Ｃ．求子串      Ｄ．求串长
（ D  ）3.设串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))的结果串是：
Ａ．BCDEF      Ｂ．BCDEFG    Ｃ．BCPQRST        Ｄ．BCDEFEF
解：con(x,y)返回x 和y 串的连接串，即 con(x,y)＝‘ABCDEFGPQRST ’；
subs(s, i, j)返回串s 的从序号i 开始的j 个字符组成的子串，则
subs(s1, 2, len(s2))＝subs(s1, 2, 5)=’ BCDEF’;  subs(s1, len(s2), 2)＝subs(s1, 5, 2)=’ EF’;
所以con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))＝con(’ BCDEF’, ’ EF’)之连接，即BCDEFEF （ A  ）4.假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为      。（无第0行第0列元素）
Ａ．16902    Ｂ．16904      Ｃ．14454      Ｄ．答案A, B, C 均不对
答：此题与填空题第8小题相似。（57列×60行＋31行）×2字节＋10000=16902
(  B    )5. 设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是：
Ａ．i(i-1)/2+j-1    Ｂ．i(i-1)/2+j      Ｃ．i(i+1)/2+j-1        Ｄ．
i(i+1)/2+j
⎥⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎢⎣⎡=n n n n a a a a a a A ,2,1,2,21,21,1
6. 从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。
有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是A。若按行存储，则A[3,5]和A[5,3]的第一个字节的地址分别是  B 和  C 。若按列存储，
则A[7,1]和A[2,4]的第一个字节的地址分别是  D 和  E 。
供选择的答案：
A～E：①28 ②44 ③76 ④92 ⑤108
⑥116 ⑦132 ⑧176 ⑨184 ⑩188
答案：ABCDE=8, 3, 5, 1,    6
7. 有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是A个字节。假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是  B 。若按行存储，则A[2,4]的第一个字节的地址是  C 。若按列存储，则A[5,7]的第一个字节的地址是  D 。
供选择的答案
A～D：①12 ②66 ③72 ④96 ⑤114 ⑥120
⑦156 ⑧234 ⑨276 ⑩282 （11）283 （12）288
答案：ABCD=12, 10, 3, 9
8．在串的基本运算中，属于加工型运算的有（）
①EQAL(S,T)    ②LENGTH(S)
③CONCAT(S,T)  ④REPLACE(S,T,R)  ⑤INDEX(S,T)
9. 在串的基本运算中，属于引用型运算的有（）
①ASSIGN(S,T)    ②INSERT(S1,i,S2)
③DELETE(S,i,j)  ④SUBSTR(S,i,j)  ⑤REPLACE(S,T,R)
10．串是任意有限个
①符号构成的集合②符号构成的序列
③字符构成的集合④字符构成的序列
11.数组的数据元素类型DataType可根据实际需要而定义。以下说法完全正确的是  (  )
①数组的读运算可以读取一个数据元素整体，写运算只能修改一个数据元素的一部分
②数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体
③数组的读、写运算只能读取或修改一个数据元素的一部分
④数组的读、写运算只能读取或修改一个数据元素整体
12．对于以行序为主序的存储结构来说，在数组A[c
1···d
1
，c
2
···d
2
]
中，c1和d1分别为
数组A的第一个下标的上、下界，c
2…d
2
分别为第二各下标的上、下界，每个数据元素占K
个存储单元，二维数组中任一元素a[i,j]的存储位置可由(  )式确定.
①Loc[i,j]=[( d
2-c
2
+1)(i- c
1
)
+(j- c
2
)]*k
②Loc[i,j]=loc[c
1, c
2
]+[( d
2
- c
2
+1)(i- c
1
)+(j- c
2
)]*k
③Loc{i,j}=A[c
1, c
2
]+[( d
2
- c
2
+1)(i- c
1
)+(j- c
2
)]*k
④Loc[i,j]=loc[0,0]+[( d
2- c
2
+1)(i- c
1
)=(j- c
2
)]*k
13对于C语言的二维数组DataType A[m][n]，每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由(  )式确定.
①Loc[i,j]=A[m,n]+[(n+1)*i+j]*k
②Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k
③Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k
④Loc[i,j]=[(n+1)*i+j]*k
14．对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是                (  )
①按照矩阵A的列序来进行转置，算法的时间复杂度为0(nu+tu)
②按照A的三元组a.data的次序进行转置，算法的时间复杂度为O(nu*tu)
③按照矩阵A的列序来进行转置的方法称快速转置
④按照矩阵A的列序进行转置，对于tu<<mu x nu才有意义。
15．稀疏矩阵的压缩存储方法是只存储                                      (  )
①非零元素②三元祖（i,j, a
ij ）③ a
ij
④ i,j
16．基于三元组的稀疏矩阵，对每个非零元素a
ij
，可以用一个（）唯一确定。
①非零元素②三元组(i,j,a
ij )      ③ a
ij
④ i,j
17．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队为指针，则执行出队操作的语句为（）①front=front+1                ② front=（front+1）%m
③rear=(rear+1)%m              ④ front=(front+1)%(m+1)
19.三角矩阵可压缩存储到数组（）中。
①M[1:n(n+1)/2+1]              ② M[1:n(n+1)/2]
③M[n(n+1)/2+1]                ④M[n(n+1)/2]
19常对数组进行的两种基本操作是（）
①建立与删除②索引与修改③查与修改④查与索引
20．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（）①正确②错误
21．二为数组M[i,j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从O到4，列下标j的范围从O到5。M按行存储时元素M[3,5] 的起始地址与M按列存储时元素(    )的起始地址相同。
①M [2,4]        ② M[3,4]          ③M[3,5]          ④M[4,4]
22. 以下说法正确的是
①数组是同类型值的集合
②数组是一组相继的内存单元
③数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树形的
④使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间
三．简答题
1．请用类C语言描述顺序串的类型定义。
顺序串的类型定义与顺序表类似，可描述如下：
const maxlen=串的最大长度
typedef struct
{char ch[maxlen]
int  curlen;
}string

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