点击查看：2015年计算机二级公共基础知识考点测试题汇总

　　排序技术

　　1[单选题]对长度n的线性表排序，在最坏情况下，比较次数不是n(n一1)/2的排序方法是(　　)。

　　参考答案：D

　　参考解析：排序技术有：①交换类排序法(冒泡排序法、快速排序法);②插入类排序法(简单插入排序、希尔排序);③选择类排序法(简单选择排序法、堆排序法)。在最坏情况下，希尔排序需要的比较次数是O(nl.5)、堆排序需要的比较次数是O(nlog2n)、其它排序方法需要的比较次数都是n(n.1)/2。因此本题的正确答案是D。

　　2[单选题]冒泡排序在最坏情况下的比较次数是(　　)。

　　参考答案：C

　　参考解析：对于长度为n的线性表，在最坏情况下，冒泡排序需要进行的比较次数是n(n一1)/2。因此本题的正确答案是C。

　　3[单选题]通过相邻数据元素的交换逐步：搿线性表变成有序的排序方法是(　　)

　　A.冒泡排序法B.简单选择排序法C.简单插入排序法D.希尔排序法

　　参考答案：A

　　4[单选题]冒泡排序在最坏情况下的比较次数是(　　)

　　A.n(n+1)/2B.nlog2nC.n(n-1)/2D.n/2

　　参考答案：C

　　参考解析：对于长度为n的线性表，在最坏情况下，冒泡排序需要进行的比较次数是n(n-1)/2。因此本题的正确答案是C。

　　5[单选题]快速排序法属于(　　)

　　A.选择类排序法B.交换类排序法C.插入类排序法D.归并类排序法

　　参考答案：B

　　6[单选题]对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是(　　)。

　　参考答案：D

　　参考解析：对于长度为n的线性表，在最坏情况下，冒泡排序需要进行的比较次数是n(n—1)/2，快速排序需要进行的比较次数是n(n-1)/2，简单插入排序需要进行的比较次数是n(n—1)/2，希尔排序需要进行的比较次数是0(n1 5)，简单选择排序需要进行的比较次数是n(n-1)/2，堆排序需要进行的比较次数是0(nl092n)。因此选项D正确。

　　7[单选题]下列排序方法中，最坏情况下比较次数最少的是(　　)

　　A.冒泡排序B.简单选择排序C.直接插入排序D.堆排序

　　参考答案：D

　　参考解析：冒泡排序、简单选择排序和直接插入排序法在最坏情况下的比较次数为n(n-1)/2，而堆排序法在最坏情况下的比较次数为O(nl092n)。

　　8[单选题]长度为l0的顺序表的首地址是从l023开始的，顺序表中每个元素的长度为2，在第4个元素前面插入一个元素和删除第7个元素后，顺序表的总长度还是不变。问在执行插入和删除操作前，顺序表中第5个元素在执行插入和删除操作后在顺序表中的存储地址是(　　)

　　A.1028B.1029C.1031D.1033

　　参考答案：D

　　参考解析：由于问的是原来顺序表中的第5个元素，它在插入操作后变成了第6个元素(因为插入的元素在它前面)。由于删除的第7个元素在它后面，不会影响它在顺序表中的排位。因此在执行插入和删除操作后原先顺序表中的第5个元素变成了新的顺序表中的第6个元素。再按照线性表的随机存取地址的计算公式ADD(ai)=ADD(a1)+(i-l)×k计算ADD(a6)=ADD(a1)+(6—1)×2=1023+5×2=1033，因此选项D正确。

　　9[填空题]________是-组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。

　　参考解析：算法

　　10[填空题]请写出用二分查找法在有序顺序表(1，2，3，4，6，8，9，11)中查找3的比较序列________。

　　参考解析：4，2，3

　　【分析】可采用擦去法做这类二分法查找序列的题：每次从序列中找出中间元素，刚开始时是4，由于3比4小，只能存在在4之前的序列中，于是把4以后的序列擦去，只剩下序列(1，2，3)，在重复以上过程直到查找元素或是序列为空.

　　11[填空题]在最坏情况下，冒泡排序的时间复杂度为________，简单插入排序的时间复杂度为________，希尔排序的时间复杂度为________，简单选择排序的时间复杂度为________，堆排序的时间复杂度为________。

　　参考解析：O(n(n-1)/2) O(n(n—1)/2) O(n1.5) O(n(n—1)/2) O(nlog2n)

　　12[单选题]通过相邻数据元素的交换逐步：搿线性表变成有序的排序方法是(　　)。

　　参考答案：A

　　13[单选题]快速排序法属于(　　)。

　　参考答案：B

　　14[填空题]请写出用冒泡排序法对序列(5，1，7，3，1，6，9，3，2，7，6)进行第-遍扫描后的中间结果是________。

　　参考解析：

　　(1，1，5，3，2，6，7，3，6，7，9)【分析】冒泡排序法的基本过程：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小，若前面的元素大于后面的元素，则将他们交换，这样最大者交换到了表的最后面;然后，从后往前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小若后面的元素小于前面的元素，则将他们交换，这样最小者交换到了表的最前面;从前往后和从后往前扫描一个来回称为-遍：对剩下的线性表重复上述过程，直到剩下的线性表变为空为止.这样线性表就变为有序了。

　　现在我们来看看对线性表(5，1，7，3，l，6，9，3，2，7，6)从前往后进行扫描的过程：

