📄 st10.htm
字号:
font-size:10.5pt; mso-bidi-font-size:10.0pt; font-family:"Times New Roman"; mso-fareast-font-family:宋体; mso-font-kerning:1.0pt;}ins {mso-style-type:export-only; text-decoration:none;}span.msoIns {mso-style-type:export-only; mso-style-name:""; text-decoration:underline; text-underline:single;}span.msoDel {mso-style-type:export-only; mso-style-name:""; text-decoration:line-through; color:red;} /* Page Definitions */ @page {mso-page-border-surround-header:no; mso-page-border-surround-footer:no; mso-footnote-separator:url("st10.files/header.htm") fs; mso-footnote-continuation-separator:url("st10.files/header.htm") fcs; mso-endnote-separator:url("st10.files/header.htm") es; mso-endnote-continuation-separator:url("st10.files/header.htm") ecs;}@page Section1 {size:21.0cm 842.0pt; margin:42.55pt 1.0cm 1.0cm 42.55pt; mso-header-margin:42.55pt; mso-footer-margin:49.6pt; mso-header:url("st10.files/header.htm") h1; mso-even-footer:url("st10.files/header.htm") ef1; mso-footer:url("st10.files/header.htm") f1; mso-paper-source:0; layout-grid:15.1pt .9pt; mso-layout-grid-char-alt:3690;}div.Section1 {page:Section1;} /* List Definitions */ @list l0 {mso-list-id:1061097795; mso-list-type:hybrid; mso-list-template-ids:-862415298 1138398318 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}@list l0:level1 {mso-level-text:（%1）; 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:15.1pt .9pt;mso-layout-grid-char-alt:3690'><p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><spanstyle='mso-spacerun:yes'> </span><b><spanstyle='mso-spacerun:yes'> </span></b></span><spanstyle='font-size:14.0pt;font-family:宋体;mso-bidi-font-weight:bold'>第<spanlang=EN-US>10</span>章<span lang=EN-US><span style='mso-spacerun:yes'> </span></span>排序<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal><b><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>一、选择题<spanlang=EN-US><o:p></o:p></span></span></b></p><p class=MsoNormal style='mso-outline-level:1;tab-stops:44.25pt'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>1</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．某内排序方法的稳定性是指<span lang=EN-US>(<span style='mso-spacerun:yes'> </span>)</span>。 【南京理工大学<spanlang=EN-US> 1997<span style='mso-spacerun:yes'> </span></span>一、<spanlang=EN-US>10</span>（<span lang=EN-US>2</span>分）】<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:34.2pt;mso-char-indent-count:3.0;tab-stops:44.25pt'><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><span style='mso-spacerun:yes'> </span><span style='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span>B</span>．该排序算法允许有相同的关键字记录<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:34.2pt;mso-char-indent-count:3.0;tab-stops:44.25pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>C</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>．平均时间为<span lang=EN-US>0</span>（<span lang=EN-US>n log n</span>）的排序方法<spanlang=EN-US><span style='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span>D</span>．以上都不对 <spanlang=EN-US style='mso-bidi-font-weight:bold'><o:p></o:p></span></span></p><p class=MsoNormal style='margin-left:4.55pt;text-indent:-4.55pt;mso-char-indent-count:-.4'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>2</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．下面给出的四种排序法中<span lang=EN-US>(<spanstyle='mso-spacerun:yes'> </span>)</span>排序法是不稳定性排序法。【北京航空航天大学<span lang=EN-US>1999 </span>一、<span lang=EN-US>10 </span>（<span lang=EN-US>2</span>分）】<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='margin-left:4.55pt;text-indent:-4.55pt;mso-char-indent-count:-.4'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><spanstyle='mso-spacerun:yes'> </span>A. </span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>插入<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>B. </span>冒泡<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>C. </span>二路归并<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>D. </span>堆积<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='margin-left:4.55pt;text-indent:-4.55pt;mso-char-indent-count:-.4'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>3</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．下列排序算法中，其中（<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span></span>）是稳定的。 【福州大学<spanlang=EN-US> 1998 </span>一、<span lang=EN-US>3 (2</span>分<span lang=EN-US>)</span>】<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A. </span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>堆排序，冒泡排序 <spanstyle='mso-spacerun:yes'> </span><span lang=EN-US><spanstyle='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span>B. </span>快速排序，堆排序<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><spanstyle='mso-spacerun:yes'> </span>C. </span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>直接选择排序，归并排序<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span>D. </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;tab-stops:210.75pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>4</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>．稳定的排序方法是（<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span></span>）<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span></span>【北方交通大学<span lang=EN-US>2000 </span>二、<span lang=EN-US>3</span>（<span lang=EN-US>2</span>分）】<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．直接插入排序和快速排序<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>B</span>．折半插入排序和起泡排序<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>C</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．简单选择排序和四路归并排序 <spanstyle='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span><span lang=EN-US>D</span>．树形选择排序和<spanlang=EN-US>shell</span>排序<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='margin-left:9.7pt;text-indent:-9.7pt;mso-char-indent-count:-.85'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>5</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．下列排序方法中，哪一个是稳定的排序方法？（<spanlang=EN-US><span style='mso-spacerun:yes'> </span></span> ）<spanlang=EN-US><span style='mso-spacerun:yes'> </span></span>【北方交通大学<spanlang=EN-US> 2001 </span>一、<span lang=EN-US>8</span>（<span lang=EN-US>2</span>分）】<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．直接选择排序<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>B</span>．二分法插入排序<spanlang=EN-US><span style='mso-spacerun:yes'> </span>C</span>．希尔排序<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>D</span>．快速排序<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='margin-left:9.7pt;text-indent:-9.7pt;mso-char-indent-count:-.85'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>6</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．若要求尽可能快地对序列进行稳定的排序，则应选（<spanlang=EN-US>A</span>．快速排序<span lang=EN-US><span style='mso-spacerun:yes'> </span>B</span>．归并排序<span lang=EN-US><span style='mso-spacerun:yes'> </span>C</span>．冒泡排序）。<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>【北京邮电大学<span lang=EN-US> 2001 </span>一、<spanlang=EN-US>5</span>（<span lang=EN-US>2</span>分）】<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='margin-left:9.7pt;text-indent:-9.7pt;mso-char-indent-count:-.85'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>7</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（<spanlang=EN-US><span style='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span></span>）就是不稳定的排序方法。【清华大学<spanlang=EN-US> 1998 </span>一、<span lang=EN-US>3 (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'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．起泡排序<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>B</span>．归并排序<spanlang=EN-US><span style='mso-spacerun:yes'> </span>C</span>．<spanlang=EN-US>Shell</span>排序<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>D</span>．直接插入排序<spanlang=EN-US><span style='mso-spacerun:yes'> </span>E</span>．简单选择排序<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='margin-left:32.5pt;text-indent:-32.5pt;mso-char-indent-count:-2.85'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>8</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（<spanlang=EN-US><span style='mso-spacerun:yes'> </span></span>）排序为宜。<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><spanlang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．直接插入<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>B</span>．直接选择<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>C</span>．堆<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>D</span>．快速<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>E</span>．基数<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span></span>【<span style='color:black'>中科院计算所<spanlang=EN-US> 2000 </span>一、<span lang=EN-US>5</span>（<span lang=EN-US>2</span>分）</span>】<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='margin-left:57.0pt;text-indent:-57.0pt;mso-char-indent-count:-5.0'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>9</span><spanstyle='mso-bidi-font-size:10.5pt;font-family:宋体'>．若需在<span lang=EN-US>O(nlog<sub>2</sub>n)</span>的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（<spanlang=EN-US><span style='mso-spacerun:yes'> </span></span>）。<span⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -