《7算法与数据结构辽宁科技大学》由会员分享，可在线阅读，更多相关《7算法与数据结构辽宁科技大学（81页珍藏版）》请在金锄头文库上搜索。
1、 算法与数据结构算法与数据结构 公共基础第一部分 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 本章考核内容约占13%，主要包括一下几个方面： l算法复杂度 l栈、队列、线性链表的基本概念 l树的结点计算和遍历 l排序的最坏次数计算 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点1 1 算法的基本概念算法的基本概念 1.算法是指解题方案的准确而完整的描述。 对于一个问题，如果可以通过一个计算机程序，在有限的 存储空间内运行有限的时间而得到正确的结果，则称这个问题 是可解的。 2.算法特征： 1)可行性 2)确定性 3)有穷性：即算法必须能在执行有限个步骤
2、之后终止 4)拥有足够的情报 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点1 1 算法的基本概念算法的基本概念 【2008年4月】：算法的有穷性是指（ ） A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用 答案 A 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点1 1 算法的基本概念算法的基本概念 3.算法的基本元素 一个算法通常由两种基本要素组成：一是对数据对象的运 算和操作；二是算法的控制结构。 l 一般的计算机系统中，基本运算和操作包括以下4类： 算术运算：加、减
3、、乘、除等运算； 逻辑运算：与、或、非等运算； 关系运算：等于、不等于、大于、小于等运算； 数据传输：赋值、输入、输出等操作。 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点1 1 算法的基本概念算法的基本概念 3.算法的基本元素 l 算法的控制结构 算法各操作之间的执行顺序称为算法的控制结构。 算法的控制结构包括：顺序、选择（分支）和循环。 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点1 1 算法的基本概念算法的基本概念 4.算法设计的基本方法 计算机解题的过程实际上是在实施某种算法,这种算法称 为计算机算法。 列举法； 归纳法； 递推； 递
4、归； 减半递推技术； 回溯法。 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点2 2 算法的复杂度算法的复杂度 算法的复杂度包括算法时间复杂度和算法空间复杂度。 1.算法时间复杂度 算法时间复杂度是指执行算法所需要的计算工作量。 在度量一个算法的工作量时，用算法在执行过程中所需基 本运算的执行次数来度量算法的工作量。 分析算法工作量的方法：平均性态和最坏情况复杂性。 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点2 2 算法的复杂度算法的复杂度 2.算法空间复杂度 一个算法的空间复杂度，一般是指执行这个算法所需要的 内存空间大小。 一个算法所占用
5、的存储空间包括算法程序所占的空间、输 入的初始数据所占的空间以及算法执行过程中所需要的额外空 间。 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点2 2 算法的复杂度算法的复杂度 【2005年9月】： 算法复杂度主要包括时间复杂度和_复杂度。 【2006年9月】：下列叙述中正确的是（ ） A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对 答案 D 空间 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点2 2 算法的复杂度算法
6、的复杂度 【2007年4月】：下列叙述中正确的是（ ） A）算法的效率只与问题的规模有关，而与数据的存储结构无 关 B）算法的时间复杂度是指执行算法所需要的计算工作量 C）数据的逻辑结构与存储结构是一一对应的 D）算法的时间复杂度与空间复杂度一定相关 答案 B 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点3 3 数据结构数据结构 1.基本概念 1)数据：描述客观事物的数、字符以及所有能输入到计算 机中并被计算机程序加工处理的符号的集合。 2)数据元素：数据的基本单位，即数据集合中的个体。 有时一个数据元素由若干个数据项组成，在这种情况下，将数 据元素称为记录，由记录所
7、组成的线性表为文件。 3)数据项：具有独立意义的最小数据单位。 4)数据对象：具有相同特性的数据元素的集合，是数据的 子集。 5)结构：指数据元素之间的前后件关系。 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点3 3 数据结构数据结构 1.基本概念 6)数据结构：指相互关联的数据元素的集合。 数据结构包含两方面信息：一是表示数据元素的信息；二 是表示各数据元素之间的前后件关系。 例如，描述一年四季的季节名春、夏、秋、冬，可以作为 季节的数据元素；在考虑一年4个季节的顺序关系时，则“春” 是“夏”的前件，而“夏”是“春” 的后件等。 公共基础第一部分公共基础第一部分算法
8、与数据结构算法与数据结构 考点考点3 3 数据结构数据结构 2.数据的逻辑结构 在以上所述的数据结构中，数据元素之间的前后件关系是 指它们的逻辑关系，而与它们在计算机中的存储位置无关。因 此，上面所述的数据结构实际上是数据的逻辑结构。 1)概念： 所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的 数据结构。 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点3 3 数据结构数据结构 2.数据的逻辑结构 2)表示： l图形表示：集合、线性、树、图 集合 线性 树 图 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点3 3 数据结构数据结构 2.数据的逻
9、辑结构 2)表示： l二元关系表示 数据的逻辑结构有两个要素：一是数据元素的集合，通常 记为 D； 二是D上的关系，它反映了D中各数据元素之间的前 后件关系，通常记为 R，即一个数据结构可以表示成： B = (D，R) 其中B表示数据结构。为了反映D中各数据元素之间的前后件关 系，一般用二元组来表示。 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点3 3 数据结构数据结构 2.数据的逻辑结构 2)表示： l二元关系表示 例如，一年四季的数据结构可以表示成： B=（D，R） D=春，夏，秋，冬 R=（春，夏），（夏，秋）（秋，冬） 公共基础第一部分公共基础第一部分算法与数
10、据结构算法与数据结构 考点考点4 4 数据的存储结构数据的存储结构 1.概念： 数据的逻辑结构在计算机存储空间的存放形式称为数据的 存储结构。 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点4 4 数据的存储结构数据的存储结构 2.存储形式： 数据元素之间的关系在计算机中有两种不同的表示方法： 顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺 序存储结构和链式存储结构。 顺序映像的特点是借助元素在存储器中的相对位置来表示 数据元素之间的逻辑关系；非顺序映像的特点是借助指示元素 存储地址的指针(Pointer)表示数据元素之间的逻辑关系。 公共基础第一部分公共基础第
11、一部分算法与数据结构算法与数据结构 考点考点4 4 数据的存储结构数据的存储结构 注意： 数据元素在计算机存储空间中的位置关系可能与逻辑关系 不同，数据的逻辑结构可以表示成多种存储结构。采用不同的 存储结构，其数据处理的效率是不同的。 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点4 4 数据的存储结构数据的存储结构 【2005年4月】：数据的存储结构是指（ ） A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示 答案 D 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点4 4 数
12、据的存储结构数据的存储结构 【2005年9月】下列叙述中正确的是（ ） A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结 构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结 构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结 构影响数据处理的效率 答案 D 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点4 4 数据的存储结构数据的存储结构 【2007年9月】下列叙述中正确的是（ ） A）数据的逻辑结构与存储结构必定是一一对应的 B）由于计算机存储空间是向量式的存储结构，因此，数据 的存储结构一定
13、是线性结构 C）程序设计语言中的数组一般是顺序存储结构，因此，利 用数组只能处理线性结构 D）以上三种说法都不对 答案 D 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点4 4 数据的存储结构数据的存储结构 【2008年9月】下列叙述中正确的是（ ） A）顺序存储结构的存储一定是连续的，链式存储结构的存 储空间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非 线性结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有 序表 D）链式存储结构比顺序存储结构节省存储空间 答案 A 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点
14、5 5 线性结构与非线性结构线性结构与非线性结构 根据数据结构中各数据元素之间前后件关系的复杂程度， 将数据结构分为两大类型：线性结构与非线性结构。 如果一个非空的数据结构满足两个条件： 一是有且只有一个根结点； 二是每一个结点最多有一个前件，也最多有一个后件，则 称该数据结构为线性结构。线性结构又称线性表。 注意：在一个线性结构中插入或删除任何一个结点后还应 是线性结构。 如果一个数据结构不是线性结构，则称为非线性结构。 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点6 6 线性表的基本概念线性表的基本概念 线性表是最简单，最常用的一种数据结构。线性表由一组 数据元素
15、构成的有限序列，如一年的四个季节。 线性表中结点的个数n称为线性表的长度。n=0时，称为空 表。 非空线性表有如下一些结构特征： 有且只有一个根结点，它无前件； 有且只有一个终端结点，它无后件； 除根结点与终端结点外，其他所有结点有且只有一个 前件，也有且只有一个后件。 公共基础第一部分公共基础第一部分算法与数据结构算法与数据结构 考点考点7 7 线性表的顺序存储线性表的顺序存储 在计算机中存放线性表的一种最简单的方法是顺序存储， 也称为顺序分配。用顺序存储结构存储的线性表称作顺序表。 线性表的顺序存储结构具有以下两个基本特点： 1)线性表中所有元素所占的存储空间是连续的； 2)线性表中各数据元素在存储空间中是按逻辑顺序依次存 放的。 注意：在线性表的顺序存储结构中，其前后件两个元素在 存储空间中是紧邻的，且前件元素一定存储在后件元素