　　5>15和l交换位置得到(1，5，7，3，l，6，9，3，2，7，6)

　　5<7不管，继续往后扫描，扫描到7

　　7>37和3交换位置得到(1，5，3，7，1，6，9，3，2，7，6)

　　7>17和1交换位置得到(1，5，3，l，7，6，9，3，2，7，6)

　　7>67和6交换位置得到(1，5，3，1，6，7，9，3，2，7，6)

　　7<9不管，继续往后扫描，扫描到9

　　9>39和3交挟位置得到(1，5，3，l，6，7，3，9，2，7，6)

　　9>29和2交换位置得到fl，5，3，1，6，7，3，2，9.7，6)

　　9>79和7交换位置得到(1，5，3，1，6，7，3，2，7，9，6)

　　9>69和6交换位置得到(1，5，3，l，6，7，3，2，7，6，9)

　　从前往后扫描结束，9交换到了线性表的最后。

　　现在我们来看看对剩下的线性表(1，5，3，1，6，7，3，2，7，6)从后往前进行扫描的过程：

　　6<76和7交换位置得到(1，5，3，l，6，7，3，2，6，7)

　　6>2不管，继续往前扫描，扫描到2

　　2<32和3交换位置得到(1，5，3，1，6，7，2，3，6，71

　　2<72和7交换位置得到(1，5，3，1，6，2，7，3，6，7)

　　2<62和6交换位置得到(1，5，3，1，2，6，7，3，6，7)

　　2>1不管，继续往前扫描，扫描到l

　　l<31和3交换位置得到(1，5，1，3，2，6，7，3，6

　　15[填空题]以下排序技术中属于交换类排序法的有________，属于插入类排序法的有________，属于选择类排序法的有________。

　　Ⅰ.简单插入排序

　　Ⅱ.冒泡排序

　　Ⅲ.希尔排序

　　Ⅳ.堆排序

　　Ⅴ.快速排序

　　Ⅵ.简单选择排序

　　参考解析：

　　Ⅱ Ⅴ

　　Ⅲ

　　Ⅳ Ⅵ

　　16[填空题]请写出用冒泡排序法对序列(5，1，7，3，1，6，9，3，2，7，6)进行第一遍扫描后的中间结果是(　　)。

　　参考解析：

　　(1，1，5，3，2，6，7，3，6，7，9)

　　17[填空题]请写出用希尔排序法对序列(5，1，7，3，1，6，9，3，2，7，6)进行第一遍扫描后的中间结果是(　　)。

　　参考解析：

　　(5，l，3，2，1，6，9，7，3，7，6)

　　【分析】希尔排序法的基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序(插入排序：开始线性表中只有第l个元素，然后从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面已经有序的子表中)。

　　子序列的分割方法：将相隔某个增量h(ht=n/2k(k=1，2，3，…，[10g2n]n为待排序的线性表的长度))的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到l时进行一次插入排序，排序完成。

　　按以上分析，第1次分割子序列h=n/2=11/2=5，构成的子序列有：5—6、1—9、7—3、3—2、l一7、6(最后一个元素6成单)，每一个序列进行插入排序，结果为：5—6、l一9、3—7、2—3、l一7、6(最后一个元素6成单)，所以第一遍扫描后的中间结果是(5，l，3，2，1，6，9，7，3，7，6)。

　　18[填空题]请写出用简单选择排序法对序列(5，l，7，3，l，6，9，3，2，7，6)进行第一遍扫描后的中间结果是(　　)。

　　参考解析：

　　(1，5，7，3，l，6，9，3，2，7，6)

　　【分析】扫描整个线性表，从中选择最小的元素，将他交换到袁的最前面;然后对剩下的子表采用同样的方法，直到子表为空。我们对线性表(5，1，7，3，1，6，9，3，2， 7，6)进行第1遍扫描，可以看出元素1最小，将l和第一个位置上的元素5交换，就得到第1遍扫描的结果：(1，5，7，3，l，6，9，3，2，7，6)。

　　19[填空题](　　)是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。

　　参考解析：算法

　　20[填空题]算法中各操作之间的执行顺序称为(　　)。描述算法的工具通常有(　　)、(　　)、(　　)等。

　　参考解析：算法的控制结构、传统流程图、N—S结构化流程图、算法描述语言

　　21[填空题]在最坏情况下，冒泡排序的时间复杂度为(　　) ，简单插入排序的时间复杂度为(　　)，希尔排序的时间复杂度为(　　) ，简单选择排序的时间复杂度为(　　) ，堆排序的时间复杂度为(　　) 。

　　参考解析：O(n(n-1)/2) 、O(n(n—1)/2)、O(n1.5) 、 O(n(n—1)/2)、O(nlog2n)

　　22[填空题]以下排序技术中属于交换类排序法的有(　　) ，属于插入类排序法的有(　　)，属于选择类排序法的有(　　)。

　　Ⅰ.简单插入排序

　　Ⅱ.冒泡排序

　　Ⅲ.希尔排序

　　Ⅳ.堆排序

　　Ⅴ.快速排序

　　Ⅵ.简单选择排序

　　参考解析：Ⅱ Ⅴ 、Ⅰ Ⅲ 、Ⅳ Ⅵ

　　相关推荐：

　　2015年9月计算机等级考试成绩查询时间通知

　　2015计算机二级公共基础知识考前冲刺练试题汇总

　　2015计算机二级《公共基础知识》精选选择题90道

　　2015计算机等级考试通关必看:一至四级备考经验