数据结构课后习题(第4-5章)

楚雄师院计科系网络工程2010级《算法与数据结构》课后习题（第4~5章）2011年10月第1页【课后习题】第4章串第5章数组和广义表网络工程2010级（）班学号：姓名：题号一二三四总分得分一、填空题（每空1分，共30分）1.串有三种机内表示方法：、和，其中前两种属于顺序存储结构，第三种属于。2.若n为主串长度，m为子串长度，则串的BF（朴素）匹配算法最坏的情况下需要比较字符的总次数为,T(n)=。3.是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的。4.设数组a[1…50,1…60]的基地址为1000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,58]的存储地址为。5.对于数组，比较适于采用结构够进行存储。6.广义表的深度是指_______。7.将一个100100A的三对角矩阵，按行优先存入一维数组B[297]中，A中元素66,66A在B数组中的位置k为。注意：ai,j的k为2(i-1)+j-1,(i=1时j=1,2;1i=n时,j=i-1,i,i+1)。8.称为空串；称为空白串。9.求串T在主串S中首次出现的位置的操作是，其中称为目标串，称为模式。10.对称矩阵的下三角元素a[i,j]，存放在一维数组V的元素V[k]中（下标都是从0开始），k与i，j的关系是：k=。11.在n维数组中每个元素都受到个条件的约束。12.同一数组中的各元素的长度。13.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。14.稀疏矩阵中有n个非零元素，则其三元组有行。楚雄师院计科系网络工程2010级《算法与数据结构》课后习题（第4~5章）2011年10月第2页15.求下列广义表操作的结果：（1）GetHead【((a,b),(c,d))】===;（2）GetHead【GetTail【((a,b),(c,d))】】===;（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】===;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】===;16.广义表E=(a,(b,E)),则E的长度=，深度=；二、判断题（如果正确，在下表对应位置打“”，否则打“”。每题1分，共10分)题号12345678910答案1.串是字符的有限序列。2.串与线性表的运算有所不同，是以“串的整体”作为操作对象。3.空串是由空格构成的串。4.如果一个串中的所有字符均在另一个串中出现，则说明前者是后者的子串。5.串既可以采用顺序存储，也可以采链式存储。6.数组的顺序存储结构，有行（低地址）优先和列（高地址）优先两种不同的顺序。7.具备压缩条件的矩阵有：对称矩阵，对角矩阵，稀疏矩阵等。8.任何一个非空的广义表，表头可能是原子，也可能是列表；但表尾一定是列表；9.三元组顺序表又称有序的双下标法，它可以随机存取某一行中的非零元素。10.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题1.5分，共36分)题号123456789101112答案题号131415161718192021222324答案1.串是一种特殊的线性表，其特殊性体现在：（）Ａ．可以顺序存储Ｂ．数据元素是一个字符Ｃ．可以链式存储Ｄ．数据元素可以是多个字符2.设串s1=’ABCDEFG’，s2=’PQRST’，函数concat(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，楚雄师院计科系网络工程2010级《算法与数据结构》课后习题（第4~5章）2011年10月第3页则concat(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是：（）Ａ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEF3.设有两个串s和t，求t在s中首次出现的位置的运算称作()A)连接B)模式匹配C)求子串D)求串长4.如下是一个稀疏矩阵的三元组法存储表示和基于此表示所得出的相关叙述行下标列下标值113145232326345533I.该稀疏矩阵有5行II.该稀疏矩阵有4列III.该稀疏矩阵有6个非0元素这些叙述中（）是正确的。A)仅IB)I和IIC)仅IIID)全部5.广义表((a),a)的表头和表尾分别是（)。A)a，((a))B)(a)，(a)C)b，(a)D)((a))，a6.一个广义表为(a,(a,b),d,e,((i,j)，k))，则该广义表的长度和深度分别是（)。A)5，3B)5，4C)4，3D)4，47.设串sl=“DataStructureswithJava”,s2=“it”，则子串定位函数index(s1,s2,3)的值为（)。A．15B．16C．17D．188.二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（)。A．1207B．1209C．1211D．12139.（)不是Yu**Jia**Shan的子串。A.YuB.JiaC.**ShanD.YuJiaShan10.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i≤j),在一维数组B中下标k的值是：nnnnaaaaaaA,2,1,2,21,21,1A.i(i+1)/2+j-1B.i(i-1)/2+jC.i(i-1)/2+j-1D.i(i+1)/2+j11.若块链存储结构中每个结点存放4个字符，每个指针占2个字节，则它的存储密度为（）A.3/2B.2/3C.1/2D.1/312.数组的基本操作是（）。A.插入数组元素B.删除数组元素C.只可以读D.读和写13.同一个数组中的元素（）。A.长度可以不同B.类型不限C.类型相同D.长度不限楚雄师院计科系网络工程2010级《算法与数据结构》课后习题（第4~5章）2011年10月第4页14.数组结构一旦确定，其元素的个数是（）。A.不变的B.可变的C.任意的D.015.一个数组一旦说明，其占用空间的大小（）。A.已固定B.可以改变C.不能固定D.动态变化16.数组与一般线性表的区别主要在（）。A.存储方面B.元素类型一致C.逻辑结构方面D.不能进行插入、删除运算17.一维数组的元素起始地址loc[6]=1000，元素长度为4，则loc[8]为（）。A.1032B.1004C.1008D.818.已知一个稀疏矩阵的三元组表如下:{(1,2,3,),(1,6,1)，(3,1,5)，(3,2,-1),(4,5,4),(5,1,-3)}，则其转置矩阵的三元组表中第3个三元组为（）。A.（2,1,3）B.(3,1,5)C.(3,2,-1)D.(2,3,-1.)19.下图表示串的（）存储结构。A、定长顺序；B、不定长顺序；C、堆分配；D、块链。20.如下结构为矩阵按行存储的三元组顺序表T，则对该矩阵的第2行第1列处元素加4的语句为（）。01234567891011……n-1mu6datai1123556……Nu5j1213145……Tu7e3-6-5-31232……A、4].1,2[.].1,2[.edataTedataT；B、4].2,1[.].2,1[.edataTedataT；C、4].2[.].2[.edataTedataT；D、4].3[.].3[.edataTedataT。21.假设有按行顺序存储的二维数组mnA，每个元素用相邻的c个字节存储，存储器按字节编址。已知数组第一个元素00a的起始存储地址为1000，则68a的起始存储地址是（）。A、)86(1000m；B、cm)86(1000；C、)68(1000n；D、cn)68(1000。22.如下结构为矩阵按行存储的行逻辑链接的三元组顺序表T，则该矩阵第5行具有非零元素数为（）。01234567891011……n-1图1headABCDABCDABCD^楚雄师院计科系网络工程2010级《算法与数据结构》课后习题（第4~5章）2011年10月第5页mu6datai11235556……Nu5j14521455……Tu8e3-6-5-312325……rpos134558……A、]5[.rposT；B、TuT.；C、edataT].5[.；D、]5[.]6[.rposTrposT。23.如下为一广义表的扩展线性链表存储表示如图3所示，其表示的广义表为（）。A、（（），a，（（b，c），（），d），（（（e））））；B、（（（）），a，（（b，c），（），d），（（（e））））；C、（（（）），a，（b，c，（），d），（（（e））））；D、（（（）），a，（（b，c），（），d），（（e）））。24.广义表A=(a，(b)，()，(c,d,e))的长度为()A.3B.4C.5D.6四、应用题（24分）1．（6分）某广义表的表头和表尾均为（a,(b,c)），画出该广义表的图形表示。10a1^10d^0b1^1^1^^111^0e^0c^图3楚雄师院计科系网络工程2010级《算法与数据结构》课后习题（第4~5章）2011年10月第6页2.（6分)已知两个6×7的稀疏矩阵的三元组表分别如下：013500111212218122－22234－25225693422833425453104413354215请画出这两个稀疏矩阵之和的三元组表。3、（12分）函数strcmp()是比较两个字符串s和t的大小。若st函数返回负数;若s=t函数返回0;若st,函数返回正数。intstrcmp(char*s,char*t){while(*s&&*t&&________){;;}return______;}楚雄师院计科系网络工程2010级《算法与数据结构》课后习题（第4~5章）参考答案2011年10月第1页【课后习题】第4章~第5章参考答案一、填空题（每空1分，共30分）1.串有三种机内表示方法：定长顺序存储、堆分配存储和块链存储，其中前两种属于顺序存储结构，第三种属于链式存储结构。2.若n为主串长度，m为子串长度，则串的BF（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m,T(n)=O(n*m).3.空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。4.设数组a[1…50,1…60]的基地址为1000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,58]的存储地址为4834。5.对于数组，比较适于采用顺序结构够进行存储。6.广义表的深度是指_表展开后所含括号的层数______。7.将一个100100A的三对角矩阵，按行优先存入一维数组B[297]中，A中元素66,66A在B数组中的位置k为195。注意：ai,j的k为2(i-1)+j-1,(i=1时j=1,2;1i=n时,j=i-1,i,i+1)。8.长度为0的串称为空串；一个或多个空格符组成的串称为空白串。9.求串T在主串S中首次出现的位置的操作是子串定位（模式匹配），其中S称为目标串，T称为模式。10.对称矩阵的下三角元素a[i,j]，存放在一维数组V的元素V[k]中（下标都是从0开始），k与i，j的关系是：k=(i+1)*i/2+j。11.在n维数组中每个元素都受到n个条件的约束。12.同一数组中的各元素的长度必须相等。13.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。14.稀疏矩阵中有t个非零元素，则其三元组有t行。15.求下列广义表操作的结果：（1）GetHead【((a,b),(c,d))】===(a,b);