数据结构相关文档和PPT

1、数据结构数据结构任课教师：邱任课教师：邱 保保 志志Email：单位：郑州大学信息工程学院单位：郑州大学信息工程学院为什么要学习数据结构？为什么要学习数据结构？n介于数学、计算机软件、硬件三者之间的核心介于数学、计算机软件、硬件三者之间的核心课程课程n一般程序设计（尤指非数值计算的程序设计）一般程序设计（尤指非数值计算的程序设计）的基础的基础n设计和实现编译程序、操作系统、数据库系统设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。及其它系统程序和大型应用程序的重要基础。如何利用计算机解决实际应用问题？如何利用计算机解决实际应用问题？n需经过以下三步骤：需经过以下

2、三步骤：n从具体问题中抽象出一个适当的数学模型。从具体问题中抽象出一个适当的数学模型。n设计一个解此数学模型的算法设计一个解此数学模型的算法n编程调试，得到最终答案编程调试，得到最终答案n Niklaus Wirth： Algorithm + Data Structures = Programsn 算法算法: 处理问题的策略处理问题的策略n 数据结构数据结构: 问题的数学模型问题的数学模型n 程序程序:为计算机处理问题编制一组指令集为计算机处理问题编制一组指令集 登录号登录号书名书名作者作者出版单位出版单位出版时间出版时间N.3.73.762 数据结构数据结构 严蔚敏严蔚敏 吴伟民吴伟民 清华

3、大学出版社清华大学出版社 2003.12图书馆的书目检索系统自动化问题图书馆的书目检索系统自动化问题数学模型数学模型一对一的线性结构一对一的线性结构人机对弈问题人机对弈问题数学模型数学模型一对多的树结构一对多的树结构“井井”字棋对弈字棋对弈“树树”先手：先手：C1C9C4C2C12C10C11C5C3C6C7C8计算机专业课程开设先后关系图计算机专业课程开设先后关系图数学模型数学模型多对多的图形结构多对多的图形结构计算机专业课程开设问题计算机专业课程开设问题 计 算 机 专 业 学 生 的 必 修 课 程课 程 编 号课 程 名 称 需 要 的 先 导 课 程编 号C 1程 序 设 计 基 础

4、无C 2离 散 数 学C 1C 3数 据 结 构C 1 ， C 2C 4汇 编 语 言C 1C 5算 法 分 析 与 设 计 C 3 ， C 4C 6计 算 机 组 成 原 理C 1 1C 7编 译 原 理C 5 ， C 3C 8操 作 系 统C 3 ， C 6C 9高 等 数 学无C 1 0线 性 代 数C 9C 1 1普 通 物 理C 9C 1 2数 值 分 析C 9 ， C 1 0 ， C 1怎样学数据结构？怎样学数据结构？n牢记基本概念和经典算法牢记基本概念和经典算法n联系实际，富于联想联系实际，富于联想n总结算法之间的共性和特性。总结算法之间的共性和特性。n忌忌：求偏、求难、重算法轻

5、概念求偏、求难、重算法轻概念。n三阶段三阶段：模仿模仿-总结总结-创新创新 本书的内容简介本书的内容简介n第一章第一章:综述数据结构等基本概念，介绍算法和算综述数据结构等基本概念，介绍算法和算法分析法分析(3/2周周)n第二章第二章-第七章第七章:讨论线性表讨论线性表(3周周)、栈和队列、栈和队列(2周周)、串串(2周周) 、数组和广义表、数组和广义表(2周周) 、树和二叉树、树和二叉树(2周周) 、图图(2周周)等基本类型的等基本类型的数据结构、物理结构数据结构、物理结构及其及其相相关操作关操作的的实现实现。n第九章第九章:静态查找表和动态查找表。静态查找表和动态查找表。(2周周)n第十章第

6、十章:介绍五种内排序方法介绍五种内排序方法(2周周)n复习复习（1/2周）周）1.2 基本概念和术语基本概念和术语n数据数据：信息的载体，是描述客观事物的数、字符：信息的载体，是描述客观事物的数、字符及所有能输入到计算机中被计算机程序识别和处及所有能输入到计算机中被计算机程序识别和处理的符号的集合。理的符号的集合。n数值性数据数值性数据n非数值性数据非数值性数据n数据元素数据元素：数据的：数据的基本基本单位单位n一个数据元素可由若干个数据项组成。一个数据元素可由若干个数据项组成。n数据项是数据不可分割的数据项是数据不可分割的最小最小单位。单位。n数据对象数据对象：数据的子集。具有相同性质的数据

