2.6 本章真题解析

2.6 本章真题解析

　　本章内容中需要考生重点掌握的是栈、队列的内容和应用。本节按照研究生入学考试的试题样式，参考历年的真题和全国40所高校的研究生入学试题，组织了相关的真题及解析，供读者学习。

2.6.1 单项选择题

　　例题1
　　为解决计算机主机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 （1） 。[2009年试题1]
　　（1）A．栈 B．队列 C．树 D．图
　　例题1分析
　　根据题意，主机将要输出的数据依次写入缓冲区，而打印机则依次从该缓冲区中取出数据，这说明该缓冲区中的数据应该满足先进先出的原则。因此，其数据结构为队列。
　　例题1答案
　　（1）B
　　例题2
　　设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是 （2） 。[2009年试题2]
　　（2）A．1 B．2 C．3 D．4
　　例题2分析
　　因为7个元素出队的顺序是b，d，c，f，e，a，g，而队列是一个先进先出的数据结构，因此，7个元素也是按照这个顺入进入队列Q的。根据题意，每个元素出栈后立即进入队列Q，也就是说，这7个元素是按照b，d，c，f，e，a，g顺序出栈的。而试题规定，元素a，b，c，d，e，f，g依次进入栈S，因此，元素进出栈的情况如下：a入栈，b入栈；b出栈；c入栈，d入栈；d出栈，c出栈；e入栈，f入栈；f出栈，e出栈，a出栈；g入栈，g出栈。
　　根据上述描述，栈中元素最多时为3个，因此，栈的容量至少为3。
　　例题2答案
　　（2）C
　　例题3
　　若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是 （3） 。[2010年试题1]
　　（3）A．dcebfa B．cbdaef 　 C．bcaefd 　 D．afedcb
　　例题3分析
　　栈按照后进先出的原则操作数据。
　　选项A可以按照a入栈、b入栈、c入栈、d入栈、d出栈、c出栈、e入栈、e出栈、b出栈、f入栈、f出栈、a出栈的方式得到。只有连续两次出栈操作，符合试题要求。
　　选项B可以按照a入栈、b入栈、c入栈、c出栈、b出栈、d入栈、d出栈、a出栈、e入栈、e出栈、f入栈、f出栈的方式得到。只有连续两次出栈操作，符合试题要求。
　　选项C可以按照a入栈、b入栈、b出栈、c入栈、c出栈、a出栈、d入栈、e入栈、e出栈、f入栈、f出栈、d出栈的方式得到。只有连续两次出栈操作，符合试题要求。
　　选项D可以按照a入栈、a出栈、b入栈、c入栈、d入栈、e入栈、f入栈、f出栈、e出栈、d出栈、c出栈、b出栈的方式得到，但这个顺序不符合题目中不允许连续三次进行退栈的要求。
　　例题3答案
　　（3）D
　　例题4
　　若用单链表来表示队列，下面几种数据结构中，最适合的选择是 （4） 。
　　（4）A．带尾指针的非循环链表 B．带尾指针的循环链表
　　C．带头指针的非循环链表 D．带头指针的循环链表
　　例题4分析
　　由于队列操作需要频繁访问队列的头结点和尾结点，所以，用一个带尾指针的循环链表来表示队列比较方便。
　　例题4答案
　　（4）B
　　例题5
　　某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（5） 。[2010年试题2]
　　（5）A．bacde B．dbace C．dbcae D．ecbad
　　例题5分析
　　输出受限的双端队列是一种特殊的队列。将队列两端分别叫做左端和右端，假设仅允许在右端进行出队操作。
　　选项A可以按照a左入、b右入、c左入、d左入、e左入的顺序入队，即得到队列的出队顺序bacde。
　　选项B可以按照a左入、b右入、c左入、d右入、e左入的顺序入队，即得到队列的出队顺序dbace。
　　选项C中，b、c均在a之前出队，故均在a的右侧即都是右入，而入队顺序又必须是b先入队，则c应当在b的右侧，出队时应当c先出b再出，故不能得到C中的顺序。
　　选项D可以按照a左入、b右入、c右入、d左入、e右入的顺序入队，即得到队列中从左到右的出队顺序ecbad。
　　例题5答案
　　（5）C
　　例题6
　　设有一足够大的栈，入栈序列为x，y，z，u，v，下列 （6） 序列是不可能的。
　　（6）A．x，y，z，u，v B．y，x，z，u，v
　　C．z，x，y，u，v D．v，u，z，y，x
　　例题6分析
　　由于栈的先进后出规律，在给定输入序列后，有些输出序列是不可能出现的。例如，在本题中的（z，x，y，u，v）序列中。因为第一个输出是z，说明x和y已经依次入栈。根据先进后出的原则，只可能y先出栈，x后出栈，所以，输出（z，x，y，u，v）是不可能的。其他几个序列都可以通过栈操作输出，过程不复杂，在此不依次演示。
　　例题6答案
　　（6）C
　　例题7
　　设计一个判别表达式中左、右括号是否配对出现的算法，采用 （7） 数据结构最佳。
　　（7）A．线性表的顺序存储结构 B．队列
　　　　 C．线性表的链式存储结构 D．栈
　　例题7分析
　　栈的特点是先进后出，这个特点对于判断表达式中左、右括号的匹配很适合。
　　例题7答案
　　（7）D
　　例题8
　　循环队列用数组V[0..m-1]存放其元素值，已知其头、尾指针分别是f和r，则当前队列中的元素个数是 （8） 。
　　（8）A．(r-f+m)%m       B．r-f+1
　　　　  C．(r-f+m+1) %m D．(r-f+m-1)%m
　　例题8分析
　　因为是循环队列，f有可能比r大，所以，要用到求余操作。当f>r时，当前队列中的元素个数为(r-f+m)%m。
　　例题8答案
　　（8）A
　　例题9
　　若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别是0和3。当从队列中删除一个元素，再加上两个元素后，rear和front的值为 （9） 。
　　（9）A．1和5 B．2和4 C．4和2 D．5和1
　　例题9分析
　　出队时，front执行的操作是front=(front+1)%QueneSize，入队时，rear执行的操作是rear=(rear+1)%QueneSize。
　　例题9答案
　　（9）B
　　例题10
　　已知循环队列的存储空间为数组a[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为 （10） 。
　　（10）A．5 B．6 C．16 D．17
　　例题10分析
　　根据例题8的分析，具体到本题，m=21，f=8，r=3，可以计算出(r-f+m)%m=16。
　　例题10答案
　　（10）C
　　例题11
　　一个栈的入栈元素序列是1、2、3、4、5，若允许出栈操作可在任意可能的时刻进行，则下面的序列中，不可能出现的出栈序列是 （11） 。
　　（11）A．3、4、2、5、1 B．2、5、4、1、3
　 　　　  C．2、3、1、5、4 D．3、5、4、2、1
　　例题11分析
　　栈的特点是先进后出，按照以下步骤可以很快找到答案：
　　（1）选择出栈序列的第一个元素a，入栈序列中在a之前的元素必须按照逆序出现在出栈序列中，如果不按照逆序出栈，则此出栈序列不合法，否则执行下一步。
　　（2）从入栈序列和出栈序列中将元素a删除，如果删除a后出栈序列为空，则说明此出栈序列合法，否则回到上一步继续执行。
　　在本题中，B选项的第一个出栈元素为2，在2之前入栈的元素为1，由于只有一个元素，故无论如何将会逆序出栈；在序列中剔除2，则入栈序列为1、3、4、5，出栈序列变为5、4、1、3。分析元素5，在新的入栈序列中，5之前的元素入栈序列为1、3、4，而出栈序列为4、1、3，不满足逆序出栈的条件，所以，选项B是不可能出现的出栈序列。
　　例题11答案
　　（11）B
　　例题12
　　数组A[0..5,0..6]的每个元素占5个字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素A[5,5]的起始地址是 （12） 。
　　（12）A．1200 B．1180
　　　　　C．1205 D．1210
　　例题12分析
　　由于是行优先，在A[5,5]的前面已经存放了5行元素，每行7个元素。而A[5,5]在第5行第5列，在第5列中，前面也存放了5个元素（列下标为0、1、2、3、4），因此，A[5,5]前面存放的元素个数实际为5×7+5=40个。每个元素占5个字节，因此，A[5,5]的存储地址为1000+40×5=1200。
　　对于这类试题，假设数组为a[0..x,0..y]，每个元素占用m个字节，则可以按照下列公式进行计算a[i][j]的存储地址：
　　行优先：LOC(a[i][j]) = LOC(a[0][0])+[j×(y+1)+j]×m。
　　列优先：LOC(a[i][j]) = LOC(a[0][0])+[i×(x+1)+i]×m。
　　例题12答案
　　（12）A
　　例题13
　　若栈采用顺序存储方式存储，现两栈共享空间V[m]，top[i]代表第i个栈( i =1，2)栈顶，栈空时栈1的底在v[0]，top[1]=0，栈2的底在V[m-1]，top[2]=m-1，则栈满的条件是 （13） 。
　　（13）A．top[1] = top[2] B．top[1] + 1 = top[2]
　　　　　C．top[1] + top[2] = m D．top[1] - 1 = top[2]
　　例题13分析
　　两栈合用一个数组空间，通过栈空时top的值可知：top指向了下一个元素入栈的数组下标位置，因此，如果top[1]=top[2]，可知当前还有一个元素空间未用，此后再有一个元素入栈，则栈满。
　　（1）如果栈1执行入栈操作，则top[1]++；
　　（2）如果栈2执行入栈操作，则top[2]--；
　　因此，无论是情况（1）还是情况（2），最终的结果都将是top[1]-1=top[2]。
　　例题13答案
　　（13）D
　　例题14
　　数组SZ[-3..5，0..10]含有元素的数目为 （14） 。
　　（14）A．88 B．99 C．80 D．90
　　例题14分析
　　该数组共有5-(-3)+1=9行，10-0+1=11列，故共有9×11=99个元素。
　　例题14答案
　　（14）B
　　例题15
　　稀疏矩阵的三元组存储方法 （15） 。
　　（15）A．实现转置运算很简单，只需要每个三元组中的行标和列标交换
　　　　　B．是一种链式存储方法
　　　　　C．矩阵的非零元个数和位置在操作过程中变化不大时较有效
　　　　　D．比十字链表法更高效
　　例题15分析
　　稀疏矩阵如果采用三元组存储方法，实现转置运算需要每个三元组中的行标和列标交换，还要实现三元组之间的重新排列，所以，A是错误的。
　　稀疏矩阵的三元组存储方法不是链式存储，而是利用数组存储，所以，B是错误的。
　　稀疏矩阵的三元组存储方法与十字链表相比，谁的效率更高，需要根据应用情况进行判定。所以，D是错误的。稀疏矩阵的三元组存储方法当矩阵的非零元个数和位置在操作过程中变化不大时较有效。
　　例题15答案
　　（15）C
　　例题16
　　用十字链表表示一个稀疏矩阵，每个非零元一般用一个含有 （16） 个域的结点表示。
　　（16）A．2 B．3 C．4 D．5
　　例题16分析
　　存储稀疏矩阵的十字链表结点包括5个域：该非零元的行下标、该非零元的列下标、该非零元的值、该非零元所在行表的后继链域，以及该非零元所在列表的后继链域。
　　例题16答案
　　（16）D
　　例题17
　　利用栈求解表达式的值时，设立操作数栈open，设open只有两个存储单元，在下列表达式中，不发生上溢的是 （17） 。
　　（17）A．a-b*(c-d) B．(a-b)*c-d C．(a-b*c)-d D．(a-b)*(c-d)
　　例题17分析
　　在试题的4个选项中，只有(a-b)*c-d的运算顺序是依次向右，不需要暂存其他的操作数来配合运算符优先。
　　例题17答案
　　（17）B