数据结构参与命题课件复习课

1、题型填空题 每题3分，共10题简答题 每题8分，共6题算法题 共22分，共2题第1章 绪论数据结构的定义按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的表示 方式把它们在计算机的存储器中，并在其上定义了一个运算的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算（操作）。数据结构的三个方面研究内容：问题数学模型实现建模求精线性表栈队列串及数组树形结构图形结构线性结构数据的逻辑结构（面向应用）非线性结构顺序链式索引散列数据的（面向结构）数据的运算（操作）：检索、排序、删除、修改等结构实现逻辑结构基本运算机外表示处

2、理要求算法与数据结构算法与数据结构关系密切选择的数据结构是否恰当直接影响算法的效 率；而数据结构的优劣由算法的执行来体现。N.Wirth计算机科学家“算法+数据结构=程序”算法程序算法是供人阅读的程序是让机器执行的算法用计算机语言实现时就是程序程序不具有算法的有穷性算法效率的衡量方法和准则一个算法的评价主要从时间复杂度和空间复杂度来考虑。时间复杂度T(n)为语句执行的次数称为频度lim T(n) C(C 0)f (n)nO（f（n）称为时间复杂度例如，若T(n)=n(n+1)/2,则有 1/4T(n)/n21，故它的时间复杂度为(n2), 即(n)与n2 数量级相同。空间复杂度第2章 线性表线

3、性结构的特点：在数据元素的非空有限集中，有且仅有一个开始结点和一个终端结点，并且所有结点只有一个直接前趋和一个直接后继。简言之，线性结构反映结点间的逻辑关系是 一对一。线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最简 单、最常用的是线性表。线性表的定义及特点线性表的顺序链式方法：逻辑上相邻物理上一定相邻：逻辑上相邻物理上不一定相邻顺序表顺序表线性表的顺序表示用一组地址连续的顺序单元依次线性表的元素，可通过数组来实现。（逻辑上相邻物理上一定相邻）LOC(ai ) = LOC(a1) + (i - 1) l （a1为首元素）顺序的优点可以随机存取表中任一元素O(1)；空间使用紧凑顺序的

4、缺点：元素时平均需要移动n/2个元素，删除某一元素在时，平均需要移动n-1/2个元素。算法的平均时间复杂度为 O(n)预先分配空间需按最大空间分配，利用不充分;表容量难以扩充链表线性表的链式链式结构特点用一组任意的单元线性表的数据元素单元存放逻辑上相邻的元素利用指针实现了用不相邻的每个数据元素ai，除信息本身信息外，还需其直接后继的链式结构的优点：结点空间可以动态申请和；数据元素的逻辑次序靠结点的指针来指示，需要移动数据元素。和删除时不链式结构的缺点：每个结点的指针域需额外占用空间。当数据域所占字节显得很大。不多时，指针域所占空间的链表是非随机存取结构。对任一结点的操作都要从头指针依链查找该结

5、点，这增加了算法的复杂度。不便于在表尾元素：需遍历整个表才能找到位置。第3章 排序简单排序方法（O(n2)）排序（稳定排序）直接选择排序（不稳定排序）冒泡排序（不稳定排序）先进排序方法（ O(nlogn)快速排序（不稳定排序）归并排序（稳定排序）堆排序（不稳定排序）已知一组关键字29, 18, 23, 1, 68, 41, 8,65，请分别写出按排序、冒泡排序、直接选择排序和快速排序方法排序过程，每一趟排序结束时的关键字的状态。一、时间性能各种排序方法的综合比较1.按平均时间性能来分，有三类排序方法：时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序，其中以快速排序为最好。时间复杂度为

6、 O(n2)：直接排序、起泡排序和简单选择排序，其中以直接为最好，特别是对那些对关键字基本有序的时间复杂度为 O(n*d)：基数排序。序列尤为如此。2. 当待排序列按关键字顺序有序时，改进直接排序、冒泡排序以及简单选择排序能达到 O(n) 的时间复杂度，快速排序的时间性能蜕化为 O(n2) 。3. 堆排序和归并排序的时间性能不随变。序列中关键字的分布而改二、空间性能指的是排序过所需的辅助空间大小。1.所有的简单排序方法(包括：直接堆排序的空间复杂度为 O(1)；、冒泡和简单选择) 和2.快速排序为 O(logn)，为递归程序执行过空间；归并排序所需辅助空间最多，其空间复杂度为 O(n)；链式基

