《DS第一章绪论》PPT课件.ppt

《《DS第一章绪论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《DS第一章绪论》PPT课件.ppt（63页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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()抽象数据类型是一个数据结构以及定义抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。它提供了使在该结构上的一组操作的总称。它提供了使用和实现两个不同的视图，实现了封装和信用和实现两个不同的视图，实现了封装和信息隐藏。息隐藏。典型题解析n1.假设有如

7、下遗产继承规则：丈夫和妻子可以相互继承遗产；假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承（如图）子女可以继承父亲或母亲的遗产；子女间不能相互继承（如图），则表示该遗产继承关系的最合适的，则表示该遗产继承关系的最合适的DS应该是（应该是（）。）。A.树树 B.图图 C.线性表线性表 D.集合集合解答：解答：B 丈夫妻子子女1子女n。典型题解析n2.计算机所处理的数据一般具有某种内在联系，这计算机所处理的数据一般具有某种内在联系，这是指（是指（）。）。A.数据和数据之间存在某种联系数据和数据之间存在某种联系 B.元素和元素之间存在某种联系元素

8、和元素之间存在某种联系 C.元素内部具有某种结构元素内部具有某种结构 D.数据项和数据项之间存在某种联系数据项和数据项之间存在某种联系解答：解答：B分析：分析：数据结构是指相互之间存在一定关系的数据元数据结构是指相互之间存在一定关系的数据元 素的集合，数据元素是讨论数据结构时涉及的最小数素的集合，数据元素是讨论数据结构时涉及的最小数据单位，元素内部各数据项一般不予考虑。据单位，元素内部各数据项一般不予考虑。典型题解析n3.在链接存储结构中，要求（在链接存储结构中，要求（）。）。A.每个结点占用一片连续的存储区域每个结点占用一片连续的存储区域 B.所有结点占用一片连续的存储区域所有结点占用一片连

9、续的存储区域 C.结点的最后一个域是指针类型结点的最后一个域是指针类型 D.每个结点有多少个后继就设有多少个指针每个结点有多少个后继就设有多少个指针解答：解答：A分析：分析：结点作为存取操作的独立单位，需要占用结点作为存取操作的独立单位，需要占用连续的存储区域，但不要求结点中各组成部分连续的存储区域，但不要求结点中各组成部分（域）的顺序。（域）的顺序。典型题解析n4.下列说法中不正确的是（下列说法中不正确的是（）。）。A.数据元素是数据的基本单位数据元素是数据的基本单位 B.数据项是数据中不可分割的最小单位数据项是数据中不可分割的最小单位 C.数据可由若干个数据项构成数据可由若干个数据项构成

10、D.数据元素可由若干个数据项构成数据元素可由若干个数据项构成解答：解答：C分析：分析：数据是由若干个数据元素构成，数据元素数据是由若干个数据元素构成，数据元素是由若干个数据项构成。是由若干个数据项构成。典型题解析n5.可以用（可以用（）、数据关系和基本操作定）、数据关系和基本操作定义一个完整的抽象数据类型。义一个完整的抽象数据类型。A.数据元素数据元素 B.数据对象数据对象 C.原子类型原子类型 D.存储结构存储结构解答：解答：B分析：分析：ADT的三要素为：数据对象、数据关系、的三要素为：数据对象、数据关系、基本操作。基本操作。典型题解析（应用题）n1.试描述数据结构和抽象数据类型的概念与程

11、序设计试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。语言中数据类型概念的区别。解答：解答：数据结构是指相互之间存在一定关系的数据元数据结构是指相互之间存在一定关系的数据元素的集合，抽象数据类型是指一个数据结构以及定义在素的集合，抽象数据类型是指一个数据结构以及定义在该结构上的一个操作，程序设计语言中的数据类型是一该结构上的一个操作，程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。个值的集合和定义在这个值集上一组操作的总称。抽象数据类型可以看成是对数据类型的一种抽象。在高抽象数据类型可以看成是对数据类型的一种抽象。在高级程序设计语言中，基本数据类型

