数据结构复习题-第3章答案2014-6-16

答案：

一、选择题

 -5  BCBCB-10  BCCDD -15 BDBBD -20  CCBDB

16题解释:一般只需修改队头指针，不过当队列里面只有一个结点时，需要同时修改队尾指针。

二、判断题

1-5  ×√×√√  -10 √√√√×  11-16√√√××√   

三、填空题

1.栈顶、栈底  2. 入栈、出栈   3. 队列、先进先出  4. 栈  5. 队列  

6.先进先出   7. (R-P+N) % N 8. n-1牺牲一个存储单元、设标记    栈底、两栈顶指针相邻（即值之差的绝对值为1）

1.没有、一  2. 数据域、指针域  3. 前驱 4. 前驱、后继  5. 前驱、后继  6.头结点     

7. 循环链表 . n-1  9. 栈   后进先出   10.SXSSXSXX  11.3，1，2  12. 牺牲一个存储单元 设标记   13. 栈底 两栈顶指针相邻（即值之差的绝对值为1）

四、简答题（每小题5分，共10分）

1.简述队列和栈这两种数据类型的相同点和差异处。

答：队列和栈都是操作受限的线性表，都属于线性表的逻辑结构。区别在于，队列的插入是在队尾端进行，删除是在队头端进行；而栈的插入和删除都只能在栈顶端进行。

2.简述栈和线性表的差别。

答：栈是操作受限的线性表，栈的插入和删除操作都只能在栈顶端进行，因而相应的称为“入栈”和“出栈”。

3.说明线性表、栈与队列的异同点。

答：相同点：都是线性结构；

不同点：队列和栈都是操作受限的线性表，队列的插入是在队尾端进行，删除是在队头端进行；而栈的插入和删除都只能在栈顶端进行，而线性表的插入、删除则不受，可以在任何位置进行。

4.链栈中为何不设置头结点? 

答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

5.什么是循环队列？

答：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的最高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。

6.循环队列的优点是什么? 如何判别它的空和满? 

答：循环队列的优点是：它可以克服顺序队列的“假上溢”现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的“空”或“满”不能以头尾指针是否相等来确定，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。一般是通过以下几种方法：一是少用一个元素的空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。二是另设一布尔变量来区别队列的空和满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

7.对于循环向量中的循环队列，写出求队列长度的公式。

答：公式如下(设采用少用一个元素空间的方法，front指向真正的队首元素，rear指向真正队尾后一位置，向量空间大小：QueueSize ，则循环队列的长度为

Queuelen=(QueueSize+rear-front)%QueueSize

五、应用题（每小题6分，共48分）

无答案

六、算法题（每小题6分，共12分）

1.（6分）编写算法，实现循环队列的出队操作（采用顺序存储结构，最大容量为M）。

Status dequeue(SqQueue q,int e)

{

 if(q.front==q.rear)return error;

 e=q.base[q.front];

q.front=(q.front+1)%M;

return ok;

}             

2.（6分）写出循环队列的入队操作（采用顺序存储结构，队列的最大容量为M）。

Status enqueue(SqQueue q,int e)

   {

if((q.rear+1)%M==q.front)return error;

q.base[q.rear]=e;

q.rear=(q.rear+1)%M;

return ok;

}    

3.假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”、方括号“[”和“]”和花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用。编写判别给定表达式中所含括号是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。

Status AllBrackets_Test(char *str)

{   InitStack(s);

for(p=str;*p;p++)

  {

if(*p=='('||*p=='['||*p=='{') push(s,*p);

 else if(*p==')'||*p==']'||*p=='}')

 {

   if(StackEmpty(s)) return ERROR;

   pop(s,c);

   if(*p==')'&&c!='(') return ERROR;

   if(*p==']'&&c!='[') return ERROR;

   if(*p=='}'&&c!='{') return ERROR; 

  }

}

   if(!StackEmpty(s)) return ERROR;

   return OK;

} 

4.己知Q是个非空队列，S是一个空栈。使用C语言编写一个算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q中的所有元素逆置。

栈的ADT函数有：初始化栈、入栈、出栈、判断栈空否；

队列的ADT函数有：入队列、出队列、判断队列空否；

答：//基本思想是：顺序取出队元素，入栈；所有元素入栈后，再从栈中逐个取出，入队。//答案实际上是数据结构习题集P24页3.13题目。算法如下：

    void  reverse_queue(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);

        }

    }