5.3 运用典型算法-（练习）-《信息技术基础模块下册》（高教版）同步精品课堂

5.3：运用典型算法 一、选择题 1.选择排序的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 答案：B.O(n^2) 解析：选择排序每次需要遍历数组找到最小元素，然后进行交换，因此需要进行n-1轮遍历，每轮遍历需要进行n-i次比较，所以时间复杂度为O(n^2)。 2.插入排序的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 答案：B.O(n^2)  解析：插入排序每次需要将一个新元素插入到已排序序列中的合适位置，因此需要进行n-1轮遍历，每轮遍历需要进行n-i次比较，所以时间复杂度为O(n^2)。 3.冒泡排序的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 答案：B.O(n^2)  解析：冒泡排序通过两两相邻元素的交换，将最大（或最小）元素逐渐“冒泡”到数组的末尾，需要进行n-1轮遍历，每轮遍历需要进行n-i次比较，所以时间复杂度为O(n^2)。 4.堆排序的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 答案：D.O(n log n)  解析：堆排序利用堆这种数据结构进行排序，建立堆的时间复杂度为O(n)，每次调整堆的时间复杂度为O(log n)，需要进行n-1次调整，所以总的时间复杂度为O(n log n)。 5.归并排序的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 答案：D.O(n log n)  解析：归并排序利用递归将数组划分成多个子数组，然后两两归并，每次归并的时间复杂度为O(n)，需要进行log n次归并，所以总的时间复杂度为O(n log n)。 6.顺序查找的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 答案：A.O(n)   解析：顺序查找需要从数组的头部开始，逐个比较直到找到目标元素，如果目标元素在数组的最后一个位置，则需要比较n次，所以最坏情况下时间复杂度为O(n)。 7.二分查找的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 答案：C.O(log n)  解析：二分查找需要数组有序，每次从中间元素开始比较，并根据比较结果继续在左侧或右侧数组中查找，每次查找都可以将查找范围缩小一半，所以时间复杂度为O(log n)。 8.在Python中创建列表可以使用（ ） A. 方括号 B. 圆括号 C. 花括号 D. 都可以 答案：A.方括号  解析：在Python中创建列表可以使用方括号[]，例如：a = [1, 2, 3]。 9在Python中，删除列表中的元素可以使用（ ）  A. remove方法 B. pop方法 C. del语句 D. 以上都可以 答案：D.以上都可以  解析：在Python中，删除列表中的元素可以使用remove方法、pop方法或del语句。 10递归算法的核心思想是（ ）  A. 循环 B. 调用自身 C. 调用其他函数 D. 以上都不对 答案：B.调用自身  解析：递归算法的核心思想是函数调用自身，通过递归调用，可以将问题分解为规模更小的同类问题，从而实现算法的简化。 二、问答题：  请简述冒泡排序算法的基本原理。 冒泡排序算法的基本原理是通过多次遍历待排序的列表，每次遍历都两两比较相邻的元素，并在必要时进行交换，将较大的元素逐渐“冒泡”到数组的末尾，经过n-1轮遍历后，数组中的元素就完成了从小到大的排序。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 $$ 5.3：运用典型算法 一、选择题 1.选择排序的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 2.插入排序的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 3.冒泡排序的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 4.堆排序的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 5.归并排序的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 6.顺序查找的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 7.二分查找的时间复杂度是（ ）  A. O(n) B. O(n^2) C. O(log n) D. O(n log n) 8.在Python中创建列表可以使用（ ） A. 方括号 B. 圆括号 C. 花括号 D. 都可以 9在Python中，删除列表中的元素可以使用（ ）  A. remove方法 B. pop方法 C. del语句 D. 以上都可以 10递归算法的核心思想是（ ）  A. 循环 B. 调用自身 C. 调用其他函数 D. 以上都不对 二、问答题：  请简述冒泡排序算法的基本原理。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 $$