7、数排序需附设队列首尾指针，则空间复杂度为 O(2*rd+n)，栈所需的辅助3.4.三、排序方法的稳定性能1.对于不稳定的排序方法，只要能举出一个实例说明即可。2.快速排序、堆排序是不稳定的排序方法。各种排序方法的比较排序方法平均时间情况最好情况辅助稳定性排序O(n2)O(n2)O(n)O(1）稳定选择排序O(n2)O(n2)O(n)O(1）稳定冒泡排序O(n2)O(n2)O(n)O(1）稳定快速排序O(nlgn)O(n2)O(nlgn )O(lgn)不稳定归并排序O(nlgn )O(nlgn)O(nlgn )O(n）稳定堆排序O(nlgn )O(nlgn)O(nlgn )O(1）不稳定基数排序

8、O(d n)O(d n)O(d n)O(n)稳定第4章 栈和队列栈限定仅在表尾进行和删除的线性表，把这个表尾称为栈顶。特点：后进先出(LIFO表)栈的方法顺序栈链栈栈的顺序栈的链式例1：一个栈的输入序列是12345，若在入栈的过允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，只需压入一个立即弹出一个即可。答：例2：如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？答：435612中到了12顺序不能实现； 135426可以实现。例3一个栈的输入序列为123，若在入栈的过

9、许出栈，则可能得到的出栈序列是什么？允答：可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入3、2出，即132； 1、2入，2出， 3入3出，即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出，即321；合计有5种可能性。4.34.3.1队列 （排队买票）队列的结构特点和操作队尾队头队列的定义限定在表的一端、另一端删除。队列：线性表(queue)特点：先进先出 (FIFO结构)。下图是队列的示意图：表尾称为队尾(rear)表头称为队头(front)a1a2an出队入队元素称为入队队头队尾删除元素称为出队当队列中没有

10、元素时称为空队列。在顺序队列中，当尾指针已经指向了队列的最后一个位置即数组上界时，若再有元素入队，就会发生“溢出”。“假溢出”队列的空间未满，却发生了溢出。解决“假溢出”有两种可行的方法：(1)、平移元素：把元素平移到队列的首部。效率低。(2)、将新元素到第一个位置上，循环队列，入队和出队仍按“先进先出”的原则进行。操作效率、空间利用率高。rearrearrearfront rearfrontfrontfrontJ4J3J4J3J4J3J4J3J2J1选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素。队空条件 : front = rear(初始化时：front = rea

11、r )队满条件： front = (rear+1) % N(N=maxsize)队列长度：L=（Nrearfront）% N问1：左图中队列长度L=？ 5J2J3问2： 在具有n个单元的循环队列中，队满时共有多少J1J4front个元素？n-1个J5rear例1： 一循环队列如下图所示，由图可知，队头和队尾指针的初态分别为front=1和rear=0。若先删除4个元素，接着4个元素，请问队头和队尾指针分别指向哪个位置?front再frontJ2J3J8J9frontrearJ7J1J4frontJ6J5J5frontfrontrear解：删除4个元素后front=(1+4)%6=5；4个元素后

12、，rear=(0+4)%6=4再例2 ：数组n用来表示一个循环队列，f 为当前队列头元素的前一位置，r 为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为:（） rf（）nrf（）（nfr）% n（）（nrf）% nfrontJ2J3J1J4J5分析 ：4种公式哪种合理？当 r f 时（A）合理；当 r n，则无左孩子；i的右孩子是2i + 1，如果2i + 1n则无右孩子。课堂练习：1.深度为k的二叉树的结点总数，最多为个。)k-1)log2k)k)k2. 深度为9的二叉树中至少有个结点。)9)8)913二叉树有n个叶子，没有度为1的结点，共有 2n-1个结点分析：度为2的

13、结点有n-1个，所以共2n-1个结点。 4。设一棵完全二叉树具有1000个结点，则它有个叶子结点，有个度为2的结点，有个结点只有非树，有个结点只有非空右。课堂练习：1完全二叉树的第3层有2个叶子，则共有个结点5111232323456745674589 10 118910一棵深度为6的满二叉树有个分支结点和个叶子。n个节点的完全二叉树高度为，n个叶子节点的完全二叉树高度为。已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有个？二叉树二叉树二叉树顺序方法有顺序结构和链式完全二叉树：用一组地址连续的单元依次自上为 i 的结而下、自左至右结点元素，即将在一维数组中下标为 i 的分量中（不用点元

