专升本数据结构试题解析(11)

第3章 桟和队列

3.1 选择题

1．一个栈的输入序列为123 n，若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是（ ）

A）不确定 B）n-i+1 C）i D）n-i

【答案】B

【解析】根据栈的性质（LIFO），若输出的第一个元素是n，则表明所有的元素已经入栈，则出栈顺序为n，n-1， ，3，2，1。

2．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（ ）

A）6 B）4 C）3 D）2

【答案】C

【解析】根据栈的性质（LIFO）得，e2出栈前，栈中存有e1和e2两个元素，e4出栈前，栈中存有e1、e3和e4三个元素，e4和e3出栈以后，e5和e6入栈，栈中同样存在e1、e5和e6三个元素，然后三个元素依次出栈，所以栈的容量至少应该为3。

3．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（ ）

A）top=top+1; V[top]=x B）V[top]=x; top=top+1

C）top=top-1; V[top]=x D）V[top]=x; top=top-1

【答案】C

【解析】栈式运算受限的线性表，只允许在栈顶进行插入和删除操作。本题中栈顶指针为n+1，该数组将栈顶放在了下标大的一端，所以在进行入栈操作时top指针应该进行减一操作。通常元素进栈的操作为：先移动栈顶指针后存入元素。

4．如果我们用数组A[1..100]来实现一个大小为100的栈，并且用变量top来指示栈顶，top的初值为0，表示栈空。请问在top为100时，再进行入栈操作，会产生（ ）

A）正常动作 B）溢出 C）下溢 D）同步

【答案】B

【解析】当top为100时，表示栈已经满了，此时再进行入栈操作，则会造成溢出。

5．栈在（ ）中应用。

A）递归调用 B）子程序调用 C）表达式求值 D）A，Ｂ，Ｃ

【答案】D

6．表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ），其中^为乘幂 。

A）3,2,4,1,1；(*^(+*- B)3,2,8；(*^-

C）3,2,4,2,2；(*^(- D)3,2,8；(*^(-

【答案】D

【解析】根据表达式求值的基本思想，在扫描表达式时，依次读入表达式的每个字符，若是操作数则进对象栈，若为运算符则和运算符栈的栈顶运算符比较优先级后做相应的操作。

7．用链接方式存储的队列，在进行删除运算时（ ）

A）仅修改头指针 B）仅修改尾指针

C）头、尾指针都要修改 D）头、尾指针可能都要修改

【答案】D

【解析】若队列中的元素多于一个，删除队列中的队尾元素，只需修改队尾指针；若队列中只有一个元素，删除该元素后，队头队尾指针都需要修改。

8．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )

A）(rear-front+m)%m B）rear-front+1

C）rear-front-1 D）rear-front

【答案】A

【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的求元素个数的运算可以利用求模运算。

9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )