《数据结构基础》由会员分享，可在线阅读，更多相关《数据结构基础（3页珍藏版）》请在装配图网上搜索。
1、“数据结构基础”复习主要内容：三大类数据结构+两大类问题（排序与查找）掌握层次：概念、方法、编程（下划线部分的程序需要熟练掌握）一基本概念1. 时、空复杂性（QBO）及等级、RUNTIMECALCULATION2. 数据结构基本概念：数据类型、对象、操作、数据结构三大类数据结构：线性（堆栈、队列）、树、图数据结构的物理表示方式：数组、链表堆栈和队列（STACKANDQUEUE1. 堆栈（STACK）：概念：在同一端插入和删除，FILO表示：数组、链表操作：入/出栈，空/满判断2. 队列（QueueFIFO概念：在一端插入而在另一端删除,表示：数组.、链表操作：入/出队列，空/满判断3. 应用-
2、表达式求值，EVALPOSTFIX三、树（TREE1、二叉树的若干性质：树节点数与层次的关系、完全二叉树数组表示中结点与父子节点的关系、n0/n1/n2之间的关系。2、二叉树的表示：数组、链表方式3、树的基本操作：遍历（traversal二叉数的先/中/后序(preorder/inorder/postorde)以及非递归方法森林的遍历(foresttravel)森林与树的二叉树表示4. 堆(HEAP：概念表示：数组(完全二叉树方式)(completebinarytree)操作：插入(any)、删除(min/max)d-heap5. 二分查找树(binarysearchtree)概念表示：链表操
3、作：查找(findMax/findMin)、插入(Insert)、删除(Delete)四、图(graph)1. 基本概念：component,degree,connected,path,.2. 表示：邻接矩阵(adjacencymatrix)邻接表adjacencylist(逆邻接表)、邻接多重表(adjacencymulti-list)、十字链表(orthotropiclist)3. 基本操作:DFS(depth-firstsearch)BFS(bread-firstsearch)4. 图上的典型算法：最小生成树(minimumspanningtree):PrimalgorithmandKr
4、uskalAlgorithm最短路径(shortest-path);DiikstraAlgorithm,unweightedshortestpath拓扌卜排序(TopologicalSort)网络流量问题(NetworkFlowProblems),关键路径(CriticalPath)双连图/关节点(bi-connectivity/articulationpoints)(DFS,LOW),bi-connectedcomponents五、排序(sorting)(算法、时间复杂性)1. 插入排序：基本插入排序方法(insertionsort)、希尔排序(shellsort)2. 交换排序：基本交换排
5、序(冒泡bubblesort)、快谏排序(quicksort)3. 归并排序(mergesort)4. 选择排序：基本选择排序(selectionsort)堆排序(heapsor)5. 基数排序(radixsorting)6. 排序算法的时间、空间复杂性比较，稳定性六HASH1. 基本思想：解决动态查找问题2. HASH函数的构造方法(hashfunctionconstruction):3. 冲突处理方法(collisionresolution):开放地址(openaddressing)(linearprobing,quadraticprobing)链表(chaining)、doublehashing,再HASH(rehashing)七、DisjointSet1. DisjointSetFind、uniononsets.2. Representation:tree,nodewithparentlink3. Findimprovement:_pathcompression4. Unionimprovement:union-bv-size.union-bv-height
数据结构基础
