数据结构习题集.docx

1 绪论
一、选择题：
1、下列算法的时间复杂度是（ ）
for(i=0;i<n;i+ +)
c[i]=i；
A．O（1） B．O（n） C．O（log2n） D．O（nlog2n）
2、数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（ ）
A．索引存储方法 B．顺序存储方法
C．链式存储方法 D．散列存储方法
解析：
数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链式存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。

3、以下哪一个术语与数据的存储结构无关？（ ）。
A.顺序表 B.链表
C.散列表 D.队列
4、算法在发生非法操作时可以做出处理的特性称为（ ）。
A．正确性 B．易读性 C．健壮性 D．高效性
5、逻辑结构是指数据元素的（ ）。
A．关联方式 B．存储方式 C．结构 D．数据项
6、研究数据结构就是研究（ ）。
A．数据的逻辑结构
B．数据的存储结构
C．数据的逻辑结构和存储结构
D．数据的逻辑结构、存储结构及其数据的运算
7、从逻辑上可以把数据结构分为（ ）。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.线性结构和非线性结构 D.内部结构和外部结构
8、以下有关数据的叙述中错误的是（ ）。
A．计算机能够处理的数据包括整数、实数、字符、声音、图像等
B．数据的逻辑结构是从逻辑关系上描述数据，它取决于数据的存储方式
C．数据存储结构的实现依赖于计算机语言
D．数据的运算是定义在数据的逻辑结构上的
9、数据的基本单位是（ ）。
A.数据结构 B.数据元素
C.数据项 D.文件
10、下列算法的时间复杂度是（ ）
for(i=0;i<m;i+ +)
for(j=0;j<n;j+ +)
a[i][j]=i*j；
A．O（m2） B．O（n2） C．O（m×n） D．O（m+n）
11、算法分析的两个主要方面是（ ）。
A．正确性和简明性 B．数据复杂性和程序复杂性
C．可读性和可维护性 D．时间复杂性和空间复杂性
二、填空题：
1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（　 　　）和（ ）。
2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的（　　　　　　　）无关，是独立于计算机的。
3、( )结构与数据元素本身的内容和形式无关。
4、程序段“for(i=1;i<=n;i++) {k++; for(j=1;j<=n;j++) x=x+k;}”的时间复杂度为( )。
5、数据的存储结构（物理结构）可以用（ ）、（ ）、（ ）及散列存储等四种存储方法表示。
三、 判断题：
1、顺序存储方式优点是存储密度大，且插入和删除运算效率高。 （ ）
2、顺序存储结构属于静态存储结构，链式存储结构属于动态存储结构。 （ 　）
3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。 （ ）
4、数据的机内表示称为数据的存储结构。 （ ）
5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（ ）
6、数据元素是数据的最小单位。 （ ）
7、基于某种逻辑结构之上的运算，其实现是惟一的。 （ ）

参考答案（绪论）
一、选择题

1
2
3
4
5
6
7
8
9
10
11
B
D
D
C
A
D
C
B
A
C
D

二、填空题
1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（存储结构）和（运算）。
2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的（　　　　　　　）无关，是独立于计算机的。
3、(逻辑)结构与数据元素本身的内容和形式无关。
4、程序段“for(i=1;i<=n;i++) {k++; for(j=1;j<=n;j++) x=x+k;}”的时间复杂度为(O(n2))。
5、数据的存储结构（物理结构）可以用（顺序）、（链式）、（索引）及散列存储等四种存储方法表示。

