利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。设T是一棵二叉树，K
i
和K
j
是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λK
i
和λK
j
，当关系式｜λK
i
-λK
j
｜≤1一定成立时，则称T为一棵( )。
用下列元素序列(22，8，62，35，48)构造平衡二又树，当插入( )时，会出现不平衡的现象。
邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如下图所示：关于图中各个域的说明，不正确的是()。
下面的叙述中正确的是( )。 I．线性表在链式存储时，查找第i个元素的时间同i的值成正比 Ⅱ．线性表在链式存储时，查找第i个元素的时间同i的值无关 Ⅲ．线性表在顺序存储时，查找第i个元素的时间同i的值成正比
有n个结点的二叉树，已知叶结点个数为n
0
。
(1)写出求度为1的结点的个数的n
1
的计算公式。
(2)若此树是深度为k的完全二叉树，写出n为最小的公式。
(3)若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。
假设一个序列1，2，3，…，n依次进栈，如果第一个出栈的元素是i，那么第i个出栈的元素是( )。
假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注意：图中不存在顶点到自己的弧)
对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择( )存储方式最节省时间。
若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。
将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是( )。
已知一棵二叉树高度为h，在此二叉树中只有度为0和度为2的结点，那么这棵二叉树的结点个数最少为( )。
有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以元素C；D最先出栈的次序不包括( )。
二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长(注意：可不考虑被删除的结点是根的情况)。
栈和队列的主要区别在于( )。
在有向图G的拓扑序列中，若顶点v
i
在顶点v
j
之前，则下列情形不可能出现的是( )。
下面给出的4种排序方法中，( )排序法是不稳定性排序法。
折半查找的时间复杂性为( )。
线性表(a
1
，a
2
，a
3
，…，a
n
)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。
设有集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、集合B和集合C用链式存储结构表示。