对于栈和队列，无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的...

填空题对于栈和队列，无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的时间复杂度都是（）。

1.填空题设S="I_am_a_teacther"，其长度为（）。

2.问答题设元素1，2，3，P，A依次经过一个栈，进栈次序为123PA，在栈的输出序列中，有哪些序列可作为C++程序设计语言的变量名。

3.单项选择题从栈顶指针为top的链栈中删除一个结点，用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；

4.单项选择题一个栈的入栈序列是a，b，c，d，e，则栈的不可能的出栈序列是（）。

A.edcba
B.cdeba
C.debca
D.abcde

5.单项选择题在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（）。

A.不变
B.top=0；
C.top=top-1；
D.top=top+1；

6.问答题对于采用顺序存储结构的串S，编写一个函数删除其值等于ch的所有字符。

从后向前删除值为ch的所有元素，这样所有移动的元素中没有值为ch的元素，能减少移动元素的次数，提高算法的效率。算法如下：

7.问答题用顺序存储结构存储串S，编写算法删除S中第i个字符开始的连续j个字符。

先判断串S中要删除的内容是否存在，若存在，则将第i+j-1之后的字符前移j个位置。算法如下：

8.问答题设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，…，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O（n）。

9.问答题假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针。试设计相应的入队和出队的算法。

10.问答题空串和空格串有何区别？串中的空格符有何意义？空串在串处理中有何作用？