二级MSOffice高级应用新大纲选择题题目、解析及答案时间复杂度_第1页
二级MSOffice高级应用新大纲选择题题目、解析及答案时间复杂度_第2页
二级MSOffice高级应用新大纲选择题题目、解析及答案时间复杂度_第3页
二级MSOffice高级应用新大纲选择题题目、解析及答案时间复杂度_第4页
二级MSOffice高级应用新大纲选择题题目、解析及答案时间复杂度_第5页
免费预览已结束,剩余1页可下载查看

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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解析:

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论