栈与队列(习题课)讲课教案.ppt

《栈与队列(习题课)讲课教案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章习题填空题5.在一个顺序循环队列中为了方便入队列和出队列的操作通常约定头指针front指向实际队头元素的____________，尾指针rear指向当前实际队尾元素的____________。若该顺序循环队列有m个存储单元，则队列满时共有__________个元素。前一个位置，所在位置，m-1分析：在顺序循环队列中约定头指针front和尾指针rear所指向的位置，是牺牲掉一个存储单元而方便表示队列空和队列满的条件，因此顺序循环队列中实际可用的存储单元只有m-1个6.设有一个顺序循环队列如上题中的约定，则该队列满的条件是_________，队

2、列空的条件是_________。(rear+1)%m==front，rear==front7.不论是顺序栈（队列）还是链式栈（队列），插入（删除）运算的时间复杂度均为________。O(1)8.系统在函数调用前自动把调用后的____________压入堆栈；当函数调用结束后，系统又自动作退栈处理，并将程序执行流程无条件转移到所保存的_____________处继续执行。返回地址，返回地址选择题1.设栈的输入序列是1、2、3、…、n，输出序列的第一个元素是n，则第i个输出元素是（）。①n-i②n-i-1③n-i+1④不确定(3)分析：设栈的输入序

3、列是1、2、3、……、n，输出序列的第一个元素是n，则输出序列必定是n、n-1、n-2、……、1，因此第i个输出元素是n+1-i。2．设元素进栈次序为A、B、C、D、E，则下列不可能的出栈序列是（）。①ABCDE②BCDEA③EABCD④EDCBA(3)3．设用一维数组s[m]表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进行出栈时的操作序列是（）。①x=s[op]；②x=s[top]；top=0；③x=s[top]；top==top-1；④x=s[top]；top==top+1；(3)4.设指针hs指向栈顶，指针s指向插入的结

4、点A，则插入结点A时的操作为（）。①hs->next=s；②s->next=hs；hs=s；③s->next=hs->next；hs->next=s；④s->next=hs；hs=hs->next；(2)5．设用一维数组s[m]表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进行入栈时的操作序列是（）。①s[top]=x；②top=top+1；s[top]=x；③top==top-1；s[top]=x；④s[top]=x；top==top+1；(2)6．设front是链式队列的头指针，rear是链式队列的尾指针，s指向插入的结点A

5、，则插入结点A的操作为（）。①front->next=s；front=s；②s->next=rear；rear=s；③rear->next=s；rear=s；④s->next=front；front=s；(3)7.设front是链式队列的头指针，rear是链式队列的尾指针，则删除队头元素的操作为（）。①front=front->next；②rear=rear->next；③rear=front->next；④front=rear->next；(1)8．对于一个具有m个存储单元的顺序循环队列，设front为队头指针，rear为队尾指针，则该队列中队

6、列元素的个数计算公式为（）。①rear-front②front-rear③(rear-front)%m④(rear-front+m)%m(4)分析：顺序循环队列中的元素个数=，整理合并可写成(rear-front+m)%m。9.设用一维数组q[m]作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rear指向队尾元素的当前位置，则入队列的操作序列为（）。①q[rear]=x；rear=rear+1；②q[rear]=x；rear=rear-1；③rear=(rear+1)%m；q[rear]=x；④rear=(rear-1)%m；q

7、[rear]=x；(3)10.设用一维数组q[m]作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rear指向队尾元素的当前位置，则出队列的操作序列为（）。①x=q[front]；front=front+1；②x=q[front]；front=(front+1)%m；③x=q[front]；front=front-1；④x=q[front]；front=(front-1)%m；(2)算法设计题1.设有两个顺序栈S1和S2共享一个存储区S[0：m-1]，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别

8、设计两个栈的入栈和出栈操作。分析：本题算法思想是引入形式参数flag，当形式参数flag的值为1时表示对栈1进行操作，flag的值为2时