第三章 栈与队列
一、 单项选择题
1、D A 2、A 3 C 4 B 5 D 6 C 7 D 8 C 9C 10 C 11 A 12A 13 A 14 D 15 B 16 D 17 C 18 C 19 D 20 B 21C 22 A D 23 B
二、填空题
1、后进先出
2、存储结构
3、链栈
4、可能的
5、lst=NULL
6、链栈头 链栈头
7、先进先出
8、存储结构
9、链对
三、判断题
1、错误 2、正确 3、正确 4、错误 5、错误
6、错误 7、正确 8、错误 9、正确 10、正确
11、正确 12、正确 13、正确
四、简答题
1、可能的次序有CDBAE 、 CDEBA 、 CDBEA
2、高级语言变量名的定义规则是：以字母开头的字母数字串。入栈次序为123PA ，以A 最先出栈的序列为AP321，以P 最先出栈的序列为P321A 、P32A1、P3A21、PA321。可以作为高级语言的变量名的序列为AP321、P321A 、P32A1、P3A21和PA321。
3、（1）能得到输出顺序为325641的序列，其操作序列为：AAADDAADADDD 。
（2）不能得到输出顺序为154623的序列；执行ADAAAADDAD ，得到输出序列1546后，栈中元素从栈顶到栈底为32，不能让2先出栈，所以得不到输出序列154623。
4、栈和队列是操作位置受限的线性表，即对插入和删除操作的位置加以限制。栈是仅允许在表的一端进行插入和删除操作的线性表，因而是后进先出表。队列是只允许在表的一端进行插入，另一端进行进行删除操作的线性表，因而是先进先出表。
5、由于在队列中操作遵循的原则是先进先出，出栈元素的顺序是bdcfea ，则元素进队的顺序也是bdcfea 。原素进队的顺序与元素出栈的顺序相同，在栈中存取数据遵循的原则是后进先出，要得到出栈序列bdcfea ，其操作如下表所示，可见栈的容量至少应该存放3个元素的空间。
进栈操作 栈中元素 出栈元素 a,b进栈
b出栈
cd进栈
d进栈
c出栈
f进栈
f出栈
e进栈
e出栈
a出栈
a,b a a,c,d a,c a a,f a a,e a a b d c f e a
五、算法设计题
1、typedef struct
{ ElemType S[MaxSize];
int top1,top2;
}StackType; //定义最小栈
void InitStack1(StackType &st) //初始化栈
{
st.top1=-1;
st.top2=MaxSize;
}
int StackEmpty1(StackType st,int i) //判断栈是否为空
{
if (i==)
return (st.top1==-1);
else //i=2
return (st.top2==MaxSize);
}
int Push1(StackType &st,int I,ElemType x) //进栈
{
if (st.top1==st.top2-1) //栈满
return 0;
if (i==1) //x入栈s1
{ st.top1++;
st.S[st.top1]=x;
}
else if (i==2) //x入栈s2
{ st.top2--;
st.S[st.top2]=x;
}
else return 0;
return 1;
}
int Pop1(StackType &st,int i,ElemType &x) //出栈
{
if (i==1) //s1出栈
{if (st.top1==-1) //s1栈空
return 0;
else
{ x=st.S[st.top1];
st.top1--;
}
}
else if (i==2) //s2出栈
{ if (st.top2==MaxSize) //s2栈空
return 0;
else
{ x=st.S[st.top2];
st.top2++;
}
}
else return 0;
return 1;
}
2、ElemType bottom(SqStack st)
{ ElemType x,y;
SqStack tmpst;
InitStack (tmpst); //初始化临时表
while(!StackEmpty(st)) //临时栈tmpst 中包含st 栈中逆转元素 { Pop(st,x);
Push(tmpst,x);
}
while (!StackEmpty(tmpst)) //恢复st 栈中原来的内容
{ Pop(tmpst,y);
Push (st,y);
}
return x;
}
3、void InitStack1(LiStack *&lst) //初始化栈
{
lst=NULL;
}
int StackEmpty1(LiStack *lst) //判断栈是否为空
{
return(lst==NULL);
}
void Push1(LiStack *&lst,ElemType x) //进栈
{
LiStack *p;
p=(LiStack *)malloc(sizeof(LiStack));
p->data=x;
p->next=lst; //插入*p结点作为第一个数据结点 lst=p;
}
int Pop1(LiStack *&lst,ElemType &x) //出栈
{
LiStack *p;
if (lst==NULL) //栈空的情况
return 0;
p=lst; //p指向第一个数据结点 x=p->data;
lst=p->next;
free(p);
return 1;
}
4、 int count (LiStack *lst)
{
LiStack *p=lst->next;
int n=0;
while (p!=NULL)
{ n++;
p=p->next;
}
return (n);
}
第三章 栈与队列
一、 单项选择题
1、D A 2、A 3 C 4 B 5 D 6 C 7 D 8 C 9C 10 C 11 A 12A 13 A 14 D 15 B 16 D 17 C 18 C 19 D 20 B 21C 22 A D 23 B
二、填空题
1、后进先出
2、存储结构
3、链栈
4、可能的
5、lst=NULL
6、链栈头 链栈头
7、先进先出
8、存储结构
9、链对
三、判断题
1、错误 2、正确 3、正确 4、错误 5、错误
6、错误 7、正确 8、错误 9、正确 10、正确
11、正确 12、正确 13、正确
四、简答题
1、可能的次序有CDBAE 、 CDEBA 、 CDBEA
2、高级语言变量名的定义规则是：以字母开头的字母数字串。入栈次序为123PA ，以A 最先出栈的序列为AP321，以P 最先出栈的序列为P321A 、P32A1、P3A21、PA321。可以作为高级语言的变量名的序列为AP321、P321A 、P32A1、P3A21和PA321。
3、（1）能得到输出顺序为325641的序列，其操作序列为：AAADDAADADDD 。
（2）不能得到输出顺序为154623的序列；执行ADAAAADDAD ，得到输出序列1546后，栈中元素从栈顶到栈底为32，不能让2先出栈，所以得不到输出序列154623。
4、栈和队列是操作位置受限的线性表，即对插入和删除操作的位置加以限制。栈是仅允许在表的一端进行插入和删除操作的线性表，因而是后进先出表。队列是只允许在表的一端进行插入，另一端进行进行删除操作的线性表，因而是先进先出表。
5、由于在队列中操作遵循的原则是先进先出，出栈元素的顺序是bdcfea ，则元素进队的顺序也是bdcfea 。原素进队的顺序与元素出栈的顺序相同，在栈中存取数据遵循的原则是后进先出，要得到出栈序列bdcfea ，其操作如下表所示，可见栈的容量至少应该存放3个元素的空间。
进栈操作 栈中元素 出栈元素 a,b进栈
b出栈
cd进栈
d进栈
c出栈
f进栈
f出栈
e进栈
e出栈
a出栈
a,b a a,c,d a,c a a,f a a,e a a b d c f e a
五、算法设计题
1、typedef struct
{ ElemType S[MaxSize];
int top1,top2;
}StackType; //定义最小栈
void InitStack1(StackType &st) //初始化栈
{
st.top1=-1;
st.top2=MaxSize;
}
int StackEmpty1(StackType st,int i) //判断栈是否为空
{
if (i==)
return (st.top1==-1);
else //i=2
return (st.top2==MaxSize);
}
int Push1(StackType &st,int I,ElemType x) //进栈
{
if (st.top1==st.top2-1) //栈满
return 0;
if (i==1) //x入栈s1
{ st.top1++;
st.S[st.top1]=x;
}
else if (i==2) //x入栈s2
{ st.top2--;
st.S[st.top2]=x;
}
else return 0;
return 1;
}
int Pop1(StackType &st,int i,ElemType &x) //出栈
{
if (i==1) //s1出栈
{if (st.top1==-1) //s1栈空
return 0;
else
{ x=st.S[st.top1];
st.top1--;
}
}
else if (i==2) //s2出栈
{ if (st.top2==MaxSize) //s2栈空
return 0;
else
{ x=st.S[st.top2];
st.top2++;
}
}
else return 0;
return 1;
}
2、ElemType bottom(SqStack st)
{ ElemType x,y;
SqStack tmpst;
InitStack (tmpst); //初始化临时表
while(!StackEmpty(st)) //临时栈tmpst 中包含st 栈中逆转元素 { Pop(st,x);
Push(tmpst,x);
}
while (!StackEmpty(tmpst)) //恢复st 栈中原来的内容
{ Pop(tmpst,y);
Push (st,y);
}
return x;
}
3、void InitStack1(LiStack *&lst) //初始化栈
{
lst=NULL;
}
int StackEmpty1(LiStack *lst) //判断栈是否为空
{
return(lst==NULL);
}
void Push1(LiStack *&lst,ElemType x) //进栈
{
LiStack *p;
p=(LiStack *)malloc(sizeof(LiStack));
p->data=x;
p->next=lst; //插入*p结点作为第一个数据结点 lst=p;
}
int Pop1(LiStack *&lst,ElemType &x) //出栈
{
LiStack *p;
if (lst==NULL) //栈空的情况
return 0;
p=lst; //p指向第一个数据结点 x=p->data;
lst=p->next;
free(p);
return 1;
}
4、 int count (LiStack *lst)
{
LiStack *p=lst->next;
int n=0;
while (p!=NULL)
{ n++;
p=p->next;
}
return (n);
}