12、隐含着数据结构和定级程序设计语言中，基本数据类型隐含着数据结构和定义在该结构上的操作的统一。例如义在该结构上的操作的统一。例如C+中的整型就是中的整型就是整数的数学含义与算术运算的统一体，只是由于这些基整数的数学含义与算术运算的统一体，只是由于这些基本数据类型中的数据结构的具体表示、基本操作和具体本数据类型中的数据结构的具体表示、基本操作和具体实现都很规范，可以通过系统内置而隐藏起来。实现都很规范，可以通过系统内置而隐藏起来。典型题解析（应用题）n2.说明数据的逻辑结构和存储结构之间的关系。说明数据的逻辑结构和存储结构之间的关系。解答：解答：数据的逻辑结构和存储结构是密切相关数据的逻辑结构和存

13、储结构是密切相关的两个方面。数据的逻辑结构的两个方面。数据的逻辑结构属于用户视图，是属于用户视图，是面向问题的面向问题的，反映了数据内部的构成方式。数据，反映了数据内部的构成方式。数据的存储结构属于的存储结构属于具体实现的视图，是面向计算机具体实现的视图，是面向计算机的，的，其基本目标是将数据及其逻辑关系存储到计其基本目标是将数据及其逻辑关系存储到计算机的内存中。一般来说，一种数据的逻辑结构算机的内存中。一般来说，一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。结构，其数据处理的效率往往是不同的。典型题解

14、析（应用题）n3.抽象数据类型的主要特点是什么？数据类型和抽象数据类型抽象数据类型的主要特点是什么？数据类型和抽象数据类型的关系如何？使用抽象数据类型的主要好处是什么？的关系如何？使用抽象数据类型的主要好处是什么？解答：解答：抽象数据类型是指一个数据结构及定义在该结构上的一组操抽象数据类型是指一个数据结构及定义在该结构上的一组操作。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算作。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它机内部如何表示和实现无关。无论其内部结构如何变化，只要它的逻辑特性不变就不影响它的外部使用。的逻辑特性

15、不变就不影响它的外部使用。数据类型是高级语言中的一个概念，它是一个值的集合和一数据类型是高级语言中的一个概念，它是一个值的集合和一组操作的集合，如组操作的集合，如C语言中的整型、实型和字符型等。实际上数据语言中的整型、实型和字符型等。实际上数据类型是厂家已经实现了的数据结构。抽象数据类型可以理解为对类型是厂家已经实现了的数据结构。抽象数据类型可以理解为对数据类型的进一步抽象，抽象数据类型不局限于机器已定义和实数据类型的进一步抽象，抽象数据类型不局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自定义的数据类型。现的数据类型，还包括用户在设计软件系统时自定义的数据类型。抽象数据类型是提

16、供了使用和实现两个不同的视图，实现了抽象数据类型是提供了使用和实现两个不同的视图，实现了封装和信息隐藏。抽象数据类型的定义部分只包含数据的逻辑特封装和信息隐藏。抽象数据类型的定义部分只包含数据的逻辑特性和基本操作的集合，一方面，使用者依据这些定义来使用抽象性和基本操作的集合，一方面，使用者依据这些定义来使用抽象数据类型，即通过操作集合对该抽象数据类型进行各种处理；另数据类型，即通过操作集合对该抽象数据类型进行各种处理；另一方面，抽象数据类型的实现者依据这些定义来完成该抽象数据一方面，抽象数据类型的实现者依据这些定义来完成该抽象数据类型的具体实现，包括存储结构的设计和基本操作的实现。类型的具体实

17、现，包括存储结构的设计和基本操作的实现。算法和算法分析n考核知识点考核知识点1.算法的定义（算法的定义（）说明：说明：通常一个问题可以有多种算法，一个通常一个问题可以有多种算法，一个 给定算法解决给定算法解决 一个特定的问题。一个特定的问题。2.算法的特性（算法的特性（）输入、输出、有穷性、确定性、可行性输入、输出、有穷性、确定性、可行性3.算法的描述方法（算法的描述方法（）常用的描述算法的方法有自然语言、流程图、程序设计语常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等，其中伪代码被称为算法语言，是比较合适言和伪代码等，其中伪代码被称为算法语言，是比较合适的描述算法的方法。的描

18、述算法的方法。说明：说明：伪代码的书写形式没有严格的规定，只是要求了解伪代码的书写形式没有严格的规定，只是要求了解任何一种现代程序设计语言的人都能够很好的理解。任何一种现代程序设计语言的人都能够很好的理解。算法和算法分析n考核知识点考核知识点4.算法的时间复杂度（算法的时间复杂度（）算法的渐近时间复杂度（简称时间复杂度）考察当算法的渐近时间复杂度（简称时间复杂度）考察当问题规模充分大时，算法中基本语句的执行次数在问题规模充分大时，算法中基本语句的执行次数在渐近意义上的阶，通常用大渐近意义上的阶，通常用大O记号表示。问题规模是记号表示。问题规模是指输入量的多少。基本语句是执行次数与整个算法指输入

