项目六 任务三 数组的排序和查找 (练习）-《算法与程序设计-C#》（河北科学技术出版社）同步精品课堂

6.3 数组的排序与查找 一、单项选择题 1. 以下关于冒泡排序算法的描述，正确的是（ ）​ A. 冒泡排序是一种不稳定的排序算法​ B. 冒泡排序在最好情况下的时间复杂度为 O (n)​ C. 冒泡排序每次比较相邻的两个元素，将较小的元素交换到后面​ D. 冒泡排序需要额外的存储空间来完成排序 2.选择排序算法的核心操作是（ ）​ A. 每次将最小元素放到已排序序列的末尾​ B. 每次将最大元素放到已排序序列的末尾​ C. 每次从未排序序列中选择最小元素与当前位置元素交换​ D. 每次从未排序序列中选择最大元素与当前位置元素交换 3. 二分查找法要求数组必须是（ ）​ A. 无序的 B. 有序的 C. 可以无序也可以有序 D. 以上都不对 4. 在插入排序中，已排序部分的初始状态是（ ） A. 空 B. 包含数组的第一个元素 C. 包含数组的最后一个元素 D. 包含数组的中间元素 5.以下关于顺序查找算法的说法，错误的是（ ）​ A. 顺序查找算法适用于任何类型的数组，无论是否有序​ B. 顺序查找算法的时间复杂度始终为 O (n)​ C. 顺序查找算法从数组的第一个元素开始，逐个比较元素​ D. 顺序查找算法在找到目标元素后会立即返回 6.对于一个已经基本有序的数组，使用哪种排序算法可以最快地完成排序（ ）​ A. 选择排序 B. 冒泡排序 C. 插入排序 D. 希尔排序 7. 顺序查找法的时间复杂度是（ ） A. O(n) B. O(log n) C. O(n²) D. O(1) 8. 在C#中，以下代码实现的排序算法是（ ） void Sort(int[] arr) {for (int i = 0; i < arr.Length - 1; i++) {int min = i; for (int j = i + 1; j < arr.Length; j++) { if (arr[j] < arr[min]) {min = j; } } int temp = arr[min]; arr[min] = arr[i]; arr[i] = temp;}} A. 冒泡排序 B. 插入排序 C. 选择排序 D. 快速排序 2、 判断题 1. 冒泡排序算法在每一轮比较中都会确定一个元素的最终位置。（ ） 2. 在 C# 中，选择排序是一种稳定的排序算法。（ ） 3. 顺序查找算法只能用于查找整数类型的数组。（ ） 4. 二分查找法的效率比顺序查找法高，因此在所有情况下都应该优先使用二分查找法。（ ） 5. 顺序查找法在查找失败时需要遍历整个数组。（ ） 3、 填空题 1. 选择排序的基本思想是在未排序序列中找到________（或最大）元素，存放到排序序列的起始位置。 2.插入排序将数组分为________和________两部分。 3.二分查找法中，每次查找时，查找区间的大小会变为原来的______。 4.冒泡排序中，对于一个长度为 n 的数组，最多需要进行______轮比较。 5.冒泡排序的基本思想是通过相邻元素的________和________，将较大的元素逐渐“冒泡”到数组的末尾。 四、程序填空题 1.冒泡排序代码如下，请补充完整： void BubbleSort(int[] arr) { for (int i = 0; i < _____________; i++) { for (int j = 0; j < ____________; j++) { if (arr[j] > arr[j + 1]) { _________________ arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } 2.二分查找算法代码如下，请补充完整 int BinarySearch(int[] arr, int target) { int left = 0, right = arr.Length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return ________; else if (arr[mid] < target) left = ________; else right = ________; } return -1; } 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 $$ 6.3 数组的排序与查找 一、单项选择题 1. 以下关于冒泡排序算法的描述，正确的是（ ）​ A. 冒泡排序是一种不稳定的排序算法​ B. 冒泡排序在最好情况下的时间复杂度为 O (n)​ C. 冒泡排序每次比较相邻的两个元素，将较小的元素交换到后面​ D. 冒泡排序需要额外的存储空间来完成排序 【答案】B 【解析】冒泡排序是稳定排序算法，A 错误；每次比较相邻元素，将较大元素交换到后面，C 错误；冒泡排序空间复杂度为 O (1)，不需要额外大量存储空间，D 错误；在数组已经有序时，冒泡排序只需要遍历一次数组，时间复杂度为 O (n)，B 正确。 2.选择排序算法的核心操作是（ ）​ A. 每次将最小元素放到已排序序列的末尾​ B. 每次将最大元素放到已排序序列的末尾​ C. 每次从未排序序列中选择最小元素与当前位置元素交换​ D. 每次从未排序序列中选择最大元素与当前位置元素交换 【答案】C 【解析】选择排序每次在未排序部分找到最小元素，与当前位置（从第一个位置开始，依次向后）元素交换，逐步完成排序。 3. 二分查找法要求数组必须是（ ）​ A. 无序的 B. 有序的 C. 可以无序也可以有序 D. 以上都不对 【答案】B 【解析】二分查找法的前提是数组必须有序，否则无法通过比较中间元素来缩小查找区间。 4. 在插入排序中，已排序部分的初始状态是（ ） A. 空 B. 包含数组的第一个元素 C. 包含数组的最后一个元素 D. 包含数组的中间元素 【答案】B 【解析】插入排序分为已排序与未排序两部分，已排序包含数组的第一个元素。 5.以下关于顺序查找算法的说法，错误的是（ ）​ A. 顺序查找算法适用于任何类型的数组，无论是否有序​ B. 顺序查找算法的时间复杂度始终为 O (n)​ C. 顺序查找算法从数组的第一个元素开始，逐个比较元素​ D. 顺序查找算法在找到目标元素后会立即返回 【答案】B 【解析】顺序查找算法在最好情况下，目标元素在数组第一个位置，时间复杂度为 O (1) ，平均和最坏情况下时间复杂度为 O (n) 。 6.对于一个已经基本有序的数组，使用哪种排序算法可以最快地完成排序（ ）​ A. 选择排序 B. 冒泡排序 C. 插入排序 D. 希尔排序 【答案】C 【解析】插入排序对于基本有序数组，时间复杂度接近 O (n)，效率较高。选择排序不受数组初始状态影响，时间复杂度始终为 O (n^2)；冒泡排序在基本有序时虽有优化空间，但总体效率不如插入排序；希尔排序是对插入排序的改进，对于基本有序数组优势不明显。 7. 顺序查找法的时间复杂度是（ ） A. O(n) B. O(log n) C. O(n²) D. O(1) 【答案】A 【解析】顺序查找法的时间复杂度是O(n)。 8. 在C#中，以下代码实现的排序算法是（ ） void Sort(int[] arr) {for (int i = 0; i < arr.Length - 1; i++) {int min = i; for (int j = i + 1; j < arr.Length; j++) { if (arr[j] < arr[min]) {min = j; } } int temp = arr[min]; arr[min] = arr[i]; arr[i] = temp;}} A. 冒泡排序 B. 插入排序 C. 选择排序 D. 快速排序 【答案】C 【解析】选择排序是每一次都要从待排序的元素中找到最小值（最大值）。 2、 判断题 1. 冒泡排序算法在每一轮比较中都会确定一个元素的最终位置。（ ） 【答案】正确。每一轮冒泡排序都会将未排序部分的最大（或最小，取决于排序顺序）元素交换到未排序部分的末尾（或开头），确定其最终位置。 2. 在 C# 中，选择排序是一种稳定的排序算法。（ ） 【答案】错误。选择排序在选择最小（或最大）元素与当前位置元素交换时，可能会改变相同元素的相对顺序，所以是不稳定的排序算法。 3. 顺序查找算法只能用于查找整数类型的数组。（ ） 【答案】错误。顺序查找算法适用于任何数据类型的数组，只要数组元素可比较即可。 4. 二分查找法的效率比顺序查找法高，因此在所有情况下都应该优先使用二分查找法。（ ） 【答案】错误。 5. 顺序查找法在查找失败时需要遍历整个数组。（ ） 【答案】正确。顺序查找法最坏的情况下需要遍历整个数组。 3、 填空题 1. 选择排序的基本思想是在未排序序列中找到________（或最大）元素，存放到排序序列的起始位置。 【答案】最小 2.插入排序将数组分为________和________两部分。 【答案】已排序部分、未排序部分 3.二分查找法中，每次查找时，查找区间的大小会变为原来的______。 【答案】一半 4.冒泡排序中，对于一个长度为 n 的数组，最多需要进行______轮比较。 【答案】n - 1 5.冒泡排序的基本思想是通过相邻元素的________和________，将较大的元素逐渐“冒泡”到数组的末尾。 【答案】比较、交换 四、程序填空题 1.冒泡排序代码如下，请补充完整： void BubbleSort(int[] arr) { for (int i = 0; i < _____________; i++) { for (int j = 0; j < ____________; j++) { if (arr[j] > arr[j + 1]) { _________________ arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } 【答案】arr.Length - 1 arr.Length - i - 1 int temp = arr[j]; 2.二分查找算法代码如下，请补充完整 int BinarySearch(int[] arr, int target) { int left = 0, right = arr.Length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return ________; else if (arr[mid] < target) left = ________; else right = ________; } return -1; } 【答案】mid mid + 1 mid - 1 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 $$