（12）循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。 A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 答案：D
解释：数组A[0..m]中共含有m+1个元素，故在求模运算时应除以m+1。
（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。 A. (rear+1)%n==front B. rear==front C．rear+1==front D. (rear-l)%n==front 答案：B
解释：最大容量为n的循环队列，队满条件是(rear+1)%n==front，队空条件是
rear==front。
（14）栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 答案：C
解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头
删除元素。
（15）一个递归算法必须包括（ ）。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分 答案：B
2．算法设计题
（1）将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下：
Typedef struct
{int top[2],bot[2]; SElemType *V; int m; }DblStack [题目分析]
两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈顶指针为-1，右栈顶为m。两栈顶指针相邻时为栈满。两栈顶相向、迎面增长，栈顶指针指向栈顶元素。
[算法描述] (1) 栈初始化 int Init()
6
//栈顶和栈底指针 //栈数组
//栈最大可容纳元素个数
{S.top[0]=-1;
S.top[1]=m;
return 1; //初始化成功 }
(2) 入栈操作：
int push(stk S ,int i,int x)
∥i为栈号，i=0表示左栈，i=1为右栈，x是入栈元素。入栈成功返回1，失败返回0 {if(i<0||i>1){ cout<<“栈号输入不对”< {case 0: S.V[++S.top[0]]=x; return(1); break; case 1: S.V[--S.top[1]]=x; return(1); } }∥push (3) 退栈操作 ElemType pop(stk S,int i) ∥退栈。i代表栈号，i=0时为左栈，i=1时为右栈。退栈成功时返回退栈元素 ∥否则返回-1 {if(i<0 || i>1){cout<<“栈号输入错误”< switch(i) {case 0: if(S.top[0]==-1) {cout<<“栈空”< case 1: if(S.top[1]==m { cout<<“栈空”< {return (S.top[0]==-1 && S.top[1]==m); } [算法讨论] 请注意算法中两栈入栈和退栈时的栈顶指针的计算。左栈是通常意义下的栈，而右栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。 （2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) [题目分析] 将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。即将第一个出栈元素 7 和后一半串中第一个字符比较，若相等，则再出栈一个元素与后一个字符比较，……，直至栈空，结论为字符序列是回文。在出栈元素与串中字符比较不等时，结论字符序列不是回文。 [算法描述] #define StackSize 100 //假定预分配的栈空间最多为100个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct {DataType data[StackSize]; int top; }SeqStack; int IsHuiwen( char *t) {//判断t字符向量是否为回文，若是，返回1，否则返回0 SeqStack s; int i , len; char temp; InitStack( &s); len=strlen(t); //求向量长度 for ( i=0; i Push( &s, t[i]); while( !EmptyStack( &s)) {// 每弹出一个字符与相应字符比较 temp=Pop (&s); if( temp!=S[i]) return 0 ;// 不等则返回0 else i++; } return 1 ; // 比较完毕均相等则返回 1 } （3）设从键盘输入一整数的序列：a1, a2, a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。 [算法描述] #define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s是元素为整数的栈，本算法进行入栈和退栈操作。 {int top=0; //top为栈顶指针，定义top=0时为栈空。 for(i=1; i<=n; i++) //n个整数序列作处理。 {cin>>x); //从键盘读入整数序列。 if(x!=-1) // 读入的整数不等于-1时入栈。 8 ｛if(top==maxsize-1){cout<<“栈满”< else s[++top]=x; //x入栈。 ｝ else //读入的整数等于-1时退栈。 {if(top==0){ cout<<“栈空”< else cout<<“出栈元素是”<< s[top--]< (6）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 [算法描述] //先定义链队结构: typedef struct queuenode {Datatype data; struct queuenode *next; }QueueNode; //以上是结点类型的定义 typedef struct {queuenode *rear; }LinkQueue; //只设一个指向队尾元素的指针 (1) 置空队 void InitQueue( LinkQueue *Q) { //置空队：就是使头结点成为队尾元素 QueueNode *s; Q->rear = Q->rear->next;//将队尾指针指向头结点 while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队 {s=Q->rear->next; Q->rear->next=s->next; delete s; }//回收结点空间 } (2) 判队空 int EmptyQueue( LinkQueue *Q) { //判队空。当头结点的next指针指向自己时为空队 return Q->rear->next->next==Q->rear->next; } 9 (3) 入队 void EnQueue( LinkQueue *Q, Datatype x) { //入队。也就是在尾结点处插入元素 QueueNode *p=new QueueNode;//申请新结点 p->data=x; p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p; Q->rear=p;//将尾指针移至新结点 } (4) 出队 Datatype DeQueue( LinkQueue *Q) {//出队,把头结点之后的元素摘下 Datatype t; QueueNode *p; if(EmptyQueue( Q )) Error(\ p=Q->rear->next->next; //p指向将要摘下的结点 x=p->data; //保存结点中数据 if (p==Q->rear) {//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点 Q->rear = Q->rear->next; Q->rear->next=p->next; } else Q->rear->next->next=p->next;//摘下结点p delete p;//释放被删结点 return x; } 10
数据结构（C语言版）第2版习题答案—严蔚敏（简化版）