19、量的多少。基本语句是执行次数与整个算法的执行次数成正比的语句。的执行次数成正比的语句。常用的算法时间复杂度由小到大依次为：常用的算法时间复杂度由小到大依次为：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：算法必须具备输入、输出和（算法必须具备输入、输出和（）等特性。）等特性。A.可行性、可移植性和可扩充性可行性、可移植性和可扩充性 B.可行性、确定性和有穷性可行性、确定性和有穷性 C.确定性、稳定性和有穷性确定性

22、、稳定性和有穷性 D.易读性、稳定性和健壮性易读性、稳定性和健壮性 解答：解答：B分分析析：可可移移植植性性、可可扩扩充充性性、易易读读性性、稳稳定定性性和和健健壮性都是好算法应该具备的特性。壮性都是好算法应该具备的特性。算法和算法分析典型题解析选择题选择题3：当当输输入入非非法法错错误误时时，一一个个“好好”的的算算法法会会进进行行适适当当处处理理，而而不不会会产产生生难难以以理理解解的的输输出出结结果果，这这称称为为算算法法的的（）。）。A.可读性可读性 B.健壮性健壮性 C.正确性正确性 D.有穷性有穷性解答：解答：B分分析析：健健壮壮性性也也称称鲁鲁棒棒性性，是是指指算算法法对对非非法

23、法输输入入的的抵抵抗抗能能力力，即即对对于于错错误误的的输输入入，算算法法应应能能识识别别并并做做出出处处理理，而不是产生错误动作或陷入瘫痪。而不是产生错误动作或陷入瘫痪。算法和算法分析典型题解析选择题选择题4：算法分析的目的是（算法分析的目的是（），算法分析的两个主要方面是（），算法分析的两个主要方面是（）。）。A.找出数据结构的合理性找出数据结构的合理性 B.研究算法中输入和输出的关系研究算法中输入和输出的关系 C.分析算法的效率以求改进分析算法的效率以求改进 D.分析算法的易读性和文档性分析算法的易读性和文档性 E.空间性能和时间性能空间性能和时间性能 F.正确性和简明性正确性和简明性

24、G.可读性和文档性可读性和文档性 H.数据复杂性和程序复杂性数据复杂性和程序复杂性解答：解答：C,E分分析析：数数据据结结构构的的合合理理性性需需要要从从多多方方面面进进行行权权衡衡；算算法法中中输输入入和和输输出的关系是由问题本身决定的，一般和算法无关。出的关系是由问题本身决定的，一般和算法无关。算法和算法分析典型题解析选择题选择题5：算法的时间复杂度与（算法的时间复杂度与（）有关。）有关。A.问题规模问题规模 B.待处理数据的初态待处理数据的初态 C.算法的易读性算法的易读性 D.A和和B解答：解答：D分分析析：有有时时算算法法本本身身比比较较复复杂杂但但是是时时间间性性能能较较好好，例例

25、如如快快速速排排序序算算法法比比较较复复杂杂，但但快快速速排排序序是是目目前前在在平平均均情情况况下下最最快快的的排排序序方方法法；算算法法的的时时间间复复杂杂度度不不仅仅取取决决于于问问题题规规模模，还还与与处处理理数数据据的的初初态态有有关关，例例如如对对n个个元元素素组组成成的的序序列列进进行行排排序序，如如果果初初始始排排列列不不同同则则排排序序的的时时间性能有很大的差别。间性能有很大的差别。算法和算法分析典型题解析选择题选择题6：某算法的时间复杂度是某算法的时间复杂度是O(n2)，表明该算法（，表明该算法（）。）。A.问题规模是问题规模是n2 B.执行时间等于执行时间等于n2 C.执

