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

第3章 栈和队列答案：一、选择题 1-5 BCBCB 6-10 BCCDD 11-15 BDBBD 16-20 CCBDB16题解释:一般只需修改队头指针，不过当队列里面只有一个结点时，需要同时修改队尾指针。二、判断题1-5 6-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. 循环链表 8. 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.baseq.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.baseq.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