数据结构与算法第十三单元测试题(多选+判断).docx

数据结构与算法第十三单元测试题(多选+判断)1.快速排序的特性描述正确的是（）。多选 A.快速排序是稳定排序B.快速排序不稳定排序(正确答案)C.快速排序的时间复杂度是O(nlog2n)(正确答案)D.快速排序的时间复杂度是O(nn)2.冒泡排序是稳定的排序，原因是（）。单选 A.不存在不相邻的记录的交换(正确答案)B.存在不相邻的记录的交换C.晓得记录放在前面，大的记录放在后面D.以上答案都不对3.下列排序中是不稳定排序的是（）。 多选 A.希尔排序(正确答案)B.快速排序(正确答案)C.冒泡排序D.直接插入排序4.N个记录的待排序列，采用冒泡排序，总共比较次数可能是（）。 多选 A.N-2B.N-1(正确答案)C.N(N-1)/2(正确答案)D.N(N+1)/25.根据选项的描述，冒泡排序是（）。多选 A.内排序(正确答案)B.稳定排序(正确答案)C.交换排线(正确答案)D.插入排序6.关于冒泡排序的比较次数和排序趟数描述正确的是（）。多选 A.N个记录最多N-1趟排序即可完成(正确答案)B.N个记录最少比较N-1次，可完成排序，这是记录完全有序的情况(正确答案)C.N个记录最多比较N(N-1)/2次可完成排序，这是记录完全逆序的情况。(正确答案)D.在一趟排序中若无记录交换，就会停止排序。(正确答案)7.冒泡排序的时间复杂度最好情况和最坏情况分别是（）。多选 A.O(n)(正确答案)B.O(nn)(正确答案)C.O(1)D.O(log2n)8.冒泡排序的时间复杂度不是（）。多选 A.O(nn)B.O(n)(正确答案)C.O(1)(正确答案)D.O(log2n)(正确答案)9.递归算法需要有下列哪三项条件（）。多选 A.递归前进段(正确答案)B.递归返回段(正确答案)C.递归出口(正确答案)D.递归中间段10.递归的好处描述不正确的是（）。多选 A.只需少量的程序就可描述出解题过程所需要的多次重复计算B.需要大量的程序就可描述出解题过程所需要的多次重复计算(正确答案)C.大大地增加了程序的代码量(正确答案)D.大大地减少了程序的代码量11.下面那些功能可以用递归实现（）。 多选 A.n的阶乘(正确答案)B.1到n的和(正确答案)C.n的k次幂(正确答案)D.字符串逆序(正确答案)12.递归问题：青蛙过河，若要刚好过4只青蛙，则情况可以是（）。多选 A.没有石柱，荷叶有3片的情况(正确答案)B.石柱有1个，荷叶有1片的情况(正确答案)C.石柱有1个荷叶有2片的情况D.石柱有2个，荷叶有1片的情况13.冒泡排序是（）。多选 A.稳定排序(正确答案)B.内排序(正确答案)C.时间复杂度为O(nn)的排序(正确答案)D.交换排序(正确答案)14.以下算法时间复杂度是O(nn)的是（）。多选 A.冒泡排序(正确答案)B.直接插入排序(正确答案)C.折半查找D.希尔排序15.哪些算法的时间复杂度超过O(n)的（）。多选 A.冒泡排序(正确答案)B.直接插入排序(正确答案)C.折半查找D.希尔排序(正确答案)16.属于稳定排序的有（）。多选 A.冒泡排序(正确答案)B.直接插入排序(正确答案)C.希尔排序D.改进的冒泡排序(正确答案)17.不是插入排序的有（）。多选 A.直接插入排序B.希尔排序C.冒泡排序(正确答案)D.快速排序(正确答案)18.数据结构与算法里，#include "stdio.h"int fun(int i)if(i=1)return 1;else return ifun(i-1); void main()int n; n=fun(2); printf(""%d"",n);程序的输出结果不可能是（）。多选 A 2B 3(正确答案)C 1(正确答案)D 6(正确答案)19.递归的基本思想描述不正确的是（）。多选 A.把规模大的问题转换为规模小的相似的子问题B.把规模小的问题转换为规模大的问题(正确答案)C.把规模小的问题转换为规模大的相似的子问题(正确答案)D.把规模大的问题转换为规模小的不同类型问题(正确答案)20.一般来说，递归需要有下列哪三项条件（）。多选 A.递归返回段(正确答案)B.递归前进段(正确答案)C.递归出口(正确答案)D.递归中间段21.关于递归说法正确的是（）。多选 A.递归是函数自身调用编程技术(正确答案)B.有返回值的函数可以是递归的函数(正确答案)C.无返回值函数是不能使用递归的D.递归分为直接递归和间接递归(正确答案)22.属于交换排序的有（）。多选 A.快速排序(正确答案)B.冒泡排序(正确答案)C.直接插入排序D.希尔排序23.时间复杂度低于O(nn)的排序有（）。多选 A.快速排序(正确答案)B.冒泡排序C.直接插入排序D.希尔排序(正确答案)24.属于不稳定排序的是（）。多选 A.快速排序(正确答案)B.冒泡排序C.直接插入排序D.希尔排序(正确答案)25.属于内排序的包含（）。多选 A.快速排序(正确答案)B.冒泡排序(正确答案)C.直接插入排序(正确答案)D.希尔排序(正确答案)26.关于快速排序描述正确的是（）。多选 A.快速排序是不稳定排序(正确答案)B.快速排序的时间复杂度是O(nlog2n)。(正确答案)C.快速排序是一种交换排序(正确答案)D.快速排序是内排序的一种(正确答案)84.冒泡排序是交换排序的一种。 对(正确答案)错85.冒泡排序是一种插入排序。 对错(正确答案)86.冒泡排序需要比较不相邻元素之间的大小，以便交换。 对错(正确答案)87.把规模大的问题转换为规模小的相似问题，这是变量的思想。 对错(正确答案)88.把规模大的问题转换为规模小的相似问题，这是递归的思想。 对(正确答案)错89.n!的计算方式可以采用递归的方式进行。 对(正确答案)错90.递归程序经常使用栈帮助算法实现。 对(正确答案)错91.快速排序是不稳定排序。 对(正确答案)错92.快速排序的时间复杂度是O(nn)。 对错(正确答案)93.快速排序是稳定排序。 对错(正确答案)94.从排序的稳定性上讲，快速排序是稳定排序。 对错(正确答案)95.从排序的稳定性上讲，快速排序是不稳定排序。 对(正确答案)错96.N个记录采用冒泡排序，最好情况比较N-1次。 对(正确答案)错97.N个记录采用冒泡排序，最坏情况比较N(N-1)/2次。 对(正确答案)错98.青蛙过河问题，若没有石柱只有荷叶，那么可过的青蛙数量应比荷叶的数量多一个。 对(正确答案)错99.递归函数一般情况下一定会议递归出口，否则会无限的进行下去。 对(正确答案)错100.把规模小的问题转换为规模大的相似问题，这是递归的思想。 对错(正确答案)101.青蛙过河的计算方式可以采用递归的方式进行。 对(正确答案)错102.递归是函数自身嗲用自身，根据调用的方式分为直接递归和间接递归。 对(正确答案)错103.冒泡排序的时间复杂度是O(nn)。 对(正确答案)错104.冒泡排序是一种稳定排序。 对(正确答案)错105.冒泡排序是不稳定的排序。 对错(正确答案)106.冒泡排序在一趟排序中没有记录交换，则说明记录已经有序，停止排序。 对(正确答案)错107.冒泡排序N个记录需要N-1趟排序，就可以完成排序。 对(正确答案)错108.递归就是在过程或函数里调用自身。 对(正确答案)错109.递归调用时，是没有办法结束的，所以尽量少用递归。 对错(正确答案)110.递归是函数调用其它函数来完成操作。 对错(正确答案)111.递归是需要栈帮助解决问题的。 对(正确答案)错112.程序调用自身的编程技巧就是数组。 对错(正确答案)113.快速排序的时间复杂度是O(log2n)。 对错(正确答案)114.冒泡排序与快速排序都是插入排序。 对错(正确答案)115.交换排序和插入排序是没有什么区别的。 对错(正确答案)116.稳定排序是指排序前后不同关键字的记录相对位置不变。 对错(正确答案)117.快速排序在记录越杂乱无章的情况下，越能发挥其优势。 对(正确答案)错