串、数组和稀疏矩阵
1、串是一种特殊的线性表，请从存储和运算两方面分析它的特殊之处。
2、设字符串S= 'aabaabaabaac'，P= 'aabaac'
(1) 给出S 和P 的next 值
012123456789  012123
(2) 若S 作主串，P 作模式串，试给出KMP 算法的匹配过程。 利用KMP 算法的匹配过程：
第一趟匹配：aabaabaabaac
aabaac(i=6,j=6)
第二趟匹配：aabaabaabaac数组和链表
(aa)baac
第三趟匹配：aabaabaabaac
(成功) (aa)baac
3、假设有二维数组 A 6×8，每个元素用相邻的 6 个字节存储，存储器按字节编址。已知 A 的起始存储位置(基地址)为 1000，计算：
(1) 数组 A 的体积（即存储量）;
(2) 数组 A 的最后一个元素 a 57 的第一个字节的地址;
(3) 按行存储时，元素 a 14 的第一个字节的地址;
(4) 按列存储时，元素 a 47 的第一个字节的地址。
(1）6×8×6 = 288Byte
(2）1000+288-6=1282；
(3）1000+(1×8+4)×6=1072
(4）1000+(7×6+4)×6=1276
4、一个稀疏矩阵A 如图所示
(1) 给出三元组存储示意图； (2) 给出带行指针向量的链式存储示意图；
(3) 给出十字链表存储示意图。
（1）                  （2）                    （3）
03000
020500000000900001A = 4×6

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。