7、元：数据的子集。具有相同性质的数据元素集合。素集合。n例如：整数对象例如：整数对象 N = 0, 1, 2, 数据结构（逻辑结构）数据结构（逻辑结构）n数据结构数据结构：相互间存在一种或多种相互间存在一种或多种特定关系特定关系的的数据元素集合。数据元素集合。n结构结构：数据元素相互之间的关系：数据元素相互之间的关系n特定关系：特定关系：特定关系特定关系数据结构数据结构举例举例没有关系没有关系集合集合正整数正整数一对一关系一对一关系线性表线性表图书管理图书管理一对多关系一对多关系树树棋局对弈树棋局对弈树多对多关系多对多关系 图（网）图（网）课程开设先后关系图课程开设先后关系图数据结构的形式定义数

8、据结构的形式定义nDS=(D,S)nD：数据元素的：数据元素的有限有限集合。集合。设设a1,a2,ai,aj,annS：定义在：定义在D上的关系的有限集合。上的关系的有限集合。n若若aiRaj,则则ai,ajSn若若aiRaj,且且ajRai,则则(ai,aj)Sn例：复数可定义为一种数据结构：例：复数可定义为一种数据结构：COMPLEX=(C,R)C：含有两个实数的集合：含有两个实数的集合C1,C2；R：P是定义在是定义在C上的一种关系上的一种关系n课上习题：课上习题：T=(K,R)，画出它所对应的逻辑结构画出它所对应的逻辑结构nK=1,2,3,4,5,6 ；=r r=,aiajaiaj45

9、6231ABEDCF125643四类基本逻辑结构关系图四类基本逻辑结构关系图 n数据结构在计算机中的表示：数据结构在计算机中的表示：n数据元素的表示数据元素的表示n数据元素之间关系的表示数据元素之间关系的表示n顺序映象：顺序映象：借助元素在存储器的相对位置表借助元素在存储器的相对位置表示数据元素之间的逻辑关系。对应于顺序存示数据元素之间的逻辑关系。对应于顺序存储结构储结构(sequential sets).n非顺序映象：非顺序映象：利用指示元素存储地址的指针利用指示元素存储地址的指针表示数据元素间的逻辑关系。对应于表示数据元素间的逻辑关系。对应于n链式存储结构链式存储结构(linked lis

10、ts)n索引树索引树(indexed trees)n散列表散列表(hash tables)数据的物理结构数据的物理结构(存储结构存储结构)数据逻辑结构和物理结构之间的关系数据逻辑结构和物理结构之间的关系n关系：关系：n任意一个算法的任意一个算法的设计设计取决于选定的逻辑结构取决于选定的逻辑结构n算法的算法的实现实现依赖于采用的物理结构。依赖于采用的物理结构。实际应用实际应用算法算法数据结构数据结构线性结构线性结构非线性结构非线性结构存储结构存储结构 顺序存储结构顺序存储结构非顺序存储结构非顺序存储结构定位定位(查找查找)加法、乘法加法、乘法比较、移动比较、移动（逻辑）（逻辑）(物理物理)数据结

11、构主要研究什么？数据结构主要研究什么？n解决问题时可能遇到的典型的逻辑结构解决问题时可能遇到的典型的逻辑结构n逻辑结构的存储映象（物理结构）逻辑结构的存储映象（物理结构）n数据结构的相关操作及其实现（算法）数据结构的相关操作及其实现（算法）数据类型数据类型n 数据类型数据类型：一组性质相同的值的集合以及定义于该值一组性质相同的值的集合以及定义于该值集上的一组操作的总称。集上的一组操作的总称。 例：例：C C语言中整型变量语言中整型变量值：定义在某区间上的整数值：定义在某区间上的整数操作：加、减、乘、除、取模操作：加、减、乘、除、取模 按值的不同特性分：按值的不同特性分：原子类型原子类型：值不可

