一、单选

1. 栈和队列具有相同的（ ）。

A. 抽象数据类型
B. 逻辑结构
C. 存储结构
D. 运算
[Solution]
栈和队列具有相同的逻辑结构，即线性逻辑结构，
$therefore B$??.

8. 向一个栈顶指针为top的链栈中插入一个x结点，则执行（ ）。

A. top->next=top;
B. x->next=top->next;top->next=x;
C. x->next=top;top=x;
D. x->next=top;top=top->next;
[Solution]
链栈采用不带头结点的单链表表示时，进栈操作在首部插入一个结点x(x->next=top;)，再将top指向该插入的结点(top=x;)
Push时，先让top与新结点联系上，再进行插入。如顺序栈的Push：top先+1，后插入；链栈的Push：x->next = top; top = x;
$therefore B$??.

9. 链栈执行Pop操作，并将出栈的元素存在x中应该执行（ ）。

A. x=top;top=top->next
B. x=top->data;
C. top=top->next;x=top->data;
D. x=top->data;top=top->next;
[Analysis]
出栈时，应该元素先出栈，top再-1。即x=top->data;top=top->next;
$therefore D$??.

11. 3个不同元素进栈，能得到（ ）种不同的出栈序列。

A. 4
B. 5
C. 6
D. 7
[Analysis]
出栈序列的个数=卡特兰(Catalan)数=

组合数=

$therefore B$??.

19. 一个栈的输入序列是1，2，3…，n，输出序列的第一个元素是i，则第j个输出元素是（ ）。

A. i-j+1
B. i-j
C. j-i+1
D. 不确定
[Analysis]
j都不知道是个啥，咋子确定嘛。
$therefore D$??.

23.[2013] 一个栈的入栈序列为1，2，3，…，n，其出栈序列为$p_1$，$p_2$，$p_3$，…，$p_n$。若$p_2=3$，则$p_3$可能取指的个数是（ ）。

A. n-3
B. n-2
C. n-1
D. 无法确定
[Analysis]
(1) $p_3$为3之后的数，即4，5，…，n都是可能取的数；
(2) $p_3$为3之前的数，即1或2：当$p_3$为2时，$p_1$为1，很合理；当$p_3$为1时，$p_1$就应该为2（2先出去了）。
故$p_3$可去除了3以外的所有数，即n-1个。
$therefore C$??.

24. 设栈的初始状态为空，当字符序列“n 1 _”作为栈的输入时，输出长度为3，且可用作C语言标识符的序列有（ ）个。

A. 4
B. 5
C. 3
D. 6
[Analysis]
n 1不能出现。可以出现的序列有：_n1，_1n，n1
$therefore C$??.

二、综合应用题

4. 设单链表的表头指针为L，结点结构由data和next两个域构成，其中data域为字符型。试着设计算法判断该链表的全部n个字符是否中心对称，例如xyx，xyyx，都是中心对称。

1
2
3
4
5
6
7
8
9
10
11
12
13

int (LinkList L, int n){
    char stack[n/2];                
    int index;                      // 字符栈的工作指针
    LNode *p = L->next;             // 单链表的工作指针
    if(L->next == NULL) return 0;
    for(index = 0; index < n/2; index++, p = p->next)   // 单链表中的前一半元素入栈
      大专栏  3.1-栈   stack[index] = p->data;
    index--;                        // index == n/2-1，即字符栈中的最后一个元素
    if(n % 2 == 1) p = p->next;     // 当n为奇数时，跳过中心结点
    for( ;stack[index] == p->data && p->next != NULL; index--, p = p->next);
    if(index == -1) return 1;       // 栈为空栈，则单链表中心对称
    else return 0;
}

5. 设有两个栈s1和s2都采用顺序栈方式，并且共享一个存储区[0…maxsize-1]。为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式。试着设计s1和s2有关入栈和出栈的操作算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#define ElemType int
typedef struct{
    ElemType data[MaxSize];  // 栈空间
    int top[2];              // top为两个栈顶指针，top[0]为左边的栈s1，top[1]为右边的栈s2
} Stack;

Stack stack;                // 将stack声明为全局变量

int Push(int whichOne, ElemType value){
    if(whichOne < 0 || whichOne > 1) retrun 0;
    if(top[1] - top[0] == 1){
        printf("栈已满");
        return 0;
    }
    if(whichOne == 0)
        stack[++top[0]] = value;
    else if(whichOne == 1)
        stack[--top[1]] = value;
    return 0;
}

ElemType Pop(int whichOne){
    if(whichOne < 0 || whichOne > 1) retrun 0;
    if(wichiOne == 0){
        if(top[0] == -1){
            printf("栈为空");
            return -1;
        }
        else
            return stack[top[0]--];
    }
    else if(whichOne == 1){
        if(top[1] == MaxSize){
            printf("栈为空");
            return -1;
        }
        else
            return stack[top[1]++];
    }
}

3.1-栈

原文：https://www.cnblogs.com/lijianming180/p/12046677.html