数据结构复习提纲

软件学院数据结构与算法复习提纲。

data structures and algorithms

概念：type,（类型）一组值的集合。

****** type,简单类型例如整数，因为它的值不含有子结构。

aggregate type,复杂类型，一个记录含有多项信息。银行账户含有多项信息如姓名、地址、。。

composite type,组合类型。

data type,数据类型是指一种类型和定义在该类型上的一组操作。

adt,抽象数据类型abstract data type是指数据结构作为一个软件组件的实现。

data structure,数据结构是adt的实现术语数据结构常指存储在计算机内存中的数据。

problems,问题无非是一个需要完成的任务即一组输入就会有一组相应的输出，问题的定义应该包括任何可行方案所需要的资源限制，在数学的角度可以把问题看成一个函数。

function，函数是输入（定义域domain）和输出（值域range）之间的一种映射关系algorithms,算法是指解决一个问题的方法或者一个过程，如果把问题看成一个函数那么算法就是把输入转化成输出。

programs程序就是算法在计算机程序设计语言中的实现。mathematical preliminaries

概念：set,集合由互不相同的成员或元素构成的一个整体。sequence,序列是指具有顺序的元素组，并且可以含有重元素。

bag,元包没有顺序的一组元素（像集合那样），但又重复的元素。

recursion递归用一个表达式定义了一个函数，该表达式包括了一个或多个他本身的实例。

algorithm analysis概念：asymptotic algorithm analysis,渐进算法分析估算算法和实现它的程序的效率和开销。

growth rate,增长率是指当输入的值增长的时候算法代价的增长速率。

best/worst/**erage case, upper/lower bound, space/time tradeoff, big-oh/big-omega/thetanotation

应用题：the efficiency of different growth rate expressions (see exercise of 3.1 and 3.

3 inpage 79)

list概念：list,线性表由成为元素的数据项组成的一个有限的有序的序列array-based list,顺序表。

linked list,链表动态的能够按照需要为表中的元素分配存储空间ordered/unordered list,singly/doubly linked list,单链表（单向表）每个结点只有一个指向表中下一个结点的指针。双链表可以从一个表结点出发，**性表中随意访问它的前驱结点和后继结点。

array,stack,栈是限定仅在一端进行插入或删除操作的线性表。“lifo线性表”

queue队列一种受限的线性表。队列元素只能从队尾插入，以及从队首删除。

算法：用list/stack/queue实现一些操作，比如：排序、括号匹配检查等binary trees

概念：bst,二叉查找树对于二叉树的任何一个结点，设其值为k,则该结点左子树中任意一个结点的值都小于k。该结点右子树中任意一个结点的值都大于或等于k。

**l,一颗二叉查找树，对于树结构中的每一个结点，其左右子树的高度差做多为 tree,full/complete binary tree,满二叉树每一个结点或者是一个分支结点并恰有两个非空子结点；或者是叶结点。

完全二叉树有严格的形状要求：从根结点起每一层从左到右填充。一颗高度为d的完全二叉树除了d-1层以外，每一层都是满的。底层叶结点集中在左边的若干位置上。

height/depth of a binary tree

树的高度等于最深结点的深度加1

结点m的深度就是从根结点到m的路径的长度。

应用题：bst中的插入/删除，**l的构造，huffman树的构造，heap的构造算法：binary tree tr**ersal，计算二叉树的高度，统计叶子结点个数等证明题：

1) to any binary tree, if it has n0leaf node, n2internal node of degree=2( has twochildren), then n0=n2+1

2) the number of empty subtrees in a non-empty binary tree is one more than the number ofnodes in the tree.

general trees

概念：tr**ersal，遍历按照一定顺序访问树的每一个节点。

equivalence classes不相交子集具有等价关系即自反对称和可传递性看懂：tr**ersal/union/find几个操作的实现思想应用题：根据树的线性表示还原树（例题）证明：

the number of le**es in a non-empty full k-ary tree is (k 1)n + 1, where n is the numberof internal nodes.

internal sorting

概念：各种排序算法的best/worst/**erage case时间复杂度，stable sorting algorithm如果一种排序算法不改变关键码值相同的记录的相对顺序则称为稳定的。

应用题：shellsort/bubble sort/quicksort/heapsort/的排序过程file processing and external sorting

概念：track：磁道，磁头在一个盘片上可以访问的所有数据组成一个磁道。/sector：扇区，每个磁道分为多个扇区。

cluster,簇，多个扇区通常集结成组，是文件分配的最小单位。golden rule of file processing,self-organizing list and its application,logical/physical file,逻辑文件程序员把存储在磁盘中可随机访问的文件看成是一段连续的字节，而且可以把这些字节结合起来构成记录。这称为逻辑文件。

物理文件实际存储在磁盘中的不是一段连续的字节的文件interle**ing factor,交错因子逻辑上相邻的扇区之间的物理距离。

seek time,寻道时间移动i/o磁头把它定位到包含数据的磁道上的时间rotational delay,旋转延迟等待目标扇区转到i/o磁头下面的时间transfer time,organization of buffer pool,programmer’s view of files,main idea of external sorting algorithm一组记录数量太大无法存放到主存中，由于记录必须驻留在外部存储器中，因而相对于内部排序，这些排序方法称为外部排序。

searching

概念：hashing散列，根据关键码直接访问表，把关键码的值映射到表中的位置来访问记录，这个过程叫散列。

80/20 rule, 80%的访问都是针对20%的记录。

properties of hash function,哈希函数，把关键码的值映射到位置的函数。

collision,对于一个散列函数h和两个关键码值k1,k2,如果h(k1) =b =h(k2),b是表中的一个槽，那么就说k1 k2对于b在散列函数h下冲突。

open hashing, separate chaining,开散列方法也称单链方法把冲突记录存储在表外closed hashing,闭散列方法也称开地址方法把冲突记录存储在表中的另一个槽内。probe function,探查函数，p(r,i)为关键码r的探查序列的第i个槽返回从基位置开始的偏移量。

load factor负载因子n/m，n是表中当前的记录数。应用题：hash表的构造10、indexing概念：

entry-sequenced file,输入顺序文件按记录进入系统的顺序把记录存储在磁盘中。indexing,索引把关键码和相应数据记录的位置相关联的过程。

primary key数据库中的每一条记录通常都一个唯一的标识称为主码。secondary key,可能很多条记录都有相同的关键码值称为辅码。

linear indexing,线性索引，线性索引的索引文件中是一组关键码/指针对2-3 tree, b-tree, b+tree

应用题：2-3 tree/b-tree/b+tree中的insert/delete操作11、graph

概念：path,路径。

cycle,如果一条路径将某个顶点连接到它本身，其长度大于或等于3，则称此路径为回路。

connected component,连通分量，无向图的最大连通子图。

****** path,如果路径上的各个顶点都不同，则称这个路径为简单路径adjacent list/matrix,邻接表相邻矩阵bfs, dfs,topological sort,将一个dag中所有顶点在不违反先决条件规定的基础上排成线性序列的过程。

greedy algorithm,dag,有向无环图。

the cost of single source/all-pairs shortest path problem,应用题：shortest path(dijkstra/floyd算法)的构造，mst(prim/kruskal算法)的构造。

数据结构复习提纲

数据结构复习提纲

数据结构复习提纲

数据结构复习提纲

其他用户还读了