2010公共基础知识-数据结构讲诉.pptVIP

计算机等级考试公共基础知识 计算机二级考试公共基础知识大纲 数据结构与算法 程序设计基础 软件工程基础 数据库设计基础 计算机二级考试公共基础知识试卷分析 一、基本数据结构与算法 算法 ⒈ 算法的基本概念 2.算法的基本特征 3. 算法的表示 4. 算法的要素 5. 算法的评价 算法的定义 对解题方案准确而完整的描述称为算法。 算法与计算机程序 算法____是一组逻辑步骤 程序——用计算机语言描述的算法 算法举例：n个数排序 4. 算法的两个基本要素： 5. 算法评价 评价一个算法优劣的主要标准是算法的执行效率和存储需求： 时间复杂度：执行这个算法所需要的计算工作量 一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量 空间复杂度：执行这个算法所需要的内存空间 算法在执行过程中临时占用的存储空间 时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分 一、算法 对解题方案准确而完整的描述称为算法。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的两个要素： 一是对数据对象的运算和操作；二是算法的控制结构。 算法的特征： 有穷性 、确定性 、可行性、 输入、 输出 算法评价： 时间复杂度：执行这个算法所需要的计算工作量 空间复杂度：执行这个算法所需要的内存空间 算法习题: (1) 算法一般都可以用哪几种控制结构组合而成____。 A. 循环、分支、递归 B. 顺序、循环、嵌套 C. 循环、递归、选择 D. 顺序、选择、循环 (2)算法中，对需要执行的每一步操作，必须给出清楚、严格的规定，这属于算法的 （07年4月） A）正当性 B）可行性 C）确定性 D）有穷性 (3) 在计算机中，算法是指______。 A. 查询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法 (4)下列叙述中正确的是 （07年4月） A)算法的效率只与问题的规模有关，而与数据的存储结构无关 B)算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是一一对应的 D)算法的时间复杂度与空间复杂度一定相关 (5)算法的有穷性是指 (08年4月) A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用 (6) 算法的时间复杂度是指______。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数 (7)下列叙述中正确的是 (06年9月) 　　A）一个算法的空间复杂度大，则其时间复杂度也必定大 　　B）一个算法的空间复杂度大，则其时间复杂度必定小 　　C）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对 二、数据结构 计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。 二. 数据结构 1. 逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 例： 1. 一年四季的数据结构 B=(D,R) D={春，夏，秋，冬} R={(春，夏) ,(夏，秋),(秋，冬)} 2. 家庭成员的数据结构 B=(D,R) D={父亲，儿子，女儿} R={(父亲，儿子) ,(父亲，女儿)} 常见的逻辑结构有： 线性结构、树形结构和图形结构。 2. 存储结构（物理结构） 计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。 如：一年四季 家庭成员