📄 answer_2.htm
字号:
<html xmlns:o="urn:schemas-microsoft-com:office:office"
xmlns:w="urn:schemas-microsoft-com:office:word"
xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=GB2312">
<meta name=ProgId content=Word.Document>
<meta name=Generator content="Microsoft Word 9">
<meta name=Originator content="Microsoft Word 9">
<link rel=File-List href="./Answer_2.files/filelist.xml">
<title>●试题二</title>
<!--[if gte mso 9]><xml>
<o:DocumentProperties>
<o:Author>聂钰桢</o:Author>
<o:LastAuthor>聂钰桢</o:LastAuthor>
<o:Revision>1</o:Revision>
<o:TotalTime>1</o:TotalTime>
<o:Created>2006-03-04T08:45:00Z</o:Created>
<o:LastSaved>2006-03-04T08:46:00Z</o:LastSaved>
<o:Pages>1</o:Pages>
<o:Company>Microsoft</o:Company>
<o:Lines>1</o:Lines>
<o:Paragraphs>1</o:Paragraphs>
<o:Version>9.2812</o:Version>
</o:DocumentProperties>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:WordDocument>
<w:PunctuationKerning/>
<w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>
<w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>
<w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery>
<w:Compatibility>
<w:SpaceForUL/>
<w:BalanceSingleByteDoubleByteWidth/>
<w:DoNotLeaveBackslashAlone/>
<w:ULTrailSpace/>
<w:DoNotExpandShiftReturn/>
<w:AdjustLineHeightInTable/>
<w:UseFELayout/>
</w:Compatibility>
</w:WordDocument>
</xml><![endif]-->
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"MS Sans Serif";
panose-1:0 0 0 0 0 0 0 0 0 0;
mso-font-charset:0;
mso-generic-font-family:swiss;
mso-font-format:other;
mso-font-pitch:variable;
mso-font-signature:3 0 0 0 1 0;}
@font-face
{font-family:宋体;
panose-1:2 1 6 0 3 1 1 1 1 1;
mso-font-alt:SimSun;
mso-font-charset:134;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:3 135135232 16 0 262145 0;}
@font-face
{font-family:"\@宋体";
panose-1:2 1 6 0 3 1 1 1 1 1;
mso-font-charset:134;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:3 135135232 16 0 262145 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{mso-style-parent:"";
margin:0cm;
margin-bottom:.0001pt;
text-align:justify;
text-justify:inter-ideograph;
mso-pagination:none;
font-size:10.5pt;
mso-bidi-font-size:12.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:宋体;
mso-font-kerning:1.0pt;}
/* Page Definitions */
@page
{mso-page-border-surround-header:no;
mso-page-border-surround-footer:no;}
@page Section1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;
mso-header-margin:36.0pt;
mso-footer-margin:36.0pt;
mso-paper-source:0;}
div.Section1
{page:Section1;}
-->
</style>
</head>
<body lang=ZH-CN style='tab-interval:21.0pt;text-justify-trim:punctuation'>
<div class=Section1>
<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>●试题二<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>【答案】</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>(1)j--(2)i++(3)A[i]</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>←</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>pivot</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>或</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>[j]</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>←</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>pivot(4)A</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>L</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>k-1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>或</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>A</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>L</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>k<o:p></o:p></span></p>
<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>(5)A</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>k+I</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>H</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>或</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>A</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>k</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>H<o:p></o:p></span></p>
<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>【解析】题目考查快速排序算法。快速排序采用了一种分治的策略，通常称为分治法。其基本思想是：将原问题分解为若干个规模更小，但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>快速排序的具体过程为：第一步，在待排序的</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>n</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>个记录中任取一个记录，以该记录的排序码为基准，将所有记录分成</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>2</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>组，第一组各记录的排序码都小于等于该排序码，第二组各记录的排序码都大于该排序码，并把该记录排在这</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>2</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>组中间，这个过程称为一次划分。第二步，采用同样的方法，对划分出来的</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>2</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>组元素分别进行快速排序，直到所有记录都排到相应的位置为止。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>在进行一次划分时，若选定以第一个元素为基准，就可将第一个元素备份在变量</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>pivot</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>中，如图中的第①步所示。这样基准元素在数组中占据的位置就空闲出来了，因此下一步就从后向前扫描。如图中的第②步所示，找到一个比基准元素小的元素时为止，将其前移，如图中的第③步所示。然后再从前向后扫描，如图中的第④步所示，找到一个比基准元素大的元素时为止，将其后移，如图中的第⑤步所示。这样，从后向前扫描和从前向后扫描交替进行，直到扫描到同一个位置为止，如图中的第⑥步所示。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>由题目中给出的流程图可知，以第一个元素作为基准数，并将</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>A[low]</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>备份至</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>pivot</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>用于从前向后扫描的位置指示器，其初值为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>low</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>j</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>用于从后往前扫描的位置指示器，其初值为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>high</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>。当</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i<j</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>时进行循环：<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）从后向前扫描数组</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>A</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，在</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i<j</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的情况下，如果被扫描的元素</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>A[j]>pivot</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，就继续向前扫描</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>(j--)</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>；如果被扫描的元素</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>A[i]<pivot</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>就停止扫描，并将此元素的值赋给目前空闲着的</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>A[i]</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>。⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -