数据结构课后习题（第4-5章）

楚雄师院计科系 网络工程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]的存储地址为 。

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个非零元素，则其三元组有 行。

2011年10月 第 1 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第4~5章）

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的长度，

2011年10月 第 2 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第4~5章）

则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,1?A??????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. 同一个数组中的元素（ ）。

A.长度可以不同 B.类型不限 C.类型相同 D.长度不限

2011年10月 第 3 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第4~5章）

14. 数组结构一旦确定，其元素的个数是（ ）。

A.不变的 B.可变的 C.任意的 D.0

15. 一个数组一旦说明，其占用空间的大小（ ）。

A.已固定 B.可以改变 C.不能固定 D.动态变化 16. 数组与一般线性表的区别主要在（ ）。

A.存储方面 B.元素类型一致

C.逻辑结构方面 D.不能进行插入、删除运算

17. 一维数组的元素起始地址loc[6]=1000，元素长度为4，则loc[8]为（ ）。

A.1032 B.1004 C.1008 D.8

18. 已知一个稀疏矩阵的三元组表如下:

{(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

图1

A、定长顺序； B、不定长顺序； C、堆分配； D、块链。

20. 如下结构为矩阵按行存储的三元组顺序表T，则对该矩阵的第2行第1列处元素加4的语句为

（ ）。

i data j e 0 1 1 1 3 2 1 2 3 2 1 4 3 3 5 5 1 6 5 4 7 6 5 2 8 9 10 11 ?? ?? ?? ?? n-1 head B C D A B C D A B C D ^ mu 6 Nu 5 Tu 7 -6 -5 -3 12 3 [2,1].e?T.data[2,1].e?4； B、T.data[1,2].e?T.data[1,2].e?4； A、T.data[2].e?T.data[2].e?4； D、T.data[3].e?T.data[3].e?4。 C、T.data21. 假设有按行顺序存储的二维数组An?m，每个元素用相邻的c个字节存储，存储器按字节编址。已

知数组第一个元素a00的起始存储地址为1000，则a68的起始存储地址是（ ）。 A、1000?(6?m?8)； B、1000?(6?m?8)?c； C、1000?(8?n?6)； D、1000?(8?n?6)?c。

22. 如下结构为矩阵按行存储的行逻辑链接的三元组顺序表T，则该矩阵第5行具有非零元素数为（ ）。 0 1 2 3 4 5 6 7 8 9 10 11 ?? n-1

2011年10月 第 4 页

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第4~5章） mu 6 Nu 5 Tu 8 rpos data i j e 1 1 3 1 1 4 3 2 5 4 3 2 5 5 1 5 5 4 8 5 5 2 6 5 5 ?? ?? ?? ?? -6 -5 -3 12 3 A、T.rpos[5]； B、T.Tu；

C、T.data[5].e； D、T.rpos[6]?T.rpos[5]。

23. 如下为一广义表的扩展线性链表存储表示如图3所示，其表示的广义表为（ ）。

1 1 1 ^ ^ ^ 0 a 1 1 1 ^ 0 d ^ 1 1 1 ^ ^ 图3 0 b 0 c ^ 0

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.3 B.4 C.5 D.6 四、应用题（24分）

1． （6分）某广义表的表头和表尾均为（a,(b,c)），画出该广义表的图形表示。

e ^ 2011年10月 第 5 页

本文来源：https://www.bwwdw.com/article/f2iv.html