26、行时间与执行时间与n2成正比成正比 D.问题规模与问题规模与n2成正比成正比解答：解答：C分分析析：算算法法的的时时间间复复杂杂度度是是O(n2)，问问题题规规模模可可能能是是n（例例如如对对n个个元元素素进进行行排排序序），也也可可能能是是n2（例例如如对对n*n的的方方阵阵进进行行转转置置），也也有有其其他他可可能能，因因此此，从从时时间间复复杂杂度度不不能能确确定定问问题题规规模模；算算法法的的时时间间复复杂杂度度是是O(n2)表明算法的执行时间表明算法的执行时间T(n)=c*n2(C为常数为常数).算法和算法分析典型题解析选择题选择题7：下面说法错误的是（下面说法错误的是（）。）。1)

27、算法原地工作的含义是指不需要任何额外的辅助空间算法原地工作的含义是指不需要任何额外的辅助空间 2)在在相相同同的的规规模模n下下，复复杂杂度度O(n)的的算算法法在在时时间间上上总总是是优优于于复复杂杂度度O(2n)的的算法算法 3)所谓的时间复杂度是指最坏情况下，估算算法执行时间的一个上界所谓的时间复杂度是指最坏情况下，估算算法执行时间的一个上界 4)同一个算法，实现语言的级别越高，执行效率就越低同一个算法，实现语言的级别越高，执行效率就越低 A.1)B.1),2)C.1),4)D.3)解答：解答：B分分析析：算算法法原原地地（也也称称就就地地）工工作作是是指指算算法法的的空空间间复复杂杂度

28、度为为O(1)，例例如如直直接接插插入入排排序序算算法法需需要要一一个个用用于于交交换换的的临临时时单单元元；说说法法2)考考虑虑在在时时间间上上的的性性能能，此此时时需需要要考考虑虑两两个个复复杂杂度度的的系系数数，例例如如复复杂杂度度为为O(n)的的算算法法其其系系数数为为100,算算法法复复杂杂度度为为O(2n)的的算算法法的的系系数数为为1，这这两两个个函函数数曲曲线线就就有有一一个个交交叉叉点点，如如果果仅仅就就时时间间复复杂杂度度而而言言，复复杂杂度度O(n)的的算算法法优优于于复复杂杂度度为为O(2n)的的算算法法；时时间间复复杂杂度度需需要要考考虑虑最最坏坏情情况况下下，算算法

29、法执执行行时时间间的的一一个个上上界界；说说法法4)中中“实现语言的级别实现语言的级别”指的是机器语言、汇编语言和高级语言。指的是机器语言、汇编语言和高级语言。算法和算法分析典型题解析选择题选择题8：设设某某算算法法完完成成对对n个个元元素素进进行行处处理理，所所需需的的时时间间是是T(n)=100nlog2n+200n+500，则则该该算算法的时间复杂度是法的时间复杂度是 A.O(1)B.O(n)C.O(nlog2n)D.O(nlog2n+n)解答：解答：C分分析析：算算法法的的时时间间复复杂杂度度可可以以忽忽略略所所有有低低次次幂幂和和最最高次幂的系数。高次幂的系数。算法和算法分析典型题解

30、析选择题选择题9：假假设设时时间间复复杂杂度度为为O(n2)的的算算法法在在有有200个个元元素素的的数数组组上上运运行行需需要要3.1ms，则则在在有有400个个元元素的数组上运行需要（素的数组上运行需要（）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

31、解答：解答：C分分 析析：外外 层层 循循 环环 执执 行行 n次次，内内 层层 循循 环环 执执 行行2,4,6,2n次次，共共执执行行(2+4+6+2n)=n(n+1)次。次。如何估算算法的时间复杂度如何估算算法的时间复杂度n算法主要由程序的算法主要由程序的控制结构控制结构（顺序，分支，（顺序，分支，循环）和循环）和原操作原操作（必须的操作）构成，算（必须的操作）构成，算法的时间主要取决于两者。法的时间主要取决于两者。n算法控制结构算法控制结构 原操作原操作 固有数据类型的操作固有数据类型的操作如何估算算法的时间复杂度如何估算算法的时间复杂度n算法的执行时间算法的执行时间 原操作原操作(i

32、)的的执执行次数行次数原操作原操作(i)的的执执行行时间时间n算法的执行时间算法的执行时间 和和 原操作执行次数之原操作执行次数之和和成正比成正比n具体而言：从算法中选取一种对于所研究具体而言：从算法中选取一种对于所研究的问题来说是的问题来说是基本操作基本操作的原操作，以该基的原操作，以该基本操作本操作在算法中重复执行的次数在算法中重复执行的次数作为算法作为算法运行时间的衡量准则。运行时间的衡量准则。或者说算法中基本操作重复执行的次或者说算法中基本操作重复执行的次数是问题规模数是问题规模n的某个函数的某个函数f(n)语句的频度语句的频度（Frequency Count)+x;s=0;时间复杂度

