算法与数据结构68931

1、1算法考试的内容：1.1算法的基本概念1. 算法的概念（必记）:算法是指解题方案的准确而完整的描述。分析：要用计算机实现某一任务时， 先应设计出一整套解决问题的指导方案，然后具体实现。整套的指导方案称之为算法，而具体的实现称之为程序。并且在设计指导方案时，可不用过 多考虑到实现程序的具体细节 （即可以一点点的理想化），但在程序实现时，必须受到具体环 境的约束（现实不同于理想）。结论：算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。2. 算法的基本特征（必记）：a可行性：由于算法总是在某个特定的计算工具上实现并执行的，因而受到计算工具的限制，所以在设计算法时，要考虑到设计的算法

2、是否是可性的。b. 确定性：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允 许有多义性。c. 有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。d. 拥有足够的情报：算法有相应的初始数据。3算法的基本要素：一个算法通常由两个基本要素所组成：一是对数据对象的运算和操作，二是算法的控制结构。基本运算和操作分为四类：a. 算术运算：（加、减、乘、除等运算）b. 逻辑运算：（与、或、非等运算）c. 关系运算：（大于、小于、等于、不等于等运算）d. 数据传输：（赋值、输入、输出等操作）算法的控制结构： 算法中各操作之间的执行顺序称之为算法的控制结构。一个

3、算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。注意：一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。4.算法设计基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。1.2算法的复杂度 （必记）算法的复杂度 主要包括时间复杂度和空间复杂度。1. 算法的时间复杂度：是指执行算法所需要的计算工作量，是由算法所执行的基本运算次数来度量。可用平均性态和最坏情况两种分析方法。其中平均性态分析是指用各种特定输入下的基本运 算次数的加权平均值来度量算法的工作量； 而最坏情况分析是指在所有特定输入下的基本运 算次数据的最大次数。2. 算法的空间复杂度：一个算法的空间复杂度，

4、是指执行这个算法所需要的内存空间。包含有三部分所组成： 算法程序所占的空间+输入的初始数据所占的存储空间+算法执行过程中所需要的额外空间。历届的考题：1、算法具有五个特性，以下选项中不属于算法特性的是（B） 2005.4A）有穷性B）简洁性C）可行性D）确定性2005.42、 问题处理方案的正确而完整的描述称为_算法_3、 下列叙述中正确的是 _D。 2006.9A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间可复杂度必定小D）上述三种说法都不对4、 算法复杂度主要包括时间复杂度和空间复杂度。2006.91.

5、2数据结构与算法考试的内容：数据结构作为计算机的一门学科，主要研究以下三个方面的问题 ：a. 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；b. 在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；c. 对各种数据结构进行的运算。注意：讨论以上问题 主要目的是为了提高数据处理的效率。提高效率包括两个方面： 一是提 高数据处理的速度，二是节省在数据处理过程中所占用的计算机存储空间。2.1什么是数据结构简单地说，数据结构是指相互有关联的数据元素的集合。而数据元素之间的关联通常是指其前后件关系（即先后顺序关系），如春、夏、秋、冬之间的先后顺序关系。因此，一个数据结构应

6、包含以下两方面的信息：a.表示数据元素的信息；b.表示各数据元素之间的前后件关系。1 数据的逻辑结构所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。注意：这种逻辑关系仅指元素之间的固有的一个先后顺序关系，而与它们在计算机中的存储顺序无关。2 数据的存储结构数据的存储结构的概念：数据的逻辑结构在计算机存储空间中的存放形式（也称数据的物理结构）。a、 数据元素在计算机中存储空间中的位置关系可以与它们的逻辑关系相同，也可以不相同。b、数据的存储结构有顺序、链接、索引等。c、数据元素采用不同的存储结构，其数据处理的效率是不同的。2.2数据结构的图形表示一般用一个中间标有元素值的方框表示一个

7、数据元素，用一条有向线段从前件结点指向后件结点。l父亲丨;儿子I 女儿I IIm- h-在数据结构中，没有前件的结点成为根结点（如上图中的春与父亲）；没有后件的结点称为终端结点（也称为叶子结点，如上图中的冬与儿子和女儿）。注意：在进行处理时，一个数据结构中的元素结点可能是在动态变化的。这种变化可能是元素结点的个数发生变化，也可以是元素结点的先后顺序发生变化。2.3线性结构与非线性结构空的数据结构是：一个数据元素都没有的数据结构。根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分为二大类：线性结构和非线性结构。一个非空的数据结构满足下列两个条件，则为线性结构，线性结构又称为线性表。

