共计 2192 个字符，预计需要花费 6 分钟才能阅读完成。
若串 S=’software’, 其子串的数目是（36）。
1+2+…+8=8*9/2=36，但是值得注意的是，software 没有重复字符，若有重复字符，要注意去除重复字符的情况
下面说法不正确的是(1)
- 广义表的表头总是一个广义表
- 广义表的表尾总是一个广义表
- 广义表难以用顺序存储结构
- 广义表可以是一个多层次的结构
广义表第一个元素是表头，其余的元素组成的表为表尾。因此表头 head 可以是原子或者一个表，但表尾 tail 一定是一个表（即使是空表）
数组与一般线性表的区别主要是(D)。
- A. 存储方面
- B. 元素类型方面
- C. 逻辑结构方面
- D. 不能进行插入和删除运算
线性表和数组的区别：
从概念上来看，线性表是一种抽象数据类型；数组是一种具体的数据结构。
线性表与数组的逻辑结构不一样，线性表是元素之间具有 1 对 1 的线性关系的数据元素的集合，而数组是一组数据元素到数组下标的一一映射。
并且从物理性质来看，数组中相邻的元素是连续地存储在内存中的；线性表只是一个抽象的数学结构，并不具有具体的物理形式，需要通过其它具有物理形式的数据结构来实现。
在存储方面，数组中相邻的元素是连续地存储在内存中的；线性表中相邻的元素则不一定存储在连续的内存空间中，除非表是用数组来实现。
对于数组，可以利用其下标在一个操作内随机存取任意位置上的元素；对于线性表，除非通过数组实现，否则只能根据当前元素找到其前驱或后继，因此要存取需要为 i 的元素，一般不能在一个操作内实现
线性表可以动态分配元素，数组不行，不能进行插入和删除运算
常对数组进行的两种基本操作是（C）
- A. 建立与删除
- B. 索引与修改
- C. 查找与修改
- D. 查找与索引
查找与索引的区别：一般查找可能要遍历所有记录，而如果建立了索引就相当为记录创建了一个目录，查找时只要到目录中搜索即可，数据量非常大的时候速度快。打个比方：如果有一本 1000 页的书，如果要找书中的某个内容时，在没有目录的情况下，你是否要一页一页的去翻书找呢；而如果对书建一个目录的话你只要查找目录就可以找到了。道理是一样的，对一本没有目录的书进行查找就相当于一般查找，而建了目录就相当于建了索引的记录，索引查找时只要查找索引目录就可。
串 S=‘aaab’的 Next 数组值为 1123.（错）
序号：1 2 3 4
数组：a a a b
next：0 1 2 3
首先注意上边序号、数组和 next 的对应关系
求 next 值的过程：
前两位：next 数组值前两位一定为 01，即 aaab 中的前两位 aa 对应 01，如上表中 next 第 1，2 位为 0 和 1. 其实这就可以得出答案了.
第三位：3a 前面是 2a（2a 表示序号为 2 的 a），2a 的 next 数组值为 1，找到序号为 1 的字符, 即 1a, 将 2a 和 1a 相比，两者相同，都是 a，则 3a 的 next 值为 2a 的 next 值加 1，即 2；
第四位：4b 前 3a 的 next 为 2，找到序号为 2 的字符, 即 2a, 将 3a 与 2a 相比，二者相同，则其 next 值为 3a 的 next 加 1，为 3. 结果为 0123
如果比较的时候碰到与前一位字符“不同”怎么办？
如求下列序号 4 的 next 值
序号: 1 2 3 4
数组: a a b a
next: 0 1 2 1
以前一位的 next 值为序号，找到这个序号对应的字符，再进行比较，4a 前一位是 3b, next 值为 2, 找到序号 2 对应的 2a, 比较 3b 和 2a, 两者不同, 再重复这一步骤, 找到 2a 的 next 值是 1，比较 3b 和 1a, 不同, 那么所求的 4a 的 next 就是 1, 如果相同就是 2a 的 next 值加 1，为 2。
做个练习：xyxyyxxyx, 求它的 next 数组？答案是 011231223，你做对了吗？
串是一种数据对象和操作都特殊的线性表
串的逻辑结构和线性表相似，不同之处在于串针对的是字符集，也就是串中的元素都是字符；对于串的基本操作与线性表有很大的差别。线性表更关注单个元素的操作，比如说查找一个元素，插入或者删除一个元素；但串中更多关注一部分元素的操作，如查找子串位置，得到指定子串，替换子串等操作。
在进行字符初始化时，char s[] = {’H’,’e’,’l’,’l’,’o’,’!’}是不合法的。
因为没有加入字符串结束符。这个字符串的长度同样是不确定的，如果你在初始化 s 时变为 char s[]={‘h’,’e’,’l’,’l’,’o’，’ \0′}; 那么，他的长度应该就是 5（字符串结束符不算）
数组是同类型值的集合。(错)
首先要注意概念性的错误，集合中的元素不能重复，而数组中的元素可以重复，所以，数组不能简单的说成是集合
其次，虽然 java，c、C++ 中必须要同类，但是像 JS，Python，PHP 这样的脚本语言大多不需要同类。
稀疏矩阵压缩存储后, 必会失去随机存取功能
特殊矩阵压缩后不失去随机存取功能，稀疏矩阵必定失去：
特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标 i 和 j 和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（t<