数据结构第三章测验

《数据结构第三章测验》由会员分享，可在线阅读，更多相关《数据结构第三章测验（25页珍藏版）》请在装配图网上搜索。

1、第三章习题1. 按图3.1（b）所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： 如进站的车厢序列为 123，则可能得到的出站车厢序列是什么？如进站的车厢序列为 123456，能否得到 435612 和 135426 的出站序列， 并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。2. 设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重 复执行下列 4 步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。直到队列成为空队列为止，得到输出序列：（1） A、 C、 E、 C、 C（2） A、 C、

2、E（3）A、C、E、C、C、C（4）A、C、E、C3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈 满？4. 按照四则运算加、减、乘、除和幕运算（f）优先关系的惯例，画出对下列算 术表达式求值时操作数栈和运算符栈的变化过程：A B*C/D + EfF5. 试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序 列1 & 序列2模式的字符序列。其中序列1和序列2 中都不含字符&，且序 列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而 1 + 3 & 31则不是。6. 假设表达式由单字母变量和双目四则运算算符构成。 试写一个算法， 将一个通

3、常书写形式且书写正确的表达式转换为逆波兰式。7. 假设以带头结点的循环链表表示队列， 并且只设一个指针指向队尾元素结点（注 意不设头指针）， 试编写相应的队列初始化、入队列和出队列的算法。8. 要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域 tag , 以 tag 为 0 或 1 来区分头尾指针相同时的队列状态的空与满， 请编写与此结构相应的入 队与出队算法。9. 简述以下算法的功能（其中栈和队列的元素类型均为 int）：（1 ） void proc_1（Stack S） int i, n, A255;n=0;while(!EmptyStack(S)n+; Pop(&S, &An

4、);for(i=1; itop=-1表示栈空。判断栈S满：如果S-top=Stack_Size-1表示栈满。(2)链栈(top为栈顶指针，指向当前栈顶元素前面的头结点)判断栈空：如果top-next=NULL表示栈空。判断栈满： 当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满3 4 照四则运算加、减、乘、除和幂运算的优先惯例， 画出对下列表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+E f F解答】3 5 写一个算法，判断依次读入的一个以为结束符的字母序列，是否形如序列1& 序列2的字符序列。序列1和序列2中都不含&，且序列2是序列1 的逆序列。例如，a+b&b+a是

5、属于该模式的字符序歹列而1+3&3-1则不是。解答】算法如下：int IsHuiWen()Stack *S;Char ch,temp;InitStack(&S);Printf(“n 请输入字符序列：”);Ch=getchar();While( ch!=&)/*序列 1入栈*/ Push(&S,ch);ch=getchar();do/*判断序列 2是否是序列 1的逆序列*/ ch=getchar();Pop(&S,&temp);if(ch!= temp)/*序列 2不是序列 1的逆序列*/ return(FALSE); printf(“ nNO” ); while(ch!= & !IsEmpty

6、(&S)if(ch = = & IsEmpty(&S) return(TRUE); printf(“ nYES ” );/* 序列 2 是序列 1 的逆序列 */elsereturn(FALSE); printf(“ nNO” );/*IsHuiWen()*/3.8要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1 来区分头尾指针相同时的队列状态的空与满， 请编写与此相应的入队与出队算法。【解答】入队算法：int EnterQueue(SeqQueue *Q, QueueElementType x) /*将元素 x 入队*/if(Q-front=Q-front &

7、 tag=1)/*队满*/return(FALSE);if(Q-front=Q-front & tag=0) /*x 入队前队空， x 入队后重新设置标志*/tag=1;Q-elememtQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE;/*设置队尾指针*/Return(TRUE);出队算法：int DeleteQueue( SeqQueue *Q , QueueElementType *x) /* 删除 队头元素，用 x 返回其 值*/if(Q-front=Q-rear & tag=0) /*队空*/return(FALSE);*x=Q-elementQ-front;Q-

8、front=(Q-front+1)%MAXSIZE; /*重新设置队头指针*/重新设置标志域*/if(Q-front=Q-rear) tag=0; /*队头元素出队后队列为空Return(TUUE);编写求解Hanoi问题的算法，并给出三个盘子搬动时的递归调用过程。【解答】算法：void hanoi (int n ,char x, char y, char z) /*将塔座X上按直径由小到大且至上而下编号为1到n的n个圆盘按规则搬到塔座Z 上， Y 可用做辅助塔座*/if(n = =1)move(x,1,z);else Hanoi(n-1,x,z,y);move(x, n, z);Hanoi(

9、n-1, y,x,z);Hanoi(3,A,B,C)的递归调用过程：Hanoi(2,A,C,B):Hanoi(1,A,B,C)move(A-C) 1 号搬到 CMove(A-B)2 号搬到 BHanoi(1,C,A,B)move(C-B) 1 号搬到 BMove(A-C)3 号搬到 CHanoi(2,B,A,C)Hanoi(1,B,C,A)move(B-A) 1 号搬到 AMove(B-C)2 号搬到 CHanoi(1,A,B,C)move(A-C) 1 号搬到 C提示：第 3 章 限定性 线 性表 栈和 队 列习题1. 按图3.1（b）所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：

10、如进站的车厢序列为 123，则可能得到的出站车厢序列是什么？ 123、213、132231 、321 （312）如进站的车厢序列为 123456，能否得到 435612 和 135426 的出站序列，并说明 原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X62. 设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列 4 步操作：（ 1）输出队首元素；（2）把队首元素值插入到队尾；（ 3）删除队首元素；（ 4）再次删除队首元素。直到队列成为空队列为止， 则是否可能得到输

11、出序列：（ 1 ）A、 C、 E、 C、 C（2）A、 C、 E（ 3 ）A、 C、 E、 C、 C、 C（4）A、C、 E、 C提示：A、B、 C、 D、 E （输出队首元素 A）A、 B、 C、 D、 E、 A （把队首元素 A 插入到队尾B、 C、 D、 E、 A （删除队首元素 A）C、D、 E、 A （再次删除队首元素 B）C、D、E、A （输出队首元素 C）C、D、E、A、C （把队首元素 C 插入到队尾）D、E、A、C （删除队首元素 C）E、A、C （再次删除队首元素 D）3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4. 按照四则运算加、减、乘

12、、除和幕运算（f）优先关系的惯例，画出对下列算术表 达式求值时操作数栈和运算符栈的变化过程：AB*C/D + EfF5. 试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列 1 & 序列 2模式的字符序列。其中序列 1和序列 2 中都不含字符&，且序列 2 是序列1的逆序列。例如，a+b&b+a是属该模式的字符序歹列而 1 + 3 & 3 - 1则不是。提示：（ 1 ）边读边入 栈，直到&2)边读边出 栈边比较，直到6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。提示：例：中缀表达式：a+b后

13、缀表达式：ab+中缀表达式：a+bxc后缀表达式：abcx+中缀表达式：a+bxc-d后缀表达式：abcx+d-中缀表达式： a+bxc-d/e后缀表达式： abcx+de/-中缀表达式： a+bx（c-d）-e/f后缀表达式： abcd-x+ef/- 后缀表达式的计算过程：（简便）顺序扫描表达式，（ 1） 如果是操作数，直接入 栈；（2）如果是操作符op,则连续退栈两次，得操作数X, Y,计算X op Y,并将结 果入栈。 如何将中缀表达式转换为后缀表达式？顺序扫描中缀表达式,1）如果是操作数,直接输出；(2)如果是操作符op2,则与栈顶操作符0已比较：如果op2 opi，则op2入栈；如果

14、 op2= op1， 则脱括号；如果op2 opi，则输出opi ；7. 假 设以带头结点的循环链表表示队列， 并且只设一个指 针指向队尾元素结点(注意不设头指针)， 试编写相应的队列初始化、入队列和出队列的算法。提示： 参 P.56 P.70 先画图.typedef LinkList CLQueue;int InitQueue(CLQueue * Q)int EnterQueue(CLQueue Q, QueueElementType x)int DeleteQueue(CLQueue Q, QueueElementType *x)8. 要求循环队列不损失一个空间全部都能得到利用，设置一个标

15、志域tag ,以tag为0 或 1 来区分头尾指针相同时的队列状态的空与满， 请编写与此结构相应的入队与出 队算法。提示：初始状态： front=0, rear=0, tag=0队空条件：front=rear, tag=O队满条件： front=rear, tag=1其它状态:front !=rear, tag=0 （或 1、2）入队操作：（入队）if （front=rear） tag=1 ；（或直接 tag=1）出队操作：（出队）tag=0；问题：如何明确区分队空、 队满、非空非满三种情况？9. 简述以下算法的功能（其中栈和队列的元素类型均为 int（1 ） void proc_1（Stac

16、k S） int i, n, A255;n=0;while(!EmptyStack(S)n+; Pop(&S, &An);for(i=1; i=n; i+)Push(&S, Ai);将栈 S 逆序。(2)void proc_2(Stack S, int e) Stack T; int d;InitStack(&T);while(!EmptyStack(S) Pop(&S, &d);if (d!=e) Push( &T, d); while(!EmptyStack(T) Pop(&T, &d);Push( &S, d);删除栈S中所有等于e的元素。3)void proc_3(Queue *Q)

17、Stack S; int d;InitStack(&S); while(!EmptyQueue(*Q)DeleteQueue(Q, &d);Push( &S, d); while(!EmptyStack(S) Pop(&S, &d);EnterQueue(Q，d)将队列Q逆序。实习题1回文判断。 称正读与反读都相同的字符序列为“回文”序列。试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序 列 1 &序列 2模式的字符序列。其中序列1和序列 2 中都不含字符&，且序 列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而 1+3 & 31则不是。2停车场管理。设停车

18、场是一个可停放 n 辆车的狭长通道，且只有一个大门可供汽车进出。在 停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若 车场内已停满 n 辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道 上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先 退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车 离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。试编写程序，模拟上述管理过程。要求以顺序栈模 拟停车场，以链队列模拟便 道。从终端读入汽车到达或离去的数据，每组数据包括三项：是“到达”还是“离 去”；汽车牌照号码；“到达”或“离去”的时亥V。与每组输入信息相应的输 出信息为：如果是到达的车辆， 则输出其在停车场中或便道上的位置；如果是离去 的车辆， 则输出其在停车场中停留的时间和应交的费 用。（提示：需另设一个栈， 临时停放为让路而从车场退出的车。）3商品货架管理。商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。用队列和栈作为周转，实现上述管理过程。