《数据结构第四篇考前辅导导学资料.ppt》由会员分享，可在线阅读，更多相关《数据结构第四篇考前辅导导学资料.ppt（30页珍藏版）》请在三一文库上搜索。
1、数据结构考前辅导 2010-2011学年第一学期,兰州大学网络教育学院,辅导教师：马之力,考试概况,考试时间为90分钟，满分为100分，试题共分五个部分： 1、单项选择题（10道，每道2分） 2、判断题（5道，每道2分） 3、填空题（10空，每空2分）/名词解释 4、简答题（3道左右） 5、综合应用题（3道左右，本、专科都做，本、专科各做）,第1章 绪论,数据结构定义: 数据结构是一门研究非数值的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 数据元素是数据的基本单位, 数据项是数据的不可分割的最小单位. 数据结构有逻辑结构和物理结构（存储结构）之分。 通常所说的数据结构为逻
2、辑结构。,数据结构是具有一定关系的数据元素的集合，这种关系包括集合、线性、树形结构 和图形结构或网状结构。 数据结构的四类基本结构: (1) 集合 (2)线性结构 (3)树形结构 (4)图形结构或网状结构 线性结构和非线性结构 数据的存储结构有顺序结构和链式结构。 顺序结构和链式结构的优缺点。,第1章 绪论,算法的5个重要特性： 有穷性、确定性、可行性、输入、输出 要会计算时空复杂度。,举例,例：判断对错 数据项是数据的不可分割的最小单位。 （正确） 数据元素是数据的基本单位。 （正确）,第3章 栈和队列,1.栈: 限定仅在表尾进行插入或删除操作的线性表。 2.栈:后进先出. 3. 队列: 是
3、一种先进先出的线性表，它只允许在表的队尾进行插入，而在队头删除元素。 注:栈和队列都是操作受限的线性表. 要搞清楚栈和队列的相同点和不同点。,举例,例：链式队列Q为空的判定条件是？ Q.front=Q.rear 例： 栈和队列都是操作不受任何限制的线性表。 （错误） 例：在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为_。 答案：rear= = front 判断队满的条件为：(rear+l)n= = front,第四章 串,1.串(字符串):由零个或多个字符组成的有限序列. 2.空 串:零个字符组成的串. 空格串:由一个或多个空格组成的
4、串. 3.串的长度:串中元素的个数. 例1: 设s =“I AM A WOMAN”,则字符串的长度为 _ . ( B ) A、11 B、12 C、14 D、15,4.串联接Concat(否则 (1)访问根结点; (2)先序遍历左子树; (3)先序遍历右子树. 中序遍历二叉树的操作定义为: 若二叉树为空,则空操作;否则 (1) 中序遍历左子树; (2)访问根结点; (3)中序遍历右子树.,后序遍历二叉树的操作定义为: 若二叉树为空,则空操作;否则 (1)后序遍历左子树; (2)后序遍历右子树. (3)访问根结点;,例5: 已知一棵二叉树中序和后序序列为分别为: 和 画出这棵二叉树。,7.哈夫曼树
5、构造方法: 1. 根据给定的n个权值w1,w2,wn构成n棵二 叉树的集合F=T1,T2,.,Tn，其中每棵二叉树Ti中只有一个带权wi的根结点，左右子树均空。 2. 在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 3. 在F中删除这两棵树，并将新的二叉树加入F中。 4. 重复前两步（2和3），直到F中只含有一棵树为止。该树即为哈夫曼树,例7判断对错 满二叉树也是完全二叉树。 （正确） 例8若采用孩子兄弟链表作为树的存储结构，则树的先根遍历应采用二叉树的_。 ( ) A、层次遍历 B、先序遍历 C、中序遍历 D、后序
6、遍历,第七章 图,1.图分为:有向图和无向图. 2.顶点v的入度:以顶点v为头的弧的数目. 顶点v的出度:以顶点v为尾的弧的数目. 3.一个连通图的生成树: 是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边. 4.图的表示法:邻接表,邻接多重表,十字链表 5.数组表示法(邻接矩阵):以二维数组表示有n个顶点的图时,需存放n 个顶点信息和n2个弧信息的存储量. 6.强连通图：在有向图G中，对于任意一个顶点如果存在它到任意其它顶点的路径，则称G是强连通图,7.无向图的邻接矩阵是对称矩阵 。 8. n个顶点的连通图的生成树有n-1条边. 9.在一个有n个顶点的无向图中，有n(
7、n-1)/2条边的图称为完全图。 10.一个强连通图的连通分量不只有一个。 11.图的遍历:从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次. 12.两条遍历图的途径:深度优先搜索, 广度优先搜索. 13.图的广度优先遍历算法类似于二叉树的 (层次遍历 ).,第9章 查找,1.查找表：是由同一类型的数据元素（或记 录）构成的集合。 2.折半查找算法思想：将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。,折半查找的局限性：
8、(1)查找表要有序；(2)需要顺序存储结构 例1: 判断对错 折半查找适用于采用顺序存储结构的有序表。 （正确） 折半查找适用于采用链式存储结构的无序表。 （错误） 采用折半查找方法查找长度为n的线性表时,每个元 素的平均查找长度为O(logn)。,3.哈希表不需要进行比较便可以直接取得所查记录 . 4.哈希表构造方法:直接定址法,数字分析法,平方取中法,折叠法,除留余数法,随机数法. 5.处理冲突的方法: 什么是冲突?处理冲突的方法是什么? 若某个散列函数H对于不相等的关键字key1和key2得到相同的散列地址(即H(key1)=H(key2)则将该现象称为冲突. 解决冲突的方法有:开放定址
9、法和链地址法.,第10章 排序,深刻理解冒泡排序的基本思想并能够解题。 例1已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用冒泡排序法进行排序时每一趟的排序结果。,初态： 46 74 53 14 26 38 86 65 27 34 第一趟： 46 53 14 26 38 74 65 27 34 86 第二趟： 46 14 26 38 53 65 27 34 74 86 第三趟： 14 26 38 46 53 27 34 65 74 86 第四趟： 14 26 38 46 27 34 53 65 74 86 第五趟： 14 26 38 27 34 46 53 65 74 86 第六趟： 14 26 27 34 38 46 53 65 74 86 第七趟： 14 26 27 34 38 46 53 65 74 86,从未排序序列中依次取出元素与已排序序列 （初始时为空）中的元素作比较，将其放入 已排序序列的正确位置上的排序方法称为插入 排序 。 用快速排序法对包含n个关键字的序列进行排 序，最坏情况下的时间复杂度为 O(n2)。,祝大家取得好的成绩！,追求,谢谢！,