第一章（选择，填空）
数据是对客观事物的符号表示。
数据元素是数据集合中的一个实体，是计算机程序中加工处理的基本单位。
数据对象性质相同的数据元素的集合。
数据结构简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。
逻辑结构数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。分为：集合、线性结构（表、堆栈等）和非线性结构（树、图等）。
存储结构在计算机中对数据元素本身和相互间的关系的表示。
数据类型具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。
抽象数据类型基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。
算法是解决某个特定问题的一种方法或一个过程。具有五个特性：有穷性、确定性、可行性、输入、输出。
算法设计的要求正确性、可读性、健壮性、时间与空间效率。
第二章（选择题，算法设计题）
线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。
缺点 (1) 在做插入或删除元素的操作时，会产生大量的数据元素移动；
(2) 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；
(3) 线性表的容量难以扩充。
线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。对于每个数据元素不仅要表示它的具体内容，还要附加表示它的直接后继元素存储位置等信息。
不带头结点的单链表访问a节点，head，访问c节点，b ->next
带头结点的单链表访问a节点，head->next，访问c节点，b ->next
双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。
循环链表访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。循环链表并不适用于经常访问前驱结点的情况。
顺序表和链表的比较基于空间，顺序表的静态存储密度大，链表的动态存储空间小；基于时间，顺序表利于查询，链表的利于删除和插入。
算法设计：单链表的插入操作，实现将值为x的结点s插入到p结点之后。
insert(linklist *p, int x)
linklist *s;
if(!p)
return error;
s=malloc(sizeof(linklist));每句1分。
s->data=x;
s->next=p->next;
p->next=s;
单链表的删除操作，实现删除结点p
delete(linklist *p)
linklist *q;
if(!(p->next))
return error;
q=p->next;
p->next=q->next;
free(q);
第三章（选择题，算法设计题）
栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能**性表的一端进行。栈的特性：后进的元素先出去，“后进先出”。
栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。
队列特殊性在于限定插入**性表的一端进行，删除**性表的另外一端进行。注意点：空的条件： =队列长度计算： -上溢”与“下溢”：满时插入、空时删除；“假上溢”
循环队列将存储队列元素的一维数组首尾相接，形成一个环状。队列变为空或满，队头和队尾指针相等。
算法设计：1. 构造一个空队列：
void initqueue(sqqueue &q)
*)malloc(max_qsize*sizeof(qelemtype));
if(!exit(overflow);
2. 返回队列长度。
int queuelength(sqqueue q)
return (
3. 插入元素e为q的新的队尾元素。
status enqueue(sqqueue &q,qelemtype e)
if((return error;
return ok;
4. 删除q的队头元素。
status dequeue(sqqueue &q,qelemtype &e)
if(return error;
e=return ok;
第四章（选择题，解答题）
串是字符串的简称，是一个有穷字符序列。
空串串中没有任何字符，其串的长度为0。
空格串由空格字符组成的串。
子串、主串串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。
子串的位置子串在主串中第一次出现的第一个字符的位置。
两个串相等两个串的长度相等，并且各个对应的字符也都相同。
串的9个基本操作：
1）赋值串。
2）联接串strcat（s1, s2）
3）计算串长度 strlen（s1）
4）求子串substr（s1, i, j）
5）比较串的大小 strcmp(s1, s2)
6）插入串insert(s1, i, s2)
7）删除串delete(s1, i, j)
8）子串定位 index（s1, s2）
9）置换串replace（ s1, i, j ,s2 ）
朴素的模式匹配思想。
最好的情况：第i次匹配成功，(i－1)次前匹配失败都在第一个字符，所以需要比较的总次数为： (i – 1 ) m。时间复杂度：o(n+m)
最坏的情况：最坏情况，第i次匹配成功，(i－1)次前匹配失败都在最后一个字符，所以需要比较的总次数为：i x m。时间复杂度：o(nm)
第六章树（选择题，画图题，算法设计）
树是一种常用的非线性结构。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n=0，则称为空树；
1）否则，有且仅有一个特定的结点被称为根，2）当n>1时，其余结点被分成m（m>0）个互不相交的子集t1，t2，..tm，每个子集又是一棵树。
结点数据元素的内容及其指向其子树根的分支统称为结点。
结点的度结点的分支数，也即子树的个数。
树的度树中所有结点度的最大值。
终端结点（叶子） 度为0的结点。
非终端结点（分支结点） 度不为0的结点。
内部结点除根结点外的分支结点。
路径及其长度若树中存在一个结点序列k1，k2…kj，使得ki是ki+1(1<=i二叉树与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。
二叉树的性质 （1）在二叉树的第i层上最多有2i-1个结点（i≥1）。
2）深度为k的二叉树最多有2k-1个结点（k≥1）。
3）对于任意一棵二叉树，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。
完全二叉树一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应。
二叉树的遍历方式一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。第一类可分为：先序遍历；中序遍历；后序遍历。
算法设计二叉树的前、中、后三种遍历实现。
先序遍历。void preordertr**erse(btnode *t)
if (t!=null)
中序遍历。void inordertr**erse(btnode *t)
if (t!=null)
后序遍历。void postordertr**erse(btnode *t)
if (t!=null)
树转换成二叉树。
加虚线在树的每层按从“左至右”的顺序在兄弟结点之间加虚线相连。
去连线除最左的第一个子结点外，父结点与所有其它子结点的连线都去掉。
旋转将树顺时针旋转450，原有的实线左斜。
整型将旋转后树中的所有虚线改为实线，并向右斜。
二叉树转换成树。
加虚线若某结点i是其父结点的左子树的根结点，则将该结点i的右子结点以及沿右子链不断地搜索所有的右子结点，将所有这些右子结点与i结点的父结点之间加虚线相连。
数据结构总结
一 绪论。1 数据结构 数据结构是一门讨论 描述现实世界实体的数学模型 非数值计算 及其上的操作在计算机中如何表示和实现 的学科。具有相同特征的数据元素的集合，如果在这些数据元素之间存在一种或多种特定的关系，则称为一种数据结构。2 建立模型 3 数据 客观对象的符号表示 数据元素 数据的基本单位，在...
数据结构总结
第四章排序程序设计初步。本章介绍线性表的一个主要应用 排序，讲解了排序相关的基本概念和排序算法的一般思路，包括直接插入排序 简单选择排序 冒泡排序以及静态链表插入排序，并给出了其程序设计源码，通过程序设计技巧和线性表的联合来体会数据结构的作用。计算级程序设计中，最常用的一个功能就是对数据的排序，因为...
数据结构总结
目录。数据结构学习笔记 2 1.栈和队列 2 应用举例 2 1.1进制转换。2 1.2括号匹配的检验 3 1.3行编辑程序 4 1.4迷宫求解 5 1.5表达式求值 7 2.串 10 应用举例 10 2.1串的模式匹配算法 10 2.2文本编辑 12 3.树和二叉树 14 4.图 14 应用举例 1...