数据结构 2复习

一、绪论

a) 何谓程序设计？

程序=算法+数据结构 b) 数据结构的定义

是相互之间存在一种或多种特定关系的数据元素的集合 c) 数据、数据元素、数据对象的概念

数据：是对客观事物的符号表示 数据元素：是数据的基本单位

数据对象：是性质相同的数据元素的集合 d) 四种基本的数据结构类型

集合结构、线性结构、树型结构、图形结构 e) 两种存储结构（计算机中的实现方式）

顺序存储结构

特点：随机访问

优缺点：存取快，但插入元素复杂 适用情况：插入元素操作较多的情况 链式存储结构

特点：顺序访问

优缺点：访问元素麻烦，但是插入元素方便

适用情况：插入元素为主要操作而访问元素的操作较少

f) 数据类型、抽象数据类型

数据类型：用以刻画（程序）操作对象的特性

抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作 g) 抽象数据类型的意义

ADT（abstract data type）着重数据结构的操作接口，不关心具体实现，主要是面向用户

ADT是数据结构设计所追求的目标 h) 何谓算法

算法是解决特定问题求解步骤的描述 i) 算法特征

①有穷性 ②确定性 ③可行性 ④输入 ⑤输出 j) 算法设计的要求

①正确性 ②可读性 ③健壮性 ④效率与低存储量需求 k) 算法好坏的衡量标准

时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算

法的时间度量记作

T(n)?O?f?n??

它随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相

同。

空间复杂度：算法所需存储空间的度量，记作

S(n)?O?f?n??

其中n为问题规模

二、线性表

A） 何谓线性结构（特点）

①存在惟一一个被称作“第一个”的元素 ②存在唯一一个被称作“最后一个”的元素

③除第一个之外，集合中的每个数据元素均只有一个前驱 ④除最后一个之外，集合中的每个数据元素均只有一个后继 B） 线性结构主要有哪几种

线性表、栈、队列、串

C） 线性表ADT，尤其是它的几个主要操作

初始化、插入、删除 D） 线性表的两种实现方式

顺序表、链表

E） 顺序表的C语言实现

看代码

F） 链表的C语言实现

单链表、循环链表、双向链表中结点的操作，比如插入、删除、查找、定位等等 看代码

G） 实现代码中，如何方便地更换数据元素的类型，以便代码复用

看代码

H) 顺序表和链表的优缺点、适用场景

顺序表：

优点：随机存取，访问元素快，求长度方便 缺点：插入或者删除元素耗时麻烦

适用场景：对元素存取操作使用较多的地方 链表：

优点：插入或删除元素不需要移动其它元素，速度快 缺点：访问元素慢，求长度不如顺序表方便 适用场景：需要插入或删除操作较多的地方

三、栈与队列

A） 栈的概念，ADT

栈：限定仅在表尾4进行插入或删除操作的线性表。（因此，对栈来说，表尾端有 其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈）

ADT：InitStack、DestroyStack、StackEmpty、PUSH、POP B） 栈的三个基本操作

Push、Pop、GetTop（看代码） C） 栈的特点

先进后出（FILO）

D） 判断能否根据某种操作顺序，得到某一个元素序列

（看题、做题）

E） 栈的一些应用：括号匹配（看代码）、函数调用跟踪、递归跟踪、四则运算（看书） F） 栈的顺序实现方式（Top指针的变化方式)（看代码） G） 队列的特点：FIFO

H） 队列的头尾与两个基本操作

队首（front）、队尾（rear）、入队（en），出队（de）（看代码、看题） I） 队列的顺序实现方式

Front和rear的变化方式，何时表示队列满，何时表示队列空（看书、看题、查）

四、串

A） 串的概念（串、子串）

串：由零个或多个字符组成的有限序列 子串：串中任意个连续的字符组成的子序列 B） 串的顺序实现方式，主要操作（看书略） C） 模式匹配问题（看书略） 五、数组与广义表

（略） 六、树

A） 树的定义（递归方式）

树：n（n?0）个结点的有限集。

①有且仅有一个特定的称为根（Root）的结点 ②当n>1时，其余的结点可分为m（m>0）个互不相交的有限集，其中每一个集合 本身又是一棵树，并且称为根的子树

B）树的主要术语（结点、叶子结点、孩子、兄弟、双亲、结点的度、树的度、层次、 深度、有序树、森林）

结点：一个数据元素及若干指向其子树的分支 结点的度：结点拥有的子树数目 叶子结点：度为0的结点

孩子：结点的子树的根，相应地，该结点称为孩子的双亲 兄弟：同一个双亲的孩子之间

树的度：树内各结点的度的最大值（最大的结点的度） 层次：根为第一层，根的孩子为第二层，以此类推。。。 深度：树中结点的最大层次

有序树：树中结点的各子树看成从左至右是有次序的（即不能互换），这样的树。 森林：m（m?0）课互不相交的树的集合 C） 二叉树的概念（递归方式）

二叉树：一种树型结构，它的特点是每个结点至多只有两颗子树（即不存在度大于 2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒 D） 二叉树的链式实现，几个重要操作的实现（插入结点、删除结点、遍历） （看代码） E） 二叉树的几个性质*（看题） 性质1：在二叉树的第i层上至多有2ki?1个结点（i?1）

性质2：深度为k的二叉树至多有2?1个结点，（k?1）

性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点树为n2，

则n0=n2+1

性质4：具有n个结点的完全二叉树的深度为?log2n??1

性质5：如果对一棵有n个结点的完全二叉树（其深度为?log2n??1）的结点按层

序编号（从第1层到第?log2n??1层，每层从左到右），则对任一结点i

（1?i?n），有

①：如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则双亲是结点

?i/2?

②：如果2i?n，则结点i无做孩子（结点i为叶子结点）；否则其左孩子 是结点2i

③：如果2i?1?n，则结点i无右孩子；否则其右孩子是结点2i?1

F） 四种二叉树遍历方法（前序、中序、后序、层次） （前中后略）

层次：从上到下、从左到右按层次进行

G） 给定前序和中序、中序和后序的遍历序列，画出树的形状（做题） H） 如何把任意一棵树、森林转化为一棵等价的二叉树（看视频） I） Huffman树、如何构造（看书P145） J） Huffman编码构造方法（看书P146） 七、查找

A） 查找表、关键字、主关键字、次关键字（看书P214） B） 静态查找表与动态查找表的区别

静态~是事先生成好的表，而动态~表结构本身是在查找过程中动态生成的。 C） 折半查找算法（二分法）（看代码） D） 二叉排序树（二叉查找树（动态））（看代码）

E) 根据一串输入数据，如何构造二叉排序树（看代码） F) 如何在二叉排序树中进行查找 （看代码） G) 二叉排序树的性能取决于什么

取决于树的形态，树的层次越少查找性能越好 H) 二叉平衡树的概念、平衡因子

二叉 …… 此处隐藏：2526字，全部文档内容请下载后查看。喜欢就下载吧 ……