三、判断题
1、顺序存储方式优点是存储密度大，且插入和删除运算效率高。 （×）
2、顺序存储结构属于静态存储结构，链式存储结构属于动态存储结构。 （×）
3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。 （ √）
4、数据的机内表示称为数据的存储结构。 （√）
5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×） 6、数据元素是数据的最小单位。 （×）
7、基于某种逻辑结构之上的运算，其实现是惟一的。 （×）
2 线性表
一、 选择题：
1、在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ）。
A．n B．n/2 C．n/3 D．n/4
2、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（ ）
A．S->next=P->next;P->next=S
B．P->next=S->next;S->next=P；
C．P->next=P;P->next=S；
D．P->next=S;S->next=P；
3、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（ ）
A．Ｏ（1） B．Ｏ（log2n） C．O（n） D．O（n2）
解析：单就插入运算而言，算法时间复杂度为Ｏ（1），但要将指针定位到链表末尾，指针移动的时间复杂度为O（n）；
4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ ）
A．顺序表 B．用头指针表示的单循环链表
C．用尾指针表示的单循环链表 D．单链表
解析：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。
若用头指针来表示该链表，则查找终端结点的时间为O(n)。
5、线性表是（ ）
A．一个有限序列，可以为空 B．一个有限序列，不能为空
C．一个无限序列，可以为空 D．一个无限序列，不能为空
6、在n个结点的双链表的某个结点前插入一个结点的时间复杂度是（ ）
A．O（n） B．O（1） C．O（log2n） D．O（n2）
7、线性表采用链式存储时，结点的地址（ ）
A．必须是连续的 B．必须是不连续的
C．连续与否均可 D．必须有相等的间隔
8、在单链表中，增加头结点的目的是（ ）
A．使单链表至少有一结点 B．标志表中首结点位置
C．方便运算的实现 D．说明单链表是线性表的链式存储实现
9、带头结点的单链表head为空的判定条件是（ ）
A．head = NULL； B．head - > next = NULL；
C．head - > next = head； D．head ! = NULL；
10、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（ ）
A．Ｏ（1） B．Ｏ（n） C．Ｏ（n2） D．Ｏ（log2n）
11、下列有关线性表的叙述中，正确的是（ ）
A．线性表中的元素之间是线性关系
B．线性表中至少有一个元素
C．线性表中任何一个元素有且仅有一个直接前趋
D．线性表中任何一个元素有且仅有一个直接后继
12、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的（ ）
A．直接前趋 B．直接后继 C．开始结点 D．终端结点
13、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A．n B.2n-1 C.2n D.n-1
14、链表不具有的特点是（ ）。
A．随机访问 　　　　B．不必事先估计存储空间
C．插入删除时不需移动元素 D．所需的空间与线性表成正比
15、在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行的操作是（ ）。
A．s->next=p->next;p->next=s; B．q->next=s;s->next=p;
C．p->next=s->next;s->next=p;　 D．p->next=s;s->next=q;
16、链表具有的特点是（ ）。
A．可随机访问任一元素 B．插入、删除需要移动元素
C．不必事先估计存储空间 D．存储空间是静态分配的
17、一个顺序表一旦说明，其中可用空间大小（ ）
A．已固定 B．可以改变 C．不能固定 D．动态变化
18、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
A． 顺序表 B．单链表 C．双向链表 D．单循环链表
19、两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素的前驱的条件是（ ）。
A．P->next==Q B．Q->next==P
C．P==Q D．P->next==Q->next
20、链表不具有的特点是（ ）。
A．可随机访问任一元素 B．插入、删除不需要移动元素
C．不必事先估计存储空间 D．所需空间与线性表长度成正比
21、下面关于线性表的叙述中，错误的是（ ）。
A．线性表采用顺序存储，必须占用一片连续的存储单元
B．线性表采用顺序存储，便于进行插入和删除操作
C．线性表采用链接存储，不必占用一片连续的存储单元
D．线性表采用链接存储，便于进行插入和删除操作
22、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前趋（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．将n个结点从小到大排序
23、在一个单链表中，若删除p指向结点的后继结点，则执行的操作为（ ）。
A．q=p->next;p->next=p->next->next;free(q);
B．p=p->next;q=p->next;p=q->next;free(q);
C．q=p->next->next;p=p->next;free(q);
D．p=p->next->next;q=p->next;free(q);
二、 填空题：
1、在双链表中要删除已知结点*p，其时间复杂度为（　　　　　）。
2、在仅有尾指针R指示的单循环链表R中，在表尾插入一个结点S的语句序列是（　　　 　　　　　　　　　　　　　）。
3、在带头结点的双链表Ｌ中，指针Ｐ所指结点是开始结点的条件是（　　　　　）。
4、在具有n个结点的双链表中做插入、删除运算，平均时间复杂度为（　　　　　）。
5、在一个长度为n的顺序表中第i个元素（1 ≤ i ≤ n）之前插入一个元素时，需向后移动（　　　　　　　）个元素。
6、在双循环链表中，若要在指针p所指结点之前插入指针s所指的结点，则需执行下列语句：s->prior=p->prior;p->prior->next=s;( )和p->prior=s;。
7、已知指针p指向双向链表中的一个结点（非首结点、非尾结点），则将结点s插入在p结点的直接后继位置的语句是（ ）s->prior=p；s->next->prior=s；p->next=s;
8、已知带表头结点的单链表L，指针p指向L链表中的一个结点（非首结点、非尾结点），则删除结点p的直接后继结点的语句是（ ）；删除首结点的语句是（ ）。

