10(答案)公共基础1-数据结构与算法

数据结构与算法1算法的基本概念◦算法是解题方案的准确而完整的描述，它不等于程序，也不等于计算方法◦算法可以使用语言、图形、程序（VBA语言、c语言）描述2算法的基本特征◦A.可行性：能得到满意结果◦B.确定性：没有多义性◦C.有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止◦D.拥有足够的情报：输入足够数据3算法复杂度：评价算法的执行效率，度量一个算法的好坏◦时间复杂度：执行算法需要的工作量，即执行运算的次数。不是执行的时间，不是指令（语句）的条数。◦空间复杂度算法执行过程所需要的内存空间◦算法的空间复杂度与时间复杂度没有直接联系，即无关1、问题处理方案的正确而完整的描述称为：(算法)2005.42、算法的有穷性是指：()····2008.04-5◦A算法程序的运行时间是有限的◦B算法程序处理的数据量是有限的◦C算法程序的长度是有限的◦D算法只能被有限的用户使用◦算法的有穷性，是指算法必须在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。故本题答案为A。3、算法的空间复杂度是指：()···2009.09-4◦A）算法在执行过程中所需要的计算机存储空间◦B）算法所处理的数据量◦C）算法程序中的语句或指令条数◦D）算法在执行过程中所需要的临时工作单元数◦一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。故本题答案为A。4、算法的时间复杂度是指：()···2010.03-2◦A算法的执行时间◦B算法所处理的数据量◦C算法程序中的语句或指令条数◦D算法在执行过程中的所需要的基本运算次数◦所谓算法的时间复杂度，是指执行算法所需要的计算工作量。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。故本题答案为D。5、判断：随着算法的空间复杂度的增大，时间复杂度也跟着增大（true/false）false6、算法的工作量大小和实现算法所需的存储单元多少分别称为算法的（时间复杂度;空间复杂度）1数据结构研究的主要内容◦A数据的逻辑结构：反映数据之间的逻辑关系的结构。◦B数据的存储结构：逻辑结构在计算机的存储形式。◦C对各种数据结构进行的运算2．研究数据结构目的◦提高数据处理的速度···时间复杂度◦尽量节省在数据处理过程中所占用的计算机存储空间···空间复杂度◦注：不同的数据结构直接影响算法的执行效率3数据逻辑结构的定义◦数据结构是指相互有关联的数据元素的集合◦数据元素：每一个需要处理的对象都可以抽象为数据元素；◦数据结构中，用前后件关系来描述数据元素之间的关系。◦所以一个数据结构应包含两方面的信息：表示数据元素的信息；表示各数据元素之间的前后件关系（逻辑关系）春夏秋冬春夏秋冬是四个数据元素，根据一年四季的顺序关系，则“春”是“夏”的前件，而“夏”是“春”的后件··父亲女儿儿子父亲、儿子、女儿是数据元素，父亲是儿子、女儿的前件···4、数据的逻辑结构◦对数据元素之间的逻辑关系的描述；◦只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关；◦一种逻辑结构可以采用多种存储结构；5、数据的存储结构（数据的物理结构）数据的逻辑结构在计算机存储空间中的存放形式；一种逻辑结构可以采用多种存储结构，采用不同的存储结构，对数据处理的效率是不同的；常见的存储结构有顺序、链接、索引6、数据结构的图形表示春夏秋冬春夏秋冬是四个数据元素，根据一年四季的顺序关系，则“春”是“夏”的前件，而“夏”是“春”的后件··父亲女儿儿子父亲、儿子、女儿是数据元素，父亲是儿子、女儿的前件···数据元素用方框表示，前后件关系用有向线段表示7、线性结构与非线性结构根据数据逻辑结构中各数据元素之间前后件关系的复杂程度，分为：线性结构与非线性结构线性结构（线性表）：满足a.有且只有一个根结点（没有前件的结点），b.每个结点最多有一个前件，也最多有一个后件。非线性结构：不是线性结构。如果一个数据结构中一个数据元素都没有，就称为空的数据结构，线性结构和非线性结构都可以是空的数据结构春夏秋冬父亲女儿儿子线性结构非线性结构1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储（如：顺序表的顺序存储结构）B链式存储（如：线性链表）线性表栈（特殊线性表）队列（特殊线性表）树形结构图形结构数据结构的三个方面数据的存储结构是指（D）····2005.4-1A)存储在外存中的数据B)数据所占的存储空间量C)数据在计算机中的顺序存储方式D)数据的逻辑结构在计算机中的表示下列叙述中正确的是（D）·····2005.9-4A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。数据的逻辑结构在计算机存储空间中的存放形式成为数据的（存储结构）下列叙述中正确的是····2007.4-1A）算法的效率只与问题的规模有关,而与数据的存储结构无关.B）算法的时间复杂度是指执行算法所需要的计算工作量C）数据的逻辑结构与存储结构是一一对应的.D）算法的时间复杂度与空间复杂度一定相关.我们通常用时间复杂度和空间复杂度来衡量算法效率，算法的时间复杂度是指执行算法所需要的计算工作量；算法所执行的基本运算次数与问题的规模有关，而一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间；一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。故本题答案为B。下列叙述中正确的是______2007.9-6A）数据的逻辑结构与存储结构必定是一一对应的B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D）以上三种说法都不对数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等。而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的，所以选项A是错误的。根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构和非线性结构，所以选项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,头指针font,尾指针rear,标记s◦1当尾指针大于头指针时，元素个数：rear-font◦2当头指针大于尾指针时，元素个数：m-(font-rear)◦3当头指针等于尾指针时，s=0表示元素为0个，s=1时队列满，元素个数为m个。font=3rear=8font=9rear=2m=132005.9（3）下列关于栈的描述正确的是CA）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素栈实际上也是线性表，只不过是一种特殊的线性表。在这种特殊的线性表中，其插入和删除只在线性表的一端进行。2005.4（2）下列关于栈的描述中错误的是BA)栈是先进后出的线性表B)栈只能顺序存储C)栈具有记忆作用D)对栈的插入与删除操作中，不需要改变栈底指针1.顺序存储方式2.链式存储方式2006.4（4）按照“后进先出”原则组织数据的数据结构是A．队列B．栈C．双向链表D．二叉树栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种后进先出的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种先进先出的线性表B。2008.4（7）下列关于栈的叙述正确的是A栈按”先进先出”组织数据B栈按”先进后出”组织数据C只能在栈底插入数据D不能删除数据栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能