练习题

一、选择题部分

1.一个栈的入栈序列是abcde，则栈的不可能的输出序列是（ ）。

A.edcba　B.decba　C.dceab　D.abcde

2.栈结构通常采用的两种存储结构是（ ）。

A.线性存储结构和链表存储结构　B.散列方式和索引方式

C.链表存储结构和数组　D.线性存储结构和非线性存储结构

3.判定一个栈ST（最多元素为m0）为空的条件是（ ）。

A.ST－top！＝0　B.ST－top＝＝0

C.ST－top！＝m0　D.ST－top＝m0

4.判定一个栈ST（最多元素为m0）为栈满的条件是（ ）。

A.ST－top！＝0　B.ST－top＝＝0

C.ST－top！＝m0－1　D.ST－top＝＝m0－1

5.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ ）。

A.4，3，2，1　B.1，2，3，4　C.1，4，3，2　D.3，2，4，1

6.循环队列用数组A［0，m－1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ ）。

A.（rear－front＋m）%m　B.rear－front＋1

C.rear－front－1　D.rear－front

7.栈和队列的共同点是（ ）。

A.都是先进后出

B.都是先进先出

C.只允许在端点处插入和删除元素

D.没有共同点

8.表达式a＊（b＋c）－d的后缀表达式是（ ）。

A.abcd＊＋－　B.abc＋＊d－　C.abc＊＋d－　D.－＋＊abcd

9.4个元素a1，a2，a3和a4依次通过一个栈，则不可能的出栈序列是（ ）。

A.a4，a3，a2，a1　B.a3，a2，a4，a1

C.a3，a1，a4，a2　D.a3，a4，a2，a1

10.以数组Q［0..m－1］存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ）。

A.rear－qulen　B.rear－qulen＋m

C.m－qulen　D.1＋（rear＋m－qulen）%m

二、填空题部分

1.栈的特点是_____________，队列的特点是____________。

2.线性表、栈和队列都是____________结构，可以在线性表的_____________位置插入和删除元素，对于栈只能在____________插入和删除元素，对于队列只能在____________插入元素和____________删除元素。

3.一个栈的输入序列是12345，则栈的输出序列12345是____________。

三、简答题

1.什么是栈？什么是队列？试分别举两个应用实例。

2.说明线性表、栈和队列的异同点。

3.设有编号为1，2，3，4的4辆列车，顺序进入一个栈式结构的车站，具体写出这4辆列车开出车站的所有可能的顺序。

4.假设正读和反读都相同的字符序列为“回文”，例如，'abba'和'abcba'是回文，'abcde'和'ababab'则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？

5.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？

6.设循环队列的容量为40（序号0～39），现经过一系列的入队和出队运算后，有

①front＝11，rear＝19；

②front＝19，rear＝11；

问在这两种情况下，循环队列中各有元素多少个？

7.试述栈的基本性质。

8.设输入元素为1，2，3，P和A，输入次序为123PA。元素入栈后得到输出序列，有哪些序列可以作为高级语言的变量名？

9.内存中一片连续空间（不妨假设地址从1到m）提供给两个栈s1和s2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。

10.计算表达式“6＊3／2－5＊1”，要求绘出堆栈的处理过程。