《数据结构》-第三章

习题31选择题1、栈的插入和删除操作在（A）进行。A、栈顶B、栈底C、任意位置D、指定位置2、利用大小为N的数组顺序存储一个队列时，该队列最大长度为（B）。A、N2B、N1C、ND、N13、若已知一个栈的入栈序列是1，2，3，N，其输出序列为P1，P2，P3，PN,那么P1N；PI为（C）。、I、NI、NI1、不确定4、假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列。下列序列（A）是合法的。、IOIIOIOO、IOOIOIIOC、IIIOIOIOD、OIIOIOIO5、递归函数可以调用自身（B）次。、只多1次、任意次数、0次、至多2次32填空题1、线性表、栈和队列都是（线性）结构，可以在线性表的（任意）位置插入和删除元素；对于栈只能在（栈顶）插入和删除元素；对于队列只能在（队尾）插入元素和在（队首）删除元素。2、对于一个顺序栈作进栈运算时，应先判别栈是否为（满），作退栈运算时，应先判别栈是否为（空），当栈中元素为M时，作进栈运算时发生上溢，则说明栈的可用最大容量为（M）。3、设有一个空栈，现有输入序列1，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是（2，3）。4、无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除操作的时间复杂度均相同为（O1）。5、有一个循环队列，分配到的存储空间大小为N，则其队满条件是（REAR1QUEUEMAXSIZEFRONT），队列为空的条件是（REARFRONT）。33应用题、若依次读入数据元素序列A,B,C,D进栈，进栈过程中允许出栈，试写出各种可能的出栈元素序列。答因为栈中每个元素进栈的同时又可以马上出栈，所以可能的出栈序列共14种A,B,C,DA,B,D,CA,C,B,DA,C,D,BA,D,C,BB,A,C,DB,A,D,CB,C,D,AB,C,A,DB,D,C,AC,B,A,DC,B,D,AC,D,B,AD,C,B,A2、以下代码段执行什么操作STACKS1，TMP；ELEMTYPEX；WHILEEMPTYS1XGETTOP（S1）；POPS1；PUSHTMP，X；WHILESTACKEMPTYTMPXGETTOP（TMP）；POPTMP；PUSHS1，X；解将S1栈中的元素依次读出，并送到栈TMP中，再将TMP栈中的元素依次读出，再次送到栈S1中。34算法题1、如果ELEMTYPE为INT，编写函数VOIDSELECTITEMSTACKS，INTN使用栈操作查询数据项N在栈中的第一次出现之处并将其移至栈顶。其他元素保持原来的次序。VOIDSELECTITEMSTACKS,INTNSTACKTINTM1ELEMTYPEXPOPS,XWHILEEMPTYSPOPS,XMIFEMPTYSPRINTF“不存在查找的元素N”ELSEWHILEEMPTYTPOPT,XPUSHS,XPUSHS,NPRINTF“查找元素第一次出现的位置为DN”,M2、对于一个具有M个单元的INT型循环队列，写出求队列中元素个数和在队列中插入或删除一个结点的算法。STRUCTQUEUEINTQUEUEM；INTFRONT，REAR；算法1求队列中元素个数INTCOUNTQUEUEQIFQFRONTREARRETURNQREARQFRONTELSERETURNMQFRONTQREAR算法2进队操作VOIDENQUEUEQUEUEQ,ELEMTYPEELEMIFQREAR1MQFRONTPRINTF“队列上溢出N“ELSEQREARQQUEUEQREARELEM算法3出队操作VOIDDLQUEUEQUEUEQIFQFRONTQREARPRINTF“队列为空N“ELSEQFRONTQFRONT1MAXSIZE3、试写出函数FIBONACCI数列F10N1F21，N2FNFN1FN2N2的递归算法和非递归算法。递归算法LONGFINTNIFN1|N2RETURN1ELSERETURNFN1FN2非递归算法LONGFINTNINTN1,N2,N3N1N21IFN1|N2RETURN1ELSEFORINTJ3JDATAXSNEXTNULLQREARNEXTS/将S结点链到队尾QREARS算法2循环队列的出队操作VOIDDLQUEUELINKQUEUEQLNODETIFQREARNEXTNEXTNULLPRINTF“队列为空N“ELSEIFQREARNEXTNEXTQREARTQREARQREARQREARNEXTQREARNEXTNULLELSETQREARNEXTNEXTQREARNEXTNEXTTNEXTFREET5、设有两个栈S1和S2都采用顺序存储方式，共享一个存储区0MAXSIZE1，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式，试设计有关栈基本操作的算法。（可作为上机实践题目）解为了区分两个栈，设置一个标志N,为1表示对栈1进行操作，为2表示对栈2进行操作。顺序存储类型定义为STRUCTSTACKELEMTYPESTACKMAXSIZEINTTOP1,TOP2操作一初始化。VOIDINITSTACK1STACKELSESTOP2MAXSIZE操作二清空VOIDCLEARSTACKSTACKELSESTOP2MAXSIZE操作三进栈操作VOIDPUSHSTACKELSEIFN1STOP1SSTACKSTOP1ELEMELSESTOP2SSTACKSTOP2ELEM操作四出栈操作VOIDPOPSTACKELSEWSSTACKSTOP1STOP1ELSEIFSTOP2MAXSIZEPRINTF“栈溢出N“ELSEWSSTACKSTOP2STOP2操作五读取栈顶元素操作ELEMTYPEGETTOPSTACKS,INTNIFN1IFSTOP11PRINTF“栈空N“RETURNNULLELSERETURNSSTACKSTOP1ELSEIFSTOP2MAXSIZEPRINTF