定义1(扩张矩阵)：已知e += 及反例矩阵NE. 对每一 j∈N, 用“死元素”*对 在NE中第j列的所有出现做代换，这 样得出的矩阵叫做正例e +在反例NE背景下的扩张矩阵。记为 EM(e+ |NE), 或简记为EM(e+ )

非线性数据结构。 树的递归定义: 树(tree)是n(n>=0)个结点的有限集。 当n>0时, (1)有且仅有一个特定的称为根(root)的结点; (2)当n>1时,其余结点可分为m(m>0)个互不相 交的有限集T1,T2Tm,其中每个集合本身又是一 棵树。称为子树(subtree)

6.3.1遍历二叉树 如果按某条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次

4.1 Randomized algorithm 4.2 Quicksort and randomized quicksort 4.3 Expected running time of quicksort 4.4 Max-heaps and min-heaps 4.5 Heap operations: heapify, building, and key increasing 4.6 heap sort and priority queues 4.7 Comparisons of sort algorithms: heap sort, quick sort, insertion sort, and merge sort 4.8 Comparison sort and decision tree model 4.9 Sorting in linear time: counting-sort, radix sort, and bucket sort

10.1 Graph representations 10.2 Breadth-first and depth-first search algorithms 10.3 Topological sort 10.4 Disjoint sets and strategy of union by rank and path compression 10.5 Minimum spanning tree 10.6 Prim's and Kruskal's algorithm 10.7 Single-source shortest-paths algorithms: breadth-first search, Dag shortest paths, Dijkstra algorithm, and Bellman-Ford algorithm 10.8 All-pairs shortest-paths algorithms: brute-force, dynamic programming, Floyd-Warshall algorithm, and Johnson algorithm 10.9 Ford-Fulkerson max-flow algorithm and Edmonds-Karp algorithm

6.1 Binary trees and binary search tree 6.2 Inorder, preorder, and postorder tree walk 6.3 Successor and predecessor of BST 6.4 Operations of BST: search, Minimum and maximum, constructing, deletion and insertion 6.5 Balanced search trees 6.6 AVL trees 6.7 Single and double rotation 6.8 Red-black trees 6.9 B-tree (2-3-4 tree)

3.1栈 3.1.1抽象数据类型栈的定义 栈(stack):先进后出(FILO)的线性表 或后进先出(LIFO)的线性表。 或仅在表尾进行插入和删除操作的线性表。 栈顶(top):线性表的表尾端,即可操作端。 栈底(bottom):线性表的表头

复习与补充二 结构体类型与链表 1、结构体类型的定义与结构体变量 2、结构体指针 3、自定义数据类型 4、链表的概念与形成链表的基本要素 5、链表的操作:创建、插入、删除

• 5.1 数组的定义 • 5.2 数组的顺序表示和实现 • 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构