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

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

1、楚雄师院计科系网络工程2010级《算法与数据结构》课后习题（第4~5章）【课后习题】第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]的存储地址为

2、。5.对于数组，比较适于采用结构够进行存储。6.广义表的深度是指_______。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个非零元素，则其三元组有         行。2011年10月第8页楚雄师院计科系网络工程2010级《算法与数据结构》课后习题（第4~5章）1.求下列广义表操作的结果：（1）GetHead【((a,b),(c,d))】===;（2）GetHead【GetTail【((a,b),(c,d))】】===;（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】===;

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

5、具备压缩条件的矩阵有：对称矩阵，对角矩阵，稀疏矩阵等。8.任何一个非空的广义表，表头可能是原子，也可能是列表；但表尾一定是列表；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的长度，2011年10月第8页楚雄师院计科系网络工程2010级《算法与数据结构》课后习题（第4~5章）则concat(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是：（   ）Ａ．BCDEF      Ｂ．BCDEFG    Ｃ．BCPQRST       Ｄ．BCDEFEF1.设有两个串s和t，求

7、t在s中首次出现的位置的运算称作()A)连接B)模式匹配C)求子串D)求串长2.如下是一个稀疏矩阵的三元组法存储表示和基于此表示所得出的相关叙述行下标列下标值113145232326345533I.该稀疏矩阵有5行II.该稀疏矩阵有4列III.该稀疏矩阵有6个非0元素这些叙述中（）是正确的。A)仅IB)I和IIC)仅IIID)全部3.广义表((a),a)的表头和表尾分别是（)。A)a，((a))B)(a)，(a)C)b，