33、时间复杂度 for(j=1;j=n;+j)+x;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;语句频度：语

34、句频度：为近似于为近似于n2，所以时间复杂度仍为所以时间复杂度仍为O(n2)。时间复杂度只考虑量级就可以了。时间复杂度只考虑量级就可以了。时间复杂度s=0;for(j=1;j=n;j*=2)for(k=1;k=n;+k)s+;语语句句频频度度为为：时间复杂度为：时间复杂度为：O(nlog2n)x 表示不小于表示不小于x的最的最小整数，即向上取整，小整数，即向上取整，如如 6.1 =7算法和算法分析典型题解析应用题应用题1：已知如下程序段：已知如下程序段：FOR i:=n downto 1 do 语句语句1 BEGIN x:=x+1;语句语句2 FOR j:=n downto i do 语句语句

35、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+;基本语句是基本语句是k=k+10*i；共执行了；共执行了n-2次，所以次，所以T(n)=O(n)算法和算法分析

36、典型题解析应用题应用题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+;分析条件语句，每循环一次，分析条件语句，每循环一次，i+j整体加整体加1，共循环共循环n次，次，所以所以T(n)=O(n)算法和算

37、法分析典型题解析应用题应用题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记号表示其执行时间。记号表示其执行时间。5)for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x+;x+

38、是基本语句，所以是基本语句，所以算法和算法分析典型题解析应用题应用题2：分分析析以以下下各各程程序序段段，并并用用大大O记记号号表表示示其其执执行行时间。时间。6)for(i=0;in;i+)for(j=0;jm;j+)aij=0;aij=0是基本语句，执行了是基本语句，执行了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开始递增

39、开始递增1，直到，直到m-1为止，为止，有：有：s=0+1+2+m-1=m(m-1)/2,并满足：并满足：s=m(m-1)/2n，则有，则有 ，所以，所以，该算法的时间复杂度为：该算法的时间复杂度为：算法和算法分析典型题解析应用题应用题4：设设n是是偶偶数数，试试计计算算运运行行下下列列程程序序段段后后m的的值值并并给给出出该该程程序序段段的时间复杂度。的时间复杂度。int m=0,i,j;for(i=1;i=n;i+)for(j=2*i;j=n;j+)m+;算法和算法分析典型题解析应用题应用题5：分析以下算法的时间复杂度。分析以下算法的时间复杂度。void func(int n)int i=

40、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：下下面面程程序序段段中中带带下下划划线线的的

41、语语句句的的执执行行次次数数的的数数量量级级是是（）。）。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的的执执行行次次数数为（为（）。）。for(i=1;i=i;j-)s;算法和算法分析典型

42、题解析应用题应用题10：在在有有n个个选选手手参参加加的的单单循循环环赛赛中中，总总共共进进行行（）场比赛？）场比赛？n解答：因为每个人都要和其他解答：因为每个人都要和其他n-1个人进行个人进行一次比赛，所以是一次比赛，所以是n*(n-1)，但甲和乙比赛，但甲和乙比赛和乙和甲比赛是相同的，所以要去掉，所以和乙和甲比赛是相同的，所以要去掉，所以总共进行总共进行n*(n-1)/2场比赛。场比赛。算法和算法分析典型题解析应用题应用题11：有有实实现现同同一一功功能能的的两两个个算算法法A1和和A2，其其中中A1的的时时间间复复杂杂度度为为T1=O(2n)，A2的的时时间间复复杂杂度度为为T2=O(n

43、2)，仅就时间复杂度而言，请具体分析哪一个算法好。，仅就时间复杂度而言，请具体分析哪一个算法好。解答：比较两个复杂度函数解答：比较两个复杂度函数2n和和n2，显然有：，显然有：当当n=1时，时，2112,则算法则算法A2好于算法好于算法A1；当当n=2时时，22=22,当当n=4时时，24=42，则则两两个个算算法法的的时间复杂度相同；时间复杂度相同；当当n=3时，时，234时，时，2nn2,则算法则算法A2好于算法好于算法A1.算法和算法分析典型题解析应用题应用题12：度度量量一一个个算算法法的的执执行行时时间间通通常常有有几几种种方方法法？各各有有何何优优缺点？缺点？解答：通常有两种方法：