12、再分：值不可再分C的的五种基本数据类型五种基本数据类型: :char,int,float,double,void结构类型结构类型：值由若干个成分按某种结构组成：值由若干个成分按某种结构组成抽象数据类型抽象数据类型n一个数据模型及定义在该模型上的一组操作。一个数据模型及定义在该模型上的一组操作。n按照值域的不同特性按照值域的不同特性: :原子类型（值不可分解）、原子类型（值不可分解）、固定聚合类型（值有确定数目的成分）、可变聚合固定聚合类型（值有确定数目的成分）、可变聚合类型（成分的数目不确定）。类型（成分的数目不确定）。n例例：抽象数据类型：矩阵抽象数据类型：矩阵=矩阵矩阵+(求转置、加、乘、

13、逆等）求转置、加、乘、逆等）形式定义：形式定义：DS=(D, S, P)。 D：数据对象数据对象 S：D上的关系集，上的关系集， P：对：对D的基本操作集。的基本操作集。构造性操作：插入、删除、修改构造性操作：插入、删除、修改非构造性操作：查找、排序非构造性操作：查找、排序抽象数据类型的定义格式抽象数据类型的定义格式(仅适用于本书仅适用于本书)nADT 抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 基本操作：基本操作的定义基本操作：基本操作的定义 ADT 抽象数据类型名抽象数据类型名n基本操作的定义格式为基本操

14、作的定义格式为 基本操作名（参数表）基本操作名（参数表） 初始条件：初始条件描述初始条件：初始条件描述 操作结果：操作结果描述操作结果：操作结果描述n参数表有两种参数：参数表有两种参数：n赋值参数：只为操作提供输入值；赋值参数：只为操作提供输入值；n引用参数：以引用参数：以&打头，打头， 除可提供输入值外，还将返回操作结果。除可提供输入值外，还将返回操作结果。n初始条件描述了操作执行前数据结构和参数应满足的条件，若不满足，则操初始条件描述了操作执行前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。作失败，并返回相应出错信息。n操作结果说明了操作正常完成之后，数据结

15、构的变化状况和应返回的结果。操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。若初始条件为空，则省略之。抽象数据类型举例抽象数据类型举例-矩阵矩阵ADT Matrix 数据对象数据对象:D=ai,j|i=1,2,m;j=1,2,n;ai,jElemSet 数据关系数据关系:R=Row,ColRow=|1im,1jn-1Col=|1im-1,1jn 基本操作：基本操作： CreateMatrix(&M) DestroyMatrix(&M)PrintMatrix(&M)AddMatrix(M,N,&Q)SubMatrix(M

16、,N,&Q)MultMatrix(M,N,&Q)TransposeMatrix(M,&T) ADT Matrix1.3 类语言的语法规则类语言的语法规则1、预定义常量和类型：、预定义常量和类型：2、数据结构的描述，数据元素类型的定义、数据结构的描述，数据元素类型的定义 3、基本操作的算法可以使用的函数表示、基本操作的算法可以使用的函数表示4、算法描述中可以使用的赋值语句形式、算法描述中可以使用的赋值语句形式5、算法描述中可以使用的选择结构语句形式、算法描述中可以使用的选择结构语句形式6、算法描述中可以使用的循环结构语句形式、算法描述中可以使用的循环结构语句形式7、描述算

17、法中可以使用的结束语句形式、描述算法中可以使用的结束语句形式8、算法描述中可以使用的输入输出语句形式、算法描述中可以使用的输入输出语句形式9、算法描述中可以使用的注释格式、算法描述中可以使用的注释格式10、算法描述中可以使用的扩展函数、算法描述中可以使用的扩展函数11、算法描述中可以使用的逻辑运算的约定、算法描述中可以使用的逻辑运算的约定类语言的语法规则示例类语言的语法规则示例例例1typedef int Status;void example_1( ) Status a10; a0.9=0;例例2#define OK 1typedef int Status;Status example_2(

18、int x,int y) if(xy) xy; return OK;类语言的语法规则示例（续）类语言的语法规则示例（续）例例3typedef struct student char id5; char name11; int age; int math; int eng; int ds; int os; student;void example_3( ) student s; s=(,0,0,0,0,0); 附加内容：算法的描述方法附加内容：算法的描述方法n步骤法步骤法n程序流程图程序流程图nN-SN-S图图n伪码伪码步骤法步骤法n顺序查找数据序列中某个特定值顺序查找数据序列中某个特定值Ste

