“数据结构基础”复习主要内容：三大类数据结构+两大类问题（排序与查找）掌握层次：概念、方法、编程（下划线部分的程序需要熟练掌握）一基本概念时、空复杂性（ΩθО）及等级、RUNTIMECALCULATION数据结构基本概念：数据类型、对象、操作、数据结构三大类数据结构：线性（堆栈、队列）、树、图数据结构的物理表示方式：数组、链表二、堆栈和队列（STACKANDQUEUE）堆栈（STACK）：概念：在同一端插入和删除，FILO表示：数组、链表操作：入/出栈，空/满判断队列（Queue）概念：在一端插入而在另一端删除，FIFO表示：数组.、链表操作：入/出队列，空/满判断应用----表达式求值，EVAL，POSTFIX三、树（TREE）二叉树的若干性质：树节点数与层次的关系、完全二叉树数组表示中结点与父子节点的关系、n0/n1/n2之间的关系。二叉树的表示：数组、链表方式树的基本操作：遍历（traversal）二叉数的先/中/后序（preorder/inorder/postorder）以及非递归方法森林的遍历（foresttravel）森林与树的二叉树表示堆（HEAP）：概念表示：数组（完全二叉树方式）（completebinarytree）操作：插入（any）、删除（min/max）d-heap二分查找树(binarysearchtree)概念表示：链表操作：查找(findMax/findMin)、插入(Insert)、删除(Delete)四、图(graph)基本概念:component,degree,connected,path,..表示：邻接矩阵(adjacencymatrix)、邻接表adjacencylist（逆邻接表）、邻接多重表(adjacencymulti-list)、十字链表(orthotropiclist)基本操作：DFS(depth-firstsearch)、BFS(bread-firstsearch)图上的典型算法：最小生成树(minimumspanningtree)：Prim’salgorithmandKruskal’sAlgorithm最短路径(shortest-path):DijkstraAlgorithm，unweightedshortestpath拓扑排序（TopologicalSort）网络流量问题（NetworkFlowProblems）,关键路径（CriticalPath）双连图/关节点(bi-connectivity/articulationpoints)（DFS，LOW），bi-connectedcomponents五、排序(sorting)（算法、时间复杂性）插入排序：基本插入排序方法(insertionsort)、希尔排序(shellsort)交换排序：基本交换排序（冒泡bubblesort）、快速排序（quicksort）归并排序(mergesort)：选择排序：基本选择排序(selectionsort)、堆排序（heapsort）基数排序（radixsorting）排序算法的时间、空间复杂性比较，稳定性六HASH基本思想:解决动态查找问题HASH函数的构造方法(hashfunctionconstruction):冲突处理方法(collisionresolution)：开放地址(openaddressing)（linearprobing,quadraticprobing）、链表(chaining)、doublehashing,再HASH(rehashing)七、DisjointSetDisjointSetFind、uniononsets.Representation:tree,nodewithparentlinkFindimprovement:pathcompressionUnionimprovement:union-by-size,union-by-height