212排序问题与算法的多样性

1、2.1.2排序问题与算法的多样性素能综合检测一、选择题（每题4分，共16分）在中央电视台举办的娱乐节目“幸福52”中，有一种：“猜数”游戏，竞猜者如果在规定的时间内猜出某种商品的价格，就可获得该件商品，现在假设你竞猜一件商品的价格，如果你报价1000元，主持人说“高”，为了在最短的时间内说出正确答案，那么下一个价格你应报（）（A）800元（B）600元（C）500元（D）300元【解析】选C.由折半插入排序法的思想内涵可知.（九江高一检测）利用“直接插入排序法”给8,1,2,3,5,7按从大到小的顺序排序，当插入第四个数3时，实际是插入哪两个数之间（）（A）8与1（B）8与2（C）5与2（D）

2、5与1【解析】选B.当插入第四个数3时，已排成（8,2,1的形式，故需插入8与2之间.1. 将有序列（5,4,3,2,1按照从小到大的顺序输出，需要排序的次数为（）（A）7（B）8（Q9（D）10【解析】选D.5与4比较，形成（4,5;3与5比较，4与3再比较，形成（3,4,5;2与5比较，2与4比较，2与3比较，形成（2,3,4,5;1与5比较，1与4比较，1与3比较，1与2比较得结果，共比较10次.用折半插入排序方法将1插入有序列（-2,-1,3,5,8中，则第一次与该有序列中的哪个数比较（）(A)-2(B) -1(C) 3(D)82. 【解析】选C.由折半插入排序方法知，共5个数据首先与

3、第3个数据比较二、填空题（每题4分，共8分）把由m个数据组成的无序列用直接插入排序法排成有序列，最多可经过次有序列插入排序过程就可完成.【解析】由直接插入排序法将无序列排成有序列的方法可知共需经过m-1次.答案：m-1将数据M插入到一个从小到大排列的有序列时，数据M应满足原有序列中这个位置右边的数据，其左边位置上的数据.【解析】由排序的特点可知数M要大于或等于其左边的数据，小于其右边的数据答案：小于大于或等于三、解答题（每题8分，共16分）用2种方法将数据27插入到有序列8,11,15,18,6,31,38,60中，用自然语言写出算法的步骤，并比较它们的相同点与不同点【解析】方法一：运用有序列

4、的直接插入排序法，算法步骤如下：1. 把27与60比较大小得60>27;把27与38比较大小得38>27;把27与31比较大小得31>27;把27与26比较大小得26V27;把27插到26和31之间.方法二：运用有序列的折半插入排序法，算法步骤如下：3. 1.选择有序列的“中间位置”的数据2.将7比较，显然7,所以27应该排在边;确定余下数据列26,31,38,60;选择新有序列的“中间位置”的数据31;将31与27比较，显然31>27,所以27应该排在31的左边；确定余下数据列26;选择新有序列的“中间位置”的数据26;将26与27比较，显然26V27,所以27应该排

5、在26的右边.两种算法的共同点是每次将新数据与有序列中的数据进行比较；不同点是直接插入排序法总是将数据A与原有序列中的数据从右到左依次进行比较，而折半插入排序法总是将新数据与该序列中的“中间位置”的数据进行比较.（思维拓展题）给定一个有序列13,27,38,39,43,47,48,51,57,66,74,82,90，若将52插入到序列中，请用折半插入排序法确定数据52在序列中的位置，并用自然语言表述算法.【解析】将原有序列列表如下：QI您Q3Qfa-j06a?%GL)aiia】CL2Q1313273839434748515766748290首先选择有序列的“中间位置”的数据a7=48,将52与

6、a7进行比较，显然52>a7,所以52应该排在a7的右边.再取余下数据列a8,a9,a10,a11,a12,a13的“中间位置”的数据a10=66与52比较,52<a10=66,因此52应插到66的左边.此时余下数据（a8,a9的“中间位置”的数据a8=51,显然52>a8=51,因此52应插到a8的右边，而52<a9,所以52应插在a8和a9的中间.探究创新（10分）如图，汉诺塔问题是指有3根杆子A、B、C.B杆上有若干碟子，把所有碟子从B杆移到A杆上,每次只能移动一个碟子，大的碟子不能叠在小的碟子上面.把B杆上的4个碟子全部移到A杆上，最少需要移动多少次？ABC【解析】用a1,a2,a3,a4依次表示从小到大的碟子，a1