三、 判断题
1、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。（ ）
2、顺序存储的线性表可以随机存取。 （ ）
3、线性表采用顺序存储，必须占用一片连续的存储单元。 （ ）

四、 程序设计题
数据结构的数据类型定义如下：
顺序存储：
typedef struct
{ int *base; int length; int listsize; }sqlist;
链式存储：
typedef struct LinkList
{int data; struct LinkList *next; }Node,*LinkList;

1、已知带头结点的单链表head中的结点是按整数值递增排序的，写一算法将值为x的结点插入到表head中，使head仍然有序。

2、用尾插法建立带头结点的单链表。

3、用头插法建立带头结点的单链表。

4、对给定的单链表L，编写一个删除L中值为x的结点的直接前趋结点算法。

5、用顺序存储结构实现线性表的就地逆置算法，即将（a1,a2, …ai,…an）逆置为（an,…,ai,…a2,a1）;

6、用链式存储结构实现线性表的就地逆置算法，即将（a1,a2, …ai,…an）逆置为（an,…,ai,…a2,a1）;

7、使用顺序存储结构分别实现A=A∪B和A=A∩B运算；

参考答案（线性表）
一、选择题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
B
A
B
C
A
B
C
C
B
B
A
B
B
A
B
C
B
A
A
A
B
A
A

二、填空题
1、在双链表中要删除已知结点*p，其时间复杂度为（O(1)）。
2、在仅有尾指针R指示的单循环链表R中，在表尾插入一个结点S的语句序列是（P=R; while(P->next!=NULL) P=P->next; P->next=S; S->next=NULL;）。
3、在带头结点的双链表Ｌ中，指针Ｐ所指结点是开始结点的条件是（P= =L）。
4、在具有n个结点的双链表中做插入、删除运算，平均时间复杂度为（O(1)）。
5、在一个长度为n的顺序表中第i个元素（1 ≤ i ≤ n）之前插入一个元素时，需向后移动（n-i+1）个元素。
6、在双循环链表中，若要在指针p所指结点之前插入指针s所指的结点，则需执行下列语句：s->prior=p->prior;p->prior->next=s;( s->next=p; )和p->prior=s;。
7、已知指针p指向双向链表中的一个结点（非首结点、非尾结点），则将结点s插入在p结点的直接后继位置的语句是（p->next=s;）s->prior=p；s->next->prior=s；p->next=s;
8、已知带表头结点的单链表L，指针p指向L链表中的一个结点（非首结点、非尾结点），则删除结点p的直接后继结点的语句是（q=p->next; p->next=q->next; free(q);）；删除首结点的语句是（q=L->next; L=L->next; free(q);）。

