数据�l�构�W�三章应用题�?qi��ng)参考答案[1]_跨考网

�?/span> 应用�?/span>

　　1. 名词解释�Q�栈。�?a target="_blank">燕山大学 1999 一�?/span>1�Q?/span>2分）(j��)】【吉林工业大�?/span> 1999 一�?/span>3�Q?/span>2分）(j��)�?/span>

　　【参考答案�?/span>

　　栈是只准在一端进行插入和删除操作的线性表�Q�允许插入和删除的一端叫栈顶�Q�另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出�Q?/span>LIFO�Q�表�?/span>

　　2. 名词解释�Q�队列�?a target="_blank">大连���事大学 1996 一�?/span>6 ( 1�?/span> )�?/span>

　　【参考答案�?/span>

　　队列是允许在一端插入而在另一端删除的�U�性表�Q�允许插入的一端叫队尾�Q�允许删除的一端叫队头。最先插入队的元素最先离开�Q�删除）(j��)�Q�故队列也常�U�先�q�先出（FIFO�Q�表�?/span>

　　3. 什么是循环队列�Q��?a target="_blank">哈尔滨工业大�?/a> 2001 三�?/span>2�Q?/span>3分）(j��)】�?a target="_blank">沛_��大学 1998 一�?/span>4�Q?/span>3分）(j��)�?/span>

　　【参考答案�?/span>

　　用常规意义下��序存储�l�构的一�l�数�l�表�C�队列，�׃��队列的性质�Q�队���插入和队头删除�Q�，�Ҏ(gu��)��造成“假溢出”现象，即队���ַ�到达一�l�数�l�的高下标，不能再插入，然而队中元素个数小于队列的长度�Q�容量）(j��)。��@环队列是解决“假溢出”的一�U�方法。通常把一�l�数�l�看成首������接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的�Ҏ(gu��)��解决“队满”和“队�I�”的判定问题�?/span>

　　4. 假设�?/span>S�?/span>X分别表示入栈和出栈操作，则对初态和�l�态均为空的栈操作可由S�?/span>X�l�成的序列表�C�（�?/span>SXSX�Q��?/span>

　　�Q?/span>1�Q�试指出判别�l�定序列是否合法的一般规则�?/span>

　　�Q?/span>2�Q�两个不同合法序列（对同一输入序列�Q�能否得到相同的输出元素序列�Q�如能得刎ͼ�请�D列说明。�?a target="_blank">东南大学 1992 二（10分）(j��)�?/span>

　　【参考答案�?/span>

　　�Q?/span>1�Q�通常有两条规则。第一是给定序列中S的个数和X的个数相�{�；�W�二是从�l�定序列的开始，到给定序列中的�Q一位置�Q?/span>S的个数要大于或等�?/span>X的个数�?/span>

　　�Q?/span>2�Q�可以得到相同的输出元素序列。例如，输入元素�?/span>A�Q?/span>B�Q?/span>C�Q�则两个输入的合法序�?/span>ABC�?/span>BAC均可得到输出元素序列ABC。对于合法序�?/span>ABC�Q�我们��用本题约定的S×S×S×操作序列�Q�对于合法序�?/span>BAC�Q�我们���?/span>SS××S×操作序列�?/span>

　　5. �?/span>5 个元素，其入栈次序�ؓ(f��)�Q?/span>A�Q?/span>B�Q?/span>C�Q?/span>D�Q?/span>E�Q�在各种可能的出栈次序中�Q�以元素C�Q?/span>D最先出栈（�?/span>C�W�一个且D�W�二个出栈）(j��)的次序有哪几个？�?a target="_blank">西南交通大�?/a> 2000 二�?/span>1�?/span>

　　【参考答案�?/span>

　　三个�Q?/span>CDEBA�Q?/span>CDBEA�Q?/span>CDBAE