8、a. 有且只有一个根结点；b.每一个结点最多有一个前件，也最多有一个后件。在上图中，左边的是线性结构，而右边的是非线性结构。注意：线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟属于线性结构还是属于非线性结构， 要根据具体情况来确定。 如果对该数据结构的运算是按线性结构的规 则来处理的，则属于线性结构；否则属于非线性结构。历届的考题：1数据的存储结构是指(D_)2005.4A) 存储在外存中的数据B)数据所占的存储空间量C)数据在计算机中的顺序存储方式D)数据的逻辑结构中计算机中的表示2、下列叙述中正确的是 (_D_)2005.9A) 一个逻辑数据结构只能有一种存储结构B) 数据

9、的逻辑结构属于线性结构，存储结构属于非线性结构C) 一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D) 一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率1.3线性表及其顺序存储结构考试的内容：3.1线性表的基本概念非空线性表的结构特征如下：a. 有且只有一个根结点，它无前件；b.有且只有一个终端结点，它无后件；c.除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。H-W 夏 fl 秋 f| 冬；线性表中结点的个数 n称为线性表的长度。当n=0时，称为空表。3.2线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点：a.

10、线性表中所有元素所占的存储空间是连续的；b. 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。注意：在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定在后件元素的前面。在线性表的顺序存储结构中，如第一个元素的地址为ADR(a1)，每个元素占用的存储空间大小为k个字节，则线性表中第i个元素的存储地址为：ADR(a1)+(i-1)*k。1存傑地址11内存状态11111! ADM&1)al占l小字节1ADR(SI)+ ka2占k午宇节11:V:1:1j ADR3 +=1）个结点。b. 深度为m的二叉树最多有2m-l个结点。深度为m的二叉树是指二叉树共有 m层。c.

11、在任意一棵二叉树中，度为0的结点（即叶子结点）总是比深度为2的结点多一个。d. 具有n个结点的二叉树，其深度至少为Iog2n+1，其中Iog2n表示取log2n的整数部分。树的傑度対4,最塞有21=16-1=L5个; 点度为0的结点有8个,度为2的结点有13满二叉树与完全二叉树满二叉树与完全二叉树是两种特殊形态的二叉树。a. 满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。b. 完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右

12、边 的若干结点。注意：满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。完全二叉树还具有以下性质：完全二叉树！滿二叉树！非滿二冥树6.3二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。6.4二叉树的遍历：(重要)在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中 序遍历、后序遍历。a. 前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树。A、 第四层中，最多有24=23=8个结点。B、树的深度为4,最多有24-1=16-仁15个结点。C、度为0的结点有8个，度为2的结点有7个。完全二叉树满二叉树非满二叉树b. 中序遍历：首先遍历左子树，然后访问根

13、结点，最后遍历右子树。c. 后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点。F|FnW： FVADBEGHP中序；ACRDFEHGP后序* ABIXHPGFF注意：在树结构中，每一个结点都代表一棵子树。前序遍历中一定以根结点开头，后序遍历一定以根结点结尾，而中序遍历中，根结点前面的为树的左子树，而其后面的为树的右子树。历届的考题：1、 在深度为7的满二叉树中，叶子结点的个数为(C )2006.4A) 32 B)31 C)64 D)632、对下图1所示二叉树进行中序遍历的结果是A Q 2006.9A)ACBDFEG B)ACBDFGE C)ABDCGEF D)FCADBEG3、 对如下

14、图2所示二叉树，进行后序遍历的结果为(D )2006.4A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA4、 某二叉树中，度为2的结点有18个，则该二叉树中有_个叶子结点。2005.45、 一棵二叉树第六层(根结点为第一层)的结点数最多为_32个。2005.91.7查找技术注意的考点：7.1顺序查找：顺序查找的方法是：用被查元素与线性表中的元素逐一比较，直到找出相等的元素，则查找成功；或者找遍所有元素都不相等，则查找失败。顺序查找的优点：对线性表的元素的逻辑次序无要求(不必对元素进行排序)，对线性表的 存储结构无要求(顺序存储、链接存储皆可)。顺序查找的效率很低，但在以下

