数据结构第四篇考前辅导导学资料(

数据结构考前辅导2010-2011学年第一学期兰州大学网络教育学院辅导教师：马之力考试概况考试时间为90分钟，满分为100分，试题共分五个部分：1、单项选择题（10道，每道2分）2、判断题（5道，每道2分）3、填空题（10空，每空2分）/名词解释4、简答题（3道左右）5、综合应用题（3道左右，本、专科都做，本、专科各做）重点章节第2章线性表第3章栈和队列第6章树和二叉树第7章图第9章查找第10章内部排序第1章绪论数据结构定义:数据结构是一门研究非数值的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据元素是数据的基本单位,数据项是数据的不可分割的最小单位.数据结构有逻辑结构和物理结构（存储结构）之分。通常所说的数据结构为逻辑结构。数据结构是具有一定关系的数据元素的集合，这种关系包括集合、线性、树形结构和图形结构或网状结构。数据结构的四类基本结构:(1)集合(2)线性结构(3)树形结构(4)图形结构或网状结构线性结构和非线性结构数据的存储结构有顺序结构和链式结构。顺序结构和链式结构的优缺点。第1章绪论算法的5个重要特性：有穷性、确定性、可行性、输入、输出要会计算时空复杂度。第2章线性表1.线性结构的特点。2.线性结构既可以用顺序结构表示，又可以用链式结构表示。3.线性表:n个数据元素的有限序列.线性表是有限序列,可以为空.4.单链表插入、删除结点时的具体操作。举例例：数据的逻辑结构中非线性结构有（）A、线形结构B、树形结构C、顺序结构D、链式结构注意：顺序结构和链式结构是物理结构，所以C、D排除；逻辑结构中非线性结构有集合、树形、图状或网状，所以选B。举例例：判断对错数据项是数据的不可分割的最小单位。（正确）数据元素是数据的基本单位。（正确）第3章栈和队列1.栈:限定仅在表尾进行插入或删除操作的线性表。2.栈:后进先出.3.队列:是一种先进先出的线性表，它只允许在表的队尾进行插入，而在队头删除元素。注:栈和队列都是操作受限的线性表.要搞清楚栈和队列的相同点和不同点。举例例：链式队列Q为空的判定条件是？Q.front==Q.rear例：栈和队列都是操作不受任何限制的线性表。（错误）例：在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为_______。答案：rear==front判断队满的条件为：(rear+l)％n==front第四章串1.串(字符串):由零个或多个字符组成的有限序列.2.空串:零个字符组成的串.空格串:由一个或多个空格组成的串.3.串的长度:串中元素的个数.例1:设s=“IAMAWOMAN”,则字符串的长度为_____.(B)A、11B、12C、14D、154.串联接Concat(&T,s1,s2)假设s1,s2,T都是ssting型的串变量,且串T是由s1联结s2得到的,即:T的值的前一段和s1的值相等,T的值的后一段和s2的值相等.例2:设s1=“GOOD”,s2=“BYE!”则字符串s1和s2连接后的结果是____。(D)A、BYEGOOD!B、GOODBYE!C、BYEDGOOD!D、GOODBYE!例3两个字符串相等的条件是_____.答案：两串的长度相等，并且对应位置上的字符相同。例4判断对错空串与空格串没有区别。（错）第五章数组和广义表1.广义表一般记为:LS=(a1,a2,…,an)当广义表LS非空时,称第一个元素a1为LS的表头,其余元素组成的表(a2,a3,…,an)是LS的表尾.一个广义表的表尾总是一个广义表例1:（判断）广义表的表头可以是广义表，也可以是单个元素。(正确)例2:广义表（（ab）,ab）的表头是______(A)A、（ab）B、abC、abD、((ab))例3判断对错广义表有两个特殊的基本运算：取表头和取表尾。（正确）三维数组存储地址的计算。第6章树和二叉树1.二叉树:每个结点至多只有二棵子树,并且,二叉树的子树有左右之分,其次序不能任意颠倒.例1:三个结点的二叉树可以有哪几种形式？2.树的度是树内各节点的度的最大值。3.二叉树有5种基本形态。4.在二叉树的第i层上至多有2^(i-1)个结点(i=1).5.深度为k的二叉树至多有2^k-1个结点(i=1).6.满二叉树:一棵深度为k且有2^k-1个结点的二叉树.7.完全二叉树:深度为k,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应.例3:对完全二叉树叙述正确的是（B）A、完全二叉树就是满二叉树B、完全二叉树同一层上左子树未满不会有右子树C、完全二叉树和满二叉树编号不对应D、以上都不正确6.遍历二叉树的操作定义先序遍历二叉树的操作定义为:若二叉树为空,则空操作;否则(1)访问根结点;(2)先序遍历左子树;(3)先序遍历右子树.中序遍历二叉树的操作定义为:若二叉树为空,则空操作;否则(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树.后序遍历二叉树的操作定义为:若二叉树为空,则空操作;否则(1)后序遍历左子树;(2)后序遍历右子树.(3)访问根结点;例5:已知一棵二叉树中序和后序序列为分别为:和画出这棵二叉树。7.哈夫曼树构造方法: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、后序遍历第七章图1.图分为:有向图和无向图.2.顶点v的入度:以顶点v为头的弧的数目.顶点v的出度:以顶点v为尾的弧的数目.3.一个连通图的生成树:是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边.4.图的表示法:邻接表,邻接多重表,十字链表5.数组表示法(邻接矩阵):以二维数组表示有n个顶点的图时,需存放n个顶点信息和n^2个弧信息的存储量.6.强连通图：在有向图G中，对于任意一个顶点如果存在它到任意其它顶点的路径，则称G是强连通图7.无向图的邻接矩阵是对称矩阵。8.n个顶点的连通图的生成树有n-1条边.9.在一个有n个顶点的无向图中，有n(n-1)/2条边的图称为完全图。10.一个强连通图的连通分量不只有一个。11.图的遍历:从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次.12.两条遍历图的途径:深度优先搜索,广度优先搜索.13.图的广度优先遍历算法类似于二叉树的(层次遍历).第9章查找1.查找表：是由同一类型的数据元素（或记录）构成的集合。2.折半查找算法思想：将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。折半查找的局限性：(1)查找表要有序；(2)需要顺序存储结构例1:判断对错折半查找适用于采用顺序存储结构的有序表。（正确）折半查找适用于采用链式存储结构的无序表。（错误）采用折半查找方法查找长度为n的线性表时,每个元素的平均查找长度为O(logn)。3.哈希表不需要进行比较便可以直接取得所查记录.4.哈希表构造方法:直接定址法,数字分析法,平方取中法,折叠法,除留余数法,随机数法.5.处理冲突的方法:什么是冲突?处理冲突的方法是什么?若某个散列函数H对于不相等的关键字key1和key2得到相同的散列地址(即H(key1)=H(key2))则将该现象称为冲突.解决冲突的方法有:开放定址法和链地址法.第10章排序深刻理解冒泡排序的基本思想并能够解题。例1已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用冒泡排序法进行排序时每一趟的排序结果。初态：[46745314263886652734]第一趟：[465314263874652734]86第二趟：[4614263853652734]7486第三趟：[14263846532734]657486第四趟：[142638462734]53657486第五趟：[1426382734]4653657486第六趟：[14262734]384653657486第七趟：[14262734]384653657486从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上的排序方法称为插入排序。用快速排序法对包含n个关键字的序列进行排序，最坏情况下的时间复杂度为O(n^2)。祝大家取得好的成绩！追求谢谢！