《数据结构》-数据结构试卷第三章

数据结构期末复习题及参考答案第3章栈和队列一、选择题1、对于栈，操作数据的原则是（）。A先进先出B后进先出C后进后出D不分顺序2、要求数据遵循FIFO（先进先出）原则的数据结构是（）。A线性表B链表C队列D栈3、若进栈的序列为1,2,3,4，则以下哪一个不可能是一个出栈序列。A3,2,4,1B3,2,1,4C4,2,3,1D1,3,2,44、有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列（）A543612B453126C346521D2341565、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。A1，2，4，3，B2，1，3，4，C1，4，3，2，D4，3，1，2，6、在一个链队列中，若F，R分别为队首、队尾指针，则插入S所指结点的操作为AFNEXTC；FSBRNEXTS；RSCSNEXTR；RSDSNEXTF；FS7、一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。A23415B54132C23145D154328、数字1、2依次入栈，则出栈的顺序可能有（）种情况；数字1、2依次进入队列，则出队列的顺序可能有（）种情况。A1,2B2,1C2,2D1,19、设一个栈的输入序列是1，2，3，4，5，则下列序列中，是栈的合法输出序列的是（）。A51234B45132C43125D3215410、某堆栈的输入序列为A,B，C，D,下面的四个序列中，不可能是它的输出序列的是（）。AA，C，B，DBB,C，D，ACC,D，B,ADD,C，A，B11、顺序存储的栈和队列中已经各有N个结点，要删除一个结点分别需要移动数据（）次和（）次。AN/2,NBN,N/2C0,NDN,012、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是。AXYZBYZXCZXYDZYX13、一个递归算法必须包括（）。A递归部分B终止条件和递归部分C迭代部分D终止条件和迭代部分14、如下四个选项中，那个选项是能够正确判断循环队列是否排满元素的操作（其中MAXQSIZE表示队列的容量）（）AIFQREARQFRONTBIFQREARQFRONTMAXQSIZECIFQREARQFRONT1MAXQSIZEDIFQFRONTQREAR1MAXQSIZE15、假设以数组AM存放循环队列的元素，其头尾指针分别为FRONT和REAR，则当前队列中的元素个数为（）。AREARFRONTMMBREARFRONT1CFRONTREARMMDREARFRONTM16、若用一个大小为6的数组来实现循环队列，且当前REAR和FRONT的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，REAR和FRONT的值分别为多少A1和5B2和4C4和2D5和117、利用栈进行十进制数1348转换成八进制数，则入栈的数依次是（）。A1,3,4,8B8,4,3,1C2,5,0,4D4,0,5,218、最大容量为N的循环队列，队尾指针是REAR，队头是FRONT，则队空的条件是（）。AREAR1MODNFRONTBREARFRONTCREAR1FRONTDREARLMODNFRONT19、栈和队列的共同点是（）。A都是先进先出B都是先进后出C只允许在端点处插入和删除元素D没有共同点二、填空题1、栈是_操作受限（或限定仅在表尾进行插入和删除操作）的线性表，其运算遵循_后进先出_的原则。2、队列的插入操作在_队尾_进行，删除操作在队头_进行，其特点是_先进先出_。3、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_SSSS_。4、表达式求值是_栈_应用的一个典型例子。5、栈和队列在本质上都是同一种基本数据结构的特例，这种基本的数据结构就是线性表。6、在作进栈运算时，应先判别栈是否满，在作退栈运算时应先判别栈是否空。当栈中元素为N个，作进栈运算时发生上溢，则说明该栈的最大容量为N。三、简答题1、简要叙述循环队列的数据结构，分析循环队列的队头指针和队尾指针与循环队列元素之间的关系，写出INITQUEUE、QUEUELENGTH、ENQUEUE、DEQUEUE等循环队列的基本操作算法，并举例说明循环队列的操作函数的应用。参考答案（1）队列是一种先进先出FIRSTINFIRSTOUT，简称FIFO表的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。在队列中，允许插入的一端叫做队尾REAR，允许删除的一端称为队头FRONT。假设队列为Q（A1,A2,AN），则A1为队头元素，AN为队尾元素。队列的顺序存储结构称为顺序队列。顺序队列用一组地址连续的存储单元依次存放从队列头到队列尾的元素。由于队列的队头和队尾的位置是变化的，因而需要附设两个指针FRONT和REAR以指示队头和队尾元素在队列中的位置。在C语言中为了方便描述，约定初始化创建空队列时，令FRONTREAR0头尾指针相等。每当插入新的队尾元素时，REAR指针增1。每当删除队头元素时，FRONT指针增1。因此，在非空队列中，头指针FRONT始终指向队头元素，而尾指针REAR始终指向队尾元素的下一位置。循环队列用顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列为了解决上述“假溢出”现象，可采用牺牲一个存储单元（即少用了队列的一个元素空间）的方法解决“队满”和“队空”的判定问题，并规定队空时FRONTREAR；队满时REAR1MAXQSIZEFRONT。循环队列的数据结构DEFINEMAXQSIZE100/最大队列长度TYPEDEFSTRUCTQELEMTYPEBASE/指向初始化的动态分配存储空间INTFRONT/头指针,若队列不空，指向队列头元素INTREAR/尾指针,若队列不空，指向队列尾元素的下一个位置SQQUEUE（2）循环队列的队头指针和队尾指针与循环队列元素之间的关系见如下示意图循环队列为了克服“假溢出”现象，少用了队列的一个元素空间。在循环队列中，指针和队列元素之间的关系不变。每当插入新的队尾元素时，REAR指针增1。每当删除队头元素时，FRONT指针增1。并规定队空时FRONTREAR；队满时REAR1MAXQSIZEFRONT。（3）基本操作的算法描述STATUSINITQUEUESQQUEUEIFQBASEEXITOVERFLOW/存储分配失败QFRONTQREAR0RETURNOKINTQUEUELENGTHSQQUEUEQ/返回队列Q的元素个数，即队列的长度RETURNQREARQFRONTMAXQSIZEMAXQSIZESTATUSENQUEUESQQUEUE/队列满QBASEQREAREQREARQREAR1MAXQSIZERETURNOKSTATUSDEQUEUESQQUEUE否则返回ERRORIFQFRONTQREARRETURNERROREQBASEQFRONTQFRONTQFRONT1MAXQSIZERETURNOK注意上述函数代码要很好掌握（4）循环队列的操作函数的应用举例（略）注意上述操作要很好理解和掌握,能灵活应用2、若元素的进栈序列为A、B、C、D、E，运用栈操作，能否得到出栈序列B、C、A、E、D和D、B、A、C、E为什么答案能得到出栈序列B、C、A、E、D，不能得到出栈序列D、B、A、C、E。其理由为若出栈序列以D开头，说明在D之前的入栈元素是A、B和C，三个元素中C是栈顶元素，B和A不可能早于C出栈，故不可能得到D、B、A、C、E出栈序列。3、有字符串次序为3YA/Y2,利用栈，给出将次序改为3YAY2/的操作步骤。（可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS。答案XSXXXSSSXXSXXSXXSSSS四、算法分析1、简要叙述顺序栈的数据结构，分析顺序栈的栈顶指针和栈底指针与顺序栈元素之间的关系，写出PUSH/栈底指针SELEMTYPETOP/栈顶指针INTTACKSIZE/当前分配量,以元素为单位SQSTACK规定TOP永远指向下一次要插入的位置，非空栈中，TOP栈顶指针始终指在栈顶元素的下一个位置上。（2）顺序栈的栈顶指针和栈底指针与顺序栈元素之间的关系见如下示意图首先说明当BASENULL时，说明栈不存在。如图所示，栈空时BASETOP，此时,栈顶指针TOP，栈底指针BASE都指向栈底；每当插入新元素，指针TOP加1，删除栈顶元素时，指针TOP减1。栈的长度TOPBASE的值。（3）基本操作的算法描述STATUSINITSTACKSQSTACKIFSBASEEXITOVERFLOW/存储分配失败STOPSBASESSTACKSIZESTACK_INIT_SIZERETURNOK/INITSTACKSTATUSGETTOPSQSTACKS,SELEMTYPEESTOP1RETURNOKSTATUSPUSHSQSTACKIFSBASEEXITOVERFLOW/存储分配失败STOPSBASESSTACKSIZE/TOP指针位置SSTACKSIZESTACKINCREMENT/存储容量增加STOPERETURNOKSTATUSPOPSQSTACKESTOPRETURNOKSTATUSDESTROYSTACKSQSTACKS/销毁栈S，S不再存在/FREESBASESBASENULLSTOPNULLSSTACKSIZE0RETURNOKSTATUSCLEARSTACKSQSTACKS/把S置为空栈/STOPSBASERETURNOKSTATUSSTACKEMPTYSQSTACKS/若栈S为空栈，则返回TRUE，否则返回FALSE/IFSTOPSBASERETURNTRUEELSERETURNFALSEINTSTACKLENGTHSQSTACKS/返回S的元素个数，即栈的长度/RETURNSTOPSBASE注意上述函数代码要很好掌握（4）顺序栈的操作函数的应用举例（略）注意上述操作要很好理解和掌握,能灵活应用2、一个栈的输入序列为123，则栈的输出序列有哪几种答案共有以下5种情况1进栈,1出栈,2进栈,2出栈,3进栈,3出栈,栈的输出序列是1231进栈,2进栈,2出栈,1出栈,3进栈,3出栈,栈的输出序列是2131进栈,2进栈,2出栈,3进栈,3出栈,1出栈,栈的输出序列是2311进栈,2进栈,3进栈,3出栈,2出栈,1出栈,栈的输出序列是3211进栈,1出栈,2进栈,3进栈,3出栈,2出栈,栈的输出序列是132五、算法描述题编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。【算法分析】利用两个临时栈S1和S2。先将S栈中的内容移到S1栈中，再将S1栈中的内容移到S2栈中，最后将S2栈中的内容移到S栈中，即可实现。【算法源代码】REVERSESQSTACKSSQSTACKS1,S2/S,S1,S2均为栈类型