数据结构与算法分析期末复习ppt

《数据结构与算法分析期末复习ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、“数据结构”复习指导2010.6考试说明本课程为闭卷考试考试时间为120分钟。考试题型为：选择题（20分）填空题（20分）判断题（10分）应用题（20分）（选做）算法题（20分）（选做）附加题一、各章节主要知识点讲解二、对相关知识点的要求和举例三、习题选讲第1部分绪论1.数据结构的基本概念数据结构:是相互之间存在一种或多种特定关系的数据元素的集合，数据元素间的关系称为结构逻辑结构：数据元素间的逻辑（抽象）关系，与计算机无关，同一种逻辑结构可以有不同的存储结构（物理结构例：链式顺序）物理结构：数据的逻辑结构在计算机中的表示（数据

2、元素的表示和关系的表示）第1部分绪论4种基本的逻辑结构：集合线性（一对一）树形（一对多）图形（多对多）4种基本的物理结构：顺序结构链式结构散列结构索引结构习题集P21.8（1，2，3）第1部分绪论2.算法的基本概念算法的5个特性:（有穷性、确定性、可行性、零个或多个输入、一个或多个输出）时间复杂度：评估算法的重要标准之一，能较好的体现算法本身的时间效率，与计算机硬件无关（基本操作、问题的规模、基本操作的频度是问题规模的函数）例:n个数中找最大的习题集P11.7（2，3）1.8（6，7）第2部分线性表1.线性表的逻辑结构前驱、后

3、继一对一的关系2.线性表的顺序存储结构（使用连续的存储空间）顺序表特点：可以随机访问插入:若有n个元素的顺序表，在第i个元素之前插入，也即插入元素作为第i个元素i=n+1时移动元素次数为0；i=1时移动元素次数为n；一般情况n-i+1；第2部分线性表删除i=1时移动元素次数为n-1；i=n时移动元素次数为0；一般情况移动次数n-i；插入、删除的基本操作为元素移动时间复杂度为O(n)习题集P42.7（1，2）当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用（）存储结构。顺序表相

4、关算法顺序查找、折半查找线性表中某个元素x，返回其位置查找顺序表中某个元素x的个数线性表的插入和删除算法第2部分线性表3.线性表的链式存储结构（存储空间可以连续也可以不连续）链表（结点、头指针、尾结点、带头结点的链表）特点：不能随机访问第2部分线性表4.单向链表静态法（说明变量）建立链表尾插法建立链表（头指针、q始终指向尾结点、p生成新结点）头插法建立链表（头指针、q始终指向头结点、p生成新结点）插入（在第i个结点前插入新结点，p生成新结点，q指向第i-1个结点…）删除（删除第i个结点，q指向第i个结点的前驱（第i-1个结点）

5、，p指向第i个结点）四种操作都必须知道操作位置结点的前驱结点的指针第2部分线性表5.单向循环链表特点：从任一结点开始可以访问到表中其它结点，但不能随机访问由单向链表构造单向循环链表如何判断单向循环链表6.双向循环链表存储结构特点插入、删除习题集P42.7（4，5，6）（单）链表的相关算法查找单链表中的最大值、最小值查找单链表中元素x的个数分析以下语句的正误线性表采用顺序存储，必须占用一片连续的存储单元。线性表采用顺序存储，便于进行插入和删除操作。线性表采用链接存储，不必占用一片连续的存储单元。线性表采用链接存储，便于插入和删除

6、操作。链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的指针域的值。第3部分栈和队列1.栈栈是运算受限的线性表插入、删除限定在表的尾部进行（栈顶）栈顶、栈底、空栈、栈顶元素顺序栈（连续的存储空间）用结构体变量实现的顺序栈结构体变量规定：栈底为数组下标为0的一端溢出：栈顶指针（下标）为-1时为空，栈顶为MaxSize-1时栈满上溢（满）、下溢（空）数组（栈元素）整型变量（栈顶指针）第3部分栈和队列链栈（用链式存储结构实现的栈）（了解）可以用不带头结点的单向链表实现链栈存储结构structnode*top；基本操作：初始

7、化、判栈空、进栈、出栈（与不带头结点的单向链表的头部插入、头部删除相同）链栈只有空和非空两种状态，没有栈满的情况相关练习习题集P53.13.2-23.5（1，3）3.33.43.6（15，16）第3部分栈和队列2.队列队列是运算受限的线性表允许在队尾插入，在队头删除队头、队尾、空队列顺序队列（顺序存储的队列）用结构体变量实现的顺序队列结构体变量数组（队元素）整型变量1:front（队头指针）整型变量2:rear（队尾指针）第3部分栈和队列队列初始化：队头指针、队尾指针均置为0队头指针front指向队头元素队尾指针rear指向队

8、尾元素的下一个位置队列为空时front=rear队列满时rear==MaxSize上溢：队列已满进行入队操作假上溢：队列未满，但尾指针已超越存储空间上界下溢：队列已空，要进行出队操作操作：初始化、判队空、入队、出队、取队头元素第3部分栈和队列3.循环队列为解决“假上溢”问题设