三、判断题
1、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。（×）
2、顺序存储的线性表可以随机存取。 （√）
3、线性表采用顺序存储，必须占用一片连续的存储单元。 （√）
四、程序设计题
1、已知带头结点的单链表head中的结点是按整数值递增排序的，写一算法将值为x的结点插入到表head中，使head仍然有序。
P=head->next;
While(p->next!=NULL&&p->data<x) p=p->next;//指针定位
p->next=x;
x->next=p->next;

2、用尾插入法建立带头结点的单链表。
请参考教材“数据结构-清华大学严尉敏著评p29-p30”;

3、用头插入法建立带头结点的单链表。
请参考教材“数据结构-清华大学严尉敏著评p29-p30”;

4、对给定的单链表L，编写一个删除L中值为x的结点的直接前趋结点算法。
//算法思路：先判断L中是否存在值为x的结点，若不存在，返回错误（-1）；若存在，用一指针p定位到值为x的第一结点,用另一个指针q定位到值为x的第一结点的前驱结点，然后实施删除操作；重点语句为：
p=L->next;//p指向第一个结点
whili(p->data!=x&&p->next!=NULL) p=p->next;
if(p= =NULL) ruturn error;//不存在
else
{
p=L->next;
while(p->next->next->data!=x) p=p->next;
q=p->next;
p->next=p->next->next;
free(q);
}

5、用顺序存储结构实现线性表的就地逆置算法，即将（a1,a2, …ai,…an）逆置为（an,…,ai,…a2,a1）;
重点语句：
for(i=0;i<sqlist.length/2;i++)
{
sqlist.base[i]ßàsqlist.base[sqlist.length-i];//第i个元素和第length-i元素交换存储
}

6、用链式存储结构实现线性表的就地逆置算法(不带头结点的单链表)，即将（a1,a2, …ai,…an）逆置为（an,…,ai,…a2,a1）;
参考答案：
Node *fun(Node *h)//h指向单链表的第一个结点
{
Node *p,*q,*r;
P=h;
If(p==NULL)
Return NULL;
q=pànext;//q指针指向第二个结点
pànext=NULL;
while(q)
{
r=qànext；//第一次循环时，r指向第三个结点
qànext=p;//第二个结点的NEXT指向第一个结点
p=q;//p总是指向逆置后的第一个结点
q=r;//q总是指向剩余单链表的第一个结点，为将其作为逆置单链表的第一个结点作准备
}
return p;
}
两外，解决本体还有另外一种思路，将结点数据域拷贝到一个一维数组中，然后反过来填充单链表结点的数据域。

7、使用顺序存储结构分别实现A=A∪B和A=A∩B运算；
请参考清华大学出版社出版，严尉敏编著《数据结构C语言版》P20例2-1；

3 栈和队列
一、 选择题：
1、循环队列是空队列的条件是（ ）
A．Q . rear = = Q . front B．（Q . rear + 1）%maxsize = = Q .front
C．Q . rear = = 0 D．Q. front = = 0

2、链栈与顺序栈相比，比较明显的优点是（ ）
A．通常不会出现栈满的情况 B．通常不会出现栈空的情况
C．插入操作更加方便 D．删除操作更加方便
[分析]不管是链栈还是顺序栈，其插入、删除操作都是在栈顶进行的，都比较方便，所以不可能选C)，D)。对链栈来讲，当栈中没有元素而又要执行出栈操作时，就会出现栈空现象，故B)也是不正确的。只要内存足够大，链栈上就不会出现栈满现象。而对顺序栈来讲，由于其大小是事先确定好的，因此可能会出现栈满现象。所以A)是正确的。

3、若一个栈的输入序列是１，２，３，……，n，输出序列的第一个元素是ｎ，则第ｉ个输出元素是（ ）
A．n - i B．n – i + 1 C．i D．不确定

