《第1章 绪论习题.ppt》由会员分享，可在线阅读，更多相关《第1章 绪论习题.ppt（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第1 1章章 绪论习题绪论习题本章要点回顾本章要点回顾:1.1.熟悉各名词、术语的含义，掌握基本概念熟悉各名词、术语的含义，掌握基本概念 数据、数据元素、数据结构、数据类型、抽象数据类型、数据、数据元素、数据结构、数据类型、抽象数据类型、逻辑结构和存储结构、算法及其设计原则、算法五个要素、逻辑结构和存储结构、算法及其设计原则、算法五个要素、问题的规模、语句频度、时间复杂度、空间复杂度。问题的规模、语句频度、时间复杂度、空间复杂度。2.2.理解算法五个要素的确切含义理解算法五个要素的确切含义3.3.掌握计算语句频度和估算算法时间复杂度的方法掌握计算语句频度和估算算法时间复杂度的方法 数据结构是
2、一门讨论数据结构是一门讨论“描述现实世界实体的数学模型描述现实世界实体的数学模型(非数非数值计算值计算)及其上的操作在计算机中如何表示和实现及其上的操作在计算机中如何表示和实现”的学科。的学科。习题习题1.1:n 数据（数据（data）：是描述客观事物的数值、字符、相关符号）：是描述客观事物的数值、字符、相关符号等所有能够输入到计算机中并能被计算机处理的符号的总称。等所有能够输入到计算机中并能被计算机处理的符号的总称。n 数据元素（数据元素（data element）：数据中具有独立意义的个）：数据中具有独立意义的个体，是数据的基本单位（也称为元素、记录、结点、顶点等）。体，是数据的基本单位（
3、也称为元素、记录、结点、顶点等）。n 数据结构（数据结构（data structures）：带结构的数据元素的集）：带结构的数据元素的集合，结构指的是数据元素之间存在有关系。合，结构指的是数据元素之间存在有关系。n 存储结构：数据的逻辑结构在计算机中的表示或实现。存储结构：数据的逻辑结构在计算机中的表示或实现。n 数据类型：是一个同类型值的的集合和定义在这个值集上数据类型：是一个同类型值的的集合和定义在这个值集上的一组操作的总称。的一组操作的总称。n 抽象数据类型（抽象数据类型（Abstract Data Type）：一个数据结构）：一个数据结构加上定义在这个数据结构上的一组操作。加上定义在这
4、个数据结构上的一组操作。习题习题1.2:r1=(p1,p2),(p3,p4),(p5,p6),(p7,p8)r2=(p1,p2),(p1,p3),(p1,p4),(p2,p3),(p2,p4),(p3,p4),(p5,p6),(p5,p7),(p5,p8),(p6,p7),(p6,p8),(p7,p8)习题习题1.3:100n3(1)(a)O(1)6n2-12n+1(2)(b)O(2n)1024(3)(c)O(n)n+2log2n(4)(d)O(n2)n(n+1)(n+2)/6(5)(e)O(log2n)2n+1+100n(6)(f)O(n3)习题习题1.4:(1)习题习题1.4:(2)(2)
5、设语句执行次数为设语句执行次数为k，则：，则：n/2k0 即：即：n/2k-11 有：有：2k-1n 因因k为整数，则：为整数，则：习题习题1.5:float polyvalue(float*a,int n,float x)/求多项式的和求多项式的和float*p=a;float xp=1;/xp用于存放用于存放x的的i次方次方float sum=0;/用于存放多项式的和用于存放多项式的和for(int i=0;i=10n=10，下面程序段的时间复杂度是（）。，下面程序段的时间复杂度是（）。for(ifor(i=10;in;i+)=10;in;i+)j=k=0;j=k=0;while(j+kw
6、hile(j+k=i)k)(jk)k+;k+;else j+;else j+;A A）O O（loglog2 2n n）B B）O(nO(n)C)C）O(nlogO(nlog2 2n)Dn)D）O(nO(n2 2)9.9.计算机算法是指计算机算法是指()()。A)A)计算方法计算方法 B)B)排序方法排序方法 C)C)调度方法调度方法 D)D)解决问题的有限运算序列解决问题的有限运算序列8.D 9.D 补充习题补充习题:10.10.数据的定义取决于数据的逻辑结构，而数据的实现取决于数据的定义取决于数据的逻辑结构，而数据的实现取决于数据的物理结构数据的物理结构()()。A)A)正确正确 B)B)
7、不正确不正确 11.11.下面说法错误的是（下面说法错误的是（）A)A)算法原地工作的含义是指不需要任何额外的辅助空间算法原地工作的含义是指不需要任何额外的辅助空间 B)B)在相同的规模在相同的规模n n下，复杂度下，复杂度O(nO(n)的算法在时间上总是优的算法在时间上总是优于复杂度于复杂度O(2O(2n n)的算法的算法 C)C)所谓时间复杂度是指最坏情况下，估算算法执行时间的所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界一个上界 D)D)同一个算法，实现语言的级别越高，执行效率就越低同一个算法，实现语言的级别越高，执行效率就越低10.A 11.AD补充习题补充习题:判断判断1.
8、数据元素是数据的最小单位。数据元素是数据的最小单位。()2.记录是数据处理的最小单位。记录是数据处理的最小单位。()3.数据的逻辑结构是指数据的各数据项之间的逻辑关系；数据的逻辑结构是指数据的各数据项之间的逻辑关系；()4.算法的优劣与算法描述语言无关，但与所用计算机有关。算法的优劣与算法描述语言无关，但与所用计算机有关。()5.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()6.算法可以用不同的语言描述，如果用算法可以用不同的语言描述，如果用C 语言或语言或PASCAL语言等高级语言语言等高级语言来描述，则算法实际上就是程序了。来描
9、述，则算法实际上就是程序了。()7.数据的物理结构是指数据在计算机内的实际存储形式。数据的物理结构是指数据在计算机内的实际存储形式。()8.数据结构的抽象操作的定义与具体实现有关。数据结构的抽象操作的定义与具体实现有关。()9.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。构的独立。()10.数据的逻辑结构说明数据元素之间的顺序关系数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的存储它依赖于计算机的存储结构结构.()1.2.3.4.5.6.7.8.9.10.补充习题补充习题:语句频度与时间复杂度语
10、句频度与时间复杂度1.计算机执行下面的语句时计算机执行下面的语句时,语句语句s的执行次数为的执行次数为:(n+3)(n-2)/2。for(i=l；i=i;j-)s;2.下面程序段中带有下划线的语句执行次数的量级是下面程序段中带有下划线的语句执行次数的量级是(log2n2)i=n*n while(i!=1)i=i/2;3.下面程序段中带下划线的语句的执行次数的数量级是下面程序段中带下划线的语句的执行次数的数量级是(nlog2n)。i=1;while(in)for(j=1;j=n;j+)x=x+1;i=i*2；i=1;for(j=1;j=n;j+)while(in)x=x+1;i=i*2；补充习题补充习题:语句频度与时间复杂度语句频度与时间复杂度5.在下面的程序段中，对的赋值语句的频度为在下面的程序段中，对的赋值语句的频度为:n(n+1)(n+2)/6 O(n3)for（i=1；i=n;i+）for(j=1;j=i;j+)for(k1;k=1;i-）/语句语句1 n+1 x=x+1；/语句语句2 n for（j=n；j=i;j-）/语句语句3 n(n+3)/2 y=y+1;/语句语句4 n(n+1)/2