二级MSOffice高级应用新大纲选择题题目、解析及答案时间复杂度

1、二级MSOffice高级应用（新大纲）选择题题目、解析及答案（时间复杂度）常用排序方法排序方法最好最坏平均冒泡排序O(n)O(n2)O(n2)插入排序O(n)O(n2)O(n2)选择排序O(n2)O(n2)O(n2)希尔排序O(n)O(n2)O(n1.3)快速排序O(nlog2n)O(n2)O(nlog2n)堆排序O(nlog2n)O(nlog2n)O(nlog2n)常用查找方法查找方法平均时间复杂度查找条件顺序查找O(n)无序或有序队列二分查找（折半查找）O(logn)有序数组二叉排序树查找O(logn)二叉排序树1 .在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（）。A

2、）B）0?D)?1/参考答案：C2 .下列排序方法中，最坏情况下比较次数最少的是（）。A）冒泡排序B）简单选择排序C）直接插入排序D）堆排序参考答案：D解析：最坏情况下：冒泡排序、简单选择排序、简单插入排序比较n（n-1）/2次；堆排序比较的次数是nlog2n次。3 .对长度为n的线性表排序，在最坏情况下，比较次数不是n（n-1）/2的排序方法是（）。A）快速排序B）冒泡排序C）直接插入排序D）堆排序参考答案：D解析：堆排序的时间复杂度是nlog2n；4 .下列排序法中，最坏情况下时间复杂度最小的是（）。A）希尔排序B）堆排序C）快速排序D）冒泡排序参考答案：B解析：快速排序、冒泡排序、希尔排

3、序最坏情况时间下的时间复杂度为O（n2）,堆排序最坏情况下的时间复杂度为O（nlog2n）。5 .设顺序表的长度为n0下列算法中，最坏情况下比较次数小于n的是（）。A）快速排序B）堆排序C）寻找最大项D）顺序查找法参考答案：C解析：最坏情况下比较次数：快速排序：n（n-1）/2堆排序：nlog2n查找最大项：先设第一个数是最大数，然后逐次和后面的（n-1）个数比较，需要比较次数为n-1；顺序查找法：最坏情况下从第一个数开始找到最后一个，比较次数为n06 .下列排序法中，每经过一次元素的交换会产生新的逆序的是（）。A）冒泡排序B）快速排序C）简单插入排序D）简单选择排序参考答案：B解析：在一个排

4、列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列7 .在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为（）。A） nB） （n+1）/2C） 3n/4D） n/4参考答案：B解析：在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为1;在最坏情

5、况下，最后一个元素才是要找的元素，则比较次数为n0则n个数总的比较次数为(1+2+-+(n-1)+n)=(1+n)xn)/2,平均为：(n+1)/28 .设顺序表的长度为n。下列排序方法中，最坏情况下比较次数小于n(n-1)/2的是()。A)堆排序B)快速排序C)简单插入排序D)冒泡排序参考答案：A解析：堆排序最坏情况下比较次数为O(nlog2n)。9 .下列各排序法中，最坏情况下的时间复杂度最低的是()。A)希尔排序B)快速排序C)堆排序D)冒泡排序参考答案：C解析：堆排序最坏情况时间下的时间复杂度为O(nlog2n)。10 .设顺序表的长度为40,对该表进行冒泡排序。在最坏情况下需要的比较

6、次数为()。A) 820B) 780C) 40D) 41参考答案：B解析：冒泡排序在最坏情况下需要比较的次数为n(n-1)/2。11 .在希尔排序法中，每经过一次数据交换后（A）只能消除一个逆序B）能消除多个逆序C）不会产生新的逆序D）消除的逆序个数一定比新产生的逆序个数多参考答案：B解析：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。12 .设顺序表的长度为16,对该表进行简单插入排序。在最坏情况下需要的比较次数为（）。A） 15B） 60C） 30D） 120参考答案：D解析：简单插入排序在最坏情况下比较次数为n（n-1）/2013 .下列叙述中正确的是（）。A）快速排序法适用于顺序存储的线性表B）快速排序适用于链式存储的线性表C）链式存储的线性表不可能排序D）堆排序适用于非线性结构参考答案：A14 .在最坏情况下比较次数相同的是（）。A）冒泡排序与快速排序B）简单插入排序与希尔排序C)简单选择排序与堆排序D)快速排序与希尔排序参考答案：A解析：