15、情况下，只能采用顺序查找：a. 如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。b. 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。7.2二分法查找：二分法查找是一种效率较高的线性表查找方法。要进行二分法查找，则线性表结点必须是排好序的，且线性表以顺序方式存储。二分法查找的方法：首先用要查找的元素值与线性表中间位置的元素值相比较，这个中间结点把线性表分成了两个子表，比较相等则查找完成，不等则根据比较结果确定下一步的查找 应在哪一个子表中进行，如此进行下去，直到找到满足条件的结点，或者确定表中没有这样 的结点。对于二分法查找的缺点是线性表排序需花费时间，顺

16、序方式存储的插入、删除不便。注意：对于长度为n的有序线性表，在最坏的情况下，二分查找只需要比较比较log2n次,而顺序查找需要比较n次。二分查找的效率要比顺序查找高得多。历届的考题：1、 在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为()2006.9A)63 B)64 C)6 D)72、 下列数据结构中，能用二分法进行查找的是()2005.9A)顺序存储的有序线性表B)线性链表C)二叉链表D)有序线性链表3、 对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为()2005.4A)log 2n B) n/2 C) n D) n+11.8排序技术(记住每种排序的比较

17、次数)注意的考点：排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。8.1交换类排序法交换类排序的基本思想：两两比较待排序线性表的元素值，并对不满足顺序要求的元素进行位 置交换，直到全部满足为止.1、冒泡排序法将相邻的元素进行两两比较，若为逆序则进行交换。将线性表照此方法从头到尾处理一遍称作一趟起泡，一趟起泡的效果是将元素值最大的记录交换到了最后的位置，即该线性表的最终位置。若某一趟起泡过程中没有发生任何交换，则排序过程结束。在最坏情况下，需要的比较 N(N-1)/2次。2、快速排序法快速排序又称分区交换排序，是对冒泡排序的一种改进。其基本方法是：在待排序线性表中 任取一个元素，以它为

18、基准用交换的方法将所有的元素分成两部分，元素值比它小的在一个部分，元素值比它大的在另一个部分。再分别对两个部分实施上述过程，一直重复到排序完成。在最坏的情况下与冒泡排序相当，然而快速排序的平均执行时间为o(nl og2n)。8.2插入类排序法插入排序的基本思想是：每步将一个待排序元素按其元素值的大小插入到前面已排序的元素 中的适当位置上，直到全部记录插入完为止。1、简单插入排序它是指将无序序列中的各元素依次插入到已经有序的线性表中。在最坏情况下比较需要 N(N-1)/2次。2、希尔排序法希尔排序的基本思想是把元素按下标的一定增量分组，对每组元素使用插入排序，随增量的逐渐减小，所分成的组包含的记

19、录越来越多，到增量的值减小到1时，整个数据合成一组，构成一组有序元素，故其属于插入排序方法。在最坏情况下需要的比较 O( ni.5)次。8.3选择类排序法选择排序的基本思想是：每次从待排序的元素中选出元素值最小(或最大)的记录，顺序放在已排序的记录序列的最后，直到全部排完。1、简单选择排序对线性表进行n-1趟扫描，第i趟扫描从剩下的n-i+1个记录中选出元素值最小的记录，与 第i个记录交换。最坏情况下需要比较N(N-1)/2次。2、堆排序堆排序的基本思想是： 对待排序的线性表，首先把它们按堆的定义排成一个序列(称为建堆)，这就找到了最小的元素，然后将最小的元素取出，用剩下的元素再建堆，便得到次

20、最小的的元素，如此反复进行，直到将全部元素排好序为止。在最坏怀况下需要比较 o(n Iog2n)次。8.4总结假设线性表的长度为n,在最坏的情况下进行比较的次数：d J 莎诙赢込卫更墜竺竺!J3 简用瑞只秤序出11(11-1)/2 -U.希尔排序法:0(n15)、堆排序法:O(ftlog2n)L-2. 匪排存羅:n6?:III历届的考题：1对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（_）2005.4A）冒泡排序为n/2 B ）冒泡排序为n C ）快速排序为n D ）快速排序为n（n-1）/22、对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为 。20

