公共基础1-数据结构与算法

《公共基础1-数据结构与算法》由会员分享，可在线阅读，更多相关《公共基础1-数据结构与算法（46页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法1 算法的基本概念 算法是解题方案的准确而完整的描述，它不等于程序，也 不等于计算方法 算法可以使用语言、图形、程序（VBA语言、c语言）描 述2 算法的基本特征 A.可行性：能得到满意结果 B.确定性：没有多义性 C.有穷性：算法必须能在有限的时间内做完，即算法必须 能在执行有限个步骤之后终止 D.拥有足够的情报：输入足够数据3 算法复杂度：评价算法的执行效率，度量一个算法的 好坏 时间复杂度： 执行算法需要的工作量，即执行运算的次数。 不是执行的时间，不是指令（语句）的条数。 空间复杂度 算法执行过程所需要的内存空间 算法的空间复杂度与时间复杂度没有直接联系，即无关1、问题处

2、理方案的正确而完整的描述称为：( 算法 )2005.42、算法的有穷性是指： ( )2008.04-5 A 算法程序的运行时间是有限的 B 算法程序处理的数据量是有限的 C 算法程序的长度是有限的 D 算法只能被有限的用户使用3、算法的空间复杂度是指：( )2009.09-4 A）算法在执行过程中所需要的计算机存储空间 B）算法所处理的数据量 C）算法程序中的语句或指令条数 D）算法在执行过程中所需要的临时工作单元数4、算法的时间复杂度是指：( )2010.03-2 A 算法的执行时间 B 算法所处理的数据量 C 算法程序中的语句或指令条数 D 算法在执行过程中的所需要的基本运算次数5、判断：

3、随着算法的空间复杂度的增大，时间复杂度也 跟着增大（true/false）6、算法的工作量大小和实现算法所需的存储单元多少分 别称为算法的 （时间、空间复杂度）1 数据结构研究的主要内容 A 数据的逻辑结构：反映数据之间的逻辑关系的结构。 B 数据的存储结构：逻辑结构在计算机的存储形式。 C 对各种数据结构进行的运算2研究数据结构目的 提高数据处理的速度时间复杂度 尽量节省在数据处理过程中所占用的计算机存储空间 空 间复杂度 注：不同的数据结构直接影响算法的执行效率3 数据逻辑结构的定义 数据结构是指相互有关联的数据元素的集合 数据元素：每一个需要处理的对象都可以抽象为数据元素； 数据结构中，

4、用前后件关系来描述数据元素之间的关系。 所以一个数据结构应包含两方面的信息：表示数据元素的信 息；表示各数据元素之间的前后件关系（逻辑关系）春夏秋冬春夏秋冬是四个数据元素， 根据一年四季的顺序关系， 则“春”是“夏”的前件， 而“夏”是“春”的后件父亲女儿儿子父亲、儿子、女儿是数据元素， 父亲是儿子、女儿的前件4、数据的逻辑结构 对数据元素之间的逻辑关系的描述； 只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关； 一种逻辑结构可以采用多种存储结构；5、数据的存储结构（数据的物理结构）数据的逻辑结构在计算机存储空间中的存放形式；一种逻辑结构可以采用多种存储结构，采用不同的存储结构，对数

5、据处理的效率是不同的；常见的存储结构有顺序、链接、索引6、数据结构的图形表示春夏秋冬春夏秋冬是四个数据元素， 根据一年四季的顺序关系， 则“春”是“夏”的前件， 而“夏”是“春”的后件父亲女儿儿子父亲、儿子、女儿是数据元素， 父亲是儿子、女儿的前件数据元素用方框表示，前后件关系用有向线段表示7、线性结构与非线性结构根据数据逻辑结构中各数据元素之间前后件关系的复杂程度，分为： 线性结构与非线性结构线性结构（线性表）：满足 a.有且只有一个根结点（没有前件的结点 ），b.每个结点最多有一个前件，也最多有一个后件。非线性结构：不是线性结构。如果一个数据结构中一个数据元素都没有，就称为空的数据结构，线

6、 性结构和非线性结构都可以是空的数据结构春夏秋冬父亲女儿儿子线性结构非线性结构1数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构 B非线性结构A 顺序存储（如：顺序表的顺序存储结构 ）B 链式存储（如：线性链表） 线性表栈（特殊线性表 ） 队列（特殊线性表）树形结构图形结构数据结构的三个方面 数据的存储结构是指（） 2005.4-1 A) 存储在外存中的数据 B) 数据所占的存储空间量 C) 数据在计算机中的顺序存储方式 D) 数据的逻辑结构在计算机中的表示下列叙述中正确的是（） 2005.9-4A）一个逻辑数据结构只能有一种存储结构B）数据的逻

7、辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的 效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的 效率数据的逻辑结构在计算机存储空间中的存放形式成为数据的（ ）下列叙述中正确的是 2007.4-1A） 算法的效率只与问题的规模有关,而与数据的存储结构无关. B）算法的时间复杂度是指执行算法所需要的计算工作量C）数据的逻辑结构与存储结构是一一对应的. D）算法的时间复杂度与空间复杂度一定相关.下列叙述中正确的是_2007.9-6A）数据的逻辑结构与存储结构必定是一一对应的B）由于计算机存储空间是向量式的存储

