一般情况下，时闯复杂度是O(nlog₂n)且其空间复杂度最优的排序方法是______。

若采用二路归并排序方法对关键字序列{25，9，78，6，65，15，58，18，45，20}进行升序排序，写出其每趟排序结束后的关键字序列。

写出向存储结构为邻接矩阵的无向图G中插入一条边(x,y)的算法。算法的头函数为：void AddEdgetoGraph(Graph*G, VertexType X, VertexType y>，无向图G的存储结构为：

#define MaxVertex num

typedef char VertexType;

typedef int EdgeType;

typedef struct graph{

  int n, e;    //图的实际顶点数和边数

  EdgeType edge[MaxVertex][MaxVertex];

  VertexType vertex[MaxVertex];   //顶点表

}Graph;

某电商有关手机的库存信息，按其价格从低到高存储在一个带有头结点的单循环链表中，链表中的结点由品牌型号(nametype)、价格(price)、数量(quantity)和指针(next)四个域组成。现新到in台、价格为c、品牌型号为x的新款手机需入库，写出相应的存储结构和实现该要求的算法。

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

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

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

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

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

一般情况下，时闯复杂度是O(nlog₂n)且其空间复杂度最优的排序方法是______。

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