da03.htm

1800道数据结构题和答案

<p class=MsoNormal style='margin-left:19.5pt;mso-para-margin-left:1.0gd;
text-indent:-8.1pt;mso-char-indent-count:-.71'><span lang=EN-US
style='font-family:宋体'>8</span><span style='font-family:宋体'>、链式存储结构<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span>9</span>、<span
lang=EN-US>S</span>×<span lang=EN-US>SS</span>×<span lang=EN-US>S</span>××<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp; </span>10</span>、<span
lang=EN-US>data[++top]=x</span>；<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:19.5pt;mso-para-margin-left:1.0gd;
text-indent:-8.1pt;mso-char-indent-count:-.71'><span lang=EN-US
style='font-family:宋体'>11</span><span style='font-family:宋体'>、<span lang=EN-US>23.12.3*2-4/34.5*7/++108.9/+</span>（注：表达式中的点<span
lang=EN-US>(.)</span>表示将数隔开，如<span lang=EN-US>23.12.3</span>是三个数）<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:19.5pt;mso-para-margin-left:1.0gd;
text-indent:-8.1pt;mso-char-indent-count:-.71'><span lang=EN-US
style='font-family:宋体'>12</span><span style='font-family:宋体'>、假溢出时大量移动数据元素。 <span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:19.5pt;mso-para-margin-left:1.0gd;
text-indent:-8.1pt;mso-char-indent-count:-.71'><span lang=EN-US
style='font-family:宋体'>13</span><span style='font-family:宋体'>、<span lang=EN-US>(M+1)
MOD N<span style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>(M+1)% N</span>； <span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>14</span>、队列<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>15</span>、先进先出<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>16</span>、先进先出 <span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span>17</span><span style='font-family:宋体'>、<span
lang=EN-US>s=(LinkedList)malloc(<b style='mso-bidi-font-weight:normal'>sizeof</b>(LNode))</span>；
<span lang=EN-US>s-&gt;data=x;s-&gt;next=r-&gt;next</span>；<span lang=EN-US>r-&gt;next=s</span>；<span
lang=EN-US>r=s</span>；<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span>18</span><span style='font-family:宋体'>、牺牲一个存储单元<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span>设标记<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>19</span><span style='font-family:宋体'>、（<span
lang=EN-US>TAIL+1</span>）<span lang=EN-US>MOD M=FRONT (</span>数组下标<span
lang=EN-US>0</span>到<span lang=EN-US>M-1</span>，若一定使用<span lang=EN-US>1</span>到<span
lang=EN-US>M</span>，则取模为<span lang=EN-US>0</span>者，值改取<span lang=EN-US>M<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:19.5pt;text-indent:-19.5pt;mso-char-indent-count:
-1.71'><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span>20</span><span style='font-family:宋体'>、<span
lang=EN-US>sq.front=(sq.front+1)%(M+1)</span>；<b style='mso-bidi-font-weight:
normal'><span lang=EN-US>return</span></b><span lang=EN-US>(sq.data(sq.front))</span>；<span
lang=EN-US>(sq.rear+1)%(M+1)==sq.front</span>；<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:19.5pt;text-indent:-19.5pt;mso-char-indent-count:
-1.71'><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span>21</span><span style='font-family:宋体'>、栈<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>22</span>、（<span
lang=EN-US>rear-front+m</span>）<span lang=EN-US>% m</span>；<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span>23</span>、（<span lang=EN-US>R-P+N</span>）<span
lang=EN-US>% N</span>；<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd'><span
lang=EN-US style='font-family:宋体'>24</span><span style='font-family:宋体'>、（<span
lang=EN-US>1</span>）<span lang=EN-US>a[i]</span>或<span lang=EN-US>a[1] </span>（<span
lang=EN-US>2</span>）<span lang=EN-US>a[i]<span style='mso-spacerun:yes'>&nbsp;
</span></span>（<span lang=EN-US>3</span>）<span lang=EN-US>pop</span>（<span
lang=EN-US>s</span>）或<span lang=EN-US>s[1]</span>；<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span>25</span><span style='font-family:宋体'>、（<span
lang=EN-US>1</span>）<span lang=EN-US>PUSH</span>（<span lang=EN-US>OPTR</span>，<span
lang=EN-US>w</span>）（<span lang=EN-US>2</span>）<span lang=EN-US>POP</span>（<span
lang=EN-US>OPTR</span>）（<span lang=EN-US>3</span>）<span lang=EN-US>PUSH</span>（<span
lang=EN-US>OPND</span>，<span lang=EN-US>operate</span>（<span lang=EN-US>a</span>，<span
lang=EN-US>theta</span>，<span lang=EN-US>b</span>））<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US><span style='mso-spacerun:yes'>&nbsp;
</span>26</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>、（</span><span lang=EN-US>1</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）</span><span lang=EN-US>T&gt;0</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>（</span><span lang=EN-US>2</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>）</span><span
lang=EN-US>i&lt;n</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>（</span><span lang=EN-US>3</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）</span><span lang=EN-US>T&gt;0</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>（</span><span lang=EN-US>4</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>）</span><span
lang=EN-US style='color:red'>top&lt;n</span><span style='font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>（</span><span
lang=EN-US>5</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>）</span><span lang=EN-US>top+1</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>（</span><span lang=EN-US>6</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>）</span><span
lang=EN-US>true</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>（</span><span lang=EN-US>7</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）</span><span lang=EN-US>i-1</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>（</span><span
lang=EN-US>8</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>）</span><span lang=EN-US>top-1</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>（</span><span lang=EN-US>9</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>）</span><span
lang=EN-US>T+w[i]</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>（</span><span lang=EN-US>10</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）</span><span lang=EN-US>false</span></p>

<p class=MsoNormal><!--[if supportFields]><span lang=EN-US><span
style='mso-element:field-begin'></span><span
style='mso-spacerun:yes'>&nbsp;</span>= 4 \* CHINESENUM3 <span
style='mso-element:field-separator'></span></span><![endif]--><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-no-proof:yes'>四</span><!--[if supportFields]><span
lang=EN-US><span style='mso-element:field-end'></span></span><![endif]--><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>、应用题</span></p>

<p class=MsoNormal><span lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;
</span>1</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>、栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（</span><span
lang=EN-US>L<b style='mso-bidi-font-weight:normal'>IF</b>O</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）表。</span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US>2</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>、队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（</span><span
lang=EN-US>F<b style='mso-bidi-font-weight:normal'>IF</b>O</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）表。</span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US>3</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>、用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。</span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US>4</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>、（</span><span lang=EN-US>1</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）通常有两条规则。第一是给定序列中</span><span lang=EN-US>S</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>的个数和</span><span lang=EN-US>X</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，</span><span
lang=EN-US>S</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>的个数要大于或等于</span><span lang=EN-US>X</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>的个数。</span></p>

<p class=MsoNormal style='text-indent:21.75pt'><span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;</span></span><span style='font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>（</span><span
lang=EN-US>2</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>）可以得到相同的输出元素序列。例如，输入元素为</span><span
lang=EN-US>A</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>，</span><span lang=EN-US>B</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>，</span><span lang=EN-US>C</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，则两个输入的合法序列</span><span
lang=EN-US>ABC</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>和</span><span lang=EN-US>BAC</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>均可得到输出元素序列</span><span lang=EN-US>ABC</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>。对于合法序列</span><span lang=EN-US>ABC</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>，我们使用本题约定的</span><span lang=EN-US style='font-family:宋体'>S</span><span
style='font-family:宋体'>×<span lang=EN-US>S</span>×<span lang=EN-US>S</span>×操作序列；对于合法序列<span
lang=EN-US>BAC</span>，我们使用<span lang=EN-US>SS</span>××<span lang=EN-US>S</span>×操作序列。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US style='font-family:宋体'>5</span><span style='font-family:宋体'>、三个：<span
lang=EN-US>CDEBA</span>，<span lang=EN-US>CDBEA</span>，<span lang=EN-US>CDBAE<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US style='font-family:宋体'>6</span><span style='font-family:宋体'>、输入序列为<span
lang=EN-US>123456</span>，不能得出<span lang=EN-US>435612</span>，其理由是，输出序列最后两元素是<span
lang=EN-US>12</span>，前面<span lang=EN-US>4</span>个元素（<span lang=EN-US>4356</span>）得到后，栈中元素剩<span
lang=EN-US>12</span>，且<span lang=EN-US>2</span>在栈顶，不可能栈底元素<span lang=EN-US>1</span>在栈顶元素<span
lang=EN-US>2</span>之前出栈。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span><span style='font-family:
宋体'>得到<span lang=EN-US>135426</span>的过程如下：<span lang=EN-US>1</span>入栈并出栈，得到部分输出序列<span
lang=EN-US>1</span>；然后<span lang=EN-US>2</span>和<span lang=EN-US>3</span>入栈，<span
lang=EN-US>3</span>出栈，部分输出序列变为：<span lang=EN-US>13</span>；接着<span lang=EN-US>4</span>和<span
lang=EN-US>5</span>入栈，<span lang=EN-US>5</span>，<span lang=EN-US>4</span>和<span
lang=EN-US>2</span>依次出栈，部分输出序列变为<span lang=EN-US>13542</span>；最后<span
lang=EN-US>6</span>入栈并退栈，得最终结果<span lang=EN-US>135426</span>。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US style='font-family:宋体'>7</span><span style='font-family:宋体'>、能得到出栈序列<span
lang=EN-US>B</span>、<span lang=EN-US>C</span>、<span lang=EN-US>A</span>、<span
lang=EN-US>E</span>、<span lang=EN-US>D</span>，不能得到出栈序列<span lang=EN-US>D</span>、<span
lang=EN-US>B</span>、<span lang=EN-US>A</span>、<span lang=EN-US>C</span>、<span
lang=EN-US>E</span>。其理由为：若出栈序列以<span lang=EN-US>D</span>开头，说明在<span lang=EN-US>D</span>之前的入栈元素是<span
lang=EN-US>A</span>、<span lang=EN-US>B</span>和<span lang=EN-US>C</span>，三个元素中<span
lang=EN-US>C</span>是栈顶元素，<span lang=EN-US>B</span>和<span lang=EN-US>A</span>不可能早于<span
lang=EN-US>C</span>出栈，故不可能得到<span lang=EN-US>D</span>、<span lang=EN-US>B</span>、<span
lang=EN-US>A</span>、<span lang=EN-US>C</span>、<span lang=EN-US>E</span>出栈序列。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US style='font-family:宋体'>8</span><span style='font-family:宋体'>、借助栈结构，<span
lang=EN-US>n</span>个入栈元素可得到<span lang=EN-US>1/(n+1)((2n</span>）！<span
lang=EN-US>/</span>（<span lang=EN-US>n!*n!</span>）<span lang=EN-US>)</span>种出栈序列。本题<span
lang=EN-US>4</span>个元素，可有<span lang=EN-US>14</span>种出栈序列，<span lang=EN-US>abcd</span>和<span
lang=EN-US>dcba</span>就是其中两种。但<span lang=EN-US>dabc</span>和<span lang=EN-US>adbc</span>是不可能得到的两种。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
lang=EN-US style='font-family:宋体'>9</span><span style='font-family:宋体'>、不能得到序列<span
lang=EN-US>2</span>，<span lang=EN-US>5</span>，<span lang=EN-US>3</span>，<span
lang=EN-US>4</spa