第一章

1、数据元素是数据的基本单位；数据项是数据的不可分割的最小单位。

2、数据结构：4种基本结构为：集合， 线性结构，树状结构，图状结构或网状结构 DS 组成：逻辑结构（结构定义中的关系描述是数据元素之间的逻辑关系），物理结构（数据结构在计算机中的表示）;常用的逻辑结构分为四种：线性结构、层次/树形结构、网状/图结构、集合结构

3、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象。由此得到两种不同的存储结构：顺序存储结构和链式存储结构

4、计算算法的时间复杂度

5、数据的四种基本存储方法：顺序、链式、索引、散列存储方法

6、算法的五个重要特征：有穷、确定、可行性、有输入、有输出。算法的设计原则：正确、可读、健壮性、高效率与低存储量需求

7、给出一个小程序计算算法的时间复杂度

8、O(1) ≦O(log2n) ≦ O(n) ≦ O(nlog2n) ≦ O(n2) ≦ O(n3) ≦… ≦ O(nk) ≦ O(2n)

9、算法执行时间的增长率和 f(n) 的增长率相同，T (n) = O(f(n)) ，称T (n) 为算法的(渐近)时间复杂度；空间复杂度是指计算机执行操作时所占的内存开销规模，S(n) = O(g(n)) 表示算法执行所需存储量的增长率与g(n)的增长率相同

第二章

1、单链表逻辑存储结构、有无头判断空的条件

第三章

入栈顺序 指针指向 栈与队列的特点 队列的顺序存储 循环队列 （r-f+m）/%m

第四章

Subtr(“taiyuan”,3,4) 执行操作：从第三个数开始依次取出四个元素 结果iyua

第五章

1、有一个5行6列的数组，以（行）列为主序的顺序存储，基地址为20xx，每个元素占有两个存储单元，问3行4列 2034

2、稀疏矩阵三元组表示法

第六章

1、二叉树的基本性质

2、深度为k的满二叉树有2-1个结点，第K层上有2kK?1个结点

3、所有度为2的结点跟所有度为0的结点的关系 N0?N2?1

4、二叉树先、中、后遍历序列 由先中序列画出二叉树，在后序遍历写出遍历序列

5、满、完全二叉树的概念

6、赫夫曼树（最优二叉树）的编码 构造 求带权路径长度 （只有度为0和度为2的结点） 空链域 叶子结点

7、线索二叉树

8、森林 先中遍历的序列 将森林转化为二叉树

9、

10、程序题

递归算法：先、中、后序遍历

先序遍历：void Preorder (BiTree T)

{ // 先序遍历二叉树

if (T) {

Visit(T->data);

Preorder(T->lchild);

Preorder(T->rchild); }

}// Preorder

中序遍历：void InOrder (BiTree T ) {

if ( T ) {

InOrder ( T->lchild ); // 遍历左子树

Visit( T->data);

InOrder ( T->rchild ); // 遍历右子树

}

}// InOrder

后序遍历：void PostOrder (BiTree T ) {

if ( T ) {

PostOrder(T->lchild ); // 遍历左子树

PostOrder(T->rchild ); // 遍历右子树

Visit( T->data);

}

}// PostOrder

2、二叉树的深度算法

int Depth (BiTree &T ){ // 返回二叉树的深度

if ( !T ) depthval = 0;

else {

depthLeft = Depth( T->lchild );

depthRight= Depth( T->rchild );

depthval = 1 + (depthLeft > depthRight ?

depthLeft : depthRight);

}

return depthval;

}// Depth

3、假设有顺序表A，它由n个数据元素，调整顺序表，使得左边所有元素小于零，右边所有元素大于零

4、void adjust_sq(SqList &LA) {

InitList_Sq(LB);

n=LA.length; x=0;y=n-1

for (i = 0; i <n; i++)

if(LA.elem[i]<0){

LB.elem[x]=LA.elem[i];x++;} //前置

else {LB.elem[y]=LA.elem[i]; y--; }

for(i=0;i<n;++i)LA.elem[i]=LB.elem[i];

DestroyList(LB);

} // adjust_sq

4、队列管理：链队列实现

5、课本P163程序（C语言）

 

第二篇：数据结构总结

总结：

第一章 绪论

1、数据结构的概念

数据、数据元素、数据对象、数据项、数据结构

2、逻辑结构

线性结构、树形结构、图形结构、集合结构

3、抽象数据类型 ADT

概念、操作（初始化、插入、删除、定位）

4、算法分析

时间复杂度（顺序、条件（if…else）、循环（for while））

空间复杂度

第二章 线性表

1、概念

特点、抽象数据类型

2、线性表的顺序表示

构造空表、求表长、判断表空、取指定位置元素、表元素的插入、删除

3、线性表的链式表示

单链表 head、双链表next prior （插入、删除）

循环链表 双循环链表

若要删除表尾元素或者在最后一个元素后插入一个元素 双循环链表>带尾指针的循环链表

第三章 栈和队列

1、栈的性质

2、顺序栈、链栈（top、base）

共享栈

3、队列性质

4、顺序队列、链队列（rear front）

5、循环队列（防止假溢出）

第四章 串

1、概念

子串 主串 串相等 子串位置

非平凡子串

2、操作

串比较 求串长 求子串 串联

串替换

3、串的模式匹配

next nextval

第五章 数组和广义表

1、数组类型

一维 二维 多维

2、顺序结构

行优先 列优先

特殊矩阵：对称、三角、稀疏（三元组、转置）

3、广义表

表头head 表尾tail 深度 广度

第六章 树

1、树的性质

2、二叉树的性质

五个性质、完全二叉树、满二叉树

3、顺序结构

4、链式结构

1）二叉链表

2）三叉链表

5、遍历：先序、中序、后序

6、线索化二叉树

7、赫夫曼树 赫夫曼编码

第七章 图

1、概念

有向图 无向图 连通图 强连通图

2、存储方式

顺序结构：邻接矩阵

链式结构：邻接表

3、遍历

深度、广度

4、应用

1）最小生成树（老普 老克）

2）AOV 拓扑排序

3）AOE 关键路径（最长）

4）最短路径：老迪

第九章 查找 路径 边 弧 顶点

1、ASL

2、静态查找表

顺序、有序（折半 high low mid）、索引（块）

3、动态查找表

二叉排序树

平衡二叉树（LL RR LR RL）

4、散列表

创建：直接定址法、除留余数法

解决冲突：线性探测、二次探测、随机探测、链地址法

第十章 排序

1、插入排序

直接插入 希尔 折半

2、交换排序

起泡 快速

3、选择排序

简单选择 堆

4、归并排序 基数排序