数据结构第二次课.ppt

第一章 绪 论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现* 1.4 算法和算法分析* 数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科 软件设计中如何组织数据？ －逻辑结构 计算机中如何存储和存取数据? －物理结构 如何对确定的数据集合进行操作？－操作方法 数据结构涵盖的内容 基本概念 数据类型— 一个值的集合和定义在这个值集上的一组操作的总称。在高级语言中指数据的取值范围及其上可进行的操作的总称 Q1 数据类型与抽象数据类型的区别？ 定义抽象数据类型有何意义？ 舍弃个别的,非本质的数据关系,抽出共同的,本质的数据关系, 研究共性特征。 使用与实现分离，实行数据封装和信息隐蔽，方便程序的维护、改错、升级和移植 是现代程序设计方法－面向对象程序设计方法设计思路的基本体现。 封装、继承和多态 Q2 抽象数据类型如何定义？ 例：给出自然数(Natural Number )的抽象数据类型定义。 Q3 抽象数据类型如何表示和实现？ 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 1.4 算法的描述和算法分析简介 1.4.1 算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列。 算法的描述方法： 自然语言 从0加到100 伪代码 Add（0，100） 流程图 （略） 程序代码 for（…） 1.4.3 算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量 1.数据逻辑结构包括___、___和____三种类型，树形结构和图形结构合称为___。 2.在线性结构中，第一个结点___前驱结点，其余每个结点有且只有___个前驱结点；最后一个结点___后续结点，其余每个结点有且只有___个后续结点。 3.在树形结构中，树根结点没有___结点，其余每个结点有且只有___个前驱结点；叶子结点没有___结点，其余每个结点的后续结点可以___。 4.在图形结构中，每个结点的前驱结点数和后续结点数可以___。 5.线性结构中元素之间存在___关系，树形结构中元素之间存在___关系，图形结构中元素之间存在___关系。 6.算法的5个重要特性是___、 ___、 ___、输入和输出。 7.算法可以用不同的语言描述，如果用C++或JAVA等高级语言描述，则算法实际上就是程序了。 8.数据结构、数据元素和数据项在计算机中的映射(或表示)分别称为存储结构、结点和数据域。 1.数据结构是一门研究非数值计算的程序设计问题中计算机的___以及它们之间的___和运算等的学科。 A.数据元素B.计算方法 C.逻辑存储D.数据映像 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K,R),其中K是___的有限集，R是K上的___有限集。 A.算法 B.数据元素 C.数据操作 D.逻辑结构 A.操作 B.映像 C.存储 D.关系 3.数据结构在内存中的表示是指___ 。 A.数据的存储结构 B.数据结构 C.数据的逻辑存储 D.数据元素之间的关系 4. 算法分析的两个主要方面是___ 。 A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 5.下面说法错误的是___ 。 A.算法原地工作的含义是指不需要任何额外的辅助空间 B.在相同的规模下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法。 C.所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界。 D.同一个算法，实现语句的级别越高，执行效率越低。 6. 以下说法正确的是___ 。 A.数据元素是数据的最小单位 B.数据项是数据的基本单位 C.数据结构是带结构的各数据项的集合 D.一些表面上很不相同的数据可以有相同的逻辑结构 附加题目： for(i=0;in;i++) for(j=0;ji;j++) for(k=0;kj;k++) s=s+i*k*j; 每课一帖：父子俩住山上，每天都要赶牛车下山卖柴。老父较有经验，坐镇驾车，山路崎岖，弯道特多，儿子眼神较好，总是在要转弯时提醒道：“爹，转弯啦！”有一次父亲因病没有下山，儿子一人驾车。到了弯道，牛怎么也不肯转弯，儿子用 尽各 种方法，下车又推又拉，用青草诱之，牛一动不动。到底是怎么