数据结构复习提纲.doc

数据结构复习提纲
复习内容：
基本概念掌握：数据结构，逻辑结构，存储结构；数据类型；算法；T（n），S（n）的理解。
要学习的数据结构定义形式：
n（n>=0）个数据元素的有限集合。
将约束：1、数据元素本身。2、数据元素之间的关系。3、操作子集。
大多有两种存储（表示、实现）方式：1、顺序存储。2、链式存储。
一、线性结构：
1、线性表：n（n>=0）个相同属性的数据元素的有限序列。12种基本操作。
顺序表：9种基本操作算法实现。单链表：11种基本操作算法实现。（重点：插入、删除）
顺序表与单链表之时间性能、空间性能比较。
循环链表：类型定义与单链表同。算法实现只体现在循环终止的条件不同。
双向链表：重点插入、删除算法。
2、操作受限的线性表有：栈、队列。
栈：顺序栈；链栈（注意结点的指针域指向）。（取栈顶元素、入栈、出栈）
队列：循环队列（三个问题的提出及解决）；链队列（注意头结点的作用）。（取队头元素、入队、出队。链队列中最后一个元素出队）
3、数据元素受限的线性表有：串、数组、广义表。
串：定长顺序存储；堆分配存储。块链存储（操作不方便）
数组：顺序存储。特殊矩阵的压缩存储；稀疏矩阵（三元组表示、十字链表）
广义表：长度、深度。取表头（可以是原子也可以是子表）；取表尾（肯定是子表）。链式存储。
二、树型结构：
1、树：n（n>=0）个数据元素的有限集合。这些数据元素具有以下关系：……。（另有递归定义。）
术语；存储（双亲表示、孩子表示、孩子双亲表示、孩子兄弟表示）。
2、二叉树：n（n>=0）个数据元素的有限集合。这些数据元素具有以下关系：……。（另有递归定义）
5个性质（理解、证明；拓展）。遍历二叉树（定义、序列给出、递归算法、非递归算法）；遍历二叉树应用：表达式之前序表达式、后序表达式、中序表达式转换。
线索二叉树（中序线索二叉树）。树森林与二叉树的转换。树与森林的遍历。
赫夫曼树及其应用：定义、构造、赫夫曼编码。
三、图形结构：n（n>=0）个数据元素的有限集合。这些数据元素具有以下关系：……。
术语掌握。
存储结构（数组表示法、邻接表；无向图的邻接多重表）。
图的遍历及应用：无向图的最小生成树（普里姆算法、克鲁斯卡尔算法）；拓扑排序、关键路径。
四、查找（查找表）：相关概念掌握。
静态查找表：顺序表的查找；有序表的查找；
动态查找表：二叉排序树、AVL树的定义及调整。
哈希表：定义及概念；HASH函数；
五、内部排序：概念掌握。
插入排序：直接插入排序、折半插入排序、希尔排序
交换排序：起泡排序、快速排序
选择排序：冒泡、简单选择排序
归并排序（外部排序基础）
基数排序（链式基数排序）
要求：1、排序算法。2、各种排序算法的O（n）、稳定性。
模拟卷
填空题
1、在用于表示有向图的邻接矩阵中，对第i行的元素进行累加，可得到第i个顶点的（出）度，而对第j列的元素进行累加，可得到第j个顶点的（入）度。
2、一个连通图的生成树是该图的（极小）连通子图。若这个连通图有n个顶点，则它的生成树有（N-1）条边。
3、对算法从时间和空间两方面进行度量，分别称为（）、（）分析。
4、二叉树第i层上最多有（2i-1）个结点。一个二叉树中每个结点最多只有（2）个孩子。
5、一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有（）个。
6.设一棵二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG，则二叉树中叶子结点是（）
7.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳（4）个元素。
8、循环队列判断队满的条件为（）。
9、将两个长度分别m和n(m>n)的排好序的表归并成一个排好序的表，至少要进行（n）次键值比较。
10.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为((2+NK-2N)/K。)。
度：一个结点含有的子树的个数称为该节点的度；
公式：一个有限图中，各点的度数总和是边数的2倍；而树中的边数为点数减1。
设有x个叶节点，那么分支节点数为N-x
各点度数总和为：x*0+(N-x)*K=2*(N-1);
最后计算得到叶节点个数为(2+NK-2N)/K。
11.采用散列技术实现散列表时，需要考虑的两个主要问题是：构造()和解决()。
12.试计算下面程序段时间复杂度()。
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
x=x+delta;
13.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有()个叶子结点。
出度＝入度。一个