st09.htm

1800道数据结构题和答案

	{mso-level-tab-stop:18.0pt;
	mso-level-number-position:left;
	margin-left:18.0pt;
	text-indent:-18.0pt;}
@list l2
	{mso-list-id:310720180;
	mso-list-type:hybrid;
	mso-list-template-ids:-1156575786 1579035050 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l2:level1
	{mso-level-start-at:33;
	mso-level-tab-stop:18.0pt;
	mso-level-number-position:left;
	margin-left:18.0pt;
	text-indent:-18.0pt;}
@list l3
	{mso-list-id:576136148;
	mso-list-type:hybrid;
	mso-list-template-ids:810832416 1009958044 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l3:level1
	{mso-level-number-format:alpha-upper;
	mso-level-text:%1．;
	mso-level-tab-stop:49.5pt;
	mso-level-number-position:left;
	margin-left:49.5pt;
	text-indent:-18.0pt;}
@list l4
	{mso-list-id:618877599;
	mso-list-type:hybrid;
	mso-list-template-ids:-893110710 -1372280718 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l4:level1
	{mso-level-text:"\(%1\)";
	mso-level-tab-stop:39.0pt;
	mso-level-number-position:left;
	margin-left:39.0pt;
	text-indent:-18.0pt;}
@list l5
	{mso-list-id:654067254;
	mso-list-type:hybrid;
	mso-list-template-ids:-2097228294 763905194 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l5:level1
	{mso-level-start-at:9;
	mso-level-tab-stop:15.75pt;
	mso-level-number-position:left;
	margin-left:15.75pt;
	text-indent:-18.0pt;}
@list l6
	{mso-list-id:877354227;
	mso-list-type:hybrid;
	mso-list-template-ids:1554433932 450520482 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l6:level1
	{mso-level-start-at:10;
	mso-level-tab-stop:18.0pt;
	mso-level-number-position:left;
	margin-left:18.0pt;
	text-indent:-18.0pt;}
@list l7
	{mso-list-id:989210845;
	mso-list-type:hybrid;
	mso-list-template-ids:1558987302 -836604402 654731426 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l7:level1
	{mso-level-start-at:25;
	mso-level-text:%1．;
	mso-level-tab-stop:19.5pt;
	mso-level-number-position:left;
	margin-left:19.5pt;
	text-indent:-19.5pt;}
@list l7:level2
	{mso-level-text:（%2）;
	mso-level-tab-stop:57.0pt;
	mso-level-number-position:left;
	margin-left:57.0pt;
	text-indent:-36.0pt;}
@list l8
	{mso-list-id:1039283337;
	mso-list-type:simple;
	mso-list-template-ids:946369532;}
@list l8:level1
	{mso-level-text:（%1）;
	mso-level-tab-stop:42.0pt;
	mso-level-number-position:left;
	margin-left:42.0pt;
	text-indent:-26.25pt;}
@list l9
	{mso-list-id:1122455661;
	mso-list-type:hybrid;
	mso-list-template-ids:393092194 -889553904 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l9:level1
	{mso-level-start-at:18;
	mso-level-text:%1．;
	mso-level-tab-stop:21.0pt;
	mso-level-number-position:left;
	margin-left:21.0pt;
	text-indent:-21.0pt;}
@list l10
	{mso-list-id:1172453857;
	mso-list-type:hybrid;
	mso-list-template-ids:-1612409956 1330559512 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l10:level1
	{mso-level-text:"\(%1\)";
	mso-level-tab-stop:29.25pt;
	mso-level-number-position:left;
	margin-left:29.25pt;
	text-indent:-18.0pt;
	mso-ascii-font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";
	mso-hansi-font-family:"Times New Roman";
	mso-bidi-font-family:"Times New Roman";}
@list l11
	{mso-list-id:1507015326;
	mso-list-type:hybrid;
	mso-list-template-ids:-476441954 -758203166 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l11:level1
	{mso-level-text:"\(%1\)";
	mso-level-tab-stop:44.25pt;
	mso-level-number-position:left;
	margin-left:44.25pt;
	text-indent:-18.0pt;}
@list l12
	{mso-list-id:1805387478;
	mso-list-type:hybrid;
	mso-list-template-ids:1786552502 -56752570 -834213704 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l12:level1
	{mso-level-number-format:japanese-counting;
	mso-level-text:%1．;
	mso-level-tab-stop:20.25pt;
	mso-level-number-position:left;
	margin-left:20.25pt;
	text-indent:-20.25pt;}
@list l12:level2
	{mso-level-text:（%2）;
	mso-level-tab-stop:57.0pt;
	mso-level-number-position:left;
	margin-left:57.0pt;
	text-indent:-36.0pt;}
ol
	{margin-bottom:0cm;}
ul
	{margin-bottom:0cm;}
-->
</style>
<!--[if gte mso 10]>
<style>
 /* Style Definitions */
 table.MsoNormalTable
	{mso-style-name:普通表格;
	mso-tstyle-rowband-size:0;
	mso-tstyle-colband-size:0;
	mso-style-noshow:yes;
	mso-style-parent:"";
	mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
	mso-para-margin:0cm;
	mso-para-margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:10.0pt;
	font-family:"Times New Roman";
	mso-ansi-language:#0400;
	mso-fareast-language:#0400;
	mso-bidi-language:#0400;}
</style>
<![endif]--><!--[if gte mso 9]><xml>
 <o:shapedefaults v:ext="edit" spidmax="2050"/>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <o:shapelayout v:ext="edit">
  <o:idmap v:ext="edit" data="1"/>
 </o:shapelayout></xml><![endif]-->
</head>

<body lang=ZH-CN style='tab-interval:21.0pt;text-justify-trim:punctuation'>

<div class=Section1 style='layout-grid:14.5pt -.95pt;mso-layout-grid-char-alt:
-3955'>

<p class=MsoNormal align=center style='text-align:center'><span
style='font-size:14.0pt;mso-bidi-font-size:10.5pt;font-family:黑体;mso-hansi-font-family:
宋体;mso-bidi-font-weight:bold'>第九章<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span></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:黑体;
mso-hansi-font-family:宋体'>一、 选择题<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:宋体'>1.</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>若查找每个记录的概率均等，则在具有<span lang=EN-US>n</span>个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度<span
lang=EN-US>ASL</span>为<span lang=EN-US>(<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>)</span>。【北京航空航天大学<span
lang=EN-US> 2000 </span>一、<span lang=EN-US>8 </span>（<span lang=EN-US>2</span>分）】<span
lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.05pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>． <span lang=EN-US>(n-1)/2<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>B. n/2<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>C. (n+1)/2<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>D. n<o:p></o:p></span></span></p>

<p class=MsoNormalIndent style='text-indent:0cm'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>2.<span style='mso-bidi-font-weight:
bold'> </span></span><span style='mso-bidi-font-size:10.5pt;font-family:宋体;
mso-bidi-font-weight:bold'>对<span lang=EN-US>N</span>个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为<span
lang=EN-US>(<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span>) </span></span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>【南京理工大学<span lang=EN-US>1998</span>一、<span
lang=EN-US>7</span>（<span lang=EN-US>2</span>分）】<span lang=EN-US
style='mso-bidi-font-weight:bold'><o:p></o:p></span></span></p>

<p class=MsoNormalIndent style='margin-left:21.0pt;text-indent:0cm'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-bidi-font-weight:
bold'>A</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-bidi-font-weight:
bold'>．（<span lang=EN-US>N+1</span>）<span lang=EN-US>/2<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>B. N/2<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>C. N<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>D. [</span>（<span
lang=EN-US>1+N</span>）<span lang=EN-US>*N </span></span><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>]<span style='mso-bidi-font-weight:
bold'>/2<o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:9.55pt;text-indent:-9.55pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>3</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（<span
lang=EN-US>1</span>））<span lang=EN-US>,</span>二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（<span
lang=EN-US>2</span>））。 在此假定<span lang=EN-US>N</span>为线性表中结点数，且每次查找都是成功的。【长沙铁道学院
<span lang=EN-US>1997 </span>四、<span lang=EN-US>3 (4</span>分<span lang=EN-US>)</span>】<span
lang=EN-US><o:p></o:p></span></span></p>