19、p1：输入数据序列：输入数据序列datan和欲查找值和欲查找值keyStep2：从序列中的最后一个元素开始查找：从序列中的最后一个元素开始查找Step3：若该元素值不等于：若该元素值不等于key，查找前一项，查找前一项Step4 ：若该元素值等于：若该元素值等于key，表示查找成功，返回，表示查找成功，返回key在在序列中的位置，去第六步序列中的位置，去第六步Step5：如果数据全部查找过但未能找到：如果数据全部查找过但未能找到key，表示查找，表示查找失败，返回。失败，返回。Step6：结束：结束程序流程图程序流程图五种基本控制结构五种基本控制结构程序流程图举例程序流程图举例开始开始输入待查

20、找序列输入待查找序列datan查找成功，返回查找成功，返回i输入要查找的值输入要查找的值key查找失败返回查找失败返回datai=key从最后一个元素开始查找从最后一个元素开始查找待查序列全查过待查序列全查过NNn顺序查找数据序列中某特定值顺序查找数据序列中某特定值结束结束i-N N- -S S图图nN-SN-S图也叫盒图，一种符合结构化程序设计图也叫盒图，一种符合结构化程序设计原则的图形描述工具。原则的图形描述工具。n五种基本控制结构由五种图形构件表示：五种基本控制结构由五种图形构件表示：N N- -S S图举例图举例顺序查找数据序列中某特定值顺序查找数据序列中某特定值F输入待查找序列输入待

21、查找序列datan输入要查找的值输入要查找的值key从最后一个元素开始查找从最后一个元素开始查找datai=key 查找成功查找成功返回返回key所在位置所在位置全查过全查过查找失败查找失败返回返回TFT下一次循环下一次循环Do while(data!=key)伪码伪码n以夹杂程序语法和自然语言的形式来描述解决以夹杂程序语法和自然语言的形式来描述解决问题的方法，有类问题的方法，有类C C、类、类PASCALPASCAL语言等。本书语言等。本书用的是类用的是类C C语言。语言。n顺序查找数据序列中某特定值，由顺序查找数据序列中某特定值，由类类C C给出其算法给出其算法Status Search_

22、Seq(SqList L,KeyType key)L.elem0=key;for(i=L.length;!EQ(L.elemi,key);i-);return i;Search_Seq.h代码代码/说明部分说明部分#include /包含预编译头文件包含预编译头文件#define TRUE 1/宏定义宏定义#define FALSE 0typedef int KeyType; /类型别名的定义类型别名的定义typedef struct KeyType *elem;int length;SqList;bool EQ(int i, int j)/判断两个整数是否相等判断两个整数是否相等 if(i=

23、j) return TRUE;else return FALSE;顺序查找数据序列中某特定值的程序代码顺序查找数据序列中某特定值的程序代码stdio.hmath.hstring.hmalloc.h/函数实现函数实现void Construction(SqList &L) /构造无序序列构造无序序列 int i;printf(“input the length of data:n);scanf(%d,&L.length);L.elem=(KeyType*)malloc(L.length+1)*sizeof(KeyType);printf(“input the key:n”);/输

24、入待查找的关键字输入待查找的关键字for(i=1;i=L.length;i+)scanf(%d,&L.elemi);int Search(SqList L,KeyType key)/查找函数查找函数 int i;L.elem0=key;for(i=L.length;!EQ(L.elemi,key);-i);return i;顺序查找数据序列中某特定值的程序代码顺序查找数据序列中某特定值的程序代码Search_Seq.cpp代码代码#include “search_seq.hvoid main()KeyType key;SqList L;printf(“input key:n”);sca

25、nf(“%d”,&key);/读入要查找的值读入要查找的值Construction(L);/创建待查找数据序列创建待查找数据序列int position=Search(L,key);/查找查找printf(the key is located in %d,position);顺序查找数据序列中某特定值的程序代码顺序查找数据序列中某特定值的程序代码1.41.4算法和算法分析算法和算法分析n算法的定义：算法的定义：对特定问题求解步骤的一种描述，是指对特定问题求解步骤的一种描述，是指令的令的有限有限序列，一条指令表示一个或多个操作。序列，一条指令表示一个或多个操作。n操作分为操作分为： n数

