计算机二级公共基础-数据结构与算法

公共基础,数据结构与算法,1算法的基本概念算法是解题方案的准确而完整的描述，它不等于程序，也不等于计算方法算法可以使用语言、图形、程序（VBA语言、c语言）描述2算法的基本特征A.可行性：能得到满意结果B.确定性：没有多义性C.有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止D.拥有足够的情报：输入足够数据,1.1算法,3算法复杂度：评价算法的执行效率，度量一个算法的好坏时间复杂度：执行算法需要的工作量，即执行运算的次数。不是执行的时间，不是指令（语句）的条数。空间复杂度算法执行过程所需要的内存空间算法的空间复杂度与时间复杂度没有直接联系，即无关,1.1算法,算法概念练习,1、问题处理方案的正确而完整的描述称为：()2005.42、算法的有穷性是指：()2008.04-5A算法程序的运行时间是有限的B算法程序处理的数据量是有限的C算法程序的长度是有限的D算法只能被有限的用户使用3、算法的空间复杂度是指：()2009.09-4A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数,算法概念练习,4、算法的时间复杂度是指：()2010.03-2A算法的执行时间B算法所处理的数据量C算法程序中的语句或指令条数D算法在执行过程中的所需要的基本运算次数5、判断：随着算法的空间复杂度的增大，时间复杂度也跟着增大（true/false）6、算法的工作量大小和实现算法所需的存储单元多少分别称为算法的（）,1.2数据结构的基本概念,1数据结构研究的主要内容A数据的逻辑结构：反映数据之间的逻辑关系的结构。B数据的存储结构：逻辑结构在计算机的存储形式。C对各种数据结构进行的运算2研究数据结构目的提高数据处理的速度时间复杂度尽量节省在数据处理过程中所占用的计算机存储空间空间复杂度注：不同的数据结构直接影响算法的执行效率,1.2数据结构的基本概念,3数据逻辑结构的定义数据结构是指相互有关联的数据元素的集合数据元素：每一个需要处理的对象都可以抽象为数据元素；数据结构中，用前后件关系来描述数据元素之间的关系。所以一个数据结构应包含两方面的信息：表示数据元素的信息；表示各数据元素之间的前后件关系（逻辑关系）,春夏秋冬是四个数据元素，根据一年四季的顺序关系，则“春”是“夏”的前件，而“夏”是“春”的后件,4、数据的逻辑结构对数据元素之间的逻辑关系的描述；只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关；一种逻辑结构可以采用多种存储结构；5、数据的存储结构（数据的物理结构）数据的逻辑结构在计算机存储空间中的存放形式；一种逻辑结构可以采用多种存储结构，采用不同的存储结构，对数据处理的效率是不同的；常见的存储结构有顺序、链接、索引,1.2数据结构的基本概念,6、数据结构的图形表示,1.2数据结构的基本概念,春夏秋冬是四个数据元素，根据一年四季的顺序关系，则“春”是“夏”的前件，而“夏”是“春”的后件,数据元素用方框表示，前后件关系用有向线段表示,7、线性结构与非线性结构根据数据逻辑结构中各数据元素之间前后件关系的复杂程度，分为：线性结构与非线性结构线性结构（线性表）：满足a.有且只有一个根结点（没有前件的结点），b.每个结点最多有一个前件，也最多有一个后件。非线性结构：不是线性结构。如果一个数据结构中一个数据元素都没有，就称为空的数据结构，线性结构和非线性结构都可以是空的数据结构,1.2数据结构的基本概念,线性结构,非线性结构,数据结构基本概念练习,数据的存储结构是指（）2005.4-1A)存储在外存中的数据B)数据所占的存储空间量C)数据在计算机中的顺序存储方式D)数据的逻辑结构在计算机中的表示下列叙述中正确的是（）2005.9-4A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率,数据结构基本概念练习,数据的逻辑结构在计算机存储空间中的存放形式成为数据的（）下列叙述中正确的是2007.4-1A）算法的效率只与问题的规模有关,而与数据的存储结构无关.B）算法的时间复杂度是指执行算法所需要的计算工作量C）数据的逻辑结构与存储结构是一一对应的.D）算法的时间复杂度与空间复杂度一定相关.下列叙述中正确的是_2007.9-6A）数据的逻辑结构与存储结构必定是一一对应的B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D）以上三种说法都不对,线性表是由N(n=0)个数据元素a1,a2,an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。线性表是一种线性结构，也就是一种逻辑结构线性表可以是空表，也可以是非空线性表,1.3线性表及其顺序存储结构,线性表是一种线性逻辑结构，在计算机中可以有不同的存储形式，即可以有不同的存储结构。线性表的存储结构有两种：线性表的顺序存储结构（又称顺序表）线性链表线性表的顺序存储结构（又称顺序表）线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。,1.3线性表及其顺序存储结构,线性表的顺序存储结构的插入与删除运算插入运算：要在第i个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，然后第i个位置被空出来，新元素插入到第i项。平均情况下，要在顺序表中插入一个新元素，需要移动表中一半的元素。删除运算：要删除第i个元素，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。平均情况下，要在顺序表中插入一个新元素，需要移动表中一半的元素。,1.3线性表及其顺序存储结构,栈和队列是两种特殊的线性表，它们是运算时受到某些限制的线性表。它们都是线性数据结构。栈(stack)：是限定在一端进行插入与删除元素的线性表。允许插入与删除的一端称为栈顶不允许插入与删除的一端称为栈底入栈：在栈顶位置插入一个新元素退栈：取出栈顶元素并赋给一个指定的变量栈的组织数据原则：“先进后出”(“后进先出”),1.4栈和队列,一个栈的初始状态为空。现将元素1、A、3、B、5、C依次入栈，然后再依次出栈，则元素出栈的顺序是?,C、5、B、3、A、1,队列：限定只能在表的一端进行插入和在另一端进行删除操作的线性表队尾(rear)：允许插入的一端，指向插入的最后一个元素队头(front)：允许删除的另一端，指向队头元素的前一个位置入队运算：往队列的队尾插入一个元素，队尾指针rear的变化退队运算：从队列的排头删除一个元素，队头指针front的变化队列在队尾插入元素，在队头删除元素队列的组织数据原则：“先进先出”或“后进后出”,1.4栈和队列,循环队列：队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在实际的应用中，队列的顺序存储结构一般采用循环队列形式。入队运算：队尾指针加1出队运算：队头指针加1,1.4栈和队列,循环队列元素个数的计算：队列空间容量m,头指针front,尾指针rear,标记s1当尾指针大于头指针时，元素个数：rear-front2当头指针大于尾指针时，元素个数：m-(front-rear)3当头指针等于尾指针时，s=0表示元素为0个，s=1时队列满，元素个数为m个。,1.4栈和队列,m=13,栈和队列练习,2005.9（3）下列关于栈的描述正确的是A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素2005.4（2）下列关于栈的描述中错误的是A)栈是先进后出的线性表B)栈只能顺序存储C)栈具有记忆作用D)对栈的插入与删除操作中，不需要改变栈底指针2006.4（4）按照“后进先出”原则组织数据的数据结构是A队列B栈C双向链表D二叉树,栈和队列练习,2008.4（7）下列关于栈的叙述正确的是A栈按”先进先出”组织数据B栈按”先进后出”组织数据C只能在栈底插入数据D不能删除数据2008.9（1）一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是A）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA2009.3（2）支持子程序调用的数据结构是A线B树C队列D二叉树,栈和队列练习,2009.3（填1）假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49,top=30（数组下标），则栈中具有_个元素。2007.4（5）下列队列的叙述正确的是。A）队列属于非线性表B）队列按”先进后出”的原则组织数据C）队列在队尾删除数据D）队列按先进先出原则组织数据2005.9（填4）数据结构分为逻辑结构和存储结构，循环队列属于_结构。2007.9（填3）线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的_存储结构。,栈和队列练习,设某循环队列的容量为50,头指针front=5(指向队头元素的前一位置),尾指针rear=29(指向队尾元素),则该循环队列中共有_个元素下列叙述中正确的是（）。A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B）在循环队列中，只需要队头指针就能反映队的中元素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队的中元素的动态变化情况D）循环队列中元素的个数是由队头指针和队尾指针共同决定对于循环队列，下列叙述中正确的是A）队头指针是固定不变的B）队头指针一定大于队尾指针C）队头指针一定小于队尾指针D）队头指针可以大于队尾指针，也可以小于队尾指针,线性表除了可以采用顺序存储结构，还可以采用链式存储结构。采用链式存储结构的线性表称为线性链表。链式存储结构的每个结点有两个域，一个用于存放数据，一个用于存放指针。,1.5线性链表,链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素的逻辑关系可以不一致，而数据之间的逻辑关系由指针域来确定的。,链式存储方式既可以用于表示线性结构（线性表），也可以用于表示非线性结构（如：树）。循环链表是一种特殊线性链表。,1.5线性链表,线性链表练习,下列对于线性链表的描述中正确的是A)存储空间不一定是连续，且各元素的存储顺序是任意的B)存储空间不一定是连续，且前件元素一定存储在后件元素的前面C)存储空间必须连续，且前件元素一定存储在后件元素的前面D)存储空间必须连续，且各元素的存储顺序是任意的2006.4（5）下列叙述中正确的是A线性链表是线性表的链式存储结构B栈与队列是非线性结构C双向链表是非线性结构D只有根结点的二叉树是线性结构2008.9（4）下列叙述中正确的是（）。A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间,树的基本概念树是一种简单的非线性结构。树中，所有的数据元素之间的关系具有明显的层次特征。在树的图形表示，总认为用直线连起来的两个端点，上端是前件，下端是后件，表示前后件关系的箭头就可以省略。,1.6树与二叉树,树的术语结点：一个数据元素，ADBGEF都称为结点父结点：每个结点只有一个前件，称为父节点。D、B的父节点是A。树的根节点：树中，没有前件的节点只有一个，称为树的根节点，简称树的根。该树，根节点是A。子结点：每一个节点可以有多个后件，它们都称为该结点的子结点。A的子结点是D、B.叶子结点：没有后件的结点称为叶子结点。G、E、F是叶子结点。结点的度：一个结点所拥有的后件个数。A的度为2，D的度有为3，B的度为0.树的度：所有结点中的最大的度称为树的度。该树的度为3.树的层次：根结点在一层，依次递增。A为一层，DB为二层，GEF为三层。树的深度：树的最大层次。该树的深度为3.子树：以某个结点的一个子结点为跟构成的树称为该结点的一棵子树。A有两棵子树，分别是DGEF，B。,1.6树与二叉树,什么是二叉树二叉树也是一种非线性结构。二叉树可以采用顺序存储结构，也可以采用链式存储结构，通常情况下使用链式存储结构。二叉树有两个特点：非空二叉树只有一个根节点（空二叉树没有结点）每个结点最多有两棵子树，且分别称为该结点的左子树与右子树二叉树的基本性质性质一：二叉树的第K层上，最多有2k-1个结点第1层，最多有20个；第2层，最多有21个；第3层，最多有22个。性质二：深度为m二叉树最多有2m-1个结点该树的深度为3，所以二叉树最多为1+2+4个，20+21+22，即23-1个,1.6树与二叉树,二叉树的基本性质性质三：在任意的二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。注：二叉树的结点，只有三种，度数为0的结点，即叶子结点；度数为1的结点和度数为2的结点。所以二叉树的总节点数=N0+N1+N2=N1+2N2+1性质四：具有N个结点的二叉树，其深度至少为log2n+1,其中log2n表示取log2n的整数部分。,1.6树与二叉树,满二叉树即每一层上都含有最大结点数。,1.6树与二叉树,完全二叉树除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。,1.6树与二叉树,1.6树与二叉树,二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。遍历需要访问根结点、左子树上的所有结点、右子树上的所有结点。在遍历时，一般先遍历左子树，然后遍历右子树。在这个原则下，根据访问根结点的次序分为三种：1.前序遍历（DLR）：首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。,1.6树与二叉树,二叉树的遍历2.中序遍历(LDR)：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。3.后序遍历(LRD)：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。,先序遍历：DLR中序遍历：LDR后序遍历：LRD,A,D,B,C,DLR,以先序遍历DLR为例演示遍历过程,ABDC,BDAC,DBCA,F,H,G,P,B,D,A,E,C,DLR:LDR:LRD:,树与二叉树练习,下列数据结构中，属于非线性结构的是A）循环队列B）带链队列C）二叉树D）带链栈某二叉树中度为2的结点有18个，则该二叉树中有（）个叶子结点。一棵二叉树第六层（根结点为第一层）的结点数最多为个。在深度为7的满二叉树中，叶子结点的个数为A32B31C64D63,树与二叉树练习,在深度为7的满二叉树中，度为2的结点个数为_。一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为_。A）219B）221C）229D）231深度为5的满二叉树有_个叶子结点,树与二叉树练习,2006.4（6）对如下二叉树进行后序遍历的结果为对如下二叉树进行中序遍历的结果为,顺序查找从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功