淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 9
第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．删除操作更加方便 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；
6、对于一个栈，给定输入序列为1，2，3，则下列不可能为输出序列的是（ ） A．1，2，3 B．3，2，1 C．3，1，2 D．2，1，3 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 15、循环队列的出队操作是（ ）
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 10
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 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．树
22、顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的
主要语句为（ ）。
A．s.elem［s.top］=e；s.top=s.top+1； B．s.elem［s.top］=e；s.top=s.top+1； C．s.top=s.top+1；s.elem［s.top+1］=e； D．s.top=s.top+1；s.elem［s.top］=e； 23、循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear
指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（ ）。 A． 8 B．16 C．17 D．18 24、链式栈与顺序栈相比，一个比较明显的优点是（ ）。
A． 插入操作更加方便 B．通常不会出现栈满的情况 C．不会出现栈空的情况 D．删除操作更加方便 25、若已知一个栈的入栈序列是1,2,3,4……n，其输出序列为p1,p2,p3,……pn，若p1= =n,则pi为（ ）。 A． i B．n= =i C．n-i+1 D．不确定
26、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )。
A． 2，4，3，1，5，6 B．3，2，4，1，6，5 C．4，3，2，1，5，6 D．2，3，5，1，6，4 27、对于栈操作数据的原则是（ ）。
A． 先进先出 B．后进先出 C．后进后出 D．不分顺序 28、栈和队列的共同点是（ ）。
A． 都是先进先出 B．都是先进后出 C．只允许在端点处插入和删除元素 D．没有共同点
29、一个队列的入队序列是1，2，3，4，则队列的输出序列是（ ）。
A． 4,3,2,1 B．1,2,3,4 C．1,4,3,2 D．3,2,4,1 30、引起循环队列队头位置发生变化的操作是( )。
A． 出队 B．入队 C．取队头元素 D．取队尾元素 31、设数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 11
A．(rear-front+m)%m B）rear-front+1 C）(front-rear+m)%m D）(rear-front)%m
二、 填空题：
数是（ ）。
1、循环队列用数组data[m]存放其元素值，已知其头、尾指针分别是front和rear，则当前队列中元素的个2、栈顶的位置是随着（ ）操作而变化的。
3、假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX
之后，得到的输出序列为（ ）。 4、队列的队尾位置随着（ ）而变化。
5、在（ ）的情况下，链队列的出队操作需要修改尾指针。
6、从栈顶指针为top的链栈中删除一个结点，并将被删除的结点的值保存在x中，其操作步骤为（ ）。
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;
( ); }
10、对于栈操作数据的原则是（ ）。
11、一个链栈的栈顶指针用top表示，当p所指向的结点进栈时，执行的操作为（ ）。 12、一个链栈的栈顶指针用top表示，当进行退栈时所进行的指针操作为（ ）。 13、（ ）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 14、用P表示入栈操作，D表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的
P和D的操作串为（ ） 。
15、在具有n个单元的循环队列中，队满共有（ ）个元素。 16、循环队列的引入，目的是为了克服（ ）。
三、 判断题：
1、循环队列中无上溢现象。 （ ） 2、循环队列只有下溢，没有上溢。 （ ） 3、对顺序栈而言，在栈满状态，如果此时再作进栈运算，则会发生“下溢”。 （ ） 4、顺序队列和循环队列的队满和队空的条件是一样的。 （ ） 5、为解决队列“假满”问题，可以采用循环队列实现队列存储。 （ ） 6、队列是后进先出的线性表。 （ ） 7、栈是后进先出表。 （ ）
四、 应用题：
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 12
1、设有一个栈，元素进栈的次序为A，B，C，D，E，写出下列出栈序列的操作序列。（1）CBADE（2）ACBED，其中I为进栈操作，O为出栈操作。
2、如果编号为1、2、3的三辆列车顺序进入一个栈式结构的站台，那么可能得到的三辆列车出站序列有哪些？不可能出现的序列是什么？ 答：
五、 程序设计题：
1、 写一个函数，利用栈完成数的进制转换并显示。
void conversion(int n，int base)//n为要转换的十进制数，base为进制 { }
成绩____________ 日期____________________
第4章 串
一、单选题
1．下列那些为空串（ ）
A．S=“ ” B．S=“” C．S=“φ” D．S=“θ” 2．S1=“ABCD”，S2=“CD”则S2在S3中的位置是（ ）
A．1 B．2 C．3 D．4 3．假设S=“abcaabcaaabca”，T=“bca”，Index (S,T,3) 的结果是（ ）
A． 2 B．6 C．11 D．0
4．在串中，对于SubString(&Sub,S,pos,len)基本操作，pos和len的约束条件是（ ）