26、值计算：加、减、乘、除等算术运算数值计算：加、减、乘、除等算术运算n非数值计算：检索、排序、插入、删除非数值计算：检索、排序、插入、删除。n算法的特性：算法的特性：n有穷性：有穷性：算法应在执行有穷步后结束算法应在执行有穷步后结束n确定性：确定性：每步定义都是确切、无歧义的每步定义都是确切、无歧义的n可行性：可行性：算法中描述的操作都可通过已经实现的基算法中描述的操作都可通过已经实现的基本运算执行有限次实现本运算执行有限次实现n输入：输入： 有有0 0个或多个输入个或多个输入n输出：输出： 有一个或多个输出有一个或多个输出( (处理结果处理结果) )n算法与程序的区别算法与程序的区别算法设计的

27、要求算法设计的要求n正确性正确性：程序不含语法错误；程序不含语法错误；程序对于几组输入数据能够得出满足要求的结果；程序对于几组输入数据能够得出满足要求的结果；对精心选择带有刁难性的几组数据能得出满足要求的结果；对精心选择带有刁难性的几组数据能得出满足要求的结果；程序对于一切合法的输入数据都能产生满足要求的结果。程序对于一切合法的输入数据都能产生满足要求的结果。n可读性可读性：易于阅读和交流，其次是机器运行。：易于阅读和交流，其次是机器运行。 n健壮性健壮性：n当输入数据非法时，算法能适当地作出反应或进行处理，保当输入数据非法时，算法能适当地作出反应或进行处理，保证不会产生莫名其妙的输出结果。证

28、不会产生莫名其妙的输出结果。n处理出错的方法是返回一个表示错误或错误性质的值，以便处理出错的方法是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理，不应中断程序的执行。在更高的抽象层次上进行处理，不应中断程序的执行。n高效率和低存储量需求高效率和低存储量需求：n两者都与问题的规模有关。两者都与问题的规模有关。1.4.3 算法效率的度量算法效率的度量n 事后统计：运用计算机的计时功能统计算法的运行时间。事后统计：运用计算机的计时功能统计算法的运行时间。n缺陷：要运行算法对应的程序；缺陷：要运行算法对应的程序； 时间统计结果依赖于计算机软、硬件环境；时间统计结果依赖于计算机软、硬件环

29、境；n事前分析估计：事前分析估计：算法消耗的时间与下列因素有关：算法消耗的时间与下列因素有关： n算法采用的策略算法采用的策略n 问题的规模问题的规模n 书写程序的语言书写程序的语言n 编译器产生的机器代码的质量编译器产生的机器代码的质量n 计算机执行指令的速度。计算机执行指令的速度。double start, stop;time (&start);int k = search_seq (ST,key);time (&stop);double runTime = stop - start;printf(“%f”,runTime);算法的时间量度算法的时间量度n算法的时间量度与问

30、题的规模算法的时间量度与问题的规模n有关有关n从算法中选取一种对于所研究问题来说是基本操作的原从算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行次数作为算法的时间量度。操作，以该基本操作重复执行次数作为算法的时间量度。算法中基本操作重复执行次数是问题规模算法中基本操作重复执行次数是问题规模n的某个函数的某个函数f(n)n(渐近渐近)时间复杂度时间复杂度：算法的时间量度记作：算法的时间量度记作(n)=O(f(n)，表，表示随问题规模示随问题规模n的增大，算法执行时间的增长率和的增大，算法执行时间的增长率和f(n)的的增长率相同，称为算法的渐近时间复杂度。简称时间复增长率相

31、同，称为算法的渐近时间复杂度。简称时间复杂度。杂度。n语句频度语句频度：语句重复执行的次数。：语句重复执行的次数。两个两个n*n矩阵相乘的算法矩阵相乘的算法for(i=1;i=n;+i)for(j=1; j=n; +j)cij = 0;for(k=1; k=n; +k)cij += aik * bkj; 例例问题规模问题规模: n*n原操作原操作: cij += aik * bkj;基本操作重复执行的次数基本操作重复执行的次数: f(n) = n3算法时间度算法时间度: T(n) = O(f(n) = O(n3)例例程序段程序段语句频度语句频度 时间复杂度时间复杂度+x;s=0 for(i=1

32、;i=n;+i) +x;s+=x;for(i=1;i=n;+i) for(j=1;j=n;+j) +x;s+=x;i=1; while(i=n) i=i*2; 1 O(1)nO(n)n2log2nO(log2n)O(n2)大大O O表示法的加法规则和乘法规则表示法的加法规则和乘法规则n加法规则加法规则 针对并列程序段针对并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m)n乘法规则乘法规则 针对嵌套程序段针对嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m) 特例：若特例：若T1(n)=O(c)

