第三部分 栈 队列
一、选择题
1．( A )又称为FIFO表。
A.队列 B.散列表 C.栈 D.哈希表
2．设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有(B D )。
A.a.b,c,d B.a,d,c,b C.b,a,d,c D.c,d,a,b
3. 链式栈与顺序栈相比，一个比较明显的优点是 ( B )。
A. 插入操作更加方便 B. 通常不会出现栈满的情况
C. 不会出现栈空的情况 D. 删除操作更加方便
4. 在一个顺序存储的循环队列中，队头指针指向队头元素的 ( A )。
A. 前一个位置 B. 后一个位置
C. 队头元素位置 D. 队尾元素的前一位置
5. 若一个栈的输入序列是1，2，3……n，则输出序列的第一个元素是n，则第i个输出元素是（ C ）。
A n-i B i C n-i+1 D n-i-1
6. 栈的数组表示中，top为栈顶指针，栈空的条件是( D )。
（A） top=0 （B）top=maxSize （C）top=maxSize（D）top=-1
7. 在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( B )。
（A） front=maxSize （B）(rear+1)%maxSize=front
（C） rear=maxSize （D）rear=front
8. 栈和队列的共同特点是( C )。
（A） 都是先进后出 （B）都是先进先出
（C） 只允许在端点处插入和删除 （D）没有共同点
9．与中缀表达式a+b*c-d等价的前缀表达式是( C )。
A.+a-*bcd B.*+-abcd C.-+a*bcd D.abcd+*-
10．中缀表达式A-(B+C)*D/E的后缀形式是( D )。
A.ABC+-D*E/ B.ABC+D*-E/ C.ABC+D-*E/ D.ABC+D*E/-
11．若非空队列采用链式存储结构，front和rear分别为队头元素与队列尾元素的指针，删除此时队列的一个元素的操作时依次执行p←front，( D )，call RET(P)。
A.front←link(rear) B.rear←link(p) C.rear←link(front) D.front←link(p)
12．由两个栈共享一个向量空间的好处是：（ B ）
A．减少存取时间，降低下溢发生的机率
B．节省存储空间，降低上溢发生的机率
C．减少存取时间，降低上溢发生的机率
D．节省存储空间，降低下溢发生的机率
13．数组data[m]为循环队列的存储空间, front为队头指针, rare为队尾指针,则执行入队的操作为（ D ）。
A rare=rare+1 B rare=(rare+1)%(m-1)
C rare=(rare-1)%m D rare=(rare+1)%m
14. 将递归算法转换成对应的非递归算法时，通常需要使用( A )。
（a）栈 （b）队列 （c）链表 （d）数组
15．下列关于栈的叙述中正确的是( D )。
A. 在栈中只能插入数据 B. 在栈中只能删除数据
C. 栈是先进先出的线性表 D. 栈是先进后出的线性表
16．下列关于队列的叙述中正确的是( C )。
A. 在队列中只能插入数据 B. 在队列中只能删除数据
C. 队列是先进先出的线性表 D. 队列是先进后出的线性表
17．栈和队列的共同点是( C )。
A. 都是先进后出 B. 都是先进先出
C. 只允许在端点处插入和删除元素 D. 没有共同点
18．栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈之前，栈中元素可以出栈，则出栈序列可能是（ D ）。
A. ABCED B. DBCEA C. CDABE D. DCBEA
19．表达式a*(b+c)-d的后缀表达式是( B )。
A. abcd*+1 B. abc+*d- C. abc*+d- D. -+*abcd
20．设依次进入一个栈的元素序列为c,a,b,d，不可得到的出栈的元素序列有（ B D ）。
A. a,b,c,d B. a,d,c,b C. b,a,d,c D. c,d,a,b
21．当需要随机查线性表的元素时，宜采用（ C ）作存储结构。
A. 双向链表 B. 循环链表 C. 顺序表 D. 单链表
22．表达式采用逆波兰式表示时可以不用括号，而且可以用基于（ A ）求值过程进行计算。
A. 栈 B. 队列 C. 符号表 D. 散列表
23．与逆波兰式ab+cd+*对应的中缀表达式是（ C ）。
A. a+b+c*d B. (a+b)*c+d C. (a+b)*(c+d) D. a+b*c+d
24．初始为空的堆栈中依次插入元素f、e、d、c、b、a以后，连续进行了三次删除操作，此时的栈顶元素是（ B ）。
A. c B. d C. b D. e
25．某堆栈的输入序列为1，2，3，……，n，输出序列的第一个元素为n，则第i个输出的元素为（ C ）。
A. i B. n-i C. n-i+1 D. 哪个元素无所谓
26．循环单链表表示队列，正确的说法是（ B ）。
A.可设一个头指针使入队、出队都方便
B.可设一个尾指针使入队、出队都方便
C.必须设头、尾指针才能使入队、出队都方便
D.无论如何，只可能使入队方便
27．在一个单链表中，若q所指结点是p所指结点的前驱结点，若在q与p之间插入一个s所指的结点，则执行（ D ）。
A. s->link=p->link; p->link=s; B. p->link=s; s->link=q;
C. p->link=s->link; s->link=p; D. q->link=s; s->link=p;
二、填空题
1．在 n(n>0) 个元素的顺序栈中删除1个元素的时间复杂度为： O(1)
2．设 SQ 为循环队列，存储在数组 d[m] 中，则 SQ 出队操作对其队头指针 front 的修改是 _ front = (front+1)%m 。
3．栈中元素的进出原则为 ___先进后出__________________ 。
4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个 队列 结构，其主要特点是 先进先出 。
5．对于一个以顺序实现的循环队列Q[0…m-1]，队头、队尾指针分别为f、r，其判空的条件是 r=f ，判满的条件是 (r+1)%m=f 。
6．在具有n个单元的循环队列中，队满时共有___n-1____个元素。
7．操作系统中先来先服务是___队列______数据结构应用的典型例子。
8．设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序为b、d、c、f、e、a，则栈S的容量最少应该是___3___。
9．用循环单链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别为_O(1)_和_ O(n)_；若只设尾指针，则出队和入队的时间复杂度分别为_ O(1)_和_ O(1)_。
10．用向量表示的循环队列的队首和队尾位置分别为1和max_size，试给出判断队列为满的边界条件为：(max_size+1)%MAXSIZE==1
11．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为：2 和 4 。
12．已知链栈的结点结构包括数据域(data)和指向下一个结点的指针域(next)，栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为：
1) p->next=top; 2) top=p;
三、判断题
1．若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。( R )
2．删除非空链式存储结构的堆栈(设栈顶指针为top)的一个元素的过程是依次执行:p←top,top←link(p),call RET(p)。( R )
1．若队列采用链式存储结构，队头指针与指针分别为front和rear，向队列中插入一个数据信息为item的新元素的过程是依次执行:
call GETNODE(p),data(P)←item,rear3 d←p,front←p。( W )
四、操作题
1．依次输入元素X,Y,Z, 插入到一个初始状态为空的链式栈中,试画出空的链式栈和每插入一个元素之后的链式栈示意图。
2．指出程序段完成的功能？
vode Demo1(SeqStack *S)
{ int i, arr[64], n=0;
while(!StackEmpty(S)) arr[n++] =Pop(S);
for(i=0; i<n; i++) Push(S, arr[i]);
}
3．设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。
【解答1】
template<class Type> void List<Type> :: Inverse ( ) {
if ( first == NULL ) return;
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论