数据结构复习

1、第1章1.术语 （1）数据元素 是基本单位 （2）数据项 最小单位 （3）数据对象：相同性质 （4）数据结构：数据元素之间 关系 带结构的数据元素的 （5）类型：两（线性结构+非线性结构） 四（集合、线性、层次、网） 区分线性？非线性？ （6）逻辑结构：二元组（D,R） 一是画图 二是 写出二元组 （7）物理结构：计算机表示 （8）顺序存储（数组）、非顺序存储（指针） （9）抽象数据类型 三元组（D，R，P）2.算法 （1）定义：特定问题求解步骤描述 （2）特性： 有穷性：有穷个步骤；有限个时间 确定性：不含二义性； 可行性： 输入特性：没有输入 输出特性：至少一个输出 （3）好的算法？ 正确

2、的：无语法错误；任意一组输入可以得到满足；刁难性输入可以得到；所有输入得到。 可读性：清晰第一，效率第二；注释；风格 健壮性：非法输入 效率：时间、空间 （4）算法描述工具： 传统的流程图 N-S图 PAD图 类C语言 （5）时间复杂度？循环 教材算法第2章1. 线性表概念：数据元素 有限序列 长度： 前驱、后继 空表2. ADT描述：三元组*3. 顺序存储 顺序表 （1）数组 （2）好处：随即存取；不好：不插入删除。因为时间耗费数据元素的移动 （3）C语言描述 （4）一系列操作 拓展 （5）插入 （6）删除4. 非顺序，链式 （1）指针 （2）单链表C语言 （3）一系列操作 （4）插入？删除

3、？ （5）头结点？头指针？ （6）好处？不好（从头指针：顺序存取） （7）遍历：P=p->next （8）尾结点：p->next=NULL （9）后继地址：前驱指针域 （10）循环链表特点 （11）合并 （12）课后习题第3章1. 栈、队列、线性表相同点、不同点2. 栈？线性表 一端操作。顺序存储3. 特点：后进先出LIFO。 一系列问题4. 应用：递归、表达式求值等5. 队列？线性表，两头 6. 特点FIFO7. 链式存储 列队列8. 回文？9. 课后习题第4章1. 串概念2. 存储第5章1. 二维数组求地址2. 稀疏矩阵 三元组3. 广义表 表头 表尾第6章1. 树 （0）术语

4、 （00）树的表示形式：树形、凹入法、？ （1）概念：有且只有根；递归！ （2）存储结构：孩子兄弟表示； （3）树与二叉树转换？二叉树根无右子树 （4）遍历：前序（前） 后序（中）。 通过二叉树 （5）多叉树2. 二叉树 （1）ADT描述 （2）特点：俩 度？ （3）结点形态：5种 （4）性质1：每一层最多结点的个数？证明？ （5）性质2：所有结点的数据元素最多？证明？ （6）性质3：度为0的结点个数与度为2的结点个数关系。总结点与其他结点；分支数目与结点个数之间关系；分支个数与度、结点个数之间关系。 （7）满二叉树 特点 （8）完全二叉树：特点？叶子结点个数与总结点个数；编码 （9）性质4

5、结论？编号与结点的个数 （10）性质5 编号为i 双亲？左孩子？右孩子？ （11）存储：顺序？（与性质5对应）、链式 二叉链表 （12）遍历：一是遍历；二序列得到二叉树；算术表达式与二叉树 （13）线索概念、会 （14）与树、森林转换 （15）Huffman树构成？Wpl？编码？ 3. 森林 （1）概念 （2）二叉树转换？ （2）遍历，前序 中 二叉树4. 课后习题第7章1. 概念2. 逻辑结构（二元组）与图示 画3. 存储 邻接表 无向图 有向图处度 逆邻接表4. 存储 邻接矩阵 画 有 无（对称的）5. 十字链表=邻接表+逆邻接表 有向图。6. 邻接多重表 无向图7. 遍历：深度 广度。生成树、序列、边8. 最小生成树：prim kruscal 算法 边集9. 拓扑排序10. 关键路径 概念 会求 例子11. 单源点到其余点 表 S v012. 课后习题第9章1. 顺序查找：监视哨？查找成功最好 最坏n；失败n+1。等概率成功ASL？2. 有序表：前提 有序+顺序；判定树；ASL（成功？不成功？）3. 二叉排序树：给定序列 会画；树形 会填；插入？删除？ASL（成功？不成功？）4. 平衡二叉树：二叉排序树；平衡因子？5. 哈希表（线性探测、二