11数据结构串和数组试题及答案一、填空题1.不包含任何字符（长度为0）的串称为空串;由一个或多个空格（仅由空格符）组成的串称为空白串。（对应严题集4.1①，简答题：简述空串和空格串的区别）2.设S=“A：/document/Mary.doc”则strlen（s）二20,“/”的字符定位的位置为34.子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。5.设目标T二”abccdcdccbaa”模式P=“cdcc”则第6次匹配成功。6.若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为_（n-m+l）*m。7•假设有二维数组A，每个元素用相邻的6个字节存储，存储器按6X8字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288B；末尾元素A的第一个字节地址为571282；若按行存储时，元素A的第一个字节地址为（8+4）X146+1000=1072；若按列存储时，元素A的第一个字节地址为（6X747+4)X6+1000)=127611(注:数组是从0行0列还是从1行1列计算起呢？由末单元为A可知,57是从0行0列开始！)8.〖00年计算机系考研题〗设数组a[1・・・60,1-70]的基地址为2048,每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为_8950答：不考虑0行0列，利用列优先公式：LOC(aij)二L0C(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60T+1)+32-1]]*2=89509.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和_元素值10.求下列广义表操作的结果：(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)；11二、单选题(B)1.串是一种特殊的线性表，其特殊性体现在：A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符(B)2.设有两个串p和q,求q在p中首次出现的位置的运算称作：A.连接B.模式匹配C.求子串D.求串长(D)3.设串si二'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(si,len(s2),2))的结果串是：A.BCDEFB.BCDEFGC.BCPQRSTD.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.〖01年计算机系考研题D假设有60行70列的二维数组a[1…60,1・・・70]以列序为主序顺序存储，其基地址为10000,每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为。11a1,1aaA=2,12,2C・i(i+1)/2+j-1（无第0行第0列元素）A.16902B.16904C・14454D・答案A,B,C均不对答：此题与填空题第8小题相似。（57列X60行+31行）X2字节+10000=16902（B）5.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[1,n（n-1）/2]中，对下三角部分中任一元素a（iWj）,在一维数组B中下标k的值是:i,j解：注意B的下标要求从1开始。先用第一个元素去套用，可能有B和C；再用第二个元素去套用B和C，B=2而C=3（不符）;所以选Baa1-n,1n,2A・i(i-1)/2+j-1B・i(i-1)/2+jD・i(i+1)/2+j6.从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5,每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是_L。若按行存储，则A[3,5]和A[5,3]的第一个字节的地址分别是_丄_和C。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址分别是_D_和E供选择的答案：A〜E：①28②44③76④92⑤10811⑥116⑦132⑧176⑨...
