1、第一章 绪论n考纲要求考纲要求 考纲中没有这一章考纲中没有这一章n 考纲分析考纲分析 建议考生复习时复习这一章，因为把握这一章有建议考生复习时复习这一章，因为把握这一章有助于对整个课程知识的理解。本章主要掌握助于对整个课程知识的理解。本章主要掌握DS和算和算法的基本概念，其出题形式主要为选择题。关于法的基本概念，其出题形式主要为选择题。关于DS的深刻理解有可能出小分值的综合应用题。由于分值的深刻理解有可能出小分值的综合应用题。由于分值有限，算法时间复杂度的分析一般不会以综合应用题有限，算法时间复杂度的分析一般不会以综合应用题的形式单独出题，通常会结合算法设计题来分析，由的形式单独出题，通常会结
2、合算法设计题来分析，由于于DS课程要求掌握初步的算法分析技术，因此，算课程要求掌握初步的算法分析技术，因此，算法分析题不会太难。法分析题不会太难。n基本知识点：基本知识点：数据结构和算法的概念数据结构和算法的概念n重点：重点：数据结构的定义、逻辑结构、存储结数据结构的定义、逻辑结构、存储结构和数据运算三方面的概念及相互关系构和数据运算三方面的概念及相互关系n难点：难点：分析算法的时间复杂度分析算法的时间复杂度第一章第一章 绪论绪论DS的基本概念n考核知识点考核知识点1.数据：是信息的载体。数据：是信息的载体。2.数据元素（也称为结点）：是表示数据的基本单位，数据元素（也称为结点）：是表示数据的
3、基本单位，在计算机程序中通常作为一个整体进行考虑和处理。在计算机程序中通常作为一个整体进行考虑和处理。3.数据项：是构成数据元素的不可分割的最小单位。数据项：是构成数据元素的不可分割的最小单位。4.数据对象：是具有相同性质的数据元素的集合，是数据对象：是具有相同性质的数据元素的集合，是数据的子集。（在不产生混淆的情况下，将数据对数据的子集。（在不产生混淆的情况下，将数据对象简称为数据）。象简称为数据）。5.数据结构数据结构()DataStructure=(D,R)，其中，其中D是数据元素的集合，是数据元素的集合，R是是D上关系的集合。按照视上关系的集合。按照视点的不同，数据结构分为逻辑结构和存
4、储结构（物点的不同，数据结构分为逻辑结构和存储结构（物理结构）。理结构）。DS的基本概念n考核知识点考核知识点6.数据的逻辑结构数据的逻辑结构() 是指数据元素之间逻辑关系的整体。根据数据是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系的不同，数据结构分为四类：元素之间逻辑关系的不同，数据结构分为四类： 1) 集合：数据元素之间就是集合：数据元素之间就是“属于同一个集合属于同一个集合”，除此之外，无任何关系；除此之外，无任何关系； 2) 线性结构：一对一；线性结构：一对一； 3) 树结构：一对多的层次关系；树结构：一对多的层次关系； 4) 图结构：多对多的任意关系。图结构：多对多的任意
5、关系。树和图结构也称为非线性结构。树和图结构也称为非线性结构。DS的基本概念n考核知识点考核知识点7. 数据的存储结构数据的存储结构() 又称为物理结构，是数据及其逻辑结构在计算又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：机中的表示。通常有两种存储结构：顺序存储结构顺序存储结构和和链接存储结构链接存储结构。 顺序存储结构的基本思想是：用一组连续的存顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示；系由元素的存储位置来表示； 链接存储结构的基本思想是：用一组任意的存
6、链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。指针来表示。 存储结构除了存储数据元素之外，还必须存储存储结构除了存储数据元素之外，还必须存储数据元素之间的逻辑关系。数据元素之间的逻辑关系。DS的基本概念n考核知识点考核知识点8.抽象数据类型抽象数据类型ADT() 抽象数据类型是一个数据结构以及定义抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。它提供了使在该结构上的一组操作的总称。它提供了使用和实现两个不同的视图，实现了封装和信用和实现两个不同的视图，实现了封装和信息隐藏。息隐藏。典型题
7、解析n1. 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承（如子女可以继承父亲或母亲的遗产；子女间不能相互继承（如图），则表示该遗产继承关系的最合适的图），则表示该遗产继承关系的最合适的DS应该是（应该是（ ）。）。 A. 树树 B. 图图 C. 线性表线性表 D. 集合集合解答：解答： B 丈夫妻子子女1子女n。典型题解析n2. 计算机所处理的数据一般具有某种内在联系，计算机所处理的数据一般具有某种内在联系，这是指（这是指（ ）。）。 A. 数据和数据之间存在某种联系数据和数据之间存在某
8、种联系 B. 元素和元素之间存在某种联系元素和元素之间存在某种联系 C. 元素内部具有某种结构元素内部具有某种结构 D. 数据项和数据项之间存在某种联系数据项和数据项之间存在某种联系解答：解答： B分析：分析： 数据结构是指相互之间存在一定关系的数据元数据结构是指相互之间存在一定关系的数据元 素的集合，数据元素是讨论数据结构时涉及的最小数素的集合，数据元素是讨论数据结构时涉及的最小数据单位，元素内部各数据项一般不予考虑。据单位，元素内部各数据项一般不予考虑。典型题解析n3. 在链接存储结构中，要求（在链接存储结构中，要求（ ）。）。 A. 每个结点占用一片连续的存储区域每个结点占用一片连续的存
9、储区域 B. 所有结点占用一片连续的存储区域所有结点占用一片连续的存储区域 C. 结点的最后一个域是指针类型结点的最后一个域是指针类型 D. 每个结点有多少个后继就设有多少个指针每个结点有多少个后继就设有多少个指针解答：解答： A分析：分析： 结点作为存取操作的独立单位，需要占用结点作为存取操作的独立单位，需要占用连续的存储区域，但不要求结点中各组成部分连续的存储区域，但不要求结点中各组成部分（域）的顺序。（域）的顺序。典型题解析n4. 下列说法中不正确的是（下列说法中不正确的是（ ）。）。 A. 数据元素是数据的基本单位数据元素是数据的基本单位 B. 数据项是数据中不可分割的最小单位数据项是
10、数据中不可分割的最小单位 C. 数据可由若干个数据项构成数据可由若干个数据项构成 D. 数据元素可由若干个数据项构成数据元素可由若干个数据项构成解答：解答： C分析：分析： 数据是由若干个数据元素构成，数据元素数据是由若干个数据元素构成，数据元素是由若干个数据项构成。是由若干个数据项构成。典型题解析n5. 可以用（可以用（ ）、数据关系和基本操作）、数据关系和基本操作定义一个完整的抽象数据类型。定义一个完整的抽象数据类型。 A. 数据元素数据元素 B. 数据对象数据对象 C. 原子类型原子类型 D. 存储结构存储结构解答：解答： B分析：分析： ADT的三要素为：数据对象、数据关系、的三要素为
11、：数据对象、数据关系、基本操作。基本操作。典型题解析（应用题）n1. 试描述数据结构和抽象数据类型的概念与程序设试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。计语言中数据类型概念的区别。 解答：解答： 数据结构是指相互之间存在一定关系的数据元数据结构是指相互之间存在一定关系的数据元素的集合，抽象数据类型是指一个数据结构以及定义在素的集合，抽象数据类型是指一个数据结构以及定义在该结构上的一个操作，程序设计语言中的数据类型是一该结构上的一个操作，程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。个值的集合和定义在这个值集上一组操作的总称。 抽象数据类型
12、可以看成是对数据类型的一种抽象。抽象数据类型可以看成是对数据类型的一种抽象。在高级程序设计语言中，基本数据类型隐含着数据结构在高级程序设计语言中，基本数据类型隐含着数据结构和定义在该结构上的操作的统一。例如和定义在该结构上的操作的统一。例如C+中的整型中的整型就是整数的数学含义与算术运算的统一体，只是由于这就是整数的数学含义与算术运算的统一体，只是由于这些基本数据类型中的数据结构的具体表示、基本操作和些基本数据类型中的数据结构的具体表示、基本操作和具体实现都很规范，可以通过系统内置而隐藏起来。具体实现都很规范，可以通过系统内置而隐藏起来。典型题解析（应用题）n2. 说明数据的逻辑结构和存储结构
13、之间的关说明数据的逻辑结构和存储结构之间的关系。系。 解答：解答： 数据的逻辑结构和存储结构是密切相关数据的逻辑结构和存储结构是密切相关的两个方面。数据的逻辑结构的两个方面。数据的逻辑结构属于用户视图，是属于用户视图，是面向问题的面向问题的，反映了数据内部的构成方式。数据，反映了数据内部的构成方式。数据的存储结构属于的存储结构属于具体实现的视图，是面向计算机具体实现的视图，是面向计算机的，的，其基本目标是将数据及其逻辑关系存储到计其基本目标是将数据及其逻辑关系存储到计算机的内存中。一般来说，一种数据的逻辑结构算机的内存中。一般来说，一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储可
14、以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。结构，其数据处理的效率往往是不同的。典型题解析（应用题）n3. 抽象数据类型的主要特点是什么？数据类型和抽象数据类型的关系如何？抽象数据类型的主要特点是什么？数据类型和抽象数据类型的关系如何？使用抽象数据类型的主要好处是什么？使用抽象数据类型的主要好处是什么？ 解答：解答：抽象数据类型是指一个数据结构及定义在该结构上的一组操作。抽象数抽象数据类型是指一个数据结构及定义在该结构上的一组操作。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表
15、示和实现无关。无论其内部结构如何变化，只要它的逻辑特性不变就不影响它的外部使用。关。无论其内部结构如何变化，只要它的逻辑特性不变就不影响它的外部使用。 数据类型是高级语言中的一个概念，它是一个值的集合和一组操作的集合，数据类型是高级语言中的一个概念，它是一个值的集合和一组操作的集合，如如C语言中的整型、实型和字符型等。实际上数据类型是厂家已经实现了的数语言中的整型、实型和字符型等。实际上数据类型是厂家已经实现了的数据结构。抽象数据类型可以理解为对数据类型的进一步抽象，抽象数据类型不据结构。抽象数据类型可以理解为对数据类型的进一步抽象，抽象数据类型不局限于机器已定义和实现的数据类型，还包括用户在
16、设计软件系统时自定义的局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自定义的数据类型。数据类型。 抽象数据类型是提供了使用和实现两个不同的视图，实现了封装和信息隐抽象数据类型是提供了使用和实现两个不同的视图，实现了封装和信息隐藏。抽象数据类型的定义部分只包含数据的逻辑特性和基本操作的集合，一方藏。抽象数据类型的定义部分只包含数据的逻辑特性和基本操作的集合，一方面，使用者依据这些定义来使用抽象数据类型，即通过操作集合对该抽象数据面，使用者依据这些定义来使用抽象数据类型，即通过操作集合对该抽象数据类型进行各种处理；另一方面，抽象数据类型的实现者依据这些定义来完成该类型进行各种处理；另
17、一方面，抽象数据类型的实现者依据这些定义来完成该抽象数据类型的具体实现，包括存储结构的设计和基本操作的实现。抽象数据类型的具体实现，包括存储结构的设计和基本操作的实现。算法和算法分析n考核知识点考核知识点1. 算法的定义（算法的定义（） 说明：说明：通常一个问题可以有多种算法，一个给定算法解决通常一个问题可以有多种算法，一个给定算法解决 一个特定的问题。一个特定的问题。2. 算法的特性（算法的特性（） 输入、输出、有穷性、确定性、可行性输入、输出、有穷性、确定性、可行性3. 算法的描述方法（算法的描述方法（） 常用的描述算法的方法有自然语言、流程图、程序设计语常用的描述算法的方法有自然语言、流
18、程图、程序设计语言和伪代码等，其中伪代码被称为算法语言，是比较合适言和伪代码等，其中伪代码被称为算法语言，是比较合适的描述算法的方法。的描述算法的方法。 说明：说明：伪代码的书写形式没有严格的规定，只是要求了解伪代码的书写形式没有严格的规定，只是要求了解任何一种现代程序设计语言的人都能够很好的理解。任何一种现代程序设计语言的人都能够很好的理解。算法和算法分析n考核知识点考核知识点4. 算法的时间复杂度（算法的时间复杂度（） 算法的渐近时间复杂度（简称时间复杂度）考察当算法的渐近时间复杂度（简称时间复杂度）考察当问题规模充分大时，算法中基本语句的执行次数在问题规模充分大时，算法中基本语句的执行次
19、数在渐近意义上的阶，通常用大渐近意义上的阶，通常用大O记号表示。问题规模是记号表示。问题规模是指输入量的多少。基本语句是执行次数与整个算法指输入量的多少。基本语句是执行次数与整个算法的执行次数成正比的语句。的执行次数成正比的语句。 常用的算法时间复杂度由小到大依次为：常用的算法时间复杂度由小到大依次为：c log2n n nlog2n n2 n3 2n 3n n! 说明：说明：撇开与计算机软硬件有关的因素，影响算法时间撇开与计算机软硬件有关的因素，影响算法时间代价的最主要因素是问题规模。代价的最主要因素是问题规模。算法和算法分析n考核知识点考核知识点5. 算法的空间复杂度（算法的空间复杂度（）
20、 算法的空间复杂度是指在算法的执行过程算法的空间复杂度是指在算法的执行过程中需要的辅助空间数量。辅助空间是除算法本中需要的辅助空间数量。辅助空间是除算法本身和输入输出数据所占据的空间之外，算法在身和输入输出数据所占据的空间之外，算法在运行过程中临时开辟的存储空间。运行过程中临时开辟的存储空间。 算法的空间复杂度表示为：算法的空间复杂度表示为： S(n)=O(g(n) 表示随着问题规模表示随着问题规模 n 的增大，算法运行所需存的增大，算法运行所需存储量的增长率与函数储量的增长率与函数g(n)的增长率相同。的增长率相同。算法和算法分析典型题解析选择题：选择题： 主要考察算法的基本概念，要求深刻理
21、解算法、主要考察算法的基本概念，要求深刻理解算法、算法的特性、算法与程序的关系，掌握算法时算法的特性、算法与程序的关系，掌握算法时间性能的度量方法、基本语句执行次数的计算、间性能的度量方法、基本语句执行次数的计算、时间复杂度的分析等有关内容。时间复杂度的分析等有关内容。算法和算法分析典型题解析选择题选择题1： 下面（下面（ ）不是算法应具备的特性。）不是算法应具备的特性。 A. 有穷性有穷性 B. 确切性确切性 C. 高效性高效性 D. 可行性可行性 解答：解答： C分析：分析： 高效性是好算法应具备的特性。高效性是好算法应具备的特性。算法和算法分析典型题解析选择题选择题2： 算法必须具备输入
22、、输出和（算法必须具备输入、输出和（ ）等特性。）等特性。 A. 可行性、可移植性和可扩充性可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性可行性、确定性和有穷性 C. 确定性、稳定性和有穷性确定性、稳定性和有穷性 D. 易读性、稳定性和健壮性易读性、稳定性和健壮性 解答：解答： B分析：可移植性、可扩充性、易读性、稳定性和分析：可移植性、可扩充性、易读性、稳定性和健壮性都是好算法应该具备的特性。健壮性都是好算法应该具备的特性。 算法和算法分析典型题解析选择题选择题3： 当输入非法错误时，一个当输入非法错误时，一个“好好”的算法会进行适当处的算法会进行适当处理，而不会产生难以理解的输出
23、结果，这称为算法的理，而不会产生难以理解的输出结果，这称为算法的（ ）。）。 A. 可读性可读性 B. 健壮性健壮性 C. 正确性正确性 D. 有穷性有穷性解答：解答： B分析：健壮性也称分析：健壮性也称鲁棒性鲁棒性，是指算法对非法输入的抵抗能，是指算法对非法输入的抵抗能力，即对于错误的输入，算法应能识别并做出处理，力，即对于错误的输入，算法应能识别并做出处理，而不是产生错误动作或陷入瘫痪。而不是产生错误动作或陷入瘫痪。 算法和算法分析典型题解析选择题选择题4： 算法分析的目的是（算法分析的目的是（ ），算法分析的两个主要方面是（），算法分析的两个主要方面是（ ）。）。 A. 找出数据结构的合
24、理性找出数据结构的合理性 B. 研究算法中输入和输出的关系研究算法中输入和输出的关系 C. 分析算法的效率以求改进分析算法的效率以求改进 D. 分析算法的易读性和文档性分析算法的易读性和文档性 E. 空间性能和时间性能空间性能和时间性能 F. 正确性和简明性正确性和简明性 G. 可读性和文档性可读性和文档性 H. 数据复杂性和程序复杂性数据复杂性和程序复杂性解答：解答： C E分析：数据结构的合理性需要从多方面进行权衡；算法中输入和输分析：数据结构的合理性需要从多方面进行权衡；算法中输入和输出的关系是由问题本身决定的，一般和算法无关。出的关系是由问题本身决定的，一般和算法无关。 算法和算法分析
25、典型题解析选择题选择题5： 算法的时间复杂度与（算法的时间复杂度与（ ）有关。）有关。 A. 问题规模问题规模 B. 待处理数据的初态待处理数据的初态 C. 算法的易读性算法的易读性 D. A和和B解答：解答： D分析：有时算法本身比较复杂但是时间性能较好，例如快分析：有时算法本身比较复杂但是时间性能较好，例如快速排序算法比较复杂，但快速排序是目前在平均情况速排序算法比较复杂，但快速排序是目前在平均情况下最快的排序方法；算法的时间复杂度不仅取决于问下最快的排序方法；算法的时间复杂度不仅取决于问题规模，还与处理数据的初态有关，例如对题规模，还与处理数据的初态有关，例如对n个元素个元素组成的序列进
26、行排序，如果初始排列不同则排序的时组成的序列进行排序，如果初始排列不同则排序的时间性能有很大的差别。间性能有很大的差别。 算法和算法分析典型题解析选择题选择题6： 某算法的时间复杂度是某算法的时间复杂度是O(n2)，表明该算法（，表明该算法（ ）。）。 A. 问题规模是问题规模是n2 B. 执行时间等于执行时间等于n2 C. 执行时间与执行时间与n2成正比成正比 D. 问题规模与问题规模与n2成正比成正比解答：解答： C分析：算法的时间复杂度是分析：算法的时间复杂度是O(n2)，问题规模可能是，问题规模可能是n（例如对（例如对n个元素进行排序），也可能是个元素进行排序），也可能是n2（例如对（
27、例如对n*n的方阵进行转置），也有其他可能，因此，从时的方阵进行转置），也有其他可能，因此，从时间复杂度不能确定问题规模；算法的时间复杂度是间复杂度不能确定问题规模；算法的时间复杂度是O(n2)表明算法的执行时间表明算法的执行时间T(n)=c*n2 (C为常数为常数).算法和算法分析典型题解析选择题选择题7： 下面说法错误的是（下面说法错误的是（ ）。）。 1) 算法原地工作的含义是指不需要任何额外的辅助空间算法原地工作的含义是指不需要任何额外的辅助空间 2) 在相同的规模在相同的规模n下，复杂度下，复杂度O(n)的算法在时间上总是优于复杂度的算法在时间上总是优于复杂度O(2n)的的算法算法
28、3) 所谓的时间复杂度是指最坏情况下，估算算法执行时间的一个上界所谓的时间复杂度是指最坏情况下，估算算法执行时间的一个上界 4) 同一个算法，实现语言的级别越高，执行效率就越低同一个算法，实现语言的级别越高，执行效率就越低 A. 1) B. 1),2) C. 1),4) D. 3)解答：解答： B分析：算法原地（也称就地）工作是指算法的空间复杂度为分析：算法原地（也称就地）工作是指算法的空间复杂度为O(1)，例如直接插，例如直接插入排序算法需要一个用于交换的临时单元；说法入排序算法需要一个用于交换的临时单元；说法2)考虑在时间上的性能，考虑在时间上的性能，此时需要考虑两个复杂度的系数，例如复杂
29、度为此时需要考虑两个复杂度的系数，例如复杂度为O(n)的算法其系数为的算法其系数为100,算法复杂度为算法复杂度为O(2n)的算法的系数为的算法的系数为1，这两个函数曲线就有一个交叉点，这两个函数曲线就有一个交叉点，如果仅就时间复杂度而言，复杂度如果仅就时间复杂度而言，复杂度O(n)的算法优于复杂度为的算法优于复杂度为O(2n)的算法；的算法；时间复杂度需要考虑最坏情况下，算法执行时间的一个上界；说法时间复杂度需要考虑最坏情况下，算法执行时间的一个上界；说法4)中中“实现语言的级别实现语言的级别”指的是机器语言、汇编语言和高级语言。指的是机器语言、汇编语言和高级语言。算法和算法分析典型题解析选
30、择题选择题8： 设某算法完成对设某算法完成对n个元素进行处理，所需的时个元素进行处理，所需的时间是间是T(n)=100nlog2n+200n+500，则该算，则该算法的时间复杂度是法的时间复杂度是 A. O(1) B. O(n) C. O(nlog2n) D. O(nlog2n+n) 解答：解答： C分析：算法的时间复杂度可以忽略所有低次幂和分析：算法的时间复杂度可以忽略所有低次幂和最高次幂的系数。最高次幂的系数。算法和算法分析典型题解析选择题选择题9： 假设时间复杂度为假设时间复杂度为O(n2)的算法在有的算法在有200个元个元素的数组上运行需要素的数组上运行需要3.1ms，则在有，则在有4
31、00个元个元素的数组上运行需要（素的数组上运行需要（ ）ms? A. 3.1 B. 6.2 C. 12.4 D. 9.61解答：解答： C分析：运行时间为：分析：运行时间为： 3.1*(400/200)2=12.4ms。算法和算法分析典型题解析选择题选择题10： 下列程序段加下划线的语句执行（下列程序段加下划线的语句执行（ ）次）次? for (m=0,i=1; i=n; i+) for (j=1; j=2*i; j+) m=m+1; A. n2 B. 3n C. n(n+1) D. n3解答：解答： C分 析 ： 外 层 循 环 执 行分 析 ： 外 层 循 环 执 行 n 次 ， 内 层
32、循 环 执 行次 ， 内 层 循 环 执 行2,4,6,2n次，共执行次，共执行(2+4+6+2n)= n(n+1) 次。次。如何估算算法的时间复杂度如何估算算法的时间复杂度n算法主要由程序的算法主要由程序的控制结构控制结构（顺序，分支，（顺序，分支，循环）和循环）和原操作原操作（必须的操作）构成，算（必须的操作）构成，算法的时间主要取决于两者。法的时间主要取决于两者。n算法控制结构算法控制结构 原操作原操作 固有数据类型的操作固有数据类型的操作如何估算算法的时间复杂度如何估算算法的时间复杂度n算法的执行时间算法的执行时间 原操作原操作(i)的执行次数的执行次数原操作原操作(i)的执行时间的执
33、行时间n算法的执行时间算法的执行时间 和和 原操作执行次数之原操作执行次数之和和成正比成正比n具体而言：从算法中选取一种对于所研究具体而言：从算法中选取一种对于所研究的问题来说是的问题来说是基本操作基本操作的原操作，以该基的原操作，以该基本操作本操作在算法中重复执行的次数在算法中重复执行的次数作为算法作为算法运行时间的衡量准则。运行时间的衡量准则。 或者说算法中基本操作重复执行的或者说算法中基本操作重复执行的次数是问题规模次数是问题规模n的某个函数的某个函数f(n)语句的频度语句的频度（Frequency Count )+x; s=0;时间复杂度时间复杂度 for(j=1;j=n;+j)+x;
34、s+=x;语句的频度（语句的频度（Frequency Count ): 重复执行的次数。重复执行的次数。此算法中的语句的频度为此算法中的语句的频度为1，时间复杂度为，时间复杂度为O(1)。为常量阶为常量阶语句的频度语句的频度为为n，时间复杂度为，时间复杂度为O(n)。为线性阶为线性阶时间复杂度时间复杂度for(j=1;j=n;+j)for(k=1;k=n;+k) +x;s+=x;语句频度语句频度为为n n，时间复杂度为，时间复杂度为O(n2)。为平方阶为平方阶时间复杂度for(j=1;j=n;+j)for(k=1;k=j;+k)+x;s+=x;语句频度：语句频度：njjknnnn11221)
35、1(21.3211为近似于为近似于n2，所以时间复杂度仍为，所以时间复杂度仍为O(n2)。时间复杂度只考虑量级就可以了。时间复杂度只考虑量级就可以了。时间复杂度s=0;for(j=1;j=n;j*=2)for(k=1;k=n;+k)s+;语句频度为：语句频度为：nnnnjnjnk2log1 log11log122 时间复杂度为：时间复杂度为：O(nlog2n) x 表示不小于表示不小于x的最的最小整数，即向上取整，小整数，即向上取整，如如 6.1 =7算法和算法分析典型题解析应用题应用题1： 已知如下程序段：已知如下程序段： FOR i:=n downto 1 do 语句语句1 BEGIN x
36、:=x+1; 语句语句2 FOR j:=n downto i do 语句语句3 y:=y+1; 语句语句4 END;语句语句1执行的频度为：执行的频度为：n+1语句语句2执行的频度为：执行的频度为：n语句语句3执行的频度为：执行的频度为： 2+3+4+(n+1)=n*(2+n+1)/2=n(3+n)/2语句语句4执行的频度为：执行的频度为：1+2+3+n=n(n+1)/2算法和算法分析典型题解析应用题应用题2： 分析以下各程序段，并用大分析以下各程序段，并用大O记号表示其执行记号表示其执行时间。时间。1) i=1;k=0; while(in-1) k=k+10*i); i+; 基本语句是基本语
37、句是k=k+10*i；共执行了；共执行了n-2次，所以次，所以T(n)=O(n)算法和算法分析典型题解析应用题应用题2： 分析以下各程序段，并用大分析以下各程序段，并用大O记号表示其执行记号表示其执行时间。时间。2) i=1;k=0; do k=k+10*i); i+; while(i=n)基本语句是基本语句是k=k+10*i；共执行了；共执行了n次，所以次，所以T(n)=O(n)算法和算法分析典型题解析应用题应用题2： 分析以下各程序段，并用大分析以下各程序段，并用大O记号表示其执行记号表示其执行时间。时间。3) i=1;j=0; while(i+jj) j+; else i+; 分析条件语
38、句，每循环一次，分析条件语句，每循环一次，i+j整体加整体加1，共循环，共循环n次，次，所以所以T(n)=O(n)算法和算法分析典型题解析应用题应用题2： 分析以下各程序段，并用大分析以下各程序段，并用大O记号表示其执行记号表示其执行时间。时间。4) y=0; while(y+1)*(y+1)=n) y=y+1; 设循环体共执行了设循环体共执行了T(n)次，每循环一次，次，每循环一次，循环变量循环变量y加加1，最终，最终T(n) =y，即即(T(n)+1)2=n所以：所以：T(n)=O(n1/2)算法和算法分析典型题解析应用题应用题2： 分析以下各程序段，并用大分析以下各程序段，并用大O记号表
39、示其执行时间。记号表示其执行时间。5) for (i=1; i=n; i+) for (j=1; j=i; j+) for (k=1; k=j; k+) x+;x+是基本语句，所以是基本语句，所以)()(2)(1(61)1(*.5*44*33*22*1 (21).21 (.) 321 ()21 (1)()(31113nOnnnnnnnOnTniijjk频度）算法和算法分析典型题解析应用题应用题2： 分析以下各程序段，并用大分析以下各程序段，并用大O记号表示其执行记号表示其执行时间。时间。6) for (i=0; in; i+) for (j=0; jm; j+) aij=0;aij=0是基本语
40、句，执行了是基本语句，执行了m*n次，次，所以所以T(m,n)=O(m*n)算法和算法分析典型题解析应用题应用题3： 分析以下算法的时间复杂度。分析以下算法的时间复杂度。void func(int n) int i=0,s=0; while(sn) i+; s=s+i; 解答：对于解答：对于while语句，设执行的次数为语句，设执行的次数为m，i从从0开始递增开始递增1，直到，直到m-1为止，为止，有：有：s=0+1+2+m-1=m(m-1)/2,并满足：并满足：s=m(m-1)/2n，则有，则有 ，所以，所以，该算法的时间复杂度为：该算法的时间复杂度为： )( nOnm 算法和算法分析典型题
41、解析应用题应用题4： 设设n是偶数，试计算运行下列程序段后是偶数，试计算运行下列程序段后m的值并给出该程序段的值并给出该程序段的时间复杂度。的时间复杂度。 int m=0,i,j; for (i=1; i=n; i+) for (j=2*i; j=n; j+) m+;)(4222*) 12(1)(2, n2i, ni*2,222121212nOnninninnTniimninininij为：，所以，该语句的频度的最大值满足：即由于内循环从为解答：算法的基本操作算法和算法分析典型题解析应用题应用题5： 分析以下算法的时间复杂度。分析以下算法的时间复杂度。void func(int n) int
42、i=1,k=100; while(in) k+; i+=2; 解答：设解答：设while循环语句执行的次数为循环语句执行的次数为m，i从从1开始每次递增开始每次递增2，最后取值为，最后取值为1+2m，有：有： i=1+2mn,即即m(n-1)/2=O(n)所以，该算法的时间复杂度为：所以，该算法的时间复杂度为：O(n) 算法和算法分析典型题解析应用题应用题6： 下面程序段中带下划线的语句的执行次数的下面程序段中带下划线的语句的执行次数的数量级是（数量级是（ ）。）。 i=1；WHILE(in) DO i=i*2; 解答：解答：log2n算法和算法分析典型题解析应用题应用题7： 下面程序段中带下
43、划线的语句的执行次数的数量级是下面程序段中带下划线的语句的执行次数的数量级是（ ）。）。 i=1； WHILE (in) BEGIN FOR j=1 TO n DO X:=X+1; i=i*2; END; 解答：解答：nlog2n算法和算法分析典型题解析应用题应用题8： 下面程序段中带下划线的语句的执行次数的下面程序段中带下划线的语句的执行次数的数量级是（数量级是（ ）。）。 i=n*n； WHILE(i1) DO i=i div 2; 解答：解答：log2(n2)算法和算法分析典型题解析应用题应用题9： 计算机执行下面的语句时，语句计算机执行下面的语句时，语句s的执行次数的执行次数为（为（
44、）。）。 for (i=1; i=i; j-) s; 21212)3)(2(3.) 2() 1() 1(1niinjninnnnnin算法和算法分析典型题解析应用题应用题10： 在有在有n个选手参加的单循环赛中，总共进行个选手参加的单循环赛中，总共进行（ ）场比赛？）场比赛？n解答：因为每个人都要和其他解答：因为每个人都要和其他n-1个人进行个人进行一次比赛，所以是一次比赛，所以是n*(n-1)，但甲和乙比赛，但甲和乙比赛和乙和甲比赛是相同的，所以要去掉，所以和乙和甲比赛是相同的，所以要去掉，所以总共进行总共进行n*(n-1)/2场比赛。场比赛。算法和算法分析典型题解析应用题应用题11： 有实
45、现同一功能的两个算法有实现同一功能的两个算法A1和和A2，其中，其中A1的时间的时间复杂度为复杂度为T1=O(2n)，A2的时间复杂度为的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析哪一个算法好。仅就时间复杂度而言，请具体分析哪一个算法好。解答：比较两个复杂度函数解答：比较两个复杂度函数2n和和n2，显然有：，显然有： 当当n=1时，时，2112,则算法则算法A2好于算法好于算法A1； 当当n=2时，时，22=22,当当n=4时，时，24=42 ，则两个算法的，则两个算法的时间复杂度相同；时间复杂度相同； 当当n=3时，时，234时，时，2nn2,则算法则算法A2好于算法好于算
46、法A1. 算法和算法分析典型题解析应用题应用题12： 度量一个算法的执行时间通常有几种方法？各有何优度量一个算法的执行时间通常有几种方法？各有何优缺点？缺点？解答：通常有两种方法：事后统计和事前分析。解答：通常有两种方法：事后统计和事前分析。 事后统计方法的优点是比较精确，缺点是必须根事后统计方法的优点是比较精确，缺点是必须根据算法编写相应的程序，而且所得的时间依赖于计算据算法编写相应的程序，而且所得的时间依赖于计算机的软硬件环境，有时候容易掩盖算法本身的优劣。机的软硬件环境，有时候容易掩盖算法本身的优劣。 事前分析方法的优点是不必运行程序就可以从复事前分析方法的优点是不必运行程序就可以从复杂
47、度角度比较算法的优劣，缺点是不够精确，当一个杂度角度比较算法的优劣，缺点是不够精确，当一个算法比另一个算法稍好一些时不易判断。算法比另一个算法稍好一些时不易判断。 挑战题解析n综合应用题：主要考查难度较大的算法时间综合应用题：主要考查难度较大的算法时间性能分析、有关深层次理解性能分析、有关深层次理解DS的综合问题。的综合问题。Hanoi塔算法塔算法void Hanoi( int n, char x, char y, char z ) if( n = 1 ) move( x, 1, z );/ 把把1号盘，从号盘，从x移到移到zelse Hanoi( n 1, x, z, y );/ 把把n-1
48、个盘，从个盘，从x移到移到y，z为为辅助塔辅助塔move( x, n, z );/ 把把n号盘，从号盘，从x移到移到zHanoi( n 1, y, x, z );/把把n-1个盘，从个盘，从y移到移到z，x为辅为辅助塔助塔 n综合应用题综合应用题1：分析：分析Hanoi问题的算法时间复杂度。问题的算法时间复杂度。挑战题解析n综合应用题综合应用题1：分析：分析Hanoi问题的算法时间复杂度。问题的算法时间复杂度。关系为：算法时间复杂度的递归塔问题的算法可以得到由HanoiT(n)=1 n=12T(n-1)+1 n1)2(12212*21122.22)1(2.122)3(212)1)3(2(212
49、)2(21)1)2(2(21)1(2)(123212322nnnnnnOTnTnTnTnTnTnTT(n)=1 n=12T(n-1)+1 n1所以，时间复杂度为所以，时间复杂度为O(2n)挑战题解析n综合应用题综合应用题2：设：设n是偶数，且有程序段：是偶数，且有程序段： for(i=1;i=n;i+) if(2*i=n) for(j=2*i;jn/2时时不再执行。故总的执行次数是：不再执行。故总的执行次数是：(n-1)+(n-3)+(n-5)+3+1=n2/4挑战题解析n综合应用题综合应用题3：运算是：运算是DS的一个重要方面。举例说明两个的一个重要方面。举例说明两个DS的的逻辑结构和存储方
50、式完全相同，只是对于运算的定义不同，因而逻辑结构和存储方式完全相同，只是对于运算的定义不同，因而具有不同的特性，则这两个具有不同的特性，则这两个DS是不同的。是不同的。解答：解答：例如堆栈和队列都是线性结构，都可以采用顺序存储和例如堆栈和队列都是线性结构，都可以采用顺序存储和链式存储，由于对插入和删除操作的定义不同，栈规定在表的链式存储，由于对插入和删除操作的定义不同，栈规定在表的一端进行插入和删除操作，队列规定在表的一端进行插入在另一端进行插入和删除操作，队列规定在表的一端进行插入在另一端进行删除操作，导致了栈的后进先出，队列的先进先出特一端进行删除操作，导致了栈的后进先出，队列的先进先出特
