【正确答案】 A

【答案解析】[解析] Ⅰ：该选项旨在让考生知道一个公式。对于n个不同元素进栈，出栈序列的个数为 [*] 可以马上得出，当n=3时，出栈序列个数为 [*] 故Ⅰ正确。 Ⅱ：链式栈一般采用单链表，栈顶指针即为链头指针。进栈和出栈均在链头进行，每次都要修改栈项指针，链空即栈空(top==NULL)，故Ⅱ错误。 Ⅲ：由于栈中数据的操作只有入栈和出栈，且时间复杂度均为O(1)，因此并没有减少存取时间，故Ⅲ错误。 两个栈共享一个数组A[0...MaxSize-1]的空间，从而构成共享栈。数组A的两端是固定的，而栈底也是固定的，为此将下标为0的一端作为栈1的栈底，其栈顶指针为top1，将下标为MaxSize-1的一端作为栈2的栈底，其栈顶指针为top2，如图所示。 [*] 栈1的四要素如下： ①栈空条件：top1==-1。 ②栈满条件：top1==top2-1。 ③元素x进栈：top1++；将元素x插入A[top1]处。 ④出栈元素：弹出A[top1]元素；top1--。 栈2的四要素如下： ①栈空条件：top2==MaxSize。 ②栈满条件：top2==top1+1。 ③元素x进栈：top2--；将元素x插入A[top2]处。 ④出栈元素：弹出A[top2]元素；top2++。 注：以上都默认指针指向当前元素的下一个位置。