4、栈与一般线性表的区别主要在（ ）
A．元素个数 B．元素类型
C．逻辑结构 D．插入、删除元素的位置

5、一个链栈的栈顶指针是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；
[分析]栈顶元素出栈后，应该从栈底位置即第一个结点开始重新定位，执行语句是：q=base ; while(qànext!=top) q=qànext; free(top); top=q;

6、对于一个栈，给定输入序列为1，2，3，则下列不可能为输出序列的是（ ）
A．1，2，3 B．3，2，1 C．3，1，2 D．2，1，3
[分析] 每个元素进栈后立即出栈，结果是答案A；三个元素全部进栈后再出栈，得到答案B；1和2进栈后出栈，然后3入栈后出栈，得到答案D；而C答案不可能的原因是：3出栈后，说明1、2还在栈中，1出栈后2还在栈中，说明2的入栈次序在1之前。

7、在链接队列执行入队操作（　 ）
A．需判别队是否空 B．需判别队是否满
C．限制在链表头p进行 D．限制在链表尾p进行

8、以下不属于栈的基本运算是（ ）。
A．删除栈顶元素 B．删除栈底元素
C．判断栈是否为空 D．将栈置为空栈

9、一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ ）。
A．e,d,c,b,a　 B．d,e,c,b,a
C．d,c,e,a,b 　　 D．a,b,c,d,e
10、设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。
A．线性表的顺序存储结构　 B．栈
C．队列　　　　 D．线性表的链式存储结构

11、循环队列的特点之一是不会产生（ ）。
A．上溢出 B．下溢出 C．队满 D．假溢出
12、设数组Data[n]作为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则执行入队操作的语句为（ ）。
A．rear=(rear+1)%(n+1) B．front=(front+1)% n
C．rear=(rear+1)% n D．front=(front+1)%(n+1)

13、栈是限定在（ ）处进行插入或删除操作的线性表。
A．端点 B．栈底 C．栈顶 D．中间

14、容量是10的循环队列的队头位置qàfront为2，队列中的数据元素个数为5，则队的第一个数据元素的位置是（ ）
A．2 B．7 C．1 D．0
[分析] (front-rear+10)%10=5,并且front和rear的取值范围均是0—9，所以只有（7-2+10）%10=5。

15、循环队列的出队操作是（ ）
A． qàfront=(qàfront+1)%maxsize; B．qàfront=qàfront+1;
C．qàrear=(qàrear+1)%maxsize; D．qàrear=qàrear+1;

16、当循环队列q是满队列时，存放队列元素的数组data有n个元素，则data中存放（ ）个数据元素。
A．n B. n-1 C. n-2 D.0
[分析] 容量为maxsize的循环队列最多只能存放maxsize-1个数据元素，当队列满时，队尾指针再往前走一步就追上队头指针，即(rear+1)% maxsize=front；

17、以下哪一个不是队列的基本运算（ ）。
A．从队尾插入一个新元素 B．从队列中删除第i个元素
C．判断一个队列是否为空 D．读取队头元素的值

18、在一个链队列中，若f , r分别为队首、队尾指针，则插入s所指结点的操作为（ ）。
A．fànext=s;f=s B．rànext=s;r=s;
C．sànext=r;r=s; D．sànext=f;f=s

19、循环队列的入队操作应为（ ）。
A．qàrear=qàrear+1;qàdata[qàrear]=x;
B．qàdata[qàrear++]=x;
C．qàrear=(qàrear+1)%maxsize; qàdata[qàrear]=x;
D．qàdata[qàrear]=x;q->rear=(qàrear+1)%maxsize;

20、栈和队列都是（ ）。
A．限制存取点的线性结构 B．限制存取点的非线性结构
C．顺序存储的线性结构 D．链式存储的线性结构

21、实现递归调用属于（ ）的应用。
A．队列 B．栈 C． 数组 D．树

