五、串

1. 串是由___零___个或___多____个字符组成的有限序列, 又称为___字符串________。

一般记为 S=“a1a2.....an” (n >= 0), 串中的字符数目n称为串的__长度_____，零个字符的串称为___空串_____.

定义中谈到的"有限"是指长度 n 是一个有限的数值，所谓序列，说明串的相邻字符之间具有前驱和后驱的关系。

2. 空格串, 是包含空格的串，注意它与空串的区别，空格串是___有___(有/无)内容___有___(有/无)长度的，而且可以不知一个空格。

3. 子串在主串的位置，是子串第__1__个字符在主串的序号。

4. 两个数值，很容易比较，但两个字符串如何比较，比如"silly", "stupid",  它们的大小其实取决于它们挨个字母的前后顺序。
第一个字母相同，就比较下一个。"i"字母比"t"靠前，所以 "i" < "t" , 于是我们说 "silly" ___<___ "stupid"

5. 字符串中最常见的操作就是 查找子串的位置，或者替换子串等操作，例如: 主串“00001”，子串"001", 

如果采用朴素的模式匹配法，请估算字符比较了多少次?

6. KMP算法，它是一种可以减少回溯比较次数的算法，请写出以下字符串"abcabx"的next数组。

六、图

1. 图(Graph)是由顶点的____有穷非空___集合和顶点直间__边___的集合组成，
通常表示为 G(V, {E}), 期中，G表示一个___图__, V(Vertex)是__顶点___的集合, E是___边___的集合。

2. 线性表中我们把数据元素叫元素，树中将数据元素叫___结点___,  在图中数据元素，我们称之为___顶点__。
 
3. 线性表中可以没有数据元素，称为__空表____,  树中可以没有结点，叫做__空树_____,  

那么图呢? 从定义可知，V是顶点的集合，且该集合__有穷非空__, 而边集是可以为空的。

4. 如果图中任意两个顶点之间的边都是无向的，则称该图为_____无向图_________，该图顶点间的边称为___无向边____，期中vi, vj 之间的边，如何表示_____(vi, vj)_____.

5. 如果图中任意两个顶点之间的边都是有向的，则称该图为____有向图_____，该图顶点间的边称为___有向边________，也称为__弧____, 

期中vi 到 vj 之间的有向边，如何表示_____<vi, vj>__________，vi称为__弧头____, vj称为___弧尾____.

6. 在无向图中，如果任意两个顶点之间都存在边，则称该图为__无向完全图____，含有n个顶点的无向完全图有________个边。

顶点v的度是____________________________.

7. 在有向图中，如果任意两个顶点之间都存在边，则称该图为_________________，含有n个顶点的有向完全图有________个边。

顶点v的出度是__________，入度是___________.

8. 从一个顶点到另一个顶点的顶点序列称为path路径,  树中根结点到任意结点的路径是________, 而图中顶点间的路径却不是________.

图中路径的长度是路径上____或_____的数目。第1个顶点和最后一个顶点相同的路径称为______.

9. 在无向图G中，如果对于图中任意两个顶点vi, vj, 都是连通的，则称G是__________.

10. 无向图是必须是连通的，且n个顶点有_____个边叫生成树。

有向图中一顶点入度为0 其余顶点的入度为____的叫有向树

11. 图的邻接矩阵存储方式是用_________来表示图。

一个___________来存储图中的顶点信息，一个___________(称为邻接矩阵)存储图的边或弧的信息。

12. 请写出下图的邻接矩阵。

13. 邻接矩阵是不错的一种图存储结构，但对于边数相对顶点较少的图，这种结构存在存储空间浪费的缺陷，这时可采用邻接表。

邻接表是一种数组与链表相结合的存储方法。

14. 图的深度优先遍历，简称DFS，采用仿树的先序遍历，写出遍历序列

15. 图的广度优先遍历，简称BFS，同上图，写出遍历序列

16. 请分别用Prim算法、Kruskal算法，画出下面连通图的最小生成树。