欢迎来到天天文库
浏览记录
ID:6600586
大小:61.00 KB
页数:6页
时间:2018-01-19
《第3章栈和队列 作业(参考答案)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第三章栈和队列作业1、若按教材P44页图3.1(b)所示铁道进行车厢调度(注意:两侧铁道均为单向行驶道),则请回答:(1)如果进站的车厢序列为123,则可能得到的出站车厢序列是什么?(2)如果进站的车厢序列为123456,则能否得到435612和135426的出站序列,并请说明为什么不能得到或者如何得到?(写出进栈和出栈的栈操作序列)。123、132、213、231、321输入序列为123456,不能得出435612,其理由是,输出序列最后两元素是12,前面4个元素(4356)得到后,栈中元素剩12,且2在栈顶,不可能栈底元素1在栈顶元素2之前出栈。得到
2、135426的过程如下:1入栈并出栈,得到部分输出序列1;然后2和3入栈,3出栈,部分输出序列变为:13;接着4和5入栈,5,4和2依次出栈,部分输出序列变为13542;最后6入栈并退栈,得最终结果135426。2、试证明:若借助栈由输入序列1、2……n得到的输出序列为p1、p2……pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着,i〈j〈k使pjpj的情况,则说明要将pj压到pi之上,也就是在pj出栈之后pi才能出栈。这就说明,对于i3、,不可能出现pj4、入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列,序列1和序列2中不包含字符‘&’,序列1是序列2的逆序列 InitStack(s); c=getchar(); while(c!='&'){Push(s,c);c=getchar();} c=getchar(); while(c!='@'&&!StackEmpty(s)){ Pop(s,x); if(c==x)c=getchar(); elsereturnFALSE; } if(c=='@'&&StackEmpty(s))returnTRUE; elsereturnFA5、LSE;} 5、假设称正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是回文。StatusReturnText(){ //判断读入的一个以‘@’为结束符的字符序列是否为回文 InitStack(s); InitQueue(q);c=getchar(); while(c!='@'){ Push(s,c); EnQueue(q,c); c=getchar(); } while(!EmptyStack(s)){ Pop6、(s,x);DeQueue(q,y); if(x!=y)returnFALSE; } returnTRUE;}6、分析程序(1)、SelemType为char类型,写出下列程序运行结果voidmain(){StackS;charx,y;InitStack(S);x=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);};printf(x7、);}输出结果:stack(2)写出下列算法的功能(元素类型为int)voidtest(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);push(S,d);}while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}将队列Q中的数据元数进行逆置。7、(选作题)假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针,请写出相应的入队列和出队列算法。(1)voidEnQueue(LinkedListrear,Ele8、mTypex){//rear是带头结点的循环链队列的尾指针,本算法将元素x插入到
3、,不可能出现pj4、入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列,序列1和序列2中不包含字符‘&’,序列1是序列2的逆序列 InitStack(s); c=getchar(); while(c!='&'){Push(s,c);c=getchar();} c=getchar(); while(c!='@'&&!StackEmpty(s)){ Pop(s,x); if(c==x)c=getchar(); elsereturnFALSE; } if(c=='@'&&StackEmpty(s))returnTRUE; elsereturnFA5、LSE;} 5、假设称正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是回文。StatusReturnText(){ //判断读入的一个以‘@’为结束符的字符序列是否为回文 InitStack(s); InitQueue(q);c=getchar(); while(c!='@'){ Push(s,c); EnQueue(q,c); c=getchar(); } while(!EmptyStack(s)){ Pop6、(s,x);DeQueue(q,y); if(x!=y)returnFALSE; } returnTRUE;}6、分析程序(1)、SelemType为char类型,写出下列程序运行结果voidmain(){StackS;charx,y;InitStack(S);x=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);};printf(x7、);}输出结果:stack(2)写出下列算法的功能(元素类型为int)voidtest(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);push(S,d);}while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}将队列Q中的数据元数进行逆置。7、(选作题)假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针,请写出相应的入队列和出队列算法。(1)voidEnQueue(LinkedListrear,Ele8、mTypex){//rear是带头结点的循环链队列的尾指针,本算法将元素x插入到
4、入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列,序列1和序列2中不包含字符‘&’,序列1是序列2的逆序列 InitStack(s); c=getchar(); while(c!='&'){Push(s,c);c=getchar();} c=getchar(); while(c!='@'&&!StackEmpty(s)){ Pop(s,x); if(c==x)c=getchar(); elsereturnFALSE; } if(c=='@'&&StackEmpty(s))returnTRUE; elsereturnFA
5、LSE;} 5、假设称正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是回文。StatusReturnText(){ //判断读入的一个以‘@’为结束符的字符序列是否为回文 InitStack(s); InitQueue(q);c=getchar(); while(c!='@'){ Push(s,c); EnQueue(q,c); c=getchar(); } while(!EmptyStack(s)){ Pop
6、(s,x);DeQueue(q,y); if(x!=y)returnFALSE; } returnTRUE;}6、分析程序(1)、SelemType为char类型,写出下列程序运行结果voidmain(){StackS;charx,y;InitStack(S);x=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);};printf(x
7、);}输出结果:stack(2)写出下列算法的功能(元素类型为int)voidtest(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);push(S,d);}while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}将队列Q中的数据元数进行逆置。7、(选作题)假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针,请写出相应的入队列和出队列算法。(1)voidEnQueue(LinkedListrear,Ele
8、mTypex){//rear是带头结点的循环链队列的尾指针,本算法将元素x插入到
此文档下载收益归作者所有