【课后习题】第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. 将一个A100?100的三对角矩阵，按行优先存入一维数组B[297]中，A中元素A66,66在B数组中的位置
k为 。
注意：ai,j的k为 2(i-1)+j-1,(i=1时j=1,2;1 9. 求串T在主串S中首次出现的位置的操作是 ，其中 称为目标串， 称为模 式。 10. 对称矩阵的下三角元素a[i,j]，存放在一维数组V的元素V[k]中（下标都是从0开始）， k与i，j的关系是：k= 。 11. 在n维数组中每个元素都受到 个条件的约束。 12. 同一数组中的各元素的长度 。 13. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元 素的 、 和 。 14. 稀疏矩阵中有n个非零元素，则其三元组有 行。 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分) 题号 答案 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 1 2 3 4 5 6 7 8 9 10 串是字符的有限序列 。 串与线性表的运算有所不同，是以“串的整体”作为操作对象。 空串是由空格构成的串。 如果一个串中的所有字符均在另一个串中出现，则说明前者是后者的子串。 串既可以采用顺序存储，也可以采链式存储。 数组的顺序存储结构，有行（低地址）优先和列（高地址）优先两种不同的顺序。 具备压缩条件的矩阵有：对称矩阵，对角矩阵，稀疏矩阵等。 任何一个非空的广义表，表头可能是原子，也可能是列表；但表尾一定是列表； 三元组顺序表又称有序的双下标法，它可以随机存取某一行中的非零元素。 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩 阵的转置运算 三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题1.5分，共36分) 题号 答案 题号 答案 1 13 2 14 3 15 4 16 5 17 6 18 7 19 8 20 9 21 10 22 11 23 12 24 1. 串是一种特殊的线性表，其特殊性体现在：（ ） Ａ．可以顺序存储 Ｂ．数据元素是一个字符 Ｃ．可以链式存储 Ｄ．数据元素可以是多个字符 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 Ｄ．BCDEFEF 3. 设有两个串s和t，求t在s中首次出现的位置的运算称作( ) A)连接 B)模式匹配 C) 求子串 D)求串长 4. 如下是一个稀疏矩阵的三元组法存储表示和基于此表示所得出的相关叙述 行下标 列下标 值 1 1 2 3 3 5 1 4 3 2 4 3 3 5 2 6 5 3 I.该稀疏矩阵有5行 II.该稀疏矩阵有4列 III.该稀疏矩阵有6个非0元素 这些叙述中（ ）是正确的。 A)仅I B)I和II C)仅III D)全部 5. 广义表((a),a)的表头和表尾分别是（ )。 A) a ，((a)) B) (a) ，(a) C) b，(a) D) ((a)) ， a 6. 一个广义表为(a,(a,b),d,e,((i,j)，k))，则该广义表的长度和深度分别是（ )。 A) 5，3 B)5，4 C)4，3 D)4，4 7. 设串sl=“Data Structures with Java”,s2=“it”，则子串定位函数index(s1,s2,3)的值为（ )。 A．15 B．16 C．17 D．18 8. 二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地 址为1153，则数组元素A[6][7]的存储地址为（ )。 A．1207 B．1209 C．1211 D．1213 9. （ )不是\的子串。 A. \ 10. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数 组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一维数组B中下标k的值是： ?a1,1?a2,1A???????an,1a2,2an,2??????an,n?? A.i(i+1)/2+j-1 B.i(i-1)/2+j C.i(i-1)/2+j-1 D.i(i+1)/2+j 11. 若块链存储结构中每个结点存放4个字符，每个指针占2个字节，则它的存储密度为（） A. 3/2 B. 2/3 C.1/2 D.1/3 12. 数组的基本操作是（ ）。 A.插入数组元素 B.删除数组元素 C.只可以读 D.读和写 13. 同一个数组中的元素（ ）。