数据结构与算法基础知识总结
1 算法
算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：
（1）可行性；
（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；
（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；
（4）拥有足够的情报。
算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。
基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
2 数据结构的基本基本概念
数据结构研究的三个方面：
（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；
（3）对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含：
（1）表示数据元素的信息；
（2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件： （1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
3 线性表及其顺序存储结构
线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
解题思路
多代入法
二叉树
度
叶子结点就是没有孩子的结点，其度为0，度为二的结点是指有两个子数的结点。
注意树的度 和 图的度 区别
叶子结点
二叉排序树
完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树； 最优二叉树（就是哈弗曼树）
平衡二叉树
平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。
满二叉树
满二叉树——除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.
本题主要考查一些特殊二叉树的性质。
若二叉树中最多只有最下面两层的结点度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树，因此在完全二叉树中，任意一个结点的左、右子树的高度之差的绝对值不超过1。
二叉排序树的递归定义如下：二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：
(1)若左子树不空，则左子树上所有结点的值均小于根结点的值；
(2)若右子树不空，则右子树上所有结点的值均大于根结点的值；
(3)左右子树也都是二叉排序树。
在n个结点的二叉树链式存储中存在n+1个空指针，造成了巨大的空间浪费，为了充分利用存储资源，可以将这些空链域存放指向结点在遍历过程中的直接前驱或直接后继的指针，这种空链域就称为线索，含有线索的二叉树就是线索二叉树。
最优二叉树即哈夫曼树。
1 [试题分类]：数据结构与算法
1.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。
A.操作
B.存储映像
C.关系
D.数据元素
答案:C
题型:单选题
知识点:1.2 基本概念和术语
难度:1
2.一般而言，最适合描述算法的语言是( )。
A.自然语言
B.计算机程序语言
C.介于自然语言和程序设计语言之间的伪语言
D.数学公式
答案:C
题型:单选题
知识点:1.4 算法和算法分析
难度:1
3．在下列序列中，不是线性表的是( )。
A. (‘a’, ‘b’)
B. (a, b)
C. (‘AB’, ‘CD’)
D. (‘a’, b)
答案:D 2 题型:单选题
知识点:2.1 线性表的类型定义
难度:2
4.对于顺序表的优缺点，以下说法错误的是( )。
A.插入和删除操作较方便
B.可以方便地随机存取表中的任一结点
C.无需为表示结点间的逻辑关系而增加额外的存储空间
D.由于顺序表要求占用连续的空间，存储分配只能预先进行
题型:单选题
知识点:2.2线性表的顺序表示和实现
难度:2
5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( )。
A. s->next=p->next;p->next=s;
B. p->next=s->next;s->next=p;
C. q->next=s;s->next=p;
D. p->next=s;s->next=q;
题型:单选题
知识点:2.3线性表的链式表示和实现
难度:2
6.若某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。
A.单链表
B.带头结点的单链表
C.单循环链表 3 D.带头结点的双循环链表
题型:单选题
知识点:2 线性表
难度:3
7.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是( )。
数据结构与算法
1.1 算法
1．算法的基本概念
算法是指解题方案的准确而完整的描述。通俗的说，算法就是计算机解题的过程。算法不等于程序，也不等于计算方法，由于受到计算机系统运行环境的限制，程序的编制不可能优于算法的设计。
2．算法的基本特征
① 确定性: 算法中每一步骤都必须有明确定义，不允出现歧义。
② 有穷性: 算法必须能在有限的时间内执行完成，即能在执行有限个步骤后终止。
③ 可行性: 算法原则上能够精确地执行。
④ 拥有足够的情报: 算法有零个或多个输入、至少有一个输出。
3．算法的基本要素
一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。
·运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。
·三种基本控制结构：顺序结构、选择结构、循环结构。
4．算法的复杂度
① 算法时间复杂度：指执行算法所需要的计算工作量。即算法执行过程中所需要的基本运算次数。通常用平均性态和最坏情况复杂度衡量算法的时间复杂度。
② 算法空间复杂度：执行算法时所需要的存储空间。
1.2 数据结构的基本概念
1．数据结构
所谓数据结构是指相互有关联的数据元素的集合。主要研究以下三个方面：
① 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。
② 在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。
③ 对各种数据结构进行的运算。
2．逻辑结构
① 表示数据元素本身的信息。
② 表示各数据元素之间的前后件关系(指数据元素间的逻辑关系，与存储位置无关)。
3．存储结构(物理结构)
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据物理结构。常用的数据存储结构有顺序、链式、索引等。
4．线性结构与非线性结构
根据数据结构中各元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空数据结构满足下列两个条件，则称为线性结构，也称为线性表。 如果不是线性结构，则为非线性结构。
