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

数据结构与算法1算法的基本概念◦算法是解题方案的准确而完整的描述，它不等于程序，也不等于计算方法◦算法可以使用语言、图形、程序（VBA语言、c语言）描述2算法的基本特征◦A.可行性：能得到满意结果◦B.确定性：没有多义性◦C.有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止◦D.拥有足够的情报：输入足够数据3算法复杂度：评价算法的执行效率，度量一个算法的好坏◦时间复杂度：执行算法需要的工作量，即执行运算的次数。不是执行的时间，不是指令（语句）的条数。◦空间复杂度算法执行过程所需要的内存空间◦算法的空间复杂度与时间复杂度没有直接联系，即无关1、问题处理方案的正确而完整的描述称为：()2005.42、算法的有穷性是指：()····2008.04-5◦A算法程序的运行时间是有限的◦B算法程序处理的数据量是有限的◦C算法程序的长度是有限的◦D算法只能被有限的用户使用3、算法的空间复杂度是指：()···2009.09-4◦A）算法在执行过程中所需要的计算机存储空间◦B）算法所处理的数据量◦C）算法程序中的语句或指令条数◦D）算法在执行过程中所需要的临时工作单元数4、算法的时间复杂度是指：()···2010.03-2◦A算法的执行时间◦B算法所处理的数据量◦C算法程序中的语句或指令条数◦D算法在执行过程中的所需要的基本运算次数5、判断：随着算法的空间复杂度的增大，时间复杂度也跟着增大（true/false）6、算法的工作量大小和实现算法所需的存储单元多少分别称为算法的（）1数据结构研究的主要内容◦A数据的逻辑结构：反映数据之间的逻辑关系的结构。◦B数据的存储结构：逻辑结构在计算机的存储形式。◦C对各种数据结构进行的运算2．研究数据结构目的◦提高数据处理的速度···时间复杂度◦尽量节省在数据处理过程中所占用的计算机存储空间···空间复杂度◦注：不同的数据结构直接影响算法的执行效率3数据逻辑结构的定义◦数据结构是指相互有关联的数据元素的集合◦数据元素：每一个需要处理的对象都可以抽象为数据元素；◦数据结构中，用前后件关系来描述数据元素之间的关系。◦所以一个数据结构应包含两方面的信息：表示数据元素的信息；表示各数据元素之间的前后件关系（逻辑关系）春夏秋冬春夏秋冬是四个数据元素，根据一年四季的顺序关系，则“春”是“夏”的前件，而“夏”是“春”的后件··父亲女儿儿子父亲、儿子、女儿是数据元素，父亲是儿子、女儿的前件···4、数据的逻辑结构◦对数据元素之间的逻辑关系的描述；◦只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关；◦一种逻辑结构可以采用多种存储结构；5、数据的存储结构（数据的物理结构）数据的逻辑结构在计算机存储空间中的存放形式；一种逻辑结构可以采用多种存储结构，采用不同的存储结构，对数据处理的效率是不同的；常见的存储结构有顺序、链接、索引6、数据结构的图形表示春夏秋冬春夏秋冬是四个数据元素，根据一年四季的顺序关系，则“春”是“夏”的前件，而“夏”是“春”的后件··父亲女儿儿子父亲、儿子、女儿是数据元素，父亲是儿子、女儿的前件···数据元素用方框表示，前后件关系用有向线段表示7、线性结构与非线性结构根据数据逻辑结构中各数据元素之间前后件关系的复杂程度，分为：线性结构与非线性结构线性结构（线性表）：满足a.有且只有一个根结点（没有前件的结点），b.每个结点最多有一个前件，也最多有一个后件。非线性结构：不是线性结构。如果一个数据结构中一个数据元素都没有，就称为空的数据结构，线性结构和非线性结构都可以是空的数据结构春夏秋冬父亲女儿儿子线性结构非线性结构1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储（如：顺序表的顺序存储结构）B链式存储（如：线性链表）线性表栈（特殊线性表）队列（特殊线性表）树形结构图形结构数据结构的三个方面数据的存储结构是指（）····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组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。线性表是一种线性结构，也就是一种逻辑结构线性表可以是空表，也可以是非空线性表a1a2a3an····◦线性表是一种线性逻辑结构，在计算机中可以有不同的存储形式，即可以有不同的存储结构。◦线性表的存储结构有两种：线性表的顺序存储结构（又称顺序表）线性链表◦线性表的顺序存储结构（又称顺序表）线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。逻辑地址数据元素物理地址a1a2…aian…12inLoc(a1)Loc(a1)+kLoc(a1)+(i-1)kLoc(a1)+(n-1)k……线性表的顺序存储结构的插入与删除运算◦插入运算：要在第i个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，然后第i个位置被空出来，新元素插入到第i项。◦平均情况下，要在顺序表中插入一个新元素，需要移动表中一半的元素。◦删除运算：要删除第i个元素，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。◦平均情况下，要在顺序表中插入一个新元素，需要移动表中一半的元素。逻辑地址数据元素物理地址a1a2…aian…12inLoc(a1)Loc(a1)+kLoc(a1)+(i-1)kLoc(a1)+(n-1)k……栈和队列是两种特殊的线性表，它们是运算时受到某些限制的线性表。它们都是线性数据结构。栈(stack)：是限定在一端进行插入与删除元素的线性表。◦允许插入与删除的一端称为栈顶◦不允许插入与删除的一端称为栈底◦入栈：在栈顶位置插入一个新元素◦退栈：取出栈顶元素并赋给一个指定的变量栈的组织数据原则：“先进后出”(“后进先出”)a1a2an…栈顶top栈底bottom入栈出栈一个栈的初始状态为空。现将元素1、A、3、B、5、C依次入栈，然后再依次出栈，则元素出栈的顺序是?C、5、B、3、A、1队列：限定只能在表的一端进行插入和在另一端进行删除操作的线性表◦队尾(rear)：允许插入的一端，指向插入的最后一个元素◦队头(front)：允许删除的另一端，指向队头元素的前一个位置◦入队运算：往队列的队尾插入一个元素，队尾指针rear的变化◦退队运算：从队列的排头删除一个元素，队头指针front的变化◦队列在队尾插入元素，在队头删除元素队列的组织数据原则：“先进先出”或“后进后出”ABCDEF队头front队尾rear退队入队循环队列：队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在实际的应用中，队列的顺序存储结构一般采用循环队列形式。◦入队运算：队尾指针加1◦出队运算：队头指针加1Q(1..8)87654321rearfront(a)空队列Q(1..8)A87654321BCEFrearfrontD(b)有6个元素的循环队列Q(1..8)A8765432Y1BCEFXrearfrontD(c)元素X、Y入队后的队列Q(1..8)8765432Y1BCEFXrearfrontD(d)元素A出队后的队列循环队列元素个数的计算：队列空间容量m,头指针front,尾指针rear,标记s◦1当尾指针大于头指针时，元素个数：rear-front◦2当头指针大于尾指针时，元素个数：m-(front-rear)◦3当头指针等于尾指针时，s=0表示元素为0个，s=1时队列满，元素个数为m个。front=3rear=8front=9rear=2m=132005.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）队头指针可以大于队尾指针，也可以小于队尾指针线性表除了可以采用顺序存储结构，还可以采用链式存储结构。采用链式存储结构的线性表称为线性链表。链式存储结构的每个结点有两个域，一个用于存放数据，一个用于存放指针。链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素的逻辑关系可以不一致，而数据之间的逻辑关系由指针域来确定的。链式存储方式既可以用于表示线性结构（线性表），也可以用于表示非线性结构（如：树）。循环链表是一种特殊线性链表。下列对于线性链表的描述中正确的是A)存储空间不一定是连续，且各元素的存储顺序是任意的B)