33、，T2(n)=O(f(n)则则T(n)= T1(n)* T2(n)=O(c*f(n)= O(f(n) 问题规模问题规模: m*n原操作原操作: sumi += xij; 基本操作重复执行的次数基本操作重复执行的次数: f(n) = m*n算法时间度算法时间度: T(n) = O(f(n) = O(m*n) void add ( float x , int m, int n ) for ( int i = 0; i m; i+ ) sumi = 0.0; for ( int j = 0; j n; j+ ) sumi += xij; for ( i = 0; i m; i+ ) printf(“

34、%f”,sumi) ; 例例O(max (m*n, m)问题规模问题规模: n原操作原操作: ajaj+1;基本操作重复执行的次数基本操作重复执行的次数: 不定不定算法时间度算法时间度: T(n) = O(n2) 例例void bubble_sort(int a,int n) for(i=n-1,change=TRUE;i=1,change;-i) change=FALSE; /判断是否有相邻元素交换判断是否有相邻元素交换 for(j=0;jaj+1) ajaj+1; change=TRUE; 例例for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; aij=x; 问题规

35、模问题规模: n原操作原操作: aij=x;基本操作重复执行的次数基本操作重复执行的次数: 难以精确计算难以精确计算(1+1+2+n-2)算法时间度算法时间度: T(n) = O(n2) 算法的设计、选取和时间复杂度分析的原则算法的设计、选取和时间复杂度分析的原则n应该尽可能选用多项式阶的算法，不希望用指应该尽可能选用多项式阶的算法，不希望用指数阶数阶n算法的时间复杂度只考虑问题规模算法的时间复杂度只考虑问题规模n的增长率，的增长率，在难以精确计算基本操作执行次数（或语句频在难以精确计算基本操作执行次数（或语句频度）时，只需求得它关于度）时，只需求得它关于n的的增长率增长率或或阶阶即可。即可。

36、n算法中基本操作重复执行次数随问题的输入数算法中基本操作重复执行次数随问题的输入数据集不同而不同，要考虑据集不同而不同，要考虑最坏最坏情况下的时间复情况下的时间复杂度。杂度。例：百钱买百鸡问题例：百钱买百鸡问题100元钱买元钱买100只鸡，母鸡每只只鸡，母鸡每只5元，公鸡每只元，公鸡每只3元，小鸡元，小鸡3只只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？解：设母鸡、公鸡、小鸡各为解：设母鸡、公鸡、小鸡各为x, y, z只。则有：只。则有：x + y + z = 1005x + 3y + z/3 = 100方法方法1：for(i=0;i=

37、100;i+)for(j=0; j=100; j+)for(k=0; k=100;k+) if(k%3 =0&i+j+k=100& 5*I+3*j+k/3=100) printf(“%d,%d,%dn”, i,j,k);方法方法2：用两重循环：用两重循环： for(i=0;i100;i+)for(j=0;j100;j+) k=100 i j ;/小鸡的数目可以由母鸡数和公鸡数得到。小鸡的数目可以由母鸡数和公鸡数得到。 if(k%3=0 & 5*i+3*j+k/3=100)printf(“%d,%d,%dn”,i,j,k);方法方法3：用两重循环：用两重循环： for(i

38、=0;i=20;i+)/母鸡数不可能超过母鸡数不可能超过20只只for(j=0;j33;j+)/公鸡数也不超过公鸡数也不超过33只只 k=100 i j ; if(k%3=0 & 5*i+3*j+k/3=100)printf(“%d,%d,%dn”,i,j,k);例例 ：百钱买百鸡问题：百钱买百鸡问题(续续)例例 ：百钱买百鸡问题：百钱买百鸡问题(续续)方法方法4：用一重循环：用一重循环 由由x+y+z = 100和和5*x+3*y+z/3=100合并为一个方程：合并为一个方程：14*x+8*y = 200, 进一步简化为进一步简化为: 7*x+4*y=100 x不超过不超过14，并可

39、以进一步判断，并可以进一步判断x必为必为4的倍数，有：的倍数，有：for(i=0;i时的无穷大阶数，从小到大排时的无穷大阶数，从小到大排序（中科院计算所序（中科院计算所1995年）年） n,n-n3+7n5,nlog2n,2n/2,n3, log2n,n1/2+log2n,(3/2)n,n!,n2+log2n答：答：log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2,(3/2)n, n!c log2n n nlog2n n2 n3 2n 3n n!应掌握的类型题应掌握的类型题2、void prime(int n) int i=2

40、; while(n%i)!=0&i*1.0sqrt(n) printf(“%d is a prime number!”); else printf(“%d is not a prime number!”); 答 ：答 ： p r i m e 嵌 套 最 深 层 语 句 是 ：嵌 套 最 深 层 语 句 是 ： i + + ， 频 度 由， 频 度 由(n%2)!=0&i*1.00 )While ( y0 )If ( x100 ) If ( x100 ) x-=10 x-=10; y - -; ; y - -; Else x+;Else x+;郑州大学历年试题选（第一章续）郑州大

41、学历年试题选（第一章续）n有一计算矩阵相乘的程序，它的时间复杂度为有一计算矩阵相乘的程序，它的时间复杂度为O(nO(n3 3 ) )，当上机运行两个，当上机运行两个10101010矩阵相乘时，执行时间为矩阵相乘时，执行时间为5ms5ms，试计算两个，试计算两个30303030的矩阵相乘所需的矩阵相乘所需的时间。的时间。n1.1.数据类型是一个值集合和定义在这个值集合上的一组数据类型是一个值集合和定义在这个值集合上的一组_ _ 总称。总称。 2.2.若上机运行两个若上机运行两个10101010矩阵相乘，执行时间为矩阵相乘，执行时间为5 ms 5 ms ，该矩阵相乘算法，该矩阵相乘算法的时间复杂度

42、的时间复杂度T(n)= O( nT(n)= O( n3 3 ) )，其中，其中n n为矩阵的规模，则利用该算法计算两为矩阵的规模，则利用该算法计算两个个20202020的矩阵相乘时，执行时间为的矩阵相乘时，执行时间为_。 3. 3. 单链表中，逻辑上相邻的元素的物理位置单链表中，逻辑上相邻的元素的物理位置_紧邻。紧邻。 4. 4. 数据元素在计算机中有两种不同的存储结构即数据元素在计算机中有两种不同的存储结构即_。 5. 5. 程序段程序段for( i = 1; i = n; i + ) for( j = i; j = n; j+ ) for( i = 1; i = n; i + ) for(

43、 j = i; j = n; j+ ) k+ k+ 中中k+k+执行的频度是执行的频度是_。n设问题规模为设问题规模为n n，算法，算法1 1和算法和算法2 2的基本语句执行的频度分别为的基本语句执行的频度分别为f(n)f(n)、g(n)g(n)，用户从用户从n=1n=1测试到测试到n=10n=103 3 ，发现，发现f (n) g (n) f (n) g (n) 总成立，请问：算法总成立，请问：算法1 1的时的时间复杂度小于算法间复杂度小于算法2 2的时间复杂度吗？说明理由。的时间复杂度吗？说明理由。 郑州大学历年试题选（第一章续）n（20042004）一个算法的基本语句执行的频度如下：）一个算法的基本语句执行的频度如下： ，其中，其中n n是问题的规模，是问题的规模，试计算该算法的时间复杂度。试计算该算法的时间复杂度。 n（2007）设n为3的倍数，试分析程序段中带“”语句的执行频度 for (