《算法与数据结构考研试题精析》笔记(1) - 概论
基础概念以及性质
数据的最小单位是数据项。
数据的基本单位是数据元素。
数据对象：性质相同的元素的集合。
数据结构是带有结构的数据元素的集合。
在定义ADT时，除了数据对象和数据关系之外，还需说明基本操作。
ADT，全称为“抽象数据类型”，是指一个数学模型以及定义在该模型上的一组操作。“抽象”的意义再与数据类型的数学抽象性。 ADT = (D, S, P). Data Structure = (D, S).
数据结构中，逻辑上可分为两类：线性结构和非线性结构。
数据的存储结构 = 数据的物理结构。它是数据结构在计算机中的表示。
数据的物理结构包括数据元素表示和数据元素间关系的表示。
多形数据类型：其值成分不确定的数据类型。
对于多型数据类型而言，不论其元素具有何种特性，元素之间的关系相同，基本操作也相同。从抽象数据类型的角度看，具有相同的数学抽象性，故称之为多形数据类型。
连续存储设计时，存储单元的地址一定连续。
有序表属于逻辑结构，顺序表、哈希表、单链表不属于逻辑结构。
逻辑结构，在清华的教材里面称为“结构”。 逻辑结构的四种类型，集合结构、线形结构、树状结构和网络结构。 下面摘自此博客： 当一个结构，如数组、链表、树、图，在逻辑结构中只有一种定义，而在物理结构中却有两种选择，那么这个结构就属于逻辑结构； 相反，当此结构在原有基础上加上了某种限定，使得其在物理结构中只有一种定义，那么这个结构就属于物理（存储）结构； 逻辑结构和存储结构的区别点在于：数据的逻辑结构是独立于在计算机中的存储结构的，数据的存储方式有多种不同的选择。例如栈是一种逻辑结构，它可以用顺序存储也可以用链式存储。 而数据结构是既可以描述逻辑结构又可以描述存储结构和数据运算，必须包含以上三种元素。所以像顺序表、哈希表、单链表都是数据结构。
【错误说法】每种数据结构都应具备三种基本运算：插入、删除和查找。
反例一：多维数组，就没有插入和删除。 反例二：栈和队列，一般不需要查找(严格来说，是不能查找的，因为逻辑上其访问点被严格限制在线性表的端点)
数据的逻辑结构：数据的数据元素之间的逻辑关系。
数据结构的概念包括：数据之间的逻辑结构、数据在计算机中的存储方式、数据的运算。
数据结构的抽象操作的定义与具体实现无关。
在顺序存储结构中，任何时候都不会存储数据结构中元素之间的关系。
链式存储结构中，就会存储数据结构中数据元素元素之间的关系。
算法的优劣，与算法描述语言、具体的计算机都无关。(换一种说法可为“独立于…”)
哈夫曼树、平衡二叉树都是数据的逻辑结构。(属于树形结构)
一个数据结构在计算机中的映像(表示)称为存储结构。
数据的逻辑结构指的是数据的组织形式，即数据元素之间逻辑关系的总体，而逻辑关系是数据元素之间的关联方式(或称“邻接关系”)。
数据结构结构是研讨数据的数据的逻辑结构和物理结构(存储结构)，以及他们之间的相互关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。
抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。
【问题】todo:是否在log_m{n}在考试的时候都写成log_2{n}？[北京工业大学2005、二、1]
上述两者有如下关系：
，他们只相差一个常数。所以等规模。
算法
算法的时间复杂度取决于问题的规模和待处理数据的初态。
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外算法还具有下列5个重要特性：
- 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。
- 确定性(也可以叫做"无二义性")：算法每一条指令必须有确切含义；在任何情况下，算法只有唯一一条执行路径，即对于相同的输入只能得出相同的输出；
- 可行性：所有操作可以通过已经实现的基本运算执行有限次来实现；
- 零个或多个的输入
- 一个或多个的输出
“好”的算法应考虑以下目标：
- 正确性
- 可读性
- 健壮性
- 效率与低存储量需求
时空复杂度
在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2^n)的算法。
上句话是正确的，原因转自此网站，如下： 此句中是指算法的时间复杂度，不要想当然认为是程序（该算法的实现）的具体执行时间，而赋予n—个特殊的值。时间复杂度为O(n)的算法，必然总是优于时间复杂度为O(2n)的算法。
下面算法的时间复杂度为O(n^0.5).
int suanfa3(int n) {
int i = 1, s = 1;
while (s < n) s += ++i;
return i;
}
s的大小变化：1->3->6->10->… 表达式为
.s
汉诺塔递归中，假设碟子的个数为n，则时间复杂度为O(2^n).
Tips
关于(D, S)
D为Data，S为Structure，D为数据元素的有限集，S为D上关系的有限集。Data意为数据，Structure意为结构。在数据结构中结构的定义如下：数据元素相互之间的关系称为结构。故而S具体代表着什么也就不奇怪了。
(D, S, P)在不同的教材里面，可能会使用不同的字母表示。比如西南交通大学中，为(D, R, P).