早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->
将数组{1,1,2,4,7,5}从小到大排序,若采用(62)排序算法,则元素之间需要进行的比较次数最少,A.直接
题目
将数组{1,1,2,4,7,5}从小到大排序,若采用(62)排序算法,则元素之间需要进行的比较次数最少,
A.直接插入
B.归并
C.堆
D.快速
参考答案
正确答案:A
本题主要考查排序算法。本题给出的数组如果采用直接插入排序,那么其排序过程如下:首先1和1比较找到合适的插入位置,然后2和1比较,找到合适的插入位置;然后4和2比较,找到4的合适插入位置,然后7和4比较,找到7的合适插入位置,然后5和7比较,因为5比7小,因此要与4比较,然后就找到了5的合适位置,整个排序过程结束。总的比较次数为1+1+1+1+2=6次。归并排序的算法思想是将两个相邻的有序子序列归并为一个有序序列,然后再将新产生的相邻序列进行归并,当只剩下一个有序序列时算法结束。其过程如下:1和1比较,然后归并,2和4比较,然后归并,7和5比较,然后归并,解析来将再将[1,1]和[2,4]归并,用2分别与两个1比较得到[1,1,2,4],然后再用[1,1,2,4]与[5,7]归并。这时,用5与[1,1,2,4]中每个元素分别比较一次,最后即可得到整个有序序列。总的比较次数为:1+1+1+2+4=9次。堆排序的基本思想是先将序列建立堆,然后输出堆顶元素,再将剩下的序列建立堆,然后再输出堆顶元素,依此类推,直到所有元素均输出为止。因此在堆排序过程中,最重要的就是建堆。本题中给出的数组序列就是一个小顶堆,然后输出堆顶,将剩下的部分调整为小顶堆,调整的过程为,首先将最后一个元素5置换到堆顶,然后用5与左孩子结点比较,由于大于左孩子,因此与其置换位置,然后值为5的结点仍然大于其左孩子结点,再置换位置,这样就得到了新的小顶堆,这个过程总共比较2次。后面的排序过程是同样的道理。本题采用堆排序算法总共的比较次数为7次。快速排序的基本思想是:①以某个元素为支点(通常是第一个元素),通过比较关键码和交换记录,将待排序的序列分成两个区间。其中左区间中所有元素的关键字均不大于支点元素的关键字,而右区间中所有元素的关键字均不小于支点元素的关键字。称此过程为一次划分;②分别对左右区间的待排序序列,再按照以上方法进行划分,直到整个序列按关键字有序为止。由于本题给出的例子基本是从小到大有序,不适合采用快速排序发,其总共需要的比较次数为15次。
本题主要考查排序算法。本题给出的数组如果采用直接插入排序,那么其排序过程如下:首先1和1比较找到合适的插入位置,然后2和1比较,找到合适的插入位置;然后4和2比较,找到4的合适插入位置,然后7和4比较,找到7的合适插入位置,然后5和7比较,因为5比7小,因此要与4比较,然后就找到了5的合适位置,整个排序过程结束。总的比较次数为1+1+1+1+2=6次。归并排序的算法思想是将两个相邻的有序子序列归并为一个有序序列,然后再将新产生的相邻序列进行归并,当只剩下一个有序序列时算法结束。其过程如下:1和1比较,然后归并,2和4比较,然后归并,7和5比较,然后归并,解析来将再将[1,1]和[2,4]归并,用2分别与两个1比较得到[1,1,2,4],然后再用[1,1,2,4]与[5,7]归并。这时,用5与[1,1,2,4]中每个元素分别比较一次,最后即可得到整个有序序列。总的比较次数为:1+1+1+2+4=9次。堆排序的基本思想是先将序列建立堆,然后输出堆顶元素,再将剩下的序列建立堆,然后再输出堆顶元素,依此类推,直到所有元素均输出为止。因此在堆排序过程中,最重要的就是建堆。本题中给出的数组序列就是一个小顶堆,然后输出堆顶,将剩下的部分调整为小顶堆,调整的过程为,首先将最后一个元素5置换到堆顶,然后用5与左孩子结点比较,由于大于左孩子,因此与其置换位置,然后值为5的结点仍然大于其左孩子结点,再置换位置,这样就得到了新的小顶堆,这个过程总共比较2次。后面的排序过程是同样的道理。本题采用堆排序算法总共的比较次数为7次。快速排序的基本思想是:①以某个元素为支点(通常是第一个元素),通过比较关键码和交换记录,将待排序的序列分成两个区间。其中左区间中所有元素的关键字均不大于支点元素的关键字,而右区间中所有元素的关键字均不小于支点元素的关键字。称此过程为一次划分;②分别对左右区间的待排序序列,再按照以上方法进行划分,直到整个序列按关键字有序为止。由于本题给出的例子基本是从小到大有序,不适合采用快速排序发,其总共需要的比较次数为15次。
看了将数组{1,1,2,4,7,5...的网友还看了以下:
甲、乙、丙三个同学排队接水,甲接水用4分钟,乙接水用2分钟,丙接水用3分钟,要使三个同学等候时间总 数学 2020-04-11 …
甲、乙、丙三个同学排队接水,甲接水用4分钟,乙接水用2分钟,丙接水用3分钟,要使三个同学等候的时间 数学 2020-04-11 …
列方程小林用半小时一共接了2.4千克的水这个水龙头平均每分钟滴水多少克列方程小林用半小时一共接了2 数学 2020-05-22 …
半个小时一共接了2.4千克的水.这个水龙头平均每分钟滴水多少克/方程解答 数学 2020-05-22 …
上一排1.2.3.4.5.x下一排2.4.8.16.32.()括号里填多少? 其他 2020-06-03 …
观察下面依次排列的一组数,它的排列有什么规律?请根据你探索的规律接着写出后面的3个数,并尝试说出第 数学 2020-06-11 …
一个队列按照每排2,4,6,8人的顺序可以一直排到某一排有100人,那么这个队列共有多少人? 数学 2020-11-03 …
千瓦电压表的接线方法我现在有一个250千瓦电压表,有7个接线端.上一排是1.2.3.接线端.下一排是 其他 2020-12-05 …
将以定值电阻接到2.4伏电源上测得电流为0.2安;若将它接到3.6伏的电路中时,电流为多少? 物理 2020-12-31 …
分别求出符合下列要求的不同排法的种数(1)6名学生排3排,前排1人,中排2人,后排3人;(2)6名学 其他 2021-01-12 …