设有一组关键字值序列{e，b，d，f，a，g，C}现要求：（1）根据二叉排序树的创建方法构造出相应的二叉排序树（关键字值的大小按字母表顺序计）；（2）计算等概率情况下在该二叉排序树上查找成功的平均查找长度ASL。

问答题先序遍历、中序遍历一个森林分别等同于先序、中序遍历该森林所对应的二叉树。现已知一个森林的先序序列和中序序列分别为ABCDEFIGJH和BDCAIFJGHE，试画出该森林。

问答题为便于表示二叉树的某些基本运算，则深度为k．的二叉树的顺序存储结构中的数组的大小为多少？画出如题30图所示的二叉树的顺序存储结构示意图，并说明对一般形态的二叉树不太适合使用顺序存储结构来表示的原因。

问答题借助于队列能够将含有n个数据元素的栈逆置，比如栈S中的元素为{a，b，C}逆置后变成{C，b，a}。试简述你的解决方案。

填空题一般情况下，时闯复杂度是O（nl0g2n）且其空间复杂度最优的排序方法是（）

填空题排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素按序进行比较，将其插入已排序序列的正确位置上的方法称为（）

填空题对长度为n的有序顺序表进行二分查找，则查找表中的任意一个元素时，无论查找成功与失败，最多与表中（）个元素进行比较。

填空题一个图的最小生成树是满足一定条件的生成树，即一个图的最小生成树是指该图的所有生成树中（）的生成树

填空题设有散列函数H（k）和键值k1，k2（k1≠k2），若H（k1）=H（k2），则这种现象称为“冲突”，且称键值k1和k2互为（）

填空题若以数据集{34，5，12，23，8，18}为叶结点的权值构造一棵哈夫曼（HUffman）树，那么该Huffman树的带权路径长度WPL（）

填空题假设高度为h二叉树中只有度为2和度为0这两种类型的结点，则该类二叉树中结点个数至多为2h-1、至少为（）

填空题设一个完全二叉树共含有196个结点，则该完全二叉树中含有叶结点的个数是（）

填空题二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为l087，A[4][7]的存储地址为ll53，则每个数组元素占用的存储单元的个数是（）

填空题设以数组Q[m]存放循环队列的元素，变量rear和queuelen分别表示循环队列中队尾元素的下标位置和元素的个数。则计算该队列中队头元素下标位置的公式是（）

填空题非空的单循环链表的头指针为head，尾指针为rear，则rear一>next=（）。

填空题在表长为n的顺序表中插入或删除一个元素，则需移动元素的具体个数与表长和（）有关