《数据结构严蔚敏陈文博》由会员分享，可在线阅读，更多相关《数据结构严蔚敏陈文博（14页珍藏版）》请在金锄头文库上搜索。
1、第1章 绪论习题本章要点回顾:1.熟悉各名词、术语的含义，掌握基本概念数据、数据元素、数据结构、数据类型、抽象数据类型、逻辑结构和存储结构、算法及其设计原则、算法五个要素、 问题的规模、语句频度、时间复杂度、空间复杂度。2.理解算法五个要素的确切含义3.掌握计算语句频度和估算算法时间复杂度的方法数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。习题1.1:n 数据（data）：是描述客观事物的数值、字符、相关符号 等所有能够输入到计算机中并能被计算机处理的符号的总称 。 n 数据元素（data element）：数据中具有独立意义的个 体
2、，是数据的基本单位（也称为元素、记录、结点、顶点等 ）。 n 数据结构（data structures）：带结构的数据元素的集 合，结构指的是数据元素之间存在有关系。 n 存储结构：数据的逻辑结构在计算机中的表示或实现。 n 数据类型：是一个同类型值的的集合和定义在这个值集上 的一组操作的总称。 n 抽象数据类型（Abstract Data Type）：一个数据结构 加上定义在这个数据结构上的一组操作。习题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,
3、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+100 n(6)(f)O(n3)习题1.4:(1) 习题1.4:(2)设语句执行次数为k，则：n/2k0 即：n/2k-11 有：2k-1=10，下面程序段的时间复杂度是（ ）。for(i=10; ik) k+;else j+;A）O（log2n） B）O(n) C）O(nlog2n) D
4、）O(n2) 9.计算机算法是指( )。A)计算方法 B)排序方法 C)调度方法 D)解决问题的有限运算序列8.D 9.D 补充习题:10.数据的定义取决于数据的逻辑结构，而数据的实现取决于 数据的物理结构( )。A)正确 B) 不正确 11.下面说法错误的是（ ） A)算法原地工作的含义是指不需要任何额外的辅助空间B)在相同的规模n下，复杂度O(n)的算法在时间上总是优 于复杂度O(2n)的算法C)所谓时间复杂度是指最坏情况下，估算算法执行时间的 一个上界 D)同一个算法，实现语言的级别越高，执行效率就越低10.A 11.AD补充习题:判断1. 数据元素是数据的最小单位。( ) 2. 记录是
5、数据处理的最小单位。 ( )3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( ) 4. 算法的优劣与算法描述语言无关，但与所用计算机有关。( ) 5. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( ) 6. 算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言 来描述，则算法实际上就是程序了。( ) 7. 数据的物理结构是指数据在计算机内的实际存储形式。( ) 8. 数据结构的抽象操作的定义与具体实现有关。( ) 9. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结 构的独立。( ) 10. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计
6、算机的存储 结构. ( ) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.补充习题:语句频度与时间复杂度1.计算机执行下面的语句时,语句s的执行次数为: (n+3)(n-2)/2。for(i=l；i=i;j-)s; 2.下面程序段中带有下划线的语句执行次数的量级是( log2n2 ) i=n*nwhile (i!=1)i=i / 2; 3.下面程序段中带下划线的语句的执行次数的数量级是(nlog2n )。i=1;while( i=1; i- -） /语句1 n+1 x=x+1； /语句2 n for（j= n；j=i;j-） /语句3 n(n+3)/2y=y+1; /语句4 n(n+1)/2
