数据结构-第3章习题PPT课件

1、2021/6/70 1. 对于栈操作数据的原则是（对于栈操作数据的原则是（ ）。）。 A. 先进先出先进先出 B. 后进先出后进先出 C. 后进后出后进后出 D. 不分顺序不分顺序 2. 在作进栈运算时在作进栈运算时,应先判别栈是否应先判别栈是否( ),在作退栈运算时应在作退栈运算时应 先判别栈是否先判别栈是否( )。当栈中元素为。当栈中元素为n个个,作进栈运算时发作进栈运算时发 生上溢生上溢,则说明该栈的最大容量为则说明该栈的最大容量为( )。为了增加内存空。为了增加内存空 间的利用率和减少溢出的可能性间的利用率和减少溢出的可能性,由两个栈共享一片连续的由两个栈共享一片连续的 内存空间时内存

2、空间时,应将两栈的应将两栈的 ( )分别设在这片内存空间的两分别设在这片内存空间的两 端端,这样这样,当当( )时，才产生上溢。时，才产生上溢。 , : A. 空空 B. 满满 C. 上溢上溢 D. 下溢下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 长度长度 B. 深度深度 C. 栈顶栈顶 D. 栈底栈底 : A. 两个栈的栈顶同时到达栈空间的中心点两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空两个栈均不

3、空,且一个栈的栈顶到达另一个栈的栈底且一个栈的栈顶到达另一个栈的栈底. 2021/6/71 1.B 2.1.B 2.2.A 2.3B 2.4D 2.5C 2021/6/72 3. 一个栈的输入序列为一个栈的输入序列为123n，若输出序列的第一，若输出序列的第一 个元素是个元素是n，输出第，输出第i（1=idata=x; s-next=null； r-next=s；r=s； 2021/6/720 1、利用两个栈、利用两个栈sl,s2模拟一个队列时，如何用栈模拟一个队列时，如何用栈 的运算实现队列的插入，删除以及判队空的运算实现队列的插入，删除以及判队空 运算。请简述这些运算的算法思想。运算。请简

4、述这些运算的算法思想。 2021/6/721 栈的特点是后进先出，队列的特点是先进先出。初始栈的特点是后进先出，队列的特点是先进先出。初始 时设栈时设栈s1和栈和栈s2均为空。均为空。 （1）用栈）用栈s1和和s2模拟一个队列的输入：设模拟一个队列的输入：设s1和和s2容量容量 相等。分以下三种情况讨论：若相等。分以下三种情况讨论：若s1未满，则元素入未满，则元素入 s1栈；若栈；若s1满，满，s2空，则将空，则将s1全部元素退栈，再压全部元素退栈，再压 栈入栈入s2，之后元素入，之后元素入s1栈；若栈；若s1满，满，s2不空（已有不空（已有 出队列元素），则不能入队。出队列元素），则不能入队

5、。 （2）用栈）用栈s1和和s2模拟队列出队（删除）：若栈模拟队列出队（删除）：若栈s2不空，不空， 退栈，即是队列的出队；若退栈，即是队列的出队；若s2为空且为空且s1不空，则将不空，则将 s1栈中全部元素退栈，并依次压入栈中全部元素退栈，并依次压入s2中，中，s2栈顶元栈顶元 素退栈，这就是相当于队列的出队。若栈素退栈，这就是相当于队列的出队。若栈s1为空并为空并 且且s2也为空，队列空，不能出队。也为空，队列空，不能出队。 （3）判队空）判队空 若栈若栈s1为空并且为空并且s2也为空，才是队列空。也为空，才是队列空。 2021/6/722 讨论：讨论：s1和和s2容量之和是队列的最大容量

6、。其操作是，容量之和是队列的最大容量。其操作是，s1栈满栈满 后，全部退栈并压栈入后，全部退栈并压栈入s2（设（设s1和和s2容量相等）。再入栈容量相等）。再入栈s1 直至直至s1满。这相当队列元素满。这相当队列元素“入队入队”完毕。出队时，完毕。出队时，s2退栈退栈 完毕后，完毕后，s1栈中元素依次退栈到栈中元素依次退栈到s2，s2退栈完毕，相当于队退栈完毕，相当于队 列中全部元素出队。列中全部元素出队。 在栈在栈s2不空情况下，若要求入队操作，只要不空情况下，若要求入队操作，只要s1不满，就可压不满，就可压 入入s1中。若中。若s1满和满和s2不空状态下要求队列的入队时，按出错不空状态下要求队列的入队时，按出错 处理。处理。 2021/6/723 习题集习题集24页页3.17Int IsReverse( )/判断输入的字符串中判断输入的字符串中 While (e=getchar()!=/不允许在不允许在 while (e=getchar()!=) if(Sta