数据结构练习3（栈和队列）

数据结构练习（栈和队列）

一、选择题

1．有5个元素a,b,c,d,e依次进栈，允许任何时候出栈，则可能的出栈序列是 C 。

A．baecd B．dceab

C．abedc

D．aebcd

2．下列有关递归的叙述，不正确的是 B 。

A．在计算机系统内，执行递归函数是通过自动使用栈来实现的。

B．在时间和空间效率方面，递归算法比非递归算法好。 C．递归函数的求解过程分为递推（进栈）和回推（出栈）两个阶段。

D．在递归函数中必须有终止递归的条件。 3．栈和队列均属于哪一种逻辑结构 A 。

A．线性结构 B．顺序结构 C．非线性结构 D．链表结构

4．设输入元素为1、2、3、P和A，输入次序为123PA，元素经过栈后得到各种输出序列，则可以作为高级语言变量名的序列有 D 种。

A．4

B．5

C．6

D．7

5．一个队列的入队序列为a，b，c，d，则该队列的输出序列是

B 。

A．dcba B．abcd C．adcb

D．cbda

6． 在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是 B 。

A. f->next=s; f=s; B. r->next=s; r=s;

C. s->next=s; r=s; D. s->next=f; f=s;

7．如果5个元素出栈的顺序是1、2、3、4、5，则进栈的顺序可能是 C 。

A．3、5、4、1、2 B．1、4、5、3、2

C． 5、4、1、3、2 D．2、4、3、1、5

8．已知一个栈的进栈序列为1，2，3，…，n，其出栈输出序列是p1，p2，p3，…，pn。若p1=3，则p2的值 D 。 A．一定是2

D．可能是2

B．一定是1

C．可能是1

9．以1，2，3，…，n的顺序进队列，则可能的出队序列有 D 种。 A．1

B．n

C．n(n+1)/2

D．

10．在计算递归函数时，如不用递归过程，应借助于 B 这

种数据结构。

A. 线性表 B. 栈 C. 队列 D. 双向队列

二、填空题

1．栈和队列是一种特殊的线性表，其特殊性体现在是 运算受限 线性表。设现有元素e1,e2,e3,e4,e5和e6依次进栈，若出栈的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少是 3 。

2．顺序循环队列中，设队头指针为front，队尾指针为rear，队中最多可有MAX个元素，采用少用一个存储单元的方法区分队满与队空问题，则元素入队列时队尾指针的变化为

rear=(rear+1)%MAX ；元素出队列时队头指针的变化为 front=(front+1)%MAX ；队列中的元素个数为

(rear-fort+MAX)%MAX 。 队满的判别条件为为

(rear+1)%MAX=front ，队空的判别条件为rear==front 。

3．下列函数的功能是 从首尾开始依次交换 。 void convert(char *s, int n) { char t; if(n>0)

{ t=*(s+n-1);

*(s+n-1)=*s; *s=t;

convert(++s,n-2);

}

else return; }

4．下列算法的功能 判断回文 。

int func() {

InitStack(S); //初始化栈 InitQueue(Q); //初始化队列 while((c=getchar())!=’\\n’) { Push(S,c); EnQueue(Q,c); }

while(!StackEmpty(S)) {

Pop(S,a); DeQueue(Q,b);

if(a!=b) return 0; }

return 1; }

三、解答题

1．用一维数组a[7] 顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有5个元素：22，30，16，36，58，其中22是队首， front值为5，请画出对应的存储状态图，当连续做两次出队运算后，再做两次入队运算，让元素80，55依次进队，请再画出对应的存储状态图。 22 58 36 16 30 55 80 58

本文来源：https://www.bwwdw.com/article/fdzt.html