给出先（或后）序的次序，写出此树（因为中序是顺序的，已知）。他的插入和删除（删除不一定考）。给定树，求平均查找长度。 查找长度的量级。
平衡二叉树：一定是二叉排序树。树的所有子树都是平衡二叉树。反之不成立。若要执行4种旋转，至少7个节点。
M阶B树：关键字个数的上下限。N个关键字构成树的节点数目层数。 B＋树的概念。 键树。
哈希表：解决冲突的方法。只有链地址法可以解决二次聚集。不是同义词不会竞争同一位置。链地址法是顺序结构和链结构的完美结合。
查找长度：1。探测次数（包括最后一次比较为空的次数）。
数据结构复习资料1 2010-01-06 10:43
2．关键字比较次数（不包括最后一次为空的）。
37．内部排序：简单插入排序（稳定）；折半（不稳定）；希尔（不稳定）；冒泡（稳定）；快速（不稳定）；选择（不稳定）；堆（不稳定）；归并（稳定）。要记住她们的时间复杂度（最好，平均，最坏）。
基数排序：给定N个数，范围在（0，n2-1），以O(n)时间排序。记ni=ai*n+bi，按(ai,bi)先以bi为基数排序，再以ai 排。
基数排序利用关键字本身的值，而其他基于比较。 找最大和最小值的时间[3/2n]-2。见手写版。两两比较，小的方一个数组，大的放一个数组，再找。 找最大和次大值：可以调整堆，也可以记下比较
一、名词解释：
1. 数据结构——数据结构就是数据的组织形式，也可看成是包含数据结构的数据表，说明数据之间存在着一定的相互关系或约束。
2. 逻辑结构——我们把只表现元素之间逻辑关系，而不涉及它们在计算机中的表示，只是理论的、反映在纸面上的东西，这种抽象的数据结构称为逻辑结构。
3. 物理结构——抽象的数据结构在计算机内的表示，也就是映射在存储空间上的、具体的数据结构在计算机内表示，也就是映射在存储空间上的、具体的数据结构。 二、问答题：
2. 说明对程序进行评价时，“时间”与“空间”之间的关系。
答：时间性和空间性是程序的效率问题。
时间效率决定于：源程序转换为目标程序的时间和目标程序执行的时间。时间效率与编译质量有关，与算法的简化程度有关，还与用户对语言的熟练程度有关，其中，算法的效率起主要作用。 空间效率一般指程序花费的内存空间的问题。
对于同等复杂程度的程序：一般时间效率越高的程序，占用的内存就越大，空间效率就越低；一般时间效率越低的程序，占用的内存就越小，空间效率就越高。两者具有一定的矛盾性。但是随着内存容量的不断增大，往往会牺牲空间性来提高时间性。
五、将二叉树的左右孩子交换的算法：
algorithm swap( Tree *b ) {
Tree *t;
if( b == null ) return; else {
t = b->lchild;
b->lchild = b->rchild; b->rchild = t; swap( b->lchild ); swap( b->rchild ); }
}
六、用两个栈模拟一个队列：
algorithm 用两个栈模拟一个队列
{
stack s1, s2; // 容量都为n。 void 元素入队
6
{
int x;
if( s1->top == n )
printf( \队列上溢\ else
push( s1, x ); }
void 元素出队 {
int x;
s2->top = 0;
while( !Empty( s1 ) ) push( s2, pop( s1 ) ); pop( s2, x );
while( !Empty( s2 ) ) push( s1, pop( s2 ) ); }
void 判断队列是否为空 {
if( isEmpty( s1 ) ) return( 1 ); else
return( 0 ); } }
7