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

《数据结构课后习题(第4-5章).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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.广

2、义表的深度是指_______。7.将一个的三对角矩阵，按行优先存入一维数组B[297]中，A中元素在B数组中的位置k为。注意：ai,j的k为2(i-1)+j-1,(i=1时j=1,2;1

3、。12.同一数组中的各元素的长度         。13.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。14.稀疏矩阵中有n个非零元素，则其三元组有         行。1.求下列广义表操作的结果：（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))】】】===;2.广

4、义表E=(a,(b,E)),则E的长度=，深度=；二、判断题（如果正确，在下表对应位置打“Ö”，否则打“´”。每题1分，共10分)题号12345678910答案　　　　　　　　　1.串是字符的有限序列 。     2.串与线性表的运算有所不同，是以“串的整体”作为操作对象。3.空串是由空格构成的串。4.如果一个串中的所有字符均在另一个串中出现，则说明前者是后者的子串。5. 串既可以采用顺序存储，也可以采链式存储。6.数组的顺序存储结构，有行（低地址）优先和列（高地址）优先两种不同的顺序。7.具备压缩条件的矩阵有：对称矩阵，对角矩阵，稀疏矩阵等。8.任何一个非空的广义表

5、，表头可能是原子，也可能是列表；但表尾一定是列表；9.三元组顺序表又称有序的双下标法，它可以随机存取某一行中的非零元素。10.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题1.5分，共36分)题号123456789101112答案题号131415161718192021222324答案　　　　　　　　　1.串是一种特殊的线性表，其特殊性体现在：（    ）Ａ．可以顺序存储      Ｂ．数据元素是一个字符     Ｃ．可以链式存储       Ｄ．数据元素可以

6、是多个字符2.设串s1=’ABCDEFG’，s2=’PQRST’，函数concat(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则concat(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是：（   ）Ａ．BCDEF      Ｂ．BCDEFG    Ｃ．BCPQRST       Ｄ．BCDEFEF1.设有两个串s和t，求t在s中首次出现的位置的运算称作()A)连接B)模式匹配C)求子串D)求串长2.如下是一个稀疏矩阵的三元组法存储表示和基于此表示

7、所得出的相关叙述行下标列下标值113145232326345533I.该稀疏矩阵有5行II.该稀疏矩阵有4列III.该稀疏矩阵有6个非0元素这些叙述中（）是正确的。A)仅IB)I和IIC)仅IIID)全部3.广义表((a),a)的表头和表尾分别是（)。A)a，((a))B)(a)，(a)C)b，(a)D)((a))，a4.一个广义表为(a,(a,b),d,e,((i,j)，k))，则该广义表的长度和深度分别是（)。A)5，3B)5，4C)4，3D)4，45. 设串sl=“DataStructureswithJava”,s2=“it”，则子串定位函数i