数据结构复习指导_2012.ppt

1、1,数据结构复习大纲,第1章 概论,2,基本术语：程序、数据结构、算法、数据逻辑结构、数据存储结构、抽象数据类型。 算法：4个特性（通用性、有效性、确定性、有穷性） 算法分析：算法分析的相关概念；渐进分析方法以及3个符号（O，）的含义；最差、最佳与平均情况的意义,3,逻辑结构： 线性结构、树形结构和图形结构 存储结构： 顺序方法、链接方法、索引方法、散列方法,4,将长度为 n 的单链表接在长度为 m 的单链表之后的算法时间复杂度为 ( ) 。 A. O( n ) B. O( 1 ) C. O( m ) D. O( m + n ),5,抽象数据类型与数据结构的定义区别在于 。 数据的逻辑结构主要

2、描述元素之间的逻辑关系，它独立于数据的_。 数据结构的基本存储方式有_、_、_ 与_。 算法分析的主要内容是分析算法的_。,第2章 线性表,6,清楚线性表定义、理解类定义及抽象数据类型中定义的各个基本操作含义 存储形式：顺序存储结构与链式存储结构 顺序存储结构的特点： 1.逻辑结构与物理结构一致； 2.属于随机存取方式 缺点：插入删除元素需要移动，平均约一半的元素， 限制了长度变化 链式存储结构的特点： 1.逻辑结构与物理结构不一致； 2.属于顺序存取方式,顺序表和有序表,7,顺序表：线性表采用顺序存储结构表示(向量) 有序表：内容按从小到大排列的线性表 算法：（时间复杂性） 在有序表中插入/

3、删除一个元素使其仍有序 在给定位置插入/删除一个元素,链表单向、循环、双向,8,不特殊说明，均带头结点 算法：（时间复杂性） 在有序表中插入/删除结点 给定元素位置，插入/删除相应结点 注意： 对循环链表操作时，尾部的判断 双向链表的插入/删除结点 删除结点一定要释放空间 线性表实现方法的比较（教材2.4）,9,有序的顺序表与无序的顺序表相比，其操作优势是（ ）。 A. 删除快 B. 插入快 C. 生成快 D. 查找快,10,线性表的链式存储结构主要包括_、_、_三种形式。 线性表的顺序存储是通过_来表示数据元素之间的逻辑关系，而链式存储结构是通过_表示数据元素之间的逻辑关系。 单链表带头结点

4、的目的是_。,11,若对线性表进行的主要操作是按照下标存取，且很少插入和删除，则应该采用的存储结构是 ；若需要频繁地对线性表进行插入和删除时，则应该采用的存储结构是 。,第3章 栈与队列,12,栈与队列的定义、抽象数据类型定义及基本操作。 栈的应用：*会跟踪递归函数执行过程 *深度（纵向）周游 *表达式 （掌握后缀表达式计算中栈的应用） 队列的应用：按层周游 注意：熟悉ADT的操作形式，会直接调用抽象数据类型中定义的操作,栈的典型题,13,判回文、判表达式括号是否匹配（思路） 给定一个中缀表达式，按照教材给出的算法转换为后缀表达式（掌握） 给定后缀表达式，按照教材上给出的算法跟踪计算后缀表达式

5、的过程（掌握）,14,假设入栈顺序为1234，则下列不可能出现的出栈序列为： 4321 3421 1234 3412 给定一个序列ssxxssxxxxsxsxxxssss, s代表入栈，x代表出栈，这是合法的操作序列吗？,15,栈和队列的共同点是 。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点,16,仅允许在一端进行插入删除的线性表称为 。 设元素15，25，35和45入队，然后三个元素出队，此时留在队列里的元素是 。,17,设数组 data m 作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指

6、针front 的值为 ( )。 A. SQ.front = SQ. front + 1 B. SQ.front = (SQ. front + 1 ) % ( m 1 ) C. SQ.front = (SQ. front 1 ) % m D. SQ.front = (SQ. front + 1 ) % m,18,若已知一个栈的入栈序列是1,2,n. 其出栈序列为p1,p2,pn。若p1= n， 则pi为（ ）。 A. i B. n-i C. n-i+1 D. 不确定,19,给定表达式 23+(34*45)/(5+6+7) （1）将其转换成后缀表达式 （2）跟踪后缀表达式的计算过程,20,void

