数据结构（中国海洋大学） 第三章_智慧树知到答案2021年

第三章 栈和队列：栈（Stack）是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表（Last In First Out）。通常栈有顺序栈和链栈两种存储结构。队列（Queue）是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称      为队头（front），允许插入的一端称为队尾（rear） ，队列的操作原则是先进先出的，又称作FIFO表（First In First Out） .队列也有顺序存储和链式存储两种存储结构。3.1栈:栈和队列的抽象类型定义及其顺序存储结构和链式存储的表示及实现，栈的应用举例。
3.2栈的应用举例:利用栈解决各种经典的应用问题的举例
3.3队列:队列抽象类型定义，及链队列、循环队列的表示方法
3.1栈:栈和队列的抽象类型定义及其顺序存储结构和链式存储的表示及实现，栈的应用举例。
3.2栈的应用举例:利用栈解决各种经典的应用问题的举例
3.3队列:队列抽象类型定义，及链队列、循环队列的表示方法

[单选题]

循环队列存储在数组A[0..m-1],则出队时的操作为（     ）

选项:[front=(front mod m)+1 , front=(front+1)mod m , front=front+1, front=(front+1)mod (m-1) ]
[单选题]

设计一个迷宫求解的算法，采用___________数据结构最佳。                                    

选项:[队列 , 栈 , 线性表的链式存储结构, 线性表的顺序存储结构 ]
[单选题]

Status SymmetryString(char* p){ Queue q; if(!InitQueue(q)) return 0; Stack s; InitStack(s); ElemType e1,e2; while(*p){ Push(s,*p); EnQueue(q,*p); p++; } while(!StackEmpty(s)){    (    )           DeQueue(q,e2); if(e1!=e2) return FALSE; } return OK;}

选项:[EnQueue(q,*p), P--P--P--P--P--P--P--P--, Push(s,*p); , Pop(s,e1);]
[单选题]

若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（      ）； 

选项:[SXSSXXXX, SXXSXSSX , SXSXXSSX, SSSXXSXX]
[单选题]

1.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列₁&序列₂’模式的字符序列。其中序列₁和序列₂中都不含字符‘&’，且序列₂是序列₁的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。

BOOLSymmetry(char a[])

{

     int i=0;

     Stack s;

     InitStack(s);

     ElemType x;

     while(a[i]!='&' && a[i]){

           _________

          i++;

     }

     if(!a[i]) return FALSE;

     i++;

     while(a[i]){

          Pop(s,x);

          if(x!=a[i]){

               DestroyStack(s);

               return FALSE;

          }

          i++;

     }

     return TRUE;

}

选项:[Pop(s,a[i]), Push(s,a[i++]), Pop(s,a[i++]), Push(s,a[i])]
[单选题]

若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（      ）； 

选项:[ SXXSXSSX , SXSSXXXX, SSSXXSXX, SXSXXSSX]
[单选题]

设计一个迷宫求解的算法，采用___________数据结构最佳。                                    

选项:[队列 , 线性表的链式存储结构, 线性表的顺序存储结构 , 栈 ]
[单选题]

循环队列存储在数组A[0..m-1],则出队时的操作为（     ）

选项:[front=(front mod m)+1 , front=(front+1)mod m , front=(front+1)mod (m-1) , front=front+1]
[单选题]

1.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列₁&序列₂’模式的字符序列。其中序列₁和序列₂中都不含字符‘&’，且序列₂是序列₁的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。

BOOLSymmetry(char a[])

{

     int i=0;

     Stack s;

     InitStack(s);

     ElemType x;

     while(a[i]!='&' && a[i]){

           _________

          i++;

     }

     if(!a[i]) return FALSE;

     i++;

     while(a[i]){

          Pop(s,x);

          if(x!=a[i]){

               DestroyStack(s);

               return FALSE;

          }

          i++;

     }

     return TRUE;

}

选项:[Pop(s,a[i]), Pop(s,a[i++]), Push(s,a[i++]), Push(s,a[i])]
[单选题]

Status SymmetryString(char* p){ Queue q; if(!InitQueue(q)) return 0; Stack s; InitStack(s); ElemType e1,e2; while(*p){ Push(s,*p); EnQueue(q,*p); p++; } while(!StackEmpty(s)){    (    )           DeQueue(q,e2); if(e1!=e2) return FALSE; } return OK;}

选项:[EnQueue(q,*p), Push(s,*p); , Pop(s,e1);, P--P--P--P--P--P--P--P--]