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

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-1A) 存储在外存中的数据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个元素依次向前移动一个位置。 平均情况下，要在顺序表中插入一个新元素，需要移动表中一半的元素。栈和队列是两种特殊的线性表，它们是运算时受到某些限制的线性表。它们都是线性数据结构。栈(stack

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

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

12、，元素个数为m个。font=3rear=8font=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）下列关于栈的叙述正确的

13、是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）二叉树2007.4（5）下列队列的叙述正确的是 。A） 队列属于非线性表 B）

14、队列按”先进后出”的原则组织数据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_个元素 队列： 629之间 一共有24个 （尾指针 rear大）2008.9（2）下列叙述中正确的

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

16、放指针。链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素的逻辑关系可以不一致，而数据之间的逻辑关系由指针域来确定的。access链式存储方式既可以用于表示线性结构（线性表），也可以用于表示非线性结构（如：树）。循环链表是一种特殊线性链表。 2005.4（5）下列对于线性链表的描述中正确的是A) 存储空间不一定是连续，且各元素的存储顺序是任意的 B) 存储空间不一定是连续，且前件元素一定存储在后件元素的前面C) 存储空间必须连续，且前件元素一定存储在后件元素的前面 D) 存储空间必须连续，且各元素的存储顺序是任意的2006.4（5）下列叙述中正确的是 A线性链表是

17、线性表的链式存储结构 B栈与队列是非线性结构 C双向链表是非线性结构 D只有根结点的二叉树是线性结构 2008.9（4）下列叙述中正确的是（）。 A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间2009.3（1）下列叙述中正确的是A 栈是“先进先出”的线性表 B 队列是“先进后出”的线性表C 循环队列是非线性结构 D 有序线性表既可以采用顺序存储结构，也可以采用链式存储结构树的基本概念 树是一种简单的非线性结构。

18、树中，所有的数据元素之间的关系具有明显的层次特征。 在树的图形表示，总认为用直线连起来的两个端点，上端是前件，下端是后件，表示前后件关系的箭头就可以省略。厦门理工学院机械系电子系商学系财务管理电子商务AFEBDG树的术语 结点：一个数据元素，ADBGEF都称为结点 父结点：每个结点只有一个前件，称为父节点。D、B的父节点是A。 树的根节点：树中，没有前件的节点只有一个，称为树的根节点，简称树的根。该树，根节点是A。 子结点：每一个节点可以有多个后件，它们都称为该结点的子结点。A的子结点是D、B. 叶子结点：没有后件的结点称为叶子结点。G、E、F是叶子结点。 结点的度：一个结点所拥有的后件个数。

19、A的度为2，D的度有为3，B的度为0. 树的度：所有结点中的最大的度称为树的度。该树的度为3. 树的层次：根结点在一层，依次递增。A为一层，DB为二层，GEF为三层。 树的深度：树的最大层次。该树的深度为3. 子树：以某个结点的一个子结点为跟构成的树称为该结点的一棵子树。A有两棵子树，分别是DGEF，B。AFEBDG什么是二叉树 二叉树也是一种非线性结构。二叉树可以采用顺序存储结构，也可以采用链式存储结构，通常情况下使用链式存储结构。 二叉树有两个特点： 非空二叉树只有一个根节点（空二叉树没有结点） 每个结点最多有两棵子树，且分别称为该结点的左子树与右子树二叉树的基本性质 性质一： 二叉树的第

20、K层上，最多有2k-1个结点第1层，最多有20个；第2层，最多有21个；第3层，最多有22个。 性质二：深度为m二叉树最多有2m-1个结点 该树的深度为3，所以二叉树最多为1+2+4个， 20+21+22，即23-1个AFEBDHG 二叉树的基本性质 性质三：在任意的二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。注：二叉树的结点，只有三种，一种是度数为0的结点，即叶子结点；一种是度数为1的结点；最后一种是度数为2的结点。所以二叉树的总节点数=N0+N1+N2 =N0+2N2+1 性质四：具有N个结点的二叉树，其深度至少为log2n+1,其中 log2n 表示取log2n的整数部

21、分。AFEBDHG 满二叉树 即每一层上都含有最大结点数。AFEBDHG423167891011121314155 完全二叉树 除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。4231678910 11125 非完全二叉树非完全二叉树4231678910 11125 完全二叉树完全二叉树二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点。 遍历需要访问根结点、左子树上的所有结点、右子树上的所有结点。在遍历时，一般先遍历左子树，然后遍历右子树。在这个原则下，根据访问根结点的次序分为三种： 1.前序遍历（DLR）：首先访问根结点，然后遍历左子树，最后遍历右子

22、树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。二叉树的遍历 2.中序遍历(LDR)：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 3.后序遍历(LRD)：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。先序遍历：先序遍历：D L R中序遍历：中序遍历：L D R后序遍历：后序遍历：L R DADBCD L RAD L RD L RBDCD L R以先序遍历以先序遍历D L RD L R为例演示遍历过程为例演示

23、遍历过程 ABDCBDAC DBCA2009.9（1）下列数据结构中，属于非线性结构的是 A）循环队列 B）带链队列 C）二叉树 D）带链栈2005.4（填1）某二叉树中度为2的结点有18个，则该二叉树中有 19 个叶子结点。2005.9（填3）一棵二叉树第六层（根结点为第一层）的结点数最多为 个。 2i-1 =252006.4（7）在深度为7的满二叉树中，叶子结点的个数为 A32 B31 C64 D63 2i-1 2007.4（7）某二叉树中有n个度为2的结点则该二叉树中的叶子结点数为 A）n+1 B ）n-1 C）2n D）n/22007.4（填1）在深度为7的满二叉树中，度为2的结点个数

24、为 _63_ 。叶子结点：27-1 =64 度为2的结点: 63个 2007.9（8）一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为_。 N0=70 n1=80 n2=69A）219B）221 C）229 D）2312008.4（填2）深度为5的满二叉树有_16_个叶子结点2009.3（3）某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是A 10 B 8 C 6 D4 2007.4（6）对下列二叉树进行前序遍历的结果为2007.9（填4）对下列二叉树进行中序遍历的结果为_ _ 。 2006.4（6）对如下二叉树进行后序遍历的结果为顺序查找 从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。 平均要与表中一半以上元素进行比较，最坏情况下需要比较较n n次次。 如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。二分