第一章算法与数据结构.doc

1算法考试的内容：1.1 算法的基本概念1算法的概念(必记)：算法是指解题方案的准确而完整的描述。分析：要用计算机实现某一任务时，先应设计出一整套解决问题的指导方案，然后具体实现。整套的指导方案称之为算法，而具体的实现称之为程序。并且在设计指导方案时，可不用过多考虑到实现程序的具体细节(即可以一点点的理想化)，但在程序实现时，必须受到具体环境的约束(现实不同于理想)。结论：算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。2算法的基本特征(必记)：a.可行性：由于算法总是在某个特定的计算工具上实现并执行的，因而受到计算工具的限制，所以在设计算法时，要考虑到设计的算法是否是可性的。b.确定性：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。c.有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。d.拥有足够的情报：算法有相应的初始数据。3算法的基本要素：一个算法通常由两个基本要素所组成：一是对数据对象的运算和操作，二是算法的控制结构。基本运算和操作分为四类：a. 算术运算: (加、减、乘、除等运算)b. 逻辑运算: (与、或、非等运算)c. 关系运算: (大于、小于、等于、不等于等运算)d. 数据传输: (赋值、输入、输出等操作)算法的控制结构：算法中各操作之间的执行顺序称之为算法的控制结构。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。注意：一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。4算法设计基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。1.2 算法的复杂度 (必记)算法的复杂度主要包括时间复杂度和空间复杂度。1算法的时间复杂度：是指执行算法所需要的计算工作量，是由算法所执行的基本运算次数来度量。可_用平均性态和最坏情况两种分析方法。其中平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量；而最坏情况分析是指在所有特定输入下的基本运算次数据的最大次数。2算法的空间复杂度：一个算法的空间复杂度，是指执行这个算法所需要的内存空间。包含有三部分所组成：算法程序所占的空间+输入的初始数据所占的存储空间+算法执行过程中所需要的额外空间。历届的考题：1、算法具有五个特性，以下选项中不属于算法特性的是(_) 2005.4A)有穷性 B)简洁性 C)可行性 D)确定性2、问题处理方案的正确而完整的描述称为_。 2005.43、下列叙述中正确的是_。2006.9A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间可复杂度必定小D）上述三种说法都不对4、算法复杂度主要包括时间复杂度和_复杂度。2006.91.2数据结构与算法考试的内容：数据结构作为计算机的一门学科，主要研究以下三个方面的问题：a数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；b在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；c对各种数据结构进行的运算。注意：讨论以上问题主要目的是为了提高数据处理的效率。提高效率包括两个方面：一是提高数据处理的速度，二是节省在数据处理过程中所占用的计算机存储空间。2.1 什么是数据结构简单地说，数据结构是指相互有关联的数据元素的集合。 而数据元素之间的关联通常是指其前后件关系(即先后顺序关系)，如春、夏、秋、冬之间的先后顺序关系。因此，一个数据结构应包含以下两方面的信息：a.表示数据元素的信息； b.表示各数据元素之间的前后件关系。1数据的逻辑结构所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。注意：这种逻辑关系仅指元素之间的固有的一个先后顺序关系，而与它们在计算机中的存储顺序无关。2数据的存储结构数据的存储结构的概念：数据的逻辑结构在计算机存储空间中的存放形式 (也称数据的物理结构)。注意：a、数据元素在计算机中存储空间中的位置关系可以与它们的逻辑关系相同，也可以不相同。b、数据的存储结构有顺序、链接、索引等。c、数据元素采用不同的存储结构，其数据处理的效率是不同的。2.2 数据结构的图形表示一般用一个中间标有元素值的方框表示一个数据元素，用一条有向线段从前件结点指向后件结点。在数据结构中，没有前件的结点成为根结点(如上图中的春与父亲)；没有后件的结点称为终端结点 (也称为叶子结点，如上图中的冬与儿子和女儿)。注意：在进行处理时，一个数据结构中的元素结点可能是在动态变化的。这种变化可能是元素结点的个数发生变化，也可以是元素结点的先后顺序发生变化。2.3 线性结构与非线性结构空的数据结构是：一个数据元素都没有的数据结构。根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分为二大类：线性结构和非线性结构。一个非空的数据结构满足下列两个条件，则为线性结构，线性结构又称为线性表。a. 有且只有一个根结点； b.每一个结点最多有一个前件，也最多有一个后件。在上图中，左边的是线性结构，而右边的是非线性结构。注意：线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟属于线性结构还是属于非线性结构，要根据具体情况来确定。如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。历届的考题：1、数据的存储结构是指(_)2005.4A)存储在外存中的数据 B)数据所占的存储空间量C)数据在计算机中的顺序存储方式 D)数据的逻辑结构中计算机中的表示2、下列叙述中正确的是(_)2005.9A)一个逻辑数据结构只能有一种存储结构B)数据的逻辑结构属于线性结构，存储结构属于非线性结构C)一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D)一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率1.3线性表及其顺序存储结构考试的内容：3.1 线性表的基本概念非空线性表的结构特征如下：a.有且只有一个根结点，它无前件； b.有且只有一个终端结点，它无后件； c.除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数 n 称为线性表的长度。当n=0 时，称为空表。3.2 线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点：a.线性表中所有元素所占的存储空间是连续的；b.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。注意：在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定在后件元素的前面。在线性表的顺序存储结构中，如第一个元素的地址为ADR(a1)，每个元素占用的存储空间大小为k 个字节，则线性表中第i个元素的存储地址为：ADR(a1)+(i-1)*k。3.3 顺序表的插入运算在线性表的顺序存储结构中，当插入元素时，插入点后的元素都要向后移动一位，以让出一个存储空间。在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的。3.4 顺序表的删除运算在线性表的顺序存储结构中，当删除元素时，删除点后的元素都要向前移动一位，以保证元素都是相邻存储的。在平均情况下，要在线性表中删除一个元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要删除一个元素，其效率是很低的。1.4栈和队列注意的考点：4.1 栈及其基本运算1什么是栈栈是一种特殊的线性表。栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈按照先进后出 (FILO)或后进先出 (LIFO)组织数据，栈具有记忆作用。用top 表示栈顶位置，用botton表示栈底。2栈的顺序存储及其运算栈的基本运算有三种：.入栈运算、退栈运算和.读栈顶元素。4.2 队列及其基本运算1什么是队列队列是允许在一端进行插入、而在另一端进行删除的特殊的线性表。允许插入的一端称为队尾，允许删除的一端称为排头(或队头)。队列又称为先进先出(FIFO)或后进后出(LILO)的线性表，它体现了先来先服务的原则。往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。2循环队列及其运算所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。队列空和队列满的条件如下：队列空的条件为 s=0 ;队列满的条件为 s=1 且front=rear.循环队列主要有两种基本运算：入队运算和退队运算。a.入队运算：在循环队列的队尾加入一个新元素，首先将队尾指针进一(即rear=rear+1)，并当rear=m+1 时置rear=1；然后将新元素插入到队尾指针指向的位置。注意：当循环队列非空 (s=1)且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算，这种情况称为上溢。b.退队运算：指在循环队列的排头位置退出一个元素并赋给指定的变量。首先将排头指针进一(即front=front+1)，并当front=m+1 时置front=1;然后将排头指针指向的元素赋给指定的变量。注意：当循环队列为空 (s=0)时，不能进行退队运算，这种情况称为下溢 。历届的考题：1、下列关于栈的描述中错误的是(_)2005.4A）栈是先进后出的线性表 B）栈只能顺序存储C）栈具有记忆作用 D）对栈的插入与删除操作中，不需要改变栈底指针2、按照后进先出原则组织数据的数据结构是(_)2006.4A)队列 B)栈 C)双向链表 D)二叉树3、列关于栈的描述正确的是(_)2005.9A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素4、数据结构分为逻辑结构和存储结构，循环队列属于_结构。2005.95、按“先进后出”原则组织数据的数据结构是_。2006.91.5线性链表注意的考点：5.1 线性链表的基本概念1.链式存储在顺序存储方式中所有的数据元素在内存中是相邻存放的，从而造成了在插入与删除数据元素时，需要大量移动相应的数据元素。为了解决这种问题，可以将每个数据元素存储在内存中不相邻的不同位置，并利用上一个数据元素在存有数据的同时，也存放下一个数据元素所在的位置地址(称为一个存储单元，即结点)，以便查找。这就是链式存储方式。在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放地址，称为指针域。其中指针用于指向该结点的前一个或后一个结点 (即前件或后件)。注意：a、在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。b、链式存储方式既可以用于表示线性结构，也可以用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。2线性链表线性表的链式存储结构称为线性链表。 如果结点中有两个指针，一个用于指向前一个结点，而另一上用于指向后一个结点，则称之为双向链表。3带链的栈：栈的链式存储结构称为带链的栈。4带链的队列：队列的链式存储结构称为带链的队列。5.2 线性链表的基本运算 ：查找、插入、删除。历届的考题：1、下列对于线性链表的描述中正确的是(_)2005.4A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的2、下列叙述中正确的是(_)2006.4A)线性链表是线性表的链式存储结构 B)栈与队列是非线性结构C)双向链表是非线性结构 D)只有根结点的二叉树是线性结构3、数据结构分为线性结构和非线性结构，带链的队列属于_。2006.91.6树与二叉树注意的考点：6.1 树的基本概念树是一种简单的非线性结构，所有元素之间具有明显的层次特性。a.在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简_称为树的根。b.在树结构中，一个结点所拥有的后件个数称为该结点的度；在树中，所有结点中的最大的度称为树的度。c.树具有明显的层次关系，即树是一种层次结构。d.数的最大层次称为树的深度。f.在树中，叶子结点没有子树。6.2 二叉树及其基本性质1什么是二叉树：二叉树是一种很有用的非线性结构。二叉树具有以下两个特点：a.非空二叉树只有一个根结点；b.每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。由以上特点可以看出，在二叉树中，每一个结点的度最大为2。2二叉树的基本性质：(重要)a.在二叉树的第k 层上，最多有2k-1(k=1)个结点。b.深度为m的二叉树最多有2m-1 个结点。深度为m的二叉树是指二叉树共有m层。c.在任意一棵二叉树中，度为0 的结点(即叶子结点)总是比深度为2 的结点多一个。d.具有n 个结点的二叉树，其深度至少为log2n+1，其中log2n表示取log2n的整数部分。3满二叉树与完全二叉树满二叉树与完全二叉树是两种特殊形态的二叉树。a.满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k 层上有2k-1 个结点，且深度为m的满二叉树有2m-1 个结点。b.完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。注意：满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。完全二叉树还具有以下_性质：a.具有n 个结点的完全二叉树的深度为log2n +1。6.3 二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。6.4 二叉树的遍历：(重要)在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。a.前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树。A、 第四层中，最多有24-1=23=8 个结点。B、 树的深度为4，最多有24-1=16-1=15 个结点。C、 度为0 的结点有8 个，度为2 的结点有7个。完全二叉树 满二叉树 非满二叉树b.中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。c.后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点。注意：在树结构中，每一个结点都代表一棵子树。前序遍历中一定以根结点开头，后序遍历一定以根结点结尾，而中序遍历中，根结点前面的为树的左子树，而其后面的为树的右子树。历届的考题：1、在深度为7 的满二叉树中，叶子结点的个数为()2006.4A)32 B)31 C)64 D)632、对下图1 所示二叉树进行中序遍历的结果是_。2006.9A)ACBDFEG B)ACBDFGE C)ABDCGEF D)FCADBEG3、对如下图2 所示二叉树，进行后序遍历的结果为()2006.4A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA4、某二叉树中，度为2 的结点有18 个，则该二叉树中有_个叶子结点。2005.45、一棵二叉树第六层（根结点为第一层）的结点数最多为_个。2005.91.7查找技术注意的考点：7.1 顺序查找：顺序查找的方法是：用被查元素与线性表中的元素逐一比较，直到找出相等的元素，则查找成功；或者找遍所有元素都不相等，则查找失败。顺序查找的优点：对线性表的元素的逻辑次序无要求（不必对元素进行排序），对线性表的存储结构无要求(顺序存储、链接存储皆可)。顺序查找的效率很低，但在以下情况下，只能采用顺序查找：a.如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。b.即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。7.2 二分法查找：二分法查找是一种效率较高的线性表查找方法。要进行二分法查找，则线性表结点必须是排好序的，且线性表以顺序方式存储。二分法查找的方法：首先用要查找的元素值与线性表中间位置的元素值相比较，这个中间结点把线性表分成了两个子表，比较相等则查找完成，不等则根据比较结果确定下一步的查找应在哪一个子表中进行，如此进行下去，直到找到满足条件的结点，或者确定表中没有这样的结点。对于二分法查找的缺点是线性表排序需花费时间，顺序方式存储的插入、删除不便。注意：对于长度为 n的有序线性表，在最坏的情况下，二分查找只需要比较比较log2n 次，而顺序查找需要比较n 次。二分查找的效率要比顺序查找高得多。历届的考题：1、在长度为64 的有序线性表中进行顺序查找，最坏情况下需要比较的次数为(_)2006.9A)63 B)64 C)6 D)72、下列数据结构中，能用二分法进行查找的是(_)2005.9A)顺序存储的有序线性表 B)线性链表C)二叉链表 D)有序线性链表3、对长度为n 的线性表进行顺序查找，在最坏情况下所需要的比较次数为(_)2005.4A)log2n B) n/2 C) n D) n+11.8排序技术(记住每种排序的比较次数)注意的考点：排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。8.1 交换类排序法交换类排序的基本思想:两两比较待排序线性表的元素值,并对不满足顺序要求的元素进行位置交换,直到全部满足为止.1、冒泡排序法将相邻的元素进行两两比较，若为逆序则进行交换。将线性表照此方法从头到尾处理一遍称作一趟起泡，一趟起泡的效果是将元素值最大的记录交换到了最后的位置，即该线性表的最终位置。若某一趟起泡过程中没有发生任何交换，则排序过程结束。在最坏情况下，需要的比较N(N-1)/2 次。2、快速排序法快速排序又称分区交换排序，是对冒泡排序的一种改进。其基本方法是：在待排序线性表中任取一个元素，以它为基准用交换的方法将所有的元素分成两部分，元素值比它小的在一个部分，元素值比它大的在另一个部分。再分别对两个部分实施上述过程，一直重复到排序完成。在最坏的情况下与冒泡排序相当，然而快速排序的平均执行时间为O(nlog2n)。8.2 插入类排序法插入排序的基本思想是：每步将一个待排序元素按其元素值的大小插入到前面已排序的元素中的适当位置上，直到全部记录插入完为止。1、简单插入排序它是指将无序序列中的各元素依次插入到已经有序的线性表中。在最坏情况下比较需要N(N-1)/2 次。2、希尔排序法希尔排序的基本思想是把元素按下标的一定增量分组，对每组元素使用插入排序，随增量的逐渐减小，所分成的组包含的记录越来越多，到增量的值减小到1 时，整个数据合成一组，构成一组有序元素，故其属于插入排序方法。在最坏情况下需要的比较O(n1.5)次。8.3 选择类排序法选择排序的基本思想是：每次从待排序的元素中选出元素值最小（或最大）的记录，顺序放在已排序的记录序列的最后，直到全部排完。1、简单选择排序对线性表进行n-1 趟扫描，第i 趟扫描从剩下的n-i+1 个记录中选出元素值最小的记录，与第i个记录交换。最坏情况下需要比较N(N-1)/2 次。2、堆排序堆排序的基本思想是：对待排序的线性表，首先_把它们按堆的定义排成一个序列（称为建堆），这就找到了最小的元素，然后将最小的元素取出，用剩下的元素再建堆，便得到次最小的的元素，如此反复进行，直到将全部元素排好序为止。在最坏怀况下需要比较O(nlog2n)次。8.4 总结假设线性表的长度为n，在最坏的情况下进行比较的次数：历届的考题：1、对于长度为n 的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是(_)2005.4A）冒泡排序为n/2 B）冒泡排序为n C）快速排序为n D）快速排序为n(n-1)/22、对长度为10 的线性表进行冒泡排序，最坏情况下需要比较的次数为_。2006.4总复习图：1.9精典模拟题一选择题1.算法的时间复杂度是指_。A.执行算法程序所需要的时间 B.算法程序的长度C.算法执行过程中所需要的基本运算次数 D.算法程序中的指令条数2.算法的空间复杂度是指_。A.算法程序的长度 B.算法程序中的指令条数C.算法程序所占的存储空间 D.算法执行过程中所需要的存储空间3.下面叙述正确的是_。A.算法的执行效率与数据的存储结构无关B.算法的空间复杂度是指算法程序中指令（或语句）的条数C.算法的有穷性是指算法必须能在执行有限个步骤之后终止D.以上三种描述都不对4.在计算机中，算法是指_。A. 查询方法 B. 加工方法C. 解题方案的准确而完整的描述 D. 排序方法5.算法一般都可以用哪几种控制结构组合而成_。A. 循环、分支、递归 B. 顺序、循环、嵌套C. 循环、递归、选择 D. 顺序、选择、循环6.算法分析的目的是_。(D)A. 找出数据结构的合理性 B. 找出算法中输入和输出之间的关系C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改进7.下列列关于算法的叙述中，正确的是_。A. 算法是解决问题的实现程序 B. 算法是解决问题的计算方法C. 程序的实现可以优于算法的设计D. 算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。8下列叙述中正确的是_。A)线性表是线性结构 B)栈与队列是非线性结构C)线性链表是非线性结构 D)二叉树是线性结构9. 数据的存储结构是指_。A)数据所占的存储空间量 B)数据的逻辑结构在计算机中的表示C)数据在计算机中的顺序存储方式 D)存储在外存中的数据10下列关于队列的叙述中正确的是_。A)在队列中只能插入数据 B)在队列中只能删除数据C)队列是先进先出的线性表 D)队列是先进后出的线性表11下列关于栈的叙述中正确的是_。A)在栈中只能插入数据 B)在栈中只能删除数据C)栈是先进先出的线性表 D)栈是先进后出的线性表12. 以下数据结构中不属于线性数据结构的是_。A. 队列 B. 线性表 C. 二叉树 D. 栈13. 数据的存储结构是指_。A. 数据所占的存储空间量 B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式 D. 存储在外存中的数据14. 栈和队列的共同点是_。A. 都是先进后出 B. 都是先进先出C. 只允许在端点处插入和删除元素 D. 没有共同点15. 用链表表示线性表的优点是_。A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同C. 花费的存储空间较顺序存储少 D. 便于随机存取16.链表不具有的特点是_。A）不必事先估计存储空间 B）可随机访问任一元素C）插入删除不需要移动元素 D）所需空间与线性表长度成正比17.如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是_。A）e3,e1,e4,e2 B）e2,e4,e3,e1 C）e3,e4,e1,e2 D）任意顺序18设有下列二叉树：对此二叉树中序遍历的结果为_。A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA19在深度为5 的满二叉树中，叶子结点的个数为_。A)32 B)31 C)16 D)1520.设树T 的度为4，其中度为1，2，3，4 的结点个数分别为4，2，1，1。则 T 树中叶子结点数为_。A)8 B)7 C)6 D)521. 在一棵二叉树上第5 层的结点数最多是_。A. 8 B. 16 C. 32 D. 1522. 设一棵完全二叉树共有699 个结点，则在该二叉树中的叶子结点数为_。A. 349 B. 350 C. 255 D. 35123. 在深度为5 的满二叉树中，结点的个数为_。A. 32 B. 31 C. 16 D. 1524. 已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。A. cedba B. acbed C. decab D. deabc25.已知二叉树前序遍历序列deabc，是后序遍历序列是dabec，中序遍历序列是 _。A）debac B）decab C）deabc D）cedba26.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH 和DBGEACHF，则该二叉树的后序遍历