st01.htm

2000题经典数据结构试题

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>9</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．已知如下程序段<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:16.85pt;mso-char-indent-count:1.48'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>FOR i:= n<span
style='mso-spacerun:yes'>&nbsp; </span>DOWNTO <span
style='mso-spacerun:yes'>&nbsp;</span>1<span style='mso-spacerun:yes'>&nbsp;
</span>DO<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>{</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>语句</span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>1}<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:33.85pt;mso-char-indent-count:2.97'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>BEGIN <o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:50.95pt;mso-char-indent-count:4.47'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>x:=x+1</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>；</span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>{</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>语句</span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>2}<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:51.05pt;mso-char-indent-count:4.48'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>FOR j:=n <span
style='mso-spacerun:yes'>&nbsp;</span>DOWNTO <span
style='mso-spacerun:yes'>&nbsp;</span>i <span
style='mso-spacerun:yes'>&nbsp;</span>DO<span style='mso-spacerun:yes'>&nbsp;
</span><span style='mso-spacerun:yes'>&nbsp;</span>{</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>语句</span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>3}<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:57.0pt;mso-char-indent-count:5.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><span
style='mso-spacerun:yes'>&nbsp;</span>y:=y+1;<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>{</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>语句</span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>4}<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:33.85pt;mso-char-indent-count:2.97'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>END</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>；</span><span lang=EN-US style='mso-bidi-font-size:10.5pt'><o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:19.5pt;mso-char-indent-count:1.71'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>语句<span lang=EN-US>1</span>执行的频度为<u>
（<span lang=EN-US>1</span>） </u>；语句<span lang=EN-US>2</span>执行的频度为<u> （<span
lang=EN-US>2</span>） </u>；语句<span lang=EN-US>3</span>执行的频度为<u> （<span
lang=EN-US>3</span>） </u>；语句<span lang=EN-US>4</span>执行的频度为<u> （<span
lang=EN-US>4</span>） </u>。【北方交通大学 <span lang=EN-US>1999 <span
style='mso-spacerun:yes'>&nbsp;</span></span>二、<span lang=EN-US>4</span>（<span
lang=EN-US>5</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>10</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．在下面的程序段中，对ｘ的赋值语句的频度为<span lang=EN-US>______</span>（表示为<span lang=EN-US>n</span>的函数）<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp; </span>FOR</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>　　<span lang=EN-US>i</span>：＝１
<span lang=EN-US>TO<span style='mso-spacerun:yes'>&nbsp; </span>n</span>　<span
lang=EN-US>DO</span>　<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>　　<span
lang=EN-US>FOR</span>　　<span lang=EN-US>j</span>：＝１　<span lang=EN-US>TO<span
style='mso-spacerun:yes'>&nbsp; </span>i</span>　<span lang=EN-US>DO<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:2.0gd;
text-indent:-11.4pt;mso-char-indent-count:-1.0'><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>　<span lang=EN-US>FOR</span>　<span lang=EN-US>k</span>：＝<span
lang=EN-US>1</span>　<span lang=EN-US>TO</span>　<span lang=EN-US>j</span>　<span
lang=EN-US>DO</span>　<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:3.0gd;
text-indent:22.8pt;mso-char-indent-count:2.0'><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>ｘ：＝ｘ＋<span lang=EN-US>delta</span>；<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>【北京工业大学 <span lang=EN-US>1999<span
style='mso-spacerun:yes'>&nbsp; </span></span>一、<span lang=EN-US>6</span>（<span
lang=EN-US>2</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-right:-96.2pt;mso-para-margin-right:-8.44gd'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>11.</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>下面程序段中带下划线的语句的执行次数的数量级是：<u><span
lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></u>【合肥工业大学<span lang=EN-US>1999</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 style='margin-top:0cm;margin-right:-96.2pt;margin-bottom:
0cm;margin-left:4.2pt;margin-bottom:.0001pt;mso-para-margin-top:0cm;mso-para-margin-right:
-8.44gd;mso-para-margin-bottom:0cm;mso-para-margin-left:.37gd;mso-para-margin-bottom:
.0001pt;text-indent:36.7pt;mso-char-indent-count:3.22'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>i</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>：<span lang=EN-US>=1</span>； <span
lang=EN-US>WHILE i&lt;n DO <u>i</u></span><u>：<span lang=EN-US>=i*2</span></u><span
lang=EN-US>;<o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>12. </span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>下面程序段中带下划线的语句的执行次数的数量级是<span lang=EN-US>(<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>)</span>。【合肥工业大学<span
lang=EN-US> 2000 </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 style='text-indent:21.75pt'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>i:=1;<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:21.0pt'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>WHILE i&lt;n BEGIN<span
style='mso-spacerun:yes'>&nbsp; </span>FOR j:=1 TO n DO<u> x:=x+1</u>;i:=i*2<span
style='mso-spacerun:yes'>&nbsp; </span>END</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>；<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='tab-stops:72.0pt'><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>13. </span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体'>下面程序段中带有下划线的语句的执行次数的数量级是<span lang=EN-US>(<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>) </span>【合肥工业大学<span
lang=EN-US> 2001 </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 style='text-indent:45.6pt;mso-char-indent-count:4.0;
tab-stops:72.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'>i</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>：<span
lang=EN-US>=n*n <span style='mso-tab-count:1'>&nbsp;&nbsp; </span>WHILE
i&lt;&gt;1<span style='mso-spacerun:yes'>&nbsp; </span>DO <u>i:=i div 2</u>;<o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>14. </span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>计算机执行下面的语句时，语句<span lang=EN-US>s</span>的执行次数为 <span lang=EN-US>_______ </span>。【南京理工大学<span
lang=EN-US>2000</span>二、<span lang=EN-US>1</span>（<span lang=EN-US>1.5</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:27.0pt'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span>FOR(i=l</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>；<span lang=EN-US>i&lt;n-l</span>；<span lang=EN-US>i++)<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:27.0pt'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>FOR(j=n;j&gt;=i;j--)<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:27.0pt'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>s; <o:p></o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>15. </span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>下面程序段的时间复杂度为<span lang=EN-US>________</span>。<span lang=EN-US>(n&gt;1) <o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:17.35pt;text-indent:-17.35pt;mso-char-indent-count:
-1.52'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>sum=1</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>；<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:17.35pt;text-indent:-17.35pt;mso-char-indent-count:
-1.52'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for (i=0;sum&lt;n;i++)
sum+=1; <span style='mso-spacerun:yes'>&nbsp;&nbsp;</span></span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>【南京理工大学<span lang=EN-US> 2001 </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 style='margin-left:11.4pt;text-indent:-11.4pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>16</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．设<span lang=EN-US>m.n</span>均为自然数，<span
lang=EN-US>m</span>可表示为一些不超过<span lang=EN-US>n</span>的自然数之和，<span lang=EN-US>f(m,n)</span>为这种表示方式的数目。例<span
lang=EN-US>f(5,3)=5</span>，有<span lang=EN-US>5</span>种表示方式：<span lang=EN-US>3+2</span>，<span
lang=EN-US>3+1+1</span>，<span lang=EN-US>2+2+1</span>，<span lang=EN-US>2+1+1+1</span>，<span
lang=EN-US>1+1+1+1+1</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
style='mso-bidi-font-size:10.5pt;font-family:宋体'>①以下是该函数的程序段，请将未完成的部分填入，使之完整<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:68.4pt;mso-char-indent-count:6.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>int f(m,n)<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:68.4pt;mso-char-indent-count:6.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span>int m,n;<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:68.4pt;mso-char-indent-count:6.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>{ if(m==1)<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:68.4pt;mso-char-indent-count:6.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>return <u><span
style='mso-spacerun:yes'>&nbsp;</span>(1)<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span></u>;<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:68.4pt;mso-char-indent-count:6.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>if(n==1){<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:68.4pt;mso-char-indent-count:6.0'><span
lang=EN-US style='mso-bidi-font-size:10