第三章 栈和队列 作业
宋以后,京师所设小学馆和武学堂中的教师称谓皆称之为“教谕”。至元明清之县学一律循之不变。明朝入选翰林院的进士之师称“教习”。到清末,学堂兴起,各科教师仍沿用“教习”一称。其实“教谕”在明清时还有学官一意,即主管县一级的教育生员。而相应府和州掌管教育生员者则谓“教授”和“学正”。“教授”“学正”和“教谕”的副手一律称“训导”。于民间,特别是汉代以后,对于在“校”或“学”中传授经学者也称为“经师”。在一些特定的讲学场合,比如书院、皇室,也称教师为“院长、西席、讲席”等。 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之前出栈。
得到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使pj k i 如果i j情况,说明pi在pj入栈前先出栈。而对于pi>pj的情况,则说明要将pj压到pi之上,也就是在pj出栈之后pi才能出栈。这就说明,对于i k i的输出序列。换句话说,对于输入序列1,2,3,不可能出现3,1,2的输出序列。 3、按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,并仿照教科书3.2节3--2的格式,画出对下列算术表达式求值时操作数栈和运算符栈的变化过程: A- B*C/D-E ↑F 4、试编写一个算法,识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列,序列1和序列2中不包含字符‘&’,序列1是序列2的逆序列。例如‘a+b&b+a’是属于该模式的字符序列,而‘a+b&a-b’则不是。 Status Model(){ //识别依次读入的一个以@为结束符的字符序列是否为形如‘序列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(); else return FALSE; if (c=='@' && StackEmpty(s)) return TRUE; else return FALSE; 5、假设称正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’ 和‘ababab’则不是回文。试写一个算法判别读入的一个以‘ @ ’为结束符的字符序列是否是回文。 Status ReturnText(){ //判断读入的一个以‘@’为结束符的字符序列是否为回文 InitStack(s); InitQueue(q); c=getchar(); while (c!='@'){ Push(s,c); EnQueue(q,c); c=getchar(); while (!EmptyStack(s)){ Pop(s,x); DeQueue(q,y); if (x!=y) return FALSE; return TRUE; 6、分析程序 (1)、SelemType 为char类型,写出下列程序运行结果 void main(){ Stack S; char x,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); 输出结果:stack (2)写出下列算法的功能(元素类型为int) void test(Queue &Q){ Stack S; int d; InitStack(S); while (!QueueEmpty(Q)){ DeQueue(Q,d);push(S,d); while(!StackEmpty(S)){ Pop(S,d); EnQueue(Q,d); 将队列Q中的数据元数进行逆置。 7、(选作题)假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针,请写出相应的入队列和出队列算法。 (1) void EnQueue (LinkedList rear, ElemType x) { // rear是带头结点的循环链队列的尾指针,本算法将元素x插入到队尾。 s= (LinkedList) malloc (sizeof(LNode)); //申请结点空间 s->data=x; s->next=rear->next; //将s结点链入队尾 rear->next=s; rear=s; //rear指向新队尾 (2) void DeQueue (LinkedList rear) { // rear是带头结点的循环链队列的尾指针,本算法执行出队操作,操作成功输出队头元素;否则给出出错信息。 if (rear->next==rear) { printf(“队空\n”); exit(0); s=rear->next->next; //s指向队头元素, rear->next->next=s->next; //队头元素出队。 printf (“出队元素是”,s->data); if (s==rear) rear=rear->next; //空队列 free(s);
¥29.8
¥9.9
¥59.8