8、结构，因此，数据的存储结构一定是线 性结构C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性 结构D）以上三种说法都不对线性表是由N(n=0)个数据元素a1,a2,an组成 的一个有限序列，表中的每一个数据元素，除了第 一个外，有且只有一个前件，除了最后一个外，有 且只有一个后件。线性表是一种线性结构，也就是一种逻辑结构线性表可以是空表，也可以是非空线性表a1a2a3an 线性表是一种线性逻辑结构，在计算机中可以有不同的存 储形式，即可以有不同的存储结构。 线性表的存储结构有两种： 线性表的顺序存储结构（又称顺序表） 线性链表 线性表的顺序存储结构（又称顺序表） 线性表中所

9、有元素所占的存储空间是连续的； 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性表的顺序存储结构的插入与 删除运算 插入运算：要在第i个元素之前插入一个新元素时， 首先要从最后一个（即第n个）元素开始，直到第i个 元素之间共n-i+1个元素依次向后移动一个位置，然 后第i个位置被空出来，新元素插入到第i项。 平均情况下，要在顺序表中插入一个新元素，需要 移动表中一半的元素。 删除运算：要删除第i个元素，则要从第i+1个元素 开始，直到第n个元素之间共n-i个元素依次向前移 动一个位置。 平均情况下，要在顺序表中插入一个新元素，需要 移动表中一半的元素。栈和队列是两种特殊的线性表，它们

10、是运算时受到某些限制的线性表 。它们都是线性数据结构。栈(stack)：是限定在一端进行插入与删除元素的线性表。 允许插入与删除的一端称为栈顶 不允许插入与删除的一端称为栈底 入栈：在栈顶位置插入一个新元素 退栈：取出栈顶元素并赋给一个指定的变量栈的组织数据原则：“先进后出”(“后进先出”)一个栈的初始状态为空。现将元素 1、A、3、B、5、C 依次入栈，然后再依次出栈，则元素出栈的顺序是?C、5、B、3、A、1队列：限定只能在表的一端进行插入和在另一端进行删除 操作的线性表 队尾(rear)：允许插入的一端，指向插入的最后一个元素 队头(front)：允许删除的另一端，指向队头元素的前一个位

11、置 入队运算：往队列的队尾插入一个元素，队尾指针rear的变化 退队运算：从队列的排头删除一个元素，队头指针front的变化 队列在队尾插入元素，在队头删除元素队列的组织数据原则：“先进先出”或“后进后出”循环队列：队列存储空间的最后一个位置绕到第一个位 置，形成逻辑上的环状空间，供队列循环使用 。在实际的应用中，队列的顺序存储结构一般采用循环队列 形式。 入队运算 ：队尾指针加1 出队运算：队头指针加1循环队列元素个数的计算：队列空间容量m,头指针font,尾指针rear,标记s 1 当尾指针大于头指针时，元素个数：rear-font 2 当头指针大于尾指针时，元素个数：m-(font-re

12、ar) 3 当头指针等于尾指针时，s=0表示元素为0个，s=1时队列满， 元素个数为m个。font=3rear=8font=9rear=2m=132005.9（3）下列关于栈的描述正确的是A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素2005.4（2）下列关于栈的描述中错误的是A) 栈是先进后出的线性表 B) 栈只能顺序存储 C) 栈具有记忆作用 D) 对栈的插入与删除操作中，不需要改变栈底指针2006.4（4）按照“后进先出”原则组织数据的数据结构是 A队列

13、 B栈 C双向链表 D二叉树 2008.4（7）下列关于栈的叙述正确的是 A栈按”先进先出”组织数据 B栈按”先进后出”组织数据 C只能在栈底插入数据 D不能删除数据2008.9（1）一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是 A）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA 2009.3（2）支持子程序调用的数据结构是 A 线 B 树 C 队列 D 二叉树2009.9（2）下列数据结果中，能够按照“先进后出”原则存取数据的是 A）循环队列 B）栈 C）队列 D）二叉

14、树2007.4（5）下列队列的叙述正确的是 。 A） 队列属于非线性表 B）队列按”先进后出”的原则组织数据 C）队列在队尾删除数据 D）队列按先进先出原则组织数据2009.3（填1）假设用一个长度为50的数组（数组元素的下标从0到49）作为栈 的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如 果bottom=49,top=30（数组下标），则栈中具有_20_个元素。栈： 49-30+12008.4（填3）设某循环队列的容量为50,头指针front=5 (指向队头元素的前一 位置),尾指针 rear=29(指向队尾元素),则该循环队列中共有 _24_个元素队列： 6

15、29之间 一共有24个 （尾指针 rear大）2008.9（2）下列叙述中正确的是（ ）。A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B）在循环队列中，只需要队头指针就能反映队的中元素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队的中元素的动态变化情况D）循环队列中元素的个数是由队头指针和队尾指针共同决定2009.9（3）对于循环队列，下列叙述中正确的是 A）队头指针是固定不变的 B）队头指针一定大于队尾指针 C）队头指针一定小于队尾指针 D）队头指针可以大于队尾指针，也可以小于队 尾指针线性表除了可以采用顺序存储结构，还可以采用链 式存储结构。采用链式存储结构的线性表称为线性 链表。链式存储结构的每个结点有两个域，一个用于存放数据， 一个用于存放指针。链式存储结构中，存储数据结构的 存储空间可以不连续，各数据结点 的存储顺序与数据元素的逻辑关系 可以不一