二、 填空题：
1、循环队列用数组data[m]存放其元素值，已知其头、尾指针分别是front和rear，则当前队列中元素的个数是（　　　　　　　　　　　　）。
2、栈顶的位置是随着（　　　　　　　）操作而变化的。
3、假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为（　　　　　　　　）。
4、队列的队尾位置随着（　　　　　）而变化。
5、在（　　　　 　　　）的情况下，链队列的出队操作需要修改尾指针。
6、从栈顶指针为top的链栈中删除一个结点，并将被删除的结点的值保存在x中，其操作步骤为（ ）；top=top->next;。
7、用数组A[m]来存放循环队列q的元素，且它的头、尾指针分别为front和rear，队列满足条件(q.rear+1)%m==q.front,则队列中当前的元素个数为（ ）。
8、顺序栈s存储在数组s->data[max]中，对s进行出栈操作，执行的语句序列是（ ）。
9、以下运算实现在循环队列中的初始化操作
void initqueue(seqqueue *q){q->front=0;( );}

三、 判断题：
1、循环队列中无上溢现象。 （ ）
2、循环队列只有下溢，没有上溢。 （ ）
3、对顺序栈而言，在栈满状态，如果此时再作进栈运算，则会发生“下溢”。 （ ）
4、顺序队列和循环队列的队满和队空的条件是一样的。 （ ）
5、为解决队列“假满”问题，可以采用循环数组实现队列存储。　 （ ）
6、队列是后进先出表。 （ ）
7、栈是后进先出表。 （ ）

四、 应用题：
1、 设有一个栈，元素进栈的次序为A，B，C，D，E，写出下列出栈序列的操作序列。（1）CBADE（2）ACBED，其中I为进栈操作，O为出栈操作。

2、如果编号为1、2、3的三辆列车进入一个栈式结构的站台，那么可能得到的三辆列车出站序列有哪些？不可能出现的序列是什么？

五、 程序设计题：
1、写出循环队列入队操作的函数。

参考答案（栈和队列）
一、选择题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
A
A
B
D
B
C
D
B
C
B
D
C
C
B
A
B
B
B
C
A
B

二、填空题
1、循环队列用数组data[m]存放其元素值，已知其头、尾指针分别是front和rear，则当前队列中元素的个数是（(rear-front+maxsize）%maxsize）。
2、栈顶的位置是随着（入栈和出栈）操作而变化的。
3、假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为（bceda）。
4、队列的队尾位置随着（入队列操作变化）而变化。
5、在（链队列为空）的情况下，链队列的出队操作需要修改尾指针。
分析：Q.rear=h;
6、从栈顶指针为top的链栈中删除一个结点，并将被删除的结点的值保存在x中，其操作步骤为（x=top->data）。
7、用数组A[m]来存放循环队列q的元素，且它的头、尾指针分别为front和rear，队列满足条件(q.rear+1)%m==q.front,则队列中当前的元素个数为（0）。
8、顺序栈s存储在数组s->data[max]中，对s进行出栈操作，执行的语句序列是（sàtop--）。
9、以下运算实现在循环队列中的初始化操作
void initqueue(seqqueue *q){q->front=0;( qàbase=(qelemtype *)malloc(maxsize*sizeof(qelemtype)); qàrear=0;);}

三、判断题
1、循环队列中无上溢现象。 （×）
2、循环队列只有下溢，没有上溢。 （×）
3、对顺序栈而言，在栈满状态，如果此时再作进栈运算，则会发生“下溢”。 （×）
4、顺序队列和循环队列的队满和队空的条件是一样的。 （×）
5、为解决队列“假满”问题，可以采用循环队列实现队列存储。　 （√）
6、队列是后进先出的线性表。 （×）
7、栈是后进先出表。 （√）

四、应用题
1、设有一个栈，元素进栈的次序为A，B，C，D，E，写出下列出栈序列的操作序列。（1）CBADE（2）ACBED，其中I为进栈操作，O为出栈操作。
参考答案：（1）IIIOO