第一章-数据结构与算法ppt课件

1,第一章,数据结构与算法,2,考点1算法的基本特征,（1）可行性由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。,3,考点1算法的基本特征,（2）确定性算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性。（3）有穷性算法的有穷性，即在一定的时间是能够完成的，即算法应该在计算有限个步骤后能够正常结束。,4,考点1算法的基本特征,（4）拥有足够的情报算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会有不同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。,5,考点真题,算法的有穷性是指_。A)算法程序的运行时间是有限的B)算法程序所处理的数据量是有限的C)算法程序的长度是有限的D)算法只能被有限的用户使用2008年4月选择题第5题答案：A,6,考点2算法复杂度,算法复杂度包括算法时间复杂度和算法空间复杂度。1.算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量或所需要的基本运算次数。2.算法的空间复杂度指执行这个算法所需要的内存空间。,7,考点真题,算法的时间复杂度是指A)算法的执行时间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数2010年3月选择题第2题参考答案：D,8,考点真题,算法的空间复杂度是指_。A)算法在执行过程中所需要的计算机存储空间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的临时工作单元数参考答案：A,9,考点3数据结构的定义,数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。,10,考点3数据结构的定义,数据结构主要研究和讨论以下三个方面：（1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。,11,12,考点3数据结构的定义,数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成B=（D，R）,13,考点3数据结构的定义,其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。,14,考点4线性表与顺序存储结构,根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。线性结构又称线性表,在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。,15,考点4线性表与顺序存储结构,线性表:是n个(表长n0)同类型数据元素的有限序列。元素间是线性逻辑关系，排成线性序列。线性体现在前后件关系上。记作：(a1，a2，an)特点：有且仅有一个根结点，它无前件；有且仅有一个终端结点，它无后件；除根结点外，每个结点只有一个前件；除尾结点外，每个结点只有一个后件。n0的线性表为空表。,16,线性表实例,英文字母表：(A，B，C，D，X，Y，Z)某校2003-2008年计算机数量(50，100，250，300，500，1200)学生信息表,体现在顺序关系上,记录排列为顺序关系,17,线性表的顺序存储结构顺序表,示意图,18,a1a2ai-1,顺序表的插入,插入操作insert(i,x)：在第i个元素中插入x。若插入成功返回true。,后移n-i+1个元素,12ii+1i+2n,an,x,ai,操作演示,n,19,顺序表的删除,ai,a1ai-1,删除操作Delete(i)：删除元素ai。,1i-1ii+1n-1,an,ai+1,ai,n,操作演示,20,考点真题,下列叙述中正确的是A)线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C)线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D)上述三种说法都不对,21,考点真题,参考答案：B【解析】线性表的顺序存储结构是把线性表中相邻的元素存放在相邻的内存单元中，而链式存储结构是用一组任意存储单元来存放表中的数据元素，为了表示出每个元素与其直接后继元素之间的关系，除了存储元素本身的信息外，还需存储一个指示其直接后继的存储位置信息。故线性表的链式存储结构所需的存储空间一般要多于顺序存储结构，答案为B）。,22,考点真题,在长度为n的顺序存储的线性表中插入一个元素，最坏情况下需要移动表中【2】个元素。参考答案：n【解析】在长度为n的顺序存储的线性表中插入一个元素，最坏的情况即插入在第一个位置，线性表中所有元素均需要移动，因此需要移动n次。,.,23,考点5栈与队列,栈（stack）的定义栈是限定在一端进行插入或删除操作的线性表。,先进后出(FirstInLastOut)的线性表,栈底,栈顶,进栈,出栈,a1,a4,a2,a3,NULL,栈,a5,24,考点5栈与队列,栈的基本概念栈是限定只在一端进行插入与删除的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。栈是按照先进后出或后进先出的原则组织数据的。,25,考点5栈与队列,栈的基本运算有三种：入栈、退栈与读栈顶元素。（1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一（即top加1），然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈上溢错误。,26,考点5栈与队列,（2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针减一（即top减1）。当栈顶指针为0时，说明栈空，不可进行退栈操作。这种情况称为栈的下溢错误。,27,考点5栈与队列,（3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素,.,28,考点5栈与队列,队列的定义队列(queue)是在一端进行插入，在另一端进行删除操作的线性表。FirstInFirstOut-FIFO,a1,a2,a3,a4,a5,出队,进队,队头,队尾,Queue,29,循环队列,把队列空间从逻辑上看成是一个首尾相连的环。队尾指针rear指向队列中的队尾元素，排头指针front指向排头元素的前一个位置。,front,rear,a6,a1,a7,a4,a3,a2,队列空,队列满,30,考点真题,下列关于栈的叙述正确的是_。A)栈按先进先出组织数据B)栈按先进后出组织数据C)只能在栈底插入数据D)不能删除数据2008年4月选择题第7题参考答案：B,31,考点真题,一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后依次出栈，则元素出栈的顺序是_。A)12345ABCDEB)EDCBA54321C)ABCDE12345D)54321EDCBA2008年9月选择题第1题参考答案：B,32,考点真题,下列叙述中正确的是_。A)栈是先进先出的线性表B)队列是先进后出的线性表C)循环队列是非线性结构D)线性表既可以采用顺序存储结构，也可以采用链式存储结构2009年3月选择题第1题,33,考点真题,参考答案：D【解析】栈是先进后出的线性表；队列是先进先出的线性表；循环队列是队列的一种顺序存储结构，因此是线性结构；线性表既可以采用顺序存储结构，也可以采用链式存储结构。,34,考点真题,下列数据结构中，能够按照先进后出原则存取数据的是_。A)循环队列B)栈C)队列D)二叉树2009年9月选择题第2题答案：B,35,考点真题,下列叙述中正确的是A)在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B)在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C)在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D)上述三种说法都不对,36,考点真题,参考答案：C【解析】栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。当有新元素进栈时，栈顶指针向上移动；当有元素出栈时，栈顶指针向下移动。在栈中栈底指针不变，栈中元素随栈顶指针的变化而动态变化，故答案为C）。,37,考点真题,下列关于栈叙述正确的是A)栈顶元素最先能被删除B)栈顶元素最后才能被删除C)栈底元素永远不能被删除D)以上三种说法都不对2011年3月选择题第1题答案：A,38,考点真题,对于循环队列，下列叙述中正确的是_。A)队头指针是固定不变的B)队头指针一定大于队尾指针C)队头指针一定小于队尾指针D)队头指针可以大于队尾指针，也可以小于队尾指针2009年9月选择题第3题,39,考点真题,参考答案：D【解析】循环队列是将顺序队列首尾相连形成的，随着插入元素或删除元素的进行，其队头指针及队尾指针是在不断变化的，有时可能会出现队头指针大于队尾指针的情况，也可能是队尾指针大于队头指针，故答案为D)。,40,考点真题,假设用一个长度为50的数组(数组元素的下标从0到49)作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom49，top30(数组下标)，则栈中具有_【1】_个元素。2009年3月填空题第1题答案：20【解析】与一般的线性表一样，在程序设计语言中，用一维数组S(1，m)作为栈的顺序存储空间，其中m为栈的最大容量。通常，栈中的元素个数等于(栈底指针栈顶指针1)，即4930120。,41,考点真题,一个栈的初始状态为空。首先将元素5,4,3,2,1依次入栈，然后退栈一次，再将元素A，B，C，D依次入栈，之后将所有元素全部退栈，则所有元素退栈(包括中间退栈的元素)的顺序为【1】。参考答案：1DCBA2345【解析】栈是限定只在一端进行插入与删除的线性表，栈按照先进后出或后进先出的原则组织数据。当54321入栈后，此时执行退栈操作，出栈的元素是1，然后ABCD入栈，再将所有元素退栈，故退栈顺序为：1DCBA2345。,42,考点真题,一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队,然后再依次退队,则元素退队的顺序为【1】。2010年3月填空题第1题参考答案：ABCDEF54321【解析】队列是先进先出的数据结构，所以出队列的顺序与进度列的顺序一致。,43,考点真题,设某循环队列的容量为50，头指针front5(指向队头元素的前一位置)，尾指针rear29(指向队尾元素)，则该循环队列中共有_【3】_个元素。2008年4月填空题第3题参考答案：24【解析】实现循环队列时，头指针指向第一个元素的前一个空间，尾指针指向最后一个元素。因此，此时队列中6,7,8，.,29这24个空间存有元素，即队列中有29524个元素。,44,考点真题,设某循环队列的容量为50,如果头指针front=45(指向队头元素的前一位置),尾指针rear=10(指向队尾元素),则该循环队列中共有【2】个元素。2010年3月填空题第2题答案：15解析：元素个数为50-45+10=15,45,考点6线性链表的基本概念,在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域，另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。,46,表示每个数据元素的两部分信息组合在一起被称为结点；其中表示数据元素内容的部分被称为数据域（data）；表示直接后继元素存储地址的部分被称为指针或指针域（next）指针head指向链表中第一个元素的节点，最后一个结点的指针域为空，表示链表终止单链表简化为下图描述形式,单链表结构示意图,考点6线性链表的基本概念,47,考点6线性链表的基本概念,线性表的链式存储结构称为线性链表。在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指向其前件结点；另一个称为右指针，用以指向其后件结点。这样的表称为双向链表,48,考点真题,下列关于线性链表的叙述中，正确的是。A)各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B)各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C)进行插入与删除时，不需要移动表中的元素D)以上三种说法都不对2011年9月选择题第2题,49,考点真题,参考答案：C【解析】线性表的链式存储结构称为线性链表。在线性链表中，各元素结点的存储空间可以是不连续的，且各数据元素的存储顺序与逻辑顺序可以不一致。在线性链表中进行插入与删除，不需要移动链表中的元素。因此C)选项正确。,50,下列叙述中正确的是A)线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C)线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D)上述三种说法都不对2010年9月选择题第1题,51,考点真题,参考答案：B【解析】线性表的顺序存储结构是把线性表中相邻的元素存放在相邻的内存单元中，而链式存储结构是用一组任意存储单元来存放表中的数据元素，为了表示出每个元素与其直接后继元素之间的关系，除了存储元素本身的信息外，还需存储一个指示其直接后继的存储位置信息。故线性表的链式存储结构所需的存储空间一般要多于顺序存储结构，答案为B）。,52,考点真题,数据结构分为线性结构与非线性结构，带链的栈属于【1】。2011年9月填空题第1题参考答案：线性结构【解析】数据结构分线性结构和非线性结构，其中线性表、栈、队列、串都是线性结构，线性结构的特点是(当数据元素非空时)：存在唯一的第一个数据元素，存在唯一的最后一个数据元素，除第一个元素之外，集合中的每一个数据元素都只有一个直接前驱；除最后一个元素之外，集合中的每一个数据元素都只有一个后继。,53,考点7树与二叉树及其基本性质,树的基本概念树是一种简单的非线性结构。在树结构中，数据元素之间有着明显的层次结构。在树的图形表示中，用直线连接两端的结点，上端点为前件，下端点为后件。,54,树示意图,R,根结点,叶结点,子树,U,O,前后件关系,父结点,叶子结点,子结点,55,与树相关的术语,结点的度：某结点拥有的后件结点个数。树的度：所有结点中最大的度。,U结点的度2,R结点的度3,叶结点的度0,本树的度3,56,与树相关的术语,树的深度：是树的最大层次,R,层次结构,本树的深度4,兄弟结点,K,Y,U,57,二叉树及其性质,二叉树：非空二叉树只有一个根结点；每一个结点最多有两棵子树（左、右子树）。,左子树,右子树,58,图：二叉树的5种基本形态,(a)空二叉树(b)仅有一个根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左、右子树均非空的二叉树,R,.,59,二叉树性质,二叉树性质：二叉树第k（k1）层上至多有2k-1个结点；深度为k的二叉树，至多有2k-1个结点；在任意一棵二叉树中，度为0的结点（叶子结点），总是比度为2的结点多一个具有n个结点的二叉树，其深度h至少为：h=log2n+1,取整,60,满二叉树与完全二叉树,满二叉树若第k层有2k-1个结点，则称此层的结点数是满的；当二叉树中的每一层都是满的时，称为满二叉树。深度为m的满二叉树有2m1个结点。,24-1=15,61,满二叉树与完全二叉树,完全二叉树：如果一个二叉树各层都是“满”的，只是最下面一层从右边起连续缺若干个结点，这种二叉树叫做完全二叉树。,满二叉树,完全二叉树,按层编号：从根开始，由上而下、由左至右。,62,完全二叉树性质,具有n个结点的完全二叉树的深度h为：h=log2n+1,63,完全二叉树性质,某k结点与其父结点和左、右子结点编号间关系：若k=1，则它是根结点，无父结点；若k1，其父结点编号为int（k/2）。如果2kn，则其左子结点编号为2k；若2kn，则无左子结点。如果（2k+1）n，则其右子结点编号为（2k+1）；若（2k+1)n,则无右子结点。,K=1,5,父结点,4,左子,6,右子,根结点,K=5,K=4,K=6,无左子,K=6,无右子,64,考点真题,下列关于二叉树的叙述中，正确的是。A)叶子结点总是比度为2的结点少一个B)叶子结点总是比度为2的结点多一个C)叶子结点数是度为2的结点数的两倍D)度为2的结点数是度为1的结点数的两倍2011年9月选择题第3题参考答案：B【解析】根据二叉树的性质3，在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。故答案为B)。,65,考点真题,某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是_。A)10B)8C)6D)42009年3月选择题第3题参考答案：C【解析】对于任何一棵二叉树T，如果其终端结点(叶子)数为n1，度为2的结点数为n2，则n1n21。所以该二叉树的叶子结点数等于516。,66,某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第1层)A)3B)4C)6D)72011年3月选择题第3题参考答案：D【解析】叶子结点个数=度为2的结点个数+1，在此题中叶子结点个数为1，说明度为2的结点数为0，即二叉树中不存在度为2的结点，只有度为1的结点和叶子结点，那么此二叉树就是一棵单支树，树中结点个数即为树的深度，所以答案为D)。,67,某二叉树有5个度为2的结点及3个度为1的结点，则该二叉树中共有_【1】_个结点。2009年9月填空题第1题参考答案：14【解析】在二叉树中，度为0的结点数是度为2的结点数加1，故二叉树中结点数的总和为度为0的结点数、度为1的结点数及度为2的结点数三者相加，得出结果为14个结点。,68,一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有【3】个结点。2010年9月填空题第3题参考答案：25【解析】在二叉树中，根据性质3，度为0的结点是度为2的结点个数+1，故二叉树中结点总和为度为0的结点数、度为1的结点数以及度为2的结点数三者相加，即8+10+7，共25个结点。,69,深度为5的满二叉树有_【2】_个叶子结点。2008年4月填空题第2题参考答案：16【解析】在满二叉树中，叶子结点数目的计算公式为2n1，如果是计算节点的总数计算公式为2n-1其中n为树的深度。,70,考点8二叉树的遍历,二叉树的遍历(Traversal)指按一定规律访问二叉树的每个结点，且每个结点只被访问一次的过程。任一结点的遍历次序：左、根、右；根、左、右；左、右、根；按左先右后的原则，常采用上述、遍历，分称中序遍历、前序遍历和后序遍历。,71,考点8二叉树的遍历,(1）前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。,72,考点8二叉树的遍历,（2）中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。（3）后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。,73,二叉树遍历过程,前序遍历(DLR)：A，B，D，H，I，E，C，F，G。,B,D,H,E,I,C,F,G,A,中序遍历(LDR)：H，D，I，B，E，A，F，C，G,后序遍历(LRD)：H，I，D，E，B，F，G，C，A。,74,对下列二叉树进行中序遍历的结果是_【1】_。2008年9月填空题第1题参考答案：DBXEAYFZC【解析】二叉树中序遍历的顺序为先遍历左子树，然后访问根结点，最后遍历右子树。,75,设二叉树如下：对该二叉树进行后序遍历的结果为【3】。2010年3月填空题第3题参考答案：EDBGHFCA【解析】后序遍历二叉树的定义为：先遍历左子树，后序遍历右子树，访问根结点。根据该规则，遍历结果应为EDBGHFCA。,76,考点9顺序查找,查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始，依次将线性表中的元素与被查找的元素相比较，若相等则表示查找成功；若线性表中所有的元素都与被查找元素进行了比较但都不相等，则表示查找失败。,77,考点9顺序查找,在下列两种情况下只能采用顺序查找：（1）如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。（2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,78,考点10二分法查找,二分法只适用于顺序存储的，按非递减排列的有序表，其方法如下：设有序线性表的长度为n，被查找的元素为i（1）将i与线性表的中间项进行比较；（2）若i与中间项的值相等，则查找成功；（3）若i小于中间项，则在线性表的前半部分以相同的方法查找；（4）若i大于中间项，则在线性表的后半部分以相同的方法查找。,79,考点真题,在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是_。A)O(n)B)O(n2)C)O(log2n)B)O(nlog2n)参考答案：C,80,考点真题,下列叙述中正确的是A)对长度为n的有序链表进行查找,最坏情况下需要的比较次数为nB)对长度为n的有序链表进行对分查找,最坏情况下需要的比较次数为(n2)C)对长度为n的有序链表进行对分查找,最坏情况下需要的比较次数为(log2n)D)对长度为n的有序链表进行对