7、 DFS(Graph G, int v, int mark) visitedv = mark; coutv; for(w=FirstAdjVex(G, v); w; w=NextAdjVex(G,v,w) if ( !visitedw ) DFS(G, w, mark); / DFS,递归算法阅读,21,void programXP(Graph G, int ,22,（1）写出运行programXP() 算法后visited 的最终结果 （2）简述这个算法的功能,第 4 章 字符串(了解）,23,基本概念 存储结构（顺序、标准类） 基本操作的含义,第5章 二叉树,24,基本概念 定义、性质、存

8、储结构（相应的类定义） 满二叉树、完全二叉树及扩充二叉树 抽象数据类型定义中的基本操作含义 深度周游（递归与非递归），广度周游 二叉搜索树插入、删除（改进）与检索算法。必须能够跟踪执行过程。 堆概念、建堆与调整堆的相关算法（过程） Huffman树及Huffman编码,与算法有关的典型例题,25,已知一棵二叉树的前序和中序（后序和中序）遍历序列，构造对应的二叉树 通过二叉树，获得对应的树与森林的相关信息 深度周游与广度周游二叉树 二叉搜索树与堆的相关算法要能够根据给定实例写出执行过程,仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树,由二叉树的先序和中序序列建树,如果同时已知二叉

9、树的中序序列“cbdaegf”,则会如何？,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,28,某棵二叉树的前序序列为ABDEFC，中序序列为DBFEAC，则该二叉树对应的森林按层遍历的结果为_。 设a、b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（ ）。 A. a在b右方 B. a是b的祖先 C. a在b左方 D. a是b的子孙,29,二度树与二叉树有何区别？ 有28个结点的二叉树的最

10、大和最小深度是多少？ 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数有几个？,30,由五个分别带权值为9，2，5，7，14 的叶子结点构成Huffman树，写出该树的带权的路径长度WLP，及计算步骤。,31,给定关键码序列，创建二叉搜索树，并删除某个结点（按照教材中的改进算法）。 给定关键码序列，判断是否为最大值堆或最小值堆，如果不是，调整成堆。 给定关键码序列，建初堆。,二叉搜索树的删除,与插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。 删除过程分为如下情况： 被删除的结点是叶子 被删除的结点只有左子树

11、或只有右子树 被删除的结点有左、右子树,50,30,80,20,90,85,40,35,88,32,（1）被删除的结点是叶子结点,被删关键字 = 20,88,其双亲结点中相应指针域的值改为“空”,50,30,80,20,90,85,40,35,88,32,（2）被删除的结点只有左子树或者只有右子树,其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。,被删关键字 = 40,80,若p有左右子树，则在左子树里找中序周游的最后一个结点r，将r的右指针置成指向p的右子树的根，用结点p的左子树的根去代替被删除的结点p。,被删关键字 = 50,（3）被删除的结点既有左子树，也有右子树,50

12、,30,80,20,90,85,40,35,88,32,（3）被删除的结点既有左子树，也有右子树,40,40,以其前驱替代之，然后再删除该前驱结点,被删结点,前驱结点,被删关键字 = 50,第6章 树,37,树与森林：定义、抽象数据类型定义 以及基本操作含义 树与森林的链式存储结构（教材6.2） 树与森林的顺序存储结构（教材6.3） 树、森林遍历，与二叉树之间的关系， 相互转换 树的深度优先周游与广度优先周游 读懂代码 6.6-6.7,树的链式存储,38,1.子结点表表示法 2.左子结点/右兄弟结点表示法 3.动态结点表示法 4.动态“左子/右兄”二叉链表表示法 5.父指针表示法,1.子结点表

13、表示法,39,每个分支结点均存储其子结点信息，子结点按照从左至右的顺序形成一个链表。 “子结点表”表示法在数组中存储树的结点。每个结点包括结点值、一个父指针以及一个指向子结点链表的指针。 结点的最左结点可由链表的第一个表项找到。,40,子结点表示法,2.静态左子/右兄表示法,41,每个结点都存储结点的值及指向父结点、最左子结点和右侧兄弟的指针。 如果两棵树存储在同一个数组中，将其中一个添加为另一棵树的子树只需简单设置三个指针值即可。 这种表示法比子结点表表示法空间效率更高，而且结点数组中的每个结点仅需要固定大小的存储空间。,静态左子/右兄表示法,42,H,B,G,A,C,D,I,J,E,F,静

14、态左子/右兄表示法,43,H,B,G,A,C,D,I,J,E,F,A,A,7,A,B,0,A,C,0,A,A,A,A,A,G,/,A,D,0,A,E,2,A,F,2,A,H,6,A,I,6,A,J,7,0 1 2 3 4 5 6 7 8 9,左子 值 父 右兄,A,A,A,A,A,A,A,A,A,A,A,A,A,A,3.动态结点表示法,44,为每个结点分配可变的存储空间。 将一个指向子结点的指针数组作为结点的一部分分配给结点。在子结点的数目不变时，这种方法效果最佳；如果子结点的数目发生变动（特别是增加），就必须提供一种专门的校正机制来改变子结点指针数组的大小。 每个结点存储一条子结点指针链表。

15、本质上 “子结点表”表示法相同，但是它动态地分配结点空间，而不是把结点分配在数组中。,45,4.动态“左子/右兄”二叉链表表示法,46, | B |, | C |, | D | ,| E | , |F |, | G | , | A | ,5.父指针表示法,47,树的最简单表示方法是对每个结点只保存一个指针域指向其父结点，这种实现被称为父指针(parent pointer)表示法 如果两个结点到达同一根结点，它们一定在同一棵树中。如果找到的根结点是不同的，两个结点就不在同一棵树中,父指针数组表示法,48,父结点索引,标记,结点索引,树的顺序存储,49,1.带右链的先根次序表示法 2.带双标记位的

16、先根次序表示法,1.带右链的先根次序表示法,50,在带右链的先根次序表示中，结点按先根次序顺序存储在一片连续的存储单元中。每个结点除包括结点本身数据外，还附加两个表示结构的信息字段，结点的形式为: info是结点的数据， rlink是右指针，指向结点的下一个兄弟 ltag是一个左标记，当结点没有子结点，即对应的二叉树中结点没有左子结点时，ltag为 1，否则为0,带右链的先根次序表示法,51,带右链的先根次序rlink-ltag,52,2.带双标记位的先根次序表示法,53,带右链的先根次序表示法中每个结点都包括ltag和rlink字段，事实上rlink也不是必需的。一位rtag就足以表示出整个

17、森林的结构信息。 规定当结点没有下一个兄弟，即对应的二叉树中结点没有右子结点时rtag为1，否则为0 。,带双标记位的先根次序rtag-ltag,54,第7章 图,55,有向图/网：弧、入/出度、有向完全图 无向图/网：边、度、无向完全图 图的抽象数据类型定义 存储结构（相邻矩阵/邻接表）概念及类定义 图周游算法（掌握深度/广度，生成树） 最小生成树（prim)、拓扑排序、单源最短路径（必须会，且严格按照算法手工走给定实例）,典型题目,56,能够完成拓扑排序的图一定是一个_。 n个顶点的无向连通图至少有的边的条数是_。 已知一个有向图的相邻矩阵表示，计算第i个结点的入度的方法是_。,57,已知

18、一个无向图的顶点集为 a, b, c, d, e , 其相邻矩阵如下所示： 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 (1)画出该图的图形； (2)根据此相邻矩阵，从顶点 b 出发进行深度优先周游和广度优先周游，写出相应遍历的顶点序列。,第 8 章 内排序,58,直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、桶式排序、基数排序：手工排序每趟过程 各种排序方法的适用场合、时间复杂度 必须熟悉快速排序、堆排序的算法,59,在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（ ）。 A. 快速排序 B. 堆

19、排序 C. 归并排序 D. 基数排序 堆排序在最坏的情况下的时间复杂度是 ( )。 A. O( log2 n ) B. O( log2 n2 ) C. O( nlog2 n ) D. O( n2 ),60,用某种排序方法对线性表( 25，84，21，47，15，27，68，35，20 )进行排序时，如果元素序列前几趟的变化情况如下： 84，47，68，35，15，27，21，25，20（第一趟） 68，47，27，35，15，20，21，25，84（第二趟） 47，35，27，25，15，20，21，68，84（第三趟） 35，25，27，21，15，20，47，68，84（第四趟） 则所采用的排序方法是（ ）。 A. 选择排序 B. 堆排序 C. 归并排序 D. 快速排序,61,对关键字序列( 72, 87, 61, 23, 100, 15, 7, 60 ，20) 进行快速排序。请写出前3次次调用分割函数的结果。,第10章 检索,62,相关概念，ASL 顺序查找、二分查找、分块查找 散列表（常见的散列函数与解决冲突的方法，计算ASL）查找特点，构造方法,63,在一个无序的顺序表中，查找不成功与能够找到一个元素