邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如下图所示：关于图中各个域的说明，不正确的是()。
下面的叙述中正确的是( )。 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用链式存储结构表示。
如果具有n个顶点的图是一个环，则它有( )棵生成树。
有两个集合A和B，利用带头结点链表表示，设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法，将A与B合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在A和B的原有结点空间上完成。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。 (3)分别给出算法各部分的时间复杂度。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1．．2
h
-1]中，请写一非递归算法，产生该二叉树的二又链表结构。设二又链表中链结点的构造为(lchild，data，rchild)，根结点所在链结点的指针由T给出。