10. 循环队列存储在数组A[0..m]中，则入队时队尾的操作为( )。
A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1) % m D. rear=(rear+1)%(m+1) 参考答案： 1 C 2 C 3 D 4 C 5 C 6 A 7 D 8 B 9 C 10 D 3.3.2 填空题
1. 队列是 的线性表，其运算遵循 的原则。 2. 是限定仅在表尾进行插入或删除操作的线性表。
3. 用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为 。
4. 当两个栈共享一存储区时，存储区用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为 ，栈2空时 ，top[2]为 ，栈满的条件是 。
5. 在链式队列中，判定只有一个结点的条件是 。 6. 循环队列的引入，目的是为了克服 。
7. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是 。 8. 循环队列满与空的条件是 和 。
9. 一个栈的输入序列是12345，则栈不同的输出序列有 种。 10. 表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是 。 参考答案：
1. 限制在表的一端进行插入和在另一端进行删除 先进先出 2. 栈
3. SXSSXSXX
4. 0 n+1 top[1]+1==top[2]
5.(Q->rear==Q->front) && (Q->rear!=NULL) 6. 假溢出
7. node *p=(node *)malloc(node); p->data=x; p->next=NULL; if(r) { r->next=p; r=p; } else r=f=p;
8. (rear+1) % MAXSIZE==front rear==front。 9. 14
10. 23 12 3 * 2 – 4 /34 5 * 7 / + 108 9 / +
3.3.3 判断题
1. 消除递归一定需要使用栈。
2. 栈是实现过程和函数调用所必需的结构。
3. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 4. 用递归方法设计的算法效率高。
5. 栈与队列是一种特殊的线性表。
6. 队列逻辑上是一端既能增加又能减少的线性表。 7. 循环队列通常浪费一个存储空间。 8. 循环队列也存在空间溢出问题。
9. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。 10. 任何一个递归过程都可以转换成非递归过程。 参考答案： 1 错误 2 正确 3 正确 4 错误 5 正确 6 错误 7 正确 8 正确 9 正确 10 正确 3.3.4 应用题
1. 什么是栈、队列？栈和队列数据结构的特点，什么情况下用到栈，什么情况下用到队列？ 2. 什么是递归程序，递归程序的优、缺点是什么，递归程序在执行时，应借助于什么来完成？
3. 在什么情况下可以利用递归来解决问题，在写递归程序时应注意什么？
4. 试证明：若借助栈由输入序列1，2，? ，n得到输出序列为p1p2?pn (它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i 6. 简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满的队条件。 7. 利用两个栈sl,s2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算。请简述这些运算的算法思想。 8. 当过程P递归调用自身时，过程P内部定义的局部变量在P的2次调用期间是否占用同一数据区？为什么？ 9. 链队列队头和队尾分别是单链表的那一端，能不能反过来表示，为什么？ 10. 有如下递归函数： int dunno(int m) { int value; if (m==0) value=3; else value=dunno(m-1)+5; return(value); } 试给出dunno(3)的结果。 参考答案： 1. 略。 2. 略。 3. 该问题必须可以被分解为和该问题具有相同逻辑结构的子问题，即具有递归性质。书写递归程序的要点如下： ⑴问题与自身的子问题具有类同的性质，被定义项在定义中的应用具有更小的尺度。 ⑵被定义项在最小尺度上有直接解。 递归算法设计的原则是用自身的简单情况来定义自身，一步比一步更简单，确定递归的控制条件非常重要。设计递归算法的方法是： ⑴寻找方法，将问题化为原问题的子问题求解(例如n!=n*(n-1)!)。 ⑵设计递归出口，确定递归终止条件(例如求解n!时，当n=1时，n!=1)。 4. 证明：根据题意，因为i < j < k，所以输出的次序为pi, pj, pk, 因为输入序列的值是由小到大递增的，又pj 若要求pi最后输入，最先输出，则先输入的pj, pk必存在栈中，等pi入栈并立即出栈后再输出。对于pj, pk，因已存入栈中，出栈序列不可能是pj, pk，否则不符合栈“后进先出”的要求。所以不可能得到输出序列pi, pj, pk。 5. 略。 6. 将队列的数据区data[0..MAXSIZE-1]看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队列”。具体结构参见3.1.3节中循环队列的数据结构定义。 初始状态时front==0; rear==0; 队空时front== rear；队满时(rear+1) % MAXSIZE==front。 7. 参考3.2.5节第3题。 8. 过程P内部定义的局部变量在P的2次调用期间不占用同一数据区。当递归函数调用时，应按照“后调用的先返回”的原则处理调用过程，因此递归函数之间的信息传递和控制转移必须通过栈来实现。系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，而每当从一个函数退出时，就释放它的存储区。因此过程P内部定义和P的第2次调用时不再一个存储区域。 9. 链队列队头指向单链表的首结点，而队尾则是指向单链表的最后一个结点。不能够反过来，因为在队尾删除操作时，需要遍历单链表找到队尾所指向结点的前一个结点，这样处理其时间效率将受到影响。 10. dunno(3)＝dunno(2)＋5； dunno(2)＝dunno(1)＋5； dunno(1)＝dunno(0)＋5； dunno(0)＝3； 因此，dunno(3)＝18。 3.3.5 算法设计题 1. 假设称正读和反读都相同的字符序列为“回文”，例如，“abcddcba”、 “qwerewq”是回文，“ashgash”不是回文。是写一个算法判断读入的一个以‘@’为结束符的字符序列是否为回文。 2. 设以数组se[m]存放循环队列的元素，同时设变量rear 和front分别作为队头队尾指针，且队头指针指向队头前一个位置，写出这样设计的循环队列入队出队的算法。 3. 从键盘上输入一个逆波兰表达式，用写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$ 4. 假设以带头结点的循环链表表示一个队列，并且只设一个队尾指针指向尾元素结点(注意不设头指针)，试写出相应的置空队、入队、出队的算法。 5. 设计一个算法判别一个算术表达式的圆括号是否正确配对。 6. 两个栈共享向量空间v[m]，它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公用的栈操作算法：push(i,x)和pop(i)，i=0和1用以指示栈号。 7. 线性表中元素存放在向量A[n]中，元素是整型数。试写出递归算法求出A中的最大和最小元素。 8. 已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。 (1)将上述过程用递归函数表达出来(设求x除以y的余数可以用x % y 形式表示)。 (2)写出求解该递归函数的非递归算法。 提示与解答： 1. 提示：将字符序列分别输入一个栈和一个队列，然后分别执行出栈和出队操作，并比较输出的字符，如果直到栈空并且队空时，输出的字符都相同，则是回文，否则不是。 可以参考3.2.5算法设计例题第2题。 2. 提示：在入队时首先要判断队是否满，在出队时首先要判断队是否为空。所以要正确写出循环队列的队满和队空的条件。在对队首指针加1和队尾指针加1时，要做模MAXSIZE运算。 3. 分析：下面是逆波兰表达式求值的算法，在下面的算法中假设，每个表达式是合乎语法的，并且假设逆波兰表达式已被存入一个足够大的字符数组A中，且以’$’为结束字符。算法描述如下： typedef double DataType ; int IsNum(char c) /*判断字符是否位操作数。若是返回1，否则返回0*/ { if(c>=′0 ′ && c<=′9 ′) return (1); else return (0); } double postfix_exp(char *A) /*本函数返回由逆波兰表达式A表示的表达式运算结果*/ { PSeq_Starck S ; double result,a,b,c, operand=0; ch=*A++; S=Init_SeqStack(); /*初始化栈*/ while ( ch != ‘$’ ) { if(IsNum(ch)) /*当前字符是数字字符，计算出操作数*/ operand=operand*10+( ch - ′0 ′); else { Push_SeqStack(S,operand); /*当前字符不是数字字符，表示操作数结束,要入栈*/ if (ch!=’’) /*当前字符还不是空格字符，则是运算符，要运算*/ { Pop_SeqStack(S,&b); Pop_SeqStack(S,&a); /*取出两个操作数*/ switch (ch) { case ′+ ′： c=a+b ; break ; case ′- ′： c=a-b ; break ; case ′* ′： c=a*b ; break ; case ′/ ′： c=a/b ; } Push_SeqStack(S, c) ; /*运算结果入栈*/ } } ch=*A++ ; } GetTop_SeqStack(S, result ) ; Destroy_SeqStack(&S); return result ; } 4. 分析：由于不设置头指针，所以要设法确定队头的位置。如图3.7所示，由于有队尾指 针rear，所以根据循环链表的结构，队头指针front=rear->next->next。队空时，rear=rear->next。 e1 ? en r (b)空队列 rearear (a)非空队列 图3.7 带队尾指针的循环链表表示的队列 算法描述如下： typedef struct node{ DataType data; /*每个元素数据信息*/ struct node *next; /*存放后继元素的地址*/ } LNode，*Quenue； void SetEmpty(Quenue rear) /*置队列为空*/ { LNode *h，*front； h= rear->next； /*循环链表头结点为队列尾指针后一个结点*/ while (h!= rear) /*当前队列不空*/ { front =h->next; /*队列头结点为循环链表头结点后一个结点*/ h->next= front ->next; /*队列中只有一个结点,则释放后,队列将为空,所以让队尾指针指向头结点*/ if (front ==rear) rear=h； free front; /*释放队列头结点*/ } } void InQuenue(Quenue rear ,DataType data) /*数据data入队列*/ { LNode *new; new=( LNode *)malloc(sizeof(LNode)); new->data=data; new->next=rear->next; /*在rear后插入新的结点*/ rear->next=new; } int OutQuenue(Quenue rear ,DataType &data) {