绪论

建议应用的语言

C语言或C++

c语言语法

只需写出一个或多个可以解决问题的有着清楚接口描述的函数即可

时间复杂度分析

时间复杂度衡量算法的计算量
常用时间复杂度比较
O(1)\leq O(\log_2(n)) \leq O(n)\leq O(n\log_2(n)) \leq O(n^2)\leq O(n^3)\leq ...\leq O(2^n)
在计算时间复杂度时，将最坏的情况用作时间复杂度度量

算法的五大特性

计算机算法是指解决问题的步骤序列
算法必须有五个特征
  1. 有穷性：有限步之后结束
  2. 确定性：每一步无二义
  3. 输入
  4. 输出
  5. 可行性：算法中的所有操作都必须通过已经实现的基本操作进行运算，并在有限次内实现

数据结构三要素

数据结构的三要素分为逻辑结构，存储结构和数据的运算

逻辑结构

数据的逻辑结构是对数据之间关系的描述，与数据的存储结构无关，是独立于计算机的，同一种数据结构可以有多种存储结构，分为线性结构和非线性结构两种。

物理结构

数据的物理结构又称为存储结构，是数据的逻辑结构在计算机中的表示。有如下四种常用的存储方法
  1. 顺序存储（顺序表）
  2. 链式存储
  3. 索引存储
  4. 散列存储

Master定理

master定理

天勤数据结构习题及错题

【例1】
【答案】 A
栈衡量的是逻辑关系
双向链表是链式存储
散列算法是散列存储
线索树是在链式存储结构上对树进行线索
循环队列是建立在顺序存储结构上的
【例2】
顺序表属于线性表的一部分，是顺序存储方法的代表
散列表是散列存储结构，属于物理结构
单链表属于链式存储结构
有序表侧重于表中数据按顺序排列
【答案】 C
【例3】
涉及了递归函数的时间复杂度求法
f(n)=2f(n/2)+n
f(n/2) = 2f(n/4)+n/2
带入，得
f(n)= 4f(n/4)+2n
最后可得到
f(n) = 2^kf(n/(2^k))+kn
当k=\log_2(n) 时，即n/(2^k)=1 时，此时f(1)=1
f(n) = nf(1)+\log_2(n)\cdot{n}=n+n\log_2(n)=n\log_2(n)
【答案】[InvalidCharacterError: "S<" did not match the Name production]

王道数据结构及错题

【例1】
【答案】 D
抽象数据类型ADT描述了数据的逻辑结构和抽象运算，通常用（数据对象，数据关系，基本操作集）这样的三元组表示，从而构成一个完整的数据结构定义。
【例2】
【答案】 A
链式存储设计中，结点内的存储单元地址一定连续，结点间不一定连续
【例3】
数据的运算也是数据结构的一个重要方面。
【答案】
对于两种不同的数据结构，它们的逻辑结构和物理结构完全有可能相同。比如二叉树和二叉搜索树。
【例4】
【答案】
时间复杂度衡量执行时间
问题规模：就是指你算法中所涉及的局部来看数据量大的大小。如：求100以内还是1000以内的素数。
算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始。
【例5】
【答案】D
想一下归并法，在前一个最大元素小于后一个最小元素的时候或者前一个最小元素大于后一个最大元素时取到极值
【例6】
【答案】A
IV是一个有争议的说法，我们认为是对的。
算法原地工作是指算法所需的辅助空间是常量。