21、06.4总复习图：定义；是指解题方案的准确而完整的描述特征：是可行性、确定性*有穷性和拥有足够复杂度：包括时间复杂度和空间复杂度数据的逻辑结构数据的存储结构数据的运算线性结构非线性结构顺序存储；栈与队列链式存储：链表、双向 链表、带链的栈、带链 的队列链式存储顺序存储排序：交换类、插入类和选禅类査找：顺序査找、二分査找插入与删除1.9精典模拟题一选择题1. 算法的时间复杂度是指 _c。A. 执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数D.算法程序中的指令条数2. 算法的空间复杂度是指 _D_。A.算法程序的长度B.算法程序中的指令条数C.算法程序所占的存储空

22、间D.算法执行过程中所需要的存储空间3下面叙述正确的是_C_。A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令（或语句）的条数C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对4在计算机中，算法是指 _C_。A.查询方法 B.加工方法C.解题方案的准确而完整的描述D.排序方法5算法一般都可以用哪几种控制结构组合而成_D。A.循环、分支、递归 B.顺序、循环、嵌套C.循环、递归、选择D顺序、选择、循环6算法分析的目的是 。（D）A.找出数据结构的合理性B.找出算法中输入和输出之间的关系C.分析算法的易懂性和可靠性D.分析算法的效率以求

23、改进7. 下列列关于算法的叙述中，正确的是_D_。A.算法是解决问题的实现程序B.算法是解决问题的计算方法C. 程序的实现可以优于算法的设计D. 算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。&下列叙述中正确的是A 。A）线性表是线性结构B）栈与队列是非线性结构C）线性链表是非线性结构D） 二叉树是线性结构9.数据的存储结构是指 B。A）数据所占的存储空间量B）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式D）存储在外存中的数据10 .下列关于队列的叙述中正确的是_C。A）在队列中只能插入数据B）在队列中只能删除数据C）队列是先进先出的线性表D）队列是先进后出的线性表

24、11 .下列关于栈的叙述中正确的是D_。A）在栈中只能插入数据B）在栈中只能删除数据C）栈是先进先出的线性表D）栈是先进后出的线性表12. 以下数据结构中不属于线性数据结构的是 C_。A.队列B.线性表C.二叉树D.栈13. 数据的存储结构是指 B。A.数据所占的存储空间量B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式D.存储在外存中的数据14. 栈和队列的共同点是D_。A.都是先进后出 B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点15. 用链表表示线性表的优点是_C_。A.便于插入和删除操作B.数据元素的物理顺序与逻辑顺序相同C.花费的存储空间较顺序存储

25、少D.便于随机存取16. 链表不具有的特点是 D_。A ）不必事先估计存储空间B）可随机访问任一元素C）插入删除不需要移动元素D ）所需空间与线性表长度成正比17. 如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是 CA） e3,e1,e4,e2 B） e2,e4,e3,e1 C） e3,e4,e1,e2 D）任意顺序18 .设有下列二叉树：对此二叉树中序遍历的结果为 _B。A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA19 .在深度为5的满二叉树中，叶子结点的个数为 B。A)32 B)31 C)16 D)1520. 设树T的度为4，其中度为1，2，3，4的结点

26、个数分别为4 , 2，1，1。贝U T树中叶子结点数为。A)8 B)7 C)6 D)521. 在一棵二叉树上第5层的结点数最多是 C。A. 8 B. 16 C. 32 D. 1522. 设一棵完全二叉树共有 699个结点，则在该二叉树中的叶子结点数为 。A. 349 B. 350 C. 255 D. 35123. 在深度为5的满二叉树中，结点的个数为 B_。A. 32 B. 31 C. 16 D. 1524. 已知二叉树后序遍历序列是 dabec,中序遍历序列是debac,它的前序遍历序列是 A. cedba B. acbed C. decab D. deabc25. 已知二叉树前序遍历序列

27、deabc，是后序遍历序列是 dabec,中序遍历序列是 。A) debac B) decab C) deabc D) cedba26. 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH 和DBGEACHF，则该二叉树的后序遍历为。A) GEDHFBCA B ) DGEBHFCA C ) ABCDEFGH D ) ACBFEDHG27. 树是结点的集合，它的根结点数目是 。A)有且只有1 B) 1或多于1 C) 0或1 D)至少228. 线性表若米用链式存储结构时，要求内存中可用存储单兀的地址。A)必须是连续的 B)部分地址必须是连续的C) 一定是不连续的D)连续不连续都可以29. 下列叙述中，错误的是 。A) 数据的存储结构与数据处理的效率密切相关B) 数据的存储结构与数据处理的效率无关C) 数据