03：栈与队列习题.doc

【基础知识题】1若按3.1.1节中所示铁道进行车厢调度(注意：两侧铁道均为单向行驶道)，则请回答：(1) 如果进站的车厢序列为123，则可能得到的出站车厢序列是什么?(2) 如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到(即写出以S表示进栈和以X表示出栈的栈操作序列)。 2简述栈和线性表的差别。3写出下列程序段的输出结果（栈的元素类型 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);4简述以下算法的功能（栈的元素类型 SElemType 为 int ）。(1) status algo1(Stack S) int i, n, A 255;n=0;while (!StackEmpty(S) ) n+; Pop(S, An); ;for ( i=1; i= n ; i+) Push(S, Ai);(2) status algo2(Stack S, int e) Stack T; int d;InitStack(T);while (!StackEmpty(S) Pop(S, d); if (d!=e ) Push(T, d); while (!StackEmpty(T) Pop(T, d);Push(S, d);11简述队列和栈这两种数据类型的相同点和差异处。13简述以下算法的功能（栈和队列的元素类型均为 int）。void algo3(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); 【编程练习题】本章编程练习题中可以利用的栈和队列的类型定义如下： / stack 类型void InitStack( stack& s ); / 初始化 s 为空栈void Push( stack&s , char x); / 将元素 x 插入 s 的栈顶void Pop( stack& s ); / 删除 s 中的栈顶元素bool SEmpty( stack& s); / 若栈 s 为空则返回 TRUE,否则返回 FALSEchar GetTop( stack& s );/ 返回 s 中的栈顶元素void ClearStack( stack& s); / 将栈 s 清空int StackLength( stack& s); / 返回栈 s 中元素个数void DestroyStack( stack& s );/ 销毁栈 s 结构/ queue 类型void InitQueue( queue& q );/ 初始化 q 为空栈void EnQueue( queue& q , char x );/ 将元素 x 插入 q 的队尾void Dequeue( queue& q); / 删除 q 中队头元素char GetHead( queue& q );/ 返回 q 中队头元素bool QEmpty( queue& q); / 若队列 q 为空则返回 TRUE,否则返回 FALSEvoid ClearQueue( queue& q ); / 将队列 q 清空int QueueLength( queue& q ); / 返回队列 q 中元素个数void DestroyQueue( queue& q ); / 销毁队列 q 结构17. 试写一个算法，识别依次读入的一个以 为结束符的字符序列是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而1+3&3-1则不是。bool matching(char* str)/ 若给定字符串 str 为形如 序列1&序列2 的对称字符串/ (序列2是序列1的逆串)，则返回 true，否则返回 false19. 假设一个算术表达式中可以包含三种括号：圆括号(和)，方括号和和花括号和，且这三种括号可按任意的次序嵌套使用（如：()）。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。bool match_check( SqList exp )/ 若给定的表达式 exp 中的三种括号：()、和均配对出现，/ 则返回true，否则返回false21. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。void transformation(char* rs, SqList exp)/ 以字符串 rs 返回给定的表达式 exp（以#为结束标志） / 转换所得相应的后缀式22. 如题21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。int valuation( SqList suffixal )/ 返回由给定逆波兰式 suffixal 表示的表达式的值。28. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。void Init_Queue(LinkQueue& rear)/ rear 是指向以循环链表表示的队列的队尾指针，初始化该循环链表队列。30. 假设将循环队列定义为：以域变量 rear 和 length 分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法(在出队列的算法中要返回队头元素)。bool En_CQueue( CyclicQueue& Q, ElemType x )/ Q 是一个由其尾指针和队列长度标识的循环队列，若队列不满，/ 则将 x 插入至队尾，并返回 true ；否则返回 false31. 假设称正读和反读都相同的字符序列为回文，例如，abba 和 abcba是回文，abcde 和 ababab 则不是回文。试写一个算法判别读入的一个以为结束符的字符序列是否是回文。bool matching(char* rs)/ rs 为一个随机产生的未知长度的（以为结束符的）字符序列，/ 若是回文，则返回true，否则返回false。一、设计一个递归函数，对长度为n的一维数组A，进行下列运算：求数组A的最大值。求数组A中n个整数的平