自學考数据结构导论.doc

数据结构导论复习 概论 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 数据：凡能被计算机存储、加工处理的对象。 数据元素是数据的基本单位，在程序中作为一个整体而加以考虑和处理, 又称元素，顶点，结点，记录。 数据项：数据项组成数据元素, 又叫字段或域，它是数据的不可分割的最小标识单位。 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 逻辑结构需要注意的几点： 逻辑结构与数据元素本身的内容无关 逻辑结构与数据元素相对位置无关 逻辑结构与所有结点的个数无关 四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 运算是在逻辑结构层次上对处理功能的抽象 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。(插入，删除，更新) 引用型运算：不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。(查找，读取) 基本运算的含义？ 假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。数据结构涉及数据表示和数据处理两个方面 存储结构的含义和四种基本存储方式的基本思想？ 存储结构指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 存储结构包括三部分： 存储结点，每个存储结点存放一个数据元素。 数据元素之间关联方式的表示，也就是逻辑结构的机内表示。 附加设施，如方便运算实现而设置的“哑结点”等。 四种基本存储方式： 顺序存储方式：每个存储结点只含一个数据元素。所有存储结点相继存放在一个连续的存储区里。用存储结点间的位置关系表述数据元素之间的逻辑关系。 链式存储方式：每个存储结点不仅含有一个数据元素，还包含一组指针。每个指针指向一个与本结点有逻辑关系的结点，即用附加的指针表示逻辑关系。 索引存储方式：每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引指示各存储结点的存储位置或位置区间端点。 散列存储方式：每个结点含一个数据元素，各个结点均匀分布在存储区里，用散列函数指示各结点的存储位置或位置区间端点。 12．运算实现与运算的联系与区别？ 运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被机械地求解。 算法的类型有： 运行终止的程序可执行部分：又称为程序 伪语言算法：不可以直接在计算机上运行，但容易编写和阅读。 非形式算法：用自然语言，同时可能还使用了程序设计语言或伪语言描述的算法。 1．最坏情况时间复杂性和平均时间复杂性的概念？ 最坏情况时间复杂性也称为最坏时间复杂度，是指算法在所有输入下的计算量的最大值作为算法的计算量； 平均情况时间复杂性也称为平均时间复杂度，是指算法在所有输入下的计算量的加权平均值作为算法的计算量； 1．空间复杂性指的是一个算法除输入数据占存储空间之外所需要的附加存储空间的大小。 1．算法的性质(算法质量评价指标)：正确性、易读性、健壮性和高效率。 正确性：能够正确实现处理要求 易读性：易于阅读和理解，便于调试，修改和扩充 健壮性：当环境发生变化，算法能够适当做出反应或处理，不会产生不需要的运行结果 高效率：达到所需要的时空性能。 1. 如何确定一个算法的时空性能，称为算法分析 时空性能是指该算法的时间性能和空间性能，前者是算法包含的计算量，后者是算法需要的存储量。 算法在给定输入下的计算量： 根据该问题的特点选择一种或几种操作作为“标准操作”。 确定每个算法在给定输入下共执行了多少次标准操作，并将此次数规定为该算法在给定输入下的计算量。 若无特殊说明，将默认以赋值语句作为标准操作。估算的方法有：最坏时间复杂度和平均时间复杂度。 算法的输入规模（问题规模）是指作为该算法输入的数据所含数