da01.htm

1800道数据结构题和答案

mso-hansi-font-family:"Times New Roman"'>）见上面题</span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>4<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</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='margin-left:.05pt;text-indent:-.05pt;tab-stops:45.0pt'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><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'>4</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='margin-left:.05pt;text-indent:-.05pt;tab-stops:45.0pt'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><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'>5</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='margin-left:.05pt;text-indent:-.05pt;tab-stops:45.0pt'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><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'>6</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='margin-left:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt'>7</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 style='mso-bidi-font-size:
10.5pt;font-family:宋体'>集合、线性结构、树形结构、图形或网状结构。<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>8</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;
tab-stops:45.0pt'><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:22.8pt;mso-char-indent-count:2.0;
tab-stops:45.0pt'><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>D</span>是数据元素的有限集合，<span lang=EN-US>S</span>是<span lang=EN-US>D</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
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>11</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．</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
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:22.8pt;mso-char-indent-count:2.0;
tab-stops:45.0pt'><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>2</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;
tab-stops:45.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>100</span>个这样的记录存于数组中。因一般无增删操作，故<span style='color:red'>宜采</span>用顺序存储。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:22.8pt;text-indent:-22.8pt;mso-char-indent-count:
-2.0;tab-stops:45.0pt'><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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><b style='mso-bidi-font-weight:normal'>typedef</b> <b style='mso-bidi-font-weight:
normal'><span style='mso-spacerun:yes'>&nbsp;</span>struct</b><o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;text-indent:-22.8pt;mso-char-indent-count:
-2.0;tab-stops:45.0pt'><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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>{<b style='mso-bidi-font-weight:normal'>int</b> num;//</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:22.8pt;text-indent:-22.8pt;mso-char-indent-count:
-2.0;tab-stops:45.0pt'><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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><b style='mso-bidi-font-weight:normal'>char</b> name[8];//</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:22.8pt;text-indent:-22.8pt;mso-char-indent-count:
-2.0;tab-stops:45.0pt'><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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><b style='mso-bidi-font-weight:normal'>float</b> score;/</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:22.8pt;text-indent:-22.8pt;mso-char-indent-count:
-2.0;tab-stops:45.0pt'><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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>}node</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:22.8pt;text-indent:-22.8pt;mso-char-indent-count:
-2.0;tab-stops:45.0pt'><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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><span style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>node student[100];<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><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>4</span>（<span lang=EN-US>3</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;
tab-stops:45.0pt'><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><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0;
tab-stops:45.0pt'><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>O</span>（<span lang=EN-US>n</span>）；而在链式存储方式下，插入和删除时间复杂度都是<span
lang=EN-US>O</span>（<span lang=EN-US>1</span>）。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'>17</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>．对算法<span
lang=EN-US>A1</span>和<span lang=EN-US>A2</span>的时间复杂度<span lang=EN-US>T1</span>和<span
lang=EN-US>T2</span>取对数，得<span lang=EN-US>nlog<sup>2</sup></span>和<span
lang=EN-US>2log<sup>n</sup></span>。显然，算法<span lang=EN-US>A2</span>好于<span
lang=EN-US>A1</span>。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'>18. <b style='mso-bidi-font-weight:normal'>struct</b> node<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>{<b
style='mso-bidi-font-weight:normal'>int</b> year,month,day; };<o:p></o:p></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span><b
style='mso-bidi-font-weight:normal'>typedef struct<o:p></o:p></b></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>{<b
style='mso-bidi-font-weight:normal'>int</b> num;//</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:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span><b
style='mso-bidi-font-weight:normal'>char</b> name[8];//</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:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span><b
style='mso-bidi-font-weight:normal'>struct </b>node date;//</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:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span><b
style='mso-bidi-font-weight:normal'>int</b> tag;//</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>储蓄类型，如：<span lang=EN-US>0- </span>零存，<span
lang=EN-US>1- </span>一年定期……<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span><b
style='mso-bidi-font-weight:normal'>float</b> put;//</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:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span><b
style='mso-bidi-font-weight:normal'><span
style='mso-spacerun:yes'>&nbsp;</span>float</b> interest;//</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:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span><b
style='mso-bidi-font-weight:normal'><span
style='mso-spacerun:yes'>&nbsp;</span>float</b> total;//</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:22.8pt;mso-para-margin-left:2.0gd;
tab-stops:45.0pt 91.2pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>}count</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>；<span lang=EN-US><span
style='mso-tab-count:1'> </span><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd;
text-indent:5.7pt;mso-char-indent-count:.5;tab-stops:45.0pt'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>19</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>(1)n<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>(2)n+1<span
style='mso-spacerun:yes'>&nbsp; </span>(3)n<span
style='mso-spacerun:yes'>&nbsp; </span>(4)(n+4)(n-1)/2<span
style='mso-spacerun:yes'>&nbsp; </span>(5)(n+2)(n-1)/2<span
style='mso-spacerun:yes'>&nbsp; </span>(6)n-1<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.45pt;mso-char-indent-count:1.97;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:
宋体'><span style='mso-spacerun:yes'>&nbsp;</span></span><span style='mso-bidi-font-siz