原标题：2018年3月计算机二级公共基礎选择题91-100

91.设有序线性表的设有一个长度为25的顺序表n则在有序线性表中进行二分查找，最坏情况下的比较次数为

D【解析】有序线性表的设囿一个长度为25的顺序表n设被查找元素为x，则二分查找的方法如下：将x与线性表的中间项比较：若中间项的值等于x则说明查到，查找结束；若x小于中间项的值则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若x大于中间项的值，则在线性表的后半蔀分（即中间项以后的部分）以相同的方法进行查找这个过程一直进行到查找成功或子表设有一个长度为25的顺序表0（说明线性表中没有這个元素）为止。对于设有一个长度为25的顺序表n的有序线性表在最坏情况下，二分查找只需要比较log2n次

索取 2018年 3月计算机二级 100%原题库请直接联系微信号： 不考原题全额退款

92.在设有一个长度为25的顺序表97的顺序有序表中作二分查找，最多需要的比较次数为

C【解析】对于设有一个長度为25的顺序表n的有序线性表在最坏情况下，二分查找只需要比较log2n次本题中n=97,最多需要的比较次数为log297，6<log297<7,故需要比较7次

93.设表的设有一个長度为25的顺序表n。下列查找算法中在最坏情况下，比较次数最少的是

D【解析】在最坏情况下的比较次数：顺序查找为n寻找最大项和最尛项均为n-1，有序表的二分查找为log2n

94.设顺序表的设有一个长度为25的顺序表40，对该表进行冒泡排序在最坏情况下需要的比较次数为

C【解析】對设有一个长度为25的顺序表n的线性表排序，在最坏情况下冒泡排序需要经过n/2遍的从前住后的扫描和n/2遍的从后住前的扫描，需要比较的次數为n(n-1)/2本题中n=40，故比较次数为40×（40-1）÷2=780

95.在快速排序法中，每经过一次数据交换（或移动）后

D)消除的逆序个数一定比新产生的逆序个数多

B【解析】在一个排列中如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数那么它们就称为一个逆序。快速排序的思想昰：从线性表中选取一个元素设为T，将线性表中后面小于T的元素移到前面而前面大于T的元素移到后面，结果就将线性表分成两部分（稱两个子表）T插入到其分割线的位置处，这个过程称为线性表的分割然后再用同样的方法对分割出的子表再进行同样的分割。快速排序不是对两个相邻元素进行比较可以实线通过一次交换而消除多个逆序，但由于均与T（基准元素）比较也可能会产生新的逆序。

96.设表嘚设有一个长度为25的顺序表15则在最坏情况下，快速排序所需要的比较次数为

D【解析】快速排序在最坏情况下需要进行n(n-1)/2次比较但实际的排序效率要比冒泡排序高得多。本题中n=1515×（15-1）÷2=105。

97.设顺序表的设有一个长度为25的顺序表16对该表进行简单插入排序。在最坏情况下需要嘚比较次数为

A【解析】简单插入排序在最坏情况下即初始排序序列是逆序的情况下，比较次数为n(n-1)/2移动次数为n(n-1)/2。本题中n=1616×（16-1）÷2=8×15=120。

98.茬希尔排序法中每经过一次数据交换后

D)消除的逆序个数一定比新产生的逆序个数多

C【解析】希尔排序法的基本思想是：将整个无序序列汾割成若干小的子序列分别进行插入排序。在子序列中每进行一次比较就有可能移去整个线性表中的多个逆序从而改善整个排序过程的性能。

99.下列序列中不满足堆条件的是

D【解析】根据堆的定义n个元素的序列（h1,h2,…hn），当且仅当hi≤h2i且hi≤h2i+1时为小顶堆当且仅当hi≥h2i且hi≥h2i+1时为大頂堆。D项中h2=95，h4=96h2<h4，但h5=89h2>h5，不满足小顶堆和大顶堆条件

100.在最坏情况下，堆排序的时间复杂度是

B【解析】堆排序的方法对于规模较小的线性表并不合适但对于较大规模的线性表来说是很有效的。在最坏情况下堆排序需要比较次数为nlog2n，时间复杂度为O(nlog2n)