数据结构习题答案解析

1、完美WORD格式第三章习题1. 按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答：(1) 如进站的车厢序列为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、E

2、(3)A、C、E、C、C、C(4) A、C、E、C3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4. 按照四则运算加、减、乘、除和幕运算(T)优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：b*c/d + eTf5. 试写一个算法，判断依次读入的一个以砂结束符的字母序列，是否为形如序列1 &序列2 模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而1+3 &3 1则不是。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, &A n);for(i=1; itop=-1表示栈空。判断栈S满

4、：如果S-top=Stack_Size-1 表示栈满。(2)链栈(top为栈顶指针，指向当前栈顶元素前面的头结点)判断栈空：如果top-next=NULL表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。3. 4照四则运算加、减、乘、除和幕运算的优先惯例，画出对下列表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+ET F【解答】/OPTRI生成B*Cir-D1T-运算结果TCDAOVS OPTROVS OPTROVS OPTR,+,=OPTR,V V生成A-T(2)运算箱果TT(3),+ OPTR7,生成T(1)/DOPTRr空+进按右边界OPTR；

5、t 生成Et F右边畀rT(4)1J运算结果T(4)T(4)T(3)4-运算结果T(5)OVSOPTROVS OPTR运算结果OVSFETOVSOPTR3. 5写一个算法，判断依次读入的一个以 型结束符的字母序列，是否形如序列1&序列2的字符序列。序列1和序列2中都不含&,且序列2是序列1的逆序列。例如，a+b&b+a是属于该 模式的字符序列，而1+3&31贝U不是。【解答】算法如下：int IsHuiWe n()专业整理知识分享Stack *S;Char ch,temp;In itStack(&S);Printf( “ n请输入字符序列:”);Ch=getchar();While( ch!=

6、&)/*序列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!= &!lsEmpty(&S)if(ch = = & IsEmpty (&S) return(TRUE);printf(“ nYES );elsereturn(FALSE);printf(“ nNO );/*lsHuiWe n( )*/*序列2是序列1的逆序列*/3.8要求循环队列不损

7、失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】入队算法：int En terQueue(SeqQueue *Q, QueueEleme ntType x) /*将元素x入队*/if(Q-front=Q-front & tag=1)/*队满*/return(FALSE);if(Q-fro nt=Q-fro nt & tag=0) /*xtag=1;入队前队空，x入队后重新设置标志*/Q-elememtQ-rear=x;Q-rear=(Q-rea叶1)%MAXSIZE;/* 设置队尾指针 */Retu

8、rn(TRUE);出队算法：int DeleteQueue( SeqQueue *Q , QueueEleme ntType *x) /* 删除队头元素，用x返回其值*/if(Q-fro nt=Q-rear & tag=0)/*return(FALSE);*x=Q-eleme ntQ-fro nt;Q-fro nt=(Q-fro nt+1)%MAXSIZE; /* if(Q-front=Q-rear) tag=0;/*Return(TUUE);队空*/重新设置队头指针*/队头元素出队后队列为空，重新设置标志域 */编写求解Hanoi问题的算法，并给出三个盘子搬动时的递归调用过程【解答】算法:v

9、oid hanoi (int n ,char x, char y, char z) /* 将塔座X上按直径由小到大且至上而下编号为1到n的n个圆盘按规则搬到塔座Z上，Y可用做辅助塔座*/if(n = =1)move(x,1,z);else Han oi( n-1,x,z,y);move(x, n, z);Hanoi(n-1, y,x,z);Hanoi(3,A,B,C)的递归调用过程：Ha noi(2,A,C,B):Hanoi(1,A,B,C) move(A-C) 1号搬到 CMove(A-B)2号搬到 BHa noi(1,C,A,B)move(C-B) 1号搬到BMove(A-C)3号搬到CH

10、an oi(2,B,A,C)Ha noi(1,B,C,A)move(B-A) 1号搬到AMove(B-C)2号搬到CHa noi(1,A,B,C)move(A-C) 1号搬到C提示:第3章限定性线性表一栈和队列习题1. 按图3.1（b）所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： 如进站的车厢序列为 123，则可能得到的出站车厢序列是什么？123、213、132、231、321（ 312）表示进如进站的车厢序列为 123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”栈、以“ X”表示出栈的栈操作序列）。SXSS XSSX XXSX 或 S 1X1S

11、2S3X3 S4 S5X5X4X2S6X62. 设队列中有A、B、C D E这5个元素，其中队首元素为 A。如果对这个队列重复执行下列4步操作:(1)输出队首兀素；(2)把队首元素值 插入到队尾;(3)删除队首元素；(4)再次删除队首元素。直到队列成为空队列为止，则是否可能得到输出序列:（1）A、C、E、C C（ 2）A、C、E（3） A、C E、C C C（ 4）A、C E、C提示:A、BC D E（输出队首兀素A）A、BC D E、A （把队首元素 A插入到队尾）B、CD E、A（删除队首元素A）C、DE、A （再次删除队首元素B）C、DE、A （输出队首元素C）C、DE、A C （把队首

12、元素C插入到队尾）D、E、A C （删除队首元素C）E、AC （再次删除队首元素D）3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4. 按照四则运算加、减、乘、除和幕运算（f）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运 算符栈的变化过程：A B*C/D+EfF5. 试写一个算法，判断依次读入的一个以砂结束符的字母序列，是否为形如序列 1 &序列2模式的字符序列。其中序列1和序列2中都不含字符&,且序列 2是序列1的逆序列。例如， a+b&b+a是属该模式 的字符序列，而1+3 &3 1则不是。提示:（1）边读边入栈，直到&（2）边读边出栈边比较，直到

13、通常书写形式（中缀）且书写正6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个确的表达式转换为逆波兰式（后缀）提示:例：中缀表达式：a+b 后缀表达式：ab+中缀表达式：a+b c后缀表达式：abcx +中缀表达式：a+b c- d后缀表达式：abcx-d-中缀表达式：a+b op 1，贝U op2入栈；如果op2 = op 1，则脱括号；如果op2 op1，则输出op;，试编写相7. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针）应的队列初始化、入队列和出队列的算法。提示: 参P.56 P.70 先画图.typedef Lin kL

14、ist CLQueueint Ini tQueue（CLQueue* Q）int En terQueue（ CLQueueQ, QueueEleme ntType x）int DeleteQueue（ CLQueueQ, QueueEleme ntType *x）8. 要求循环队列不损失一个空间全部都能得到利用，设置一个标志域tag ,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。提示:初始状态： fron t=0, rear=0, tag=0队空条件：fron t=rear, tag=0队满条件：fron t=rear, tag=1其它状态：fr

15、ont !=rear, tag= 0 （或 1、2）入队操作：（入队）if （front=rear） tag=1;（或直接 tag= 1）出队操作：（出队）tag= 0;问题:如何明确区分 队空、队满、非空非满三种情况？9. 简述以下算法的功能(其中栈和队列的元素类型均为int )(1) void proc_1(Stack S) int i, n, A255;n=0;while(!EmptyStack(S)n+; Pop(&S, &A n);for(i=1; i=n; i+)Push(&S, Ai);将栈S逆序。(2) void proc_2(Stack S, int e) Stack T;

16、int d;Ini tStack(&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) Stack S; int d;Ini tStack(&S);while(!EmptyQueue(*Q)DeleteQueue(Q, &d); Push( &S, d); while(!EmptyStack(S) Pop(&S, & d);EnterQueue(Q,

17、 d)将队列Q逆序。实习题1. 回文判断。称正读与反读都相同的字符序列为“回文”序列。试写一个算法，判断依次读入的一个以 矽结束符的字母序列，是否为形如序列 1 &序列2模式的字 符序列。其中序列1和序列2中都不含字符 &,且序列2是序列1的逆序列。例如， a+b&b+a是属该模 式的字符序列，而1+3 &3 1则不是。2. 停车场管理。设停车场是一个可停放 n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须 先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停 留时间的长短交费（在便道上停留的时间不收费）。试编写程序，模拟上述管理过程。要求以