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

数据结构上机实验与习题解析 亱店↘打烊oO

15．设元素1，2，3，4，5依次入栈，若要得到输出序列34251，则应进行的操作序列为PUSH(S,1)，PUSH(S,2)，_____________，POP(S)，PUSH(S,4)，POP(S)，_____________，_____________，POP(S)，POP(S)。

【答案】（1）PUSH(S,3) （2）POP(S) （3）PUSH(S,5)

3.3 判断题

1．即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同（ ）

【答案】×

【解析】栈的性质为后进先出，不同的入栈出栈组合得到的输出序列不一定相同。例如：对于序列123，进行不同的入栈出栈操作，可能得到的输出序列有：123，213，321等。

2. 链式队列队满条件是尾指针加一等于头指针（ ）

【答案】×

【解析】链队列本身没有容量限制，所以在用户内存空间的允许范围内不会出现队满的情况。

3. 栈和队列都是线性表，只是在插入和删除时受到了一些限制（ ）

【答案】√

4. 循环队列也存在空间溢出问题（ ）

【答案】√

5. 循环队列通常用指针来实现队列的头尾相接（ ）

【答案】×

【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。

3.4 应用题

1．名词解释：栈和队列

栈是只允许在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。

队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。

2. 假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。

（1）试指出判别给定序列是否合法的一般规则。

（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举列说明。

【答案】（1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。（2）可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的SXSXSX操作序列；对于合法序列BAC，我们使用SSXXSX操作序列。

3. 如果输入序列为123456，试问能否通过栈结构得到以下两个序列：435612和13542 6，请说明为什么不能或如何才能得到。

【答案】输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。

4. 简述顺序存储队列的假溢出的避免方法及队列满和空的条件。

【答案】设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即