杭电-[数据结构(语言版)].doc

数据结构 复习提纲 (附：期末复习题及期末样卷) 绪论 基本概念和术语 　　数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 术语：数据、数据元素、数据对象、数据结构、抽象数据类型、算法。 数据结构的形式定义（二元组） 数据的逻辑结构：线性结构 非线性结构 数据的存储结构（物理结构）：主要有顺序存储结构 链式存储结构 抽象数据类型（三元组） 算法（5个重要特性） 算法的时间复杂度和空间复杂度 算法的评价：正确性、可读性、健壮性、高效率、低存储量 线性表 线性表的定义 线性结构的特点 线性表的存储结构 顺序存储结构（顺序表）插入/删除元素时，需移动元素 链式存储结构（链表，分为单向链表、双向链表） 带头结点的链表和不带头结点的链表； 循环链表； 链表空与非空的情况。 两种存储结构的优缺点比较，各适合那些场合。 线性表操作的实现（算法描述） 插入元素、删除元素、查找、判表是否满足某种特性 例： 判断题：1. 线性表的逻辑顺序与存储顺序总是一致的。F 2. 线性结构的基本特征是：每个结点有且仅有一个直接前驱和一个直接后继。F 3. 线性表的链式存储结构优于顺序存储结构。F 选择题：线性表L在( B )情况下适于使用链表结构实现。 A. 不需修改L的结构 B. 需不断对L进行删除、插入 C. 需经常修改L中结点值 D. L中含有大量结点 填空题：1. 对于顺序表中，在第i个元素前插入一个元素需移动 n-i+1 个元素，要删除第i个元素，需移动 n-i 个元素。 2. 在双向循环链表中某结点（由指针p指示）之后插入s指针所指结点的操作是： ； ； ； ；。 栈和队列 栈 栈的定义 栈的存储结构：顺序存储结构 链式存储结构 栈的应用：二叉树的先序、中序、后序遍历算法 图的深度优先遍历算法 （将递归算法改写为非递归算法可借助栈来完成； 递归算法的执行需用栈来实现） 队列 队列的定义 队列的存储结构：顺序存储结构（循环队列），链式存储结构 队列的应用：二叉树层序遍历 图的广度优先遍历算法 循环队列：·队空、队满的判断条件 ·求队列的长度 ·循环队列通常用front和rear来指示队头和队尾的位置来表示一个队列；如果用front指示队头，用length表示队列的长度，也可以表示一个队列。相应的有关操作怎样实现？ 例： 判断题：因为栈是特殊的线性表，所以对线性表的所有操作都可以用于对栈操作。 填空题：循环队列队满的条件是 rear-front 。 串 串的定义 串的术语：长度、子串 串的基本操作：求串的长度、求子串、串联接、串替换、串匹配（子串定位） 例：已知下列字符串： 　　a=THIS, b= （一个空格）, c=GOOD, d=NE, f=A SAMPLE, 执行如下操作： 　 s=Concat (a , Concat (Concat (b , SubString (a ,3 ,2)) , SubString (f , 2 , SubLength(f)))); t=Replace (f , SubString (f ,3 ,6) , c); u=Concat (SubString (c ,3 ,1) , d); v=Concat (s , Concat (b ,Concat (t , Concat (b , u)))); 试问：s，t，u，v，LENGTH(s)各是什么？ 数组和广义表 数组数组的顺序存储：行主顺序法，列主顺序法。元素存储地址计算 特殊矩阵的压缩存储 元素存储地址计算 广义表1. 广义表的概念：广义表，长度，深度，表头，表尾；2. 广义表的头尾链表存储结构 树和二叉树 树、二叉树的定义 二叉树 二叉树的性质（5条） 二叉树的存储结构：顺序存储结构（按层序存放） 链式存储结构（二叉链表、三叉链表）（空指针域的个数） 遍历二叉树：先序、中序、后序、层序 应用：给定二叉树的先序和中序（或后序和中序）序列，画出相应的二叉树 线索二叉树：先序、中序、后序线索化 树和森林 树的存储结构：双亲表示法 孩子表示法 孩子-兄弟（二叉树）表示法 树（森林）与二叉树的相互转换 树的遍历：先根、后根次序遍历 森林的遍历：先序、中序遍历 赫夫曼树及其应用 最优二叉树（赫夫曼树），求WPL 赫夫曼编码 各种二叉树概念的区分 满二叉树 完全二叉树 正则二叉树（严格二叉树）