44、事后统计和事前分析。解答：通常有两种方法：事后统计和事前分析。事事后后统统计计方方法法的的优优点点是是比比较较精精确确，缺缺点点是是必必须须根根据据算算法法编编写写相相应应的的程程序序，而而且且所所得得的的时时间间依依赖赖于于计计算算机的软硬件环境，有时候容易掩盖算法本身的优劣。机的软硬件环境，有时候容易掩盖算法本身的优劣。事事前前分分析析方方法法的的优优点点是是不不必必运运行行程程序序就就可可以以从从复复杂杂度度角角度度比比较较算算法法的的优优劣劣，缺缺点点是是不不够够精精确确，当当一一个个算法比另一个算法稍好一些时不易判断。算法比另一个算法稍好一些时不易判断。挑战题解析n综合应用题：主要考

45、查难度较大的算法时间综合应用题：主要考查难度较大的算法时间性能分析、有关深层次理解性能分析、有关深层次理解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个盘，从个盘，从x移到移到y，z为为辅助塔辅助塔move(x,n,z);/把把n号盘，从号盘，从x移到移到zHanoi(n 1,y,x,z);/把把n-1个盘，个盘，从从y移到移到z，x为辅为辅助塔助塔 n综合应用题综合应用题1：分析：分

46、析Hanoi问题的算法时间复杂度。问题的算法时间复杂度。挑战题解析n综合应用题综合应用题1：分析：分析Hanoi问题的算法时间复杂度。问题的算法时间复杂度。T(n)=1 n=122T(n-1)+1 n1T(n)=1 n=122T(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

47、：运算是：运算是DS的一个重要方面。举例说明两个的一个重要方面。举例说明两个DS的的逻辑结构和存储方式完全相同，只是对于运算的定义不同，因而逻辑结构和存储方式完全相同，只是对于运算的定义不同，因而具有不同的特性，则这两个具有不同的特性，则这两个DS是不同的。是不同的。解答：解答：例如堆栈和队列都是线性结构，都可以采用顺序存储和例如堆栈和队列都是线性结构，都可以采用顺序存储和链式存储，由于对插入和删除操作的定义不同，栈规定在表的链式存储，由于对插入和删除操作的定义不同，栈规定在表的一端进行插入和删除操作，队列规定在表的一端进行插入在另一端进行插入和删除操作，队列规定在表的一端进行插入在另一端进行

48、删除操作，导致了栈的后进先出，队列的先进先出特一端进行删除操作，导致了栈的后进先出，队列的先进先出特性，因而栈和队列是两种不同的性，因而栈和队列是两种不同的DS。再如二叉树和二叉排序树在逻辑结构上都是二叉树，都采用二再如二叉树和二叉排序树在逻辑结构上都是二叉树，都采用二叉链表形式存储，但是对于某些运算的定义不同，例如插入操叉链表形式存储，但是对于某些运算的定义不同，例如插入操作，二叉树需指明作为哪个结点的左孩子还是右孩子插入，而作，二叉树需指明作为哪个结点的左孩子还是右孩子插入，而二叉排序树无需指明，由二叉排序树的形状决定插入位置。二叉排序树无需指明，由二叉排序树的形状决定插入位置。典型题解析

49、n5.可以用（可以用（）、数据关系和基本操作定义一）、数据关系和基本操作定义一个完整的抽象数据类型。个完整的抽象数据类型。A.数据元素数据元素 B.数据对象数据对象 C.原子类型原子类型 D.存储结构存储结构解答：解答：A分析：分析：数据对象指的是具有相同类型的数据，而数据的数据对象指的是具有相同类型的数据，而数据的概念隐含着数据元素和元素之间的关系；定义抽象数概念隐含着数据元素和元素之间的关系；定义抽象数据类型无需指明存储结构，定义抽象数据类型需要定据类型无需指明存储结构，定义抽象数据类型需要定义两方面的内容：数据和操作，其中数据需要指明数义两方面的内容：数据和操作，其中数据需要指明数据元素以及数据元素之间的关系，操作需要指明基本据元素以及数据元素之间的关系，操作需要指明基本操作及其操作接口。操作及其操作接口。