一、单项选择题

1、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为______。

    A．O(1)，O(n)

    B．O(n)，O(n)

    C．O(1)，O(1)

    D．O(n)，O(1)

2、若某栈的输入序列为1，2，3，...，n-1，n，输出序列的第1个元素为n，则第i个输出元素为______。

    A．n-i+1

    B．n-1

    C．i

    D．哪个元素都有可能

3、串的模式匹配是指______。

    A．判断两个串是否相等

    B．对两个串进行大小比较

    C．找某字符在主串中第一次出现的位置

    D．找某子串在主串中第一次出现的第一个字符位置

……此处隐藏19752个字…… sp; // 将p的值加入结果数组中

    q = p;  // 将p设为q，用于判断p的右子树是否被访问过

    }

    else {

    p = p-＞rchild;  // 如果p的右子树没有被访问过，则将p的右子树压入栈中

    flag = 0;

    }

    }

    } while (top != -1);

    // 输出结果

    for (int j = i - 1; j ＞= 0; j--) {  // 从结果数组末尾开始遍历，输出结果

    printf("%d ", ans[j]);

    }

    }