14、素下标为0全二叉树单元）。此顺序结构仅适用于完不是完全二叉树怎么办？一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。缺点：浪费空间；、删除不便2、 链式结构parent二叉树结点的特点二叉树是非线性结构，适合用链式结构方式datalchildrchild一般从根结点开始来表示。（相应地，也只能从根开始），用二叉链表树中结点时l结点结构二叉树结点数据类型定义：typedef struct BiTNode emType data;struct BTNode*lchild,*rchild; BiTNode,*BiTree;rchildlchilddatachilddata

15、rchildAABBCCDDFEG二叉链表注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。GDFECDCBBAA012345678. 151.设二叉树的顺序结构如下：（1）根据其结构，画出该二叉树。（2）写出前序，中序，后序遍历该二叉树所得的结点序列。2.已知一棵二叉树的中序序列和后序序列分别是 BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。ABCEDGF二叉树遍历若规定先左后右，则只有前三种情况：DLR 先（根）序遍历，LDR 中（根）序遍历，LRD 后（根）序遍历结论已知二叉树的先序序列和中序序列，可以唯一确定一棵二叉树。已知二叉树的

16、后序序列和中序序列，可以唯一确定一棵二叉树。已知二叉树的先序序列和后序序列，不能唯一确定一棵二叉树。树和森林树和森林定义树的遍历方法Huffman树的应用带权路径计算WPL具有相同带权结点的满二叉树不一定是树不惟一树树的结点的度数为 0 或 2， 没有度为 1 的结点。包含 n 个叶子结点 的点。有2n 1 个结树本章小结双亲表示先序遍历后序遍历结构遍历孩子表示1、定义和性质孩子兄弟树顺序结构2、结构二叉链表链式结构先序遍历三叉链表二叉树森林3、遍历中序遍历遍历后序遍历先序线索树后序遍历先序遍历4、线索化：线索树中序线索树后序线索树编码树第7章 图图的相关定义(无向完全图、有向完全图、网、连通

17、 图、强连通图、度、入度、出度、生成树和生成森林)图的方式邻接矩阵无向图邻接矩阵有向图邻接矩阵网的邻接矩阵每个结点的出度？入度？度？图的边数？邻接表每个结点的出度？入度？度？图的边数？例已知某网的邻接（出边）表，请画出该网络。当邻接表的结构形成后，图便唯一确定！图的遍历广度优先搜索从图的某一结点出发，首先依次Vi2, , Vin 再按这些顶点被该结点的所有邻接顶点 Vi1,的先后次序依次与它们相邻接的所有未被的顶点，重复此过程，直至所有顶 点均被为止。深度优先搜索1、指定的起始顶点；2、若当前的顶点的邻接顶点有未被的，则任选一个访问之；反之，退回到最近过的顶点；直到与起始顶点相通的全部顶点都完

18、毕；3、若此时图中尚有顶点未被，则再选其中一个顶点作为起之，转 2； 反之，遍历结束。始顶点并最小生成树姆算法将顶点进行归并算法将边进行归并例：Prim算法UV0V056111255 5V1V2V35V1V2V364432326V4V5V4V564最小代价生成树的生成过程例： Kruscal 算法实例的执行过程V05615 5V1V2V364326V4V5图GV05155V1V2V3432算法实现要点: 每个结点增加一个数据场，用于标识该结点V4V5所属的集合。可用于判断新的边加入后是否回路。最小代价生成树1、初始连通分量： 0,1,2,3,4,52、反复执行添加、放弃动作。条件：边数不等于

19、n-1时边动作连通分量(0,2)添加0,2,1,3,4,5(3,5)添加0,2,3, 5,1,4(1,4)添加0,2,3, 5,1,4(2,5)添加0,2,3,5,1,4(0,3) 放弃 因 回路 (2,3) 放弃 因 回路 (1,2) 添加 0,2,3,5,1,4单源最短路径在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径(Dijkstra) 算法：按路径长度递增次序产生最短路径1、把 V 分成两组：S：已求出最短路径的顶点的集合。V - S = T：尚未确定最短路径的顶点集合。 2、将 T 中顶点按最短路径递增的次序加入到 S 中，保证： (1) 从源点 v0 到 S 中各顶点的最短路径长度都不大于从 v0 到 T 中任何顶点的最短路径长度。(2) 每个顶点对应一个距离值：S 中顶点：从 v0 到此顶点的最短路径长度。T 中顶点：从 v0 到此顶点的只包括S 中顶点作中间顶点的最短路径长度。拓扑排序AOV网：在一个有向图中，若用顶点表示活动，有向边表示活动间先后关系，称该有向图叫做顶点表示活动的网络(Activity On Vertex network)简称为AOV网。拓扑排序的方法：在有向图中选一个没有前驱的顶点且输出之。从图中删除该顶点