GESP-C++四级 题库
关于排序算法的稳定性,以下说法错误的是( )
稳定的排序算法不改变相等元素的相对位置
冒泡排序是稳定的排序算法
选择排序是稳定的排序算法
插入排序是稳定的排序算法
下面代码试图实现选择排序,使其能对数组 nums 排序为升序,则横线上应分别填写( )

nums[j] < nums[minIndex]
swap(nums[i], nums[minIndex])
nums[j] > nums[minIndex]
swap(nums[i], nums[minIndex])
nums[j] <= nums[minIndex]
swap(nums[j], nums[minIndex])
nums[j] <= nums[minIndex]
swap(nums[i], nums[j])
下面程序实现插入排序(升序排序),则横线上应分别填写( )

arr[j] > key
arr[j + 1] = key
arr[j] < key
arr[j + 1] = key
arr[j] > key
arr[j] = key
arr[j] < key
arr[j] = key
关于插入排序的时间复杂度,下列说法正确的是( )。
最好情况和最坏情况的时间复杂度都是
最好情况是 ,最坏情况是

最好情况是 ,最坏情况是

最好情况是 ,最坏情况是

以下哪种情况是使用插入排序的合适场景?( )
插入排序将待排序元素逐个插入到已排序部分的正确位置。
最适合:数据几乎有序(只需少量调整),此时接近最优时间复杂度 O(n),不适合数据量大且完全乱序,性能退化为 O(n^2)。
下述斐波那契数列计算的时间复杂度是?( )
斐波那契数列的递归存在 重复计算,每个 fibonacci(n) 调用会进一步分解为 fibonacci(n-1) 和 fibonacci(n-2),调用次数和2^n有关,时间复杂度为O(2^n)。
为了提高冒泡排序的效率,如果某轮“冒泡”中没有执行任何交换操作,说明数组已经完成排序,可直接返回结果,则两条横线上分别应该填写?( )
填空1,初始化 flag为false,填空2,如果发生交换,将flag置位true。
下面关于排序稳定性的描述,正确的是( )。
排序算法的稳定性指:若原始序列中存在多个相等元素,排序后它们的相对顺序保持不变。所以A选项错 误,选择排序不是稳定排序,插入排序是稳定排序,选择B 。
对数组 arr[]={5, 3, 8, 1} 进行升序排序,执行第—轮冒泡排序后数组 arr 中的内容为( )。
根据冒泡排序的逻辑,本题选择A 。
下面关于排序算法(冒泡排序、插入排序和选择排序)的描述中,不正确的是( )。
冒泡排序的第一轮操作是从左到右遍历数组,通过两两比较相邻元素,将当前最大的元素移动到末尾。给定数组 arr[]={4, 1, 3, 1, 5, 2} ,执行第一轮冒泡排序后数组 arr 中的内容为( )。
在排序算法中,稳定性指的是( )。
解析:稳定排序算法在排序时,如果有两个相等的元素,排序后这两个元素的相对顺序保持不变。
其他选项的解释不符合稳定性的定义:
A错误,排序后的数据是否丢失与稳定性无关。
C错误,排序后数据可能会被修改(如位置改变)。
D错误,时间复杂度是排序算法的性能指标,与稳定性无关。
因此,正确答案是B
下面代码实现了冒泡排序函数,则横线上应填写( )。
冒泡排序的外层循环遍历数组,从后向前控制需要比较的元素范围。
内层循环for (int j = 0; j < i; j++) 则确保在当前遍历中比较到第i 个元素,保证了在每一轮中较大的元素会逐步“冒泡”到末尾
关于直接插入排序,下列说法错误的是()
就地排序只需要O(1)的额外空间。
关于几种排序算法的说法,下面说法错误的是( )。
在冒泡排序中,两个元素交换的条件是a[j]>a[j+1],如果两个元素的值相等,他们并不会发生交换,因此是一种稳定的排序算法。
数组{45,66,23,1,10,97,52,88,5,33}进行从小到大冒泡排序过程中,第一遍冒泡过后的序列是( )。
按照冒泡排序的过程模拟一遍即可,66会被一直交换到97的前面的位置,97会被一直交换到数组末尾的位置。
对包含 n 个元素的数组进行冒泡排序,平均时间复杂度一般为( )。