《数据结构第三章习题答案》由会员分享，可在线阅读，更多相关《数据结构第三章习题答案（13页珍藏版）》请在金锄头文库上搜索。
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）
2、A、C、E（3） A、C、E、C、C、C （4） A、C、E、C3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4. 按照四则运算加、减、乘、除和幂运算（）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：AB5. 试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列 1 &序列2模式的字符序列。其中序列 1 和序列 2 中都不含字符&，且序列 2 是序列 1 的逆序列。例如，a+b&b+a是属该模式的字符序列，而+&则不是。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);for(i=1; itop=-1 表示
4、栈空。判断栈 S 满：如果 S-top=Stack_Size-1 表示栈满。(2) 链栈（top 为栈顶指针，指向当前栈顶元素前面的头结点）判断栈空：如果 top-next=NULL 表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。3 4 照四则运算加、减、乘、除和幂运算的优先惯例，画出对下列表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+EF【解答】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!= & !IsEmpt
6、y(&S)if(ch = = & IsEmpty(&S) return(TRUE); printf(“nYES”); /*序列 2 是序列 1 的逆序列*/else return(FALSE); printf(“nNO”); /*IsHuiWen()*/3.8 要求循环队列不损失一个空间全部都能得到利用，设置一个标志 tag,以 tag 为 0 或 1 来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】入队算法：int EnterQueue(SeqQueue *Q, QueueElementType x) /*将元素 x 入队*/if(Q-front=Q-fron
7、t & 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,
9、 n, z);Hanoi(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 、132、231 、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、按照四则运算加、减、乘、除和幂运算（）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：AB5. 试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列 1 &序列 2模式的字符序列。其中序列 1 和序列 2 中都不含字符& ，且序列 2 是序列 1 的逆序列。例如，a+b&b+a是属该模式的字符序列，而+&则不是。提示：（1） 边读边入栈，直到&（2） 边读边出栈边比较，直到6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。提示：例：中缀表达式：a+b 后缀表达式: ab+
13、中缀表达式：a+b c 后缀表达式: abc+中缀表达式：a+b c-d 后缀表达式: abc+d-中缀表达式：a+b c-d/e 后缀 表达式: abc+de/-中缀表达式：a+b (c-d)-e/f 后缀表达式: abcd-+ef/- 后缀表达式的计算过程：（简便）顺序扫描表达式，（1） 如果是操作数，直接入栈；（2） 如果是操作符 op，则连续退栈两次，得操作数 X, Y，计算 X op Y，并将结果入栈。 如何将中缀表达式转换为后缀表达式？顺序扫描中缀表达式，（1）如果是操作数，直接输出；（2）如果是操作符 op2，则与栈顶操作符 op1 比较：如果 op2 op1，则 op2 入栈；如果 op2 = op1，则脱括号；如果 op2 op1，则输出 op1；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. 要求循环队列不损失一个空间全部都能得到利用, 设置
