安阳工学院软件工程专业大二2017-2018数据结构与算法第十三单元测试

1、安阳工学院软件工程专业大二2017-2018数据结构与算法第十三单元测试您的姓名： 填空题 *_1.冒泡排序的每一趟的过程是要比较()元素，如果逆序进行交换（）。 单选题 *A 相邻(正确答案)B 都不对C 不相邻D 首尾2.冒泡排序要使用()语句判断两个相邻元素是否是逆序（）。 单选题 *A forB do-whileC whileD if(正确答案)3.如果待排序序列是完全有序的，使用改进的冒泡排序，只需要()趟排序（）。 单选题 *A 三B 四C 一(正确答案)D 二4.以下序列，采用优化的冒泡排序从小到大排序，排序比较次数最少的是（）。 单选题 *A 34,9,23,87,52,11B

2、 23,98,17,33,71,2C 12,23,87,33,38,46(正确答案)D 91,23,67,19,61,995.冒泡排序要使用()语句来完成排序（）。 单选题 *A for(正确答案)B do-whileC whileD if6.N个记录使用优化的冒泡排序最少需要()趟排序，可以完成排序（）。 单选题 *A 1(正确答案)B N-1C ND N-27.若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行()次比较（）。 单选题 *A 3B 10C 15(正确答案)D 258.下列选项中说法正确的是（）。 单选题 *A 冒泡排序是使用循环嵌套来完成算法的(正

3、确答案)B 冒泡排序是使用单层循环来完成算法的C 无正确答案D 冒泡排序是使用三重循环来完成算法的9.8个元素23,9,12,7,87,11,62,33采用优化的冒泡排序需要排序()趟（）。 单选题 *A 3B 4(正确答案)C 5D 610.6个元素2,7,98,12,44,56采用优化的冒泡排序，总共需要比较()次（）。 单选题 *A 1B 5C 9(正确答案)D 1511.关于递归算法，以下说法错误的是（）。 单选题 *A 递归必须有结束条件B 递归次数太多会导致内存溢出C 递归就是指在一个方法的内部调用自身的过程D 递归可以调用无数次，只要有结束条件就可以。(正确答案)12.冒泡排序要

4、使用()语句判断两个相邻元素是否是逆序（）。 单选题 *A forB do-whileC whileD if(正确答案)13.N个记录使用优化的冒泡排序最少需要()趟排序，可以完成排序（）。 单选题 *A 1(正确答案)B N-1C ND N-214.斐波那契数列数列的第6项值是（）。 单选题 *A 5B 8(正确答案)C 13D 2115.青蛙跳河问题中，假设有3个石柱，5个荷叶，则问最多可以跳过去()只青蛙（）。 单选题 *A 24B 40C 48(正确答案)D 6216.青蛙跳河问题中，假设有1个石柱，1个荷叶，则问最多可以跳过去()只青蛙（）。 单选题 *A 2B 3C 4(正确答案)

5、D 517.6!= （）。 单选题 *A 240B 360C 480D 720(正确答案)18.青蛙跳河问题中，假设有5个石柱，0个荷叶，则问最多可以跳过去()只青蛙（）。 单选题 *A 30B 31C 32(正确答案)D 3319.以下哪个数列可以使用递归完成算法（）。 单选题 *A 1 1 3 3 7 2 9 8B 1 3 5 6 8 21 32C 1 1 4 10 28 76(正确答案)D 1 2 8 32 77 9120.汉诺塔中，有3个盘子，需要移动()步（）。 单选题 *A 3B 5C 7(正确答案)D 921.某些排序存在不相邻记录之间的交换，因此是不稳定排序，以下是不稳定的排序

6、是（）。 单选题 *A.快速排序(正确答案)B.冒泡排序C.直接插入排序D.都不对22.一趟快速排序是选择一个中轴，将小于中轴位置记录的调到它的左边，大于的调到它的（）。 单选题 *A.右边(正确答案)B.左边C.两边D.都不对23.快速排序可以优化，优化的点就是选取更加合适的（）。 单选题 *A.中轴(正确答案)B.位置C.大小D.都不对24.从排序的大类上看，快速排序与冒泡排序是()排序（）。 单选题 *A.同一类(正确答案)B.不同类C.不确定D.都不对25.从算法的时间复杂度来看，O(nlog2n)是哪种排序的时间复杂度（）。 单选题 *A.快速排序(正确答案)B.直接插入排序C.简单

7、选择排序D.冒泡排序26.一趟快速排序最后要返回（）。 单选题 *A.中轴所在的位置(正确答案)B.最大元素C.最小元素D.都不对27.快速排序过程中存在()记录之间的交换，所以是不稳定排序（）。 单选题 *A.不相邻(正确答案)B.相邻C.不确定D.都不对28.快速排序与冒泡排序是()排序（）。 单选题 *A.同一类(正确答案)B.不同类C.不确定D.都不对29.快速排序和直接插入的排序的时间复杂是()的。（） 单选题 *A.不一样(正确答案)B.一样C.不确定D.都不对30.一趟快速排序是将记录一分为()，返回中轴所在的位置（）。 单选题 *A.二(正确答案)B.三C.四D.都不对31.快

8、速排序属于（）。 单选题 *A.插入排序B.选择排序C.交换排序(正确答案)D.归并排序32.快速排序的时间复杂度是（）。 单选题 *A.O(n*n)B.O(nlog2n)(正确答案)C.O(1)D.都不对33.快速排序是（）。 单选题 *A.不稳定排序(正确答案)B.稳定排序C.不确定D.都不对34.冒泡排序和()都属于交换排序（）。 单选题 *A.快速排序(正确答案)B.直接插入排序C.简单选择排序D.都不对35.O(nlog2n)是哪种排序的时间复杂度（）。 单选题 *A.快速排序(正确答案)B.直接插入排序C.简单选择排序D.冒泡排序36.写快速排序可以用()方式实现（）。 单选题 *

9、A.插入B.递归(正确答案)C.选择D.都不对37.从时间复杂度的角度来看，快速排序的时间复杂度是（）。 单选题 *A.O(n*n)B.O(nlog2n)(正确答案)C.O(1)D.都不对38.从排序的稳定性来看，快速排序是（）。 单选题 *A.不稳定排序(正确答案)B.稳定排序C.不确定D.都不对39.快速排序在()情况下，不利于发挥其长处（）。 单选题 *A.完全乱序B.基本有序(正确答案)C.倒序排放D.都不对40.快速排序是()的一种（）。 单选题 *A.插入排序B.选择排序C.交换排序(正确答案)D.归并排序41.快速排序的第一趟排序可以确定()个记录的最终位置（）。 单选题 *A.

10、3B.2C.1(正确答案)D.442.一趟()最后要返回中轴所在的位置，然后将小的移动到它的左边，将大的移动到它的右边（）。 单选题 *A.快速排序(正确答案)B.直接插入排序C.冒泡排序D.都不对43.O(n*n)是以下哪种算法的复杂度（）。 *A 直接插入排序(正确答案)B 顺序查找C 冒泡排序(正确答案)D 折半查找44.以下是稳定排序的排序有（）。 *A 直接插入排序(正确答案)B 希尔排序C 冒泡排序(正确答案)D 优化的冒泡排序(正确答案)45.排序分为哪些大类（）。 *A 插入排序(正确答案)B 选择排序(正确答案)C 交换排序(正确答案)D 归并排序(正确答案)46. ()和(

11、)都属于交换排序（）。 *A 简单选择排序B 冒泡排序(正确答案)C 快速排序(正确答案)D 直接插入排序47.以下待排序列从大到小排序，排序趟数相同的是（）。 *A 23,11,45,78,91,100(正确答案)B 23,98,12,8,99,19C 1,2,3,4,5,6(正确答案)D 11,27,33,29,86,99(正确答案)48.冒泡排序属于（）。 *A.稳定排序(正确答案)B.不稳定排序C.插入排序D.交换排序(正确答案)49.以下选项可以作为次关键字的（）。 *A 学号B 姓名(正确答案)C 成绩(正确答案)D 性别(正确答案)50.以下排序，时间复杂度相同的（）。 *A 直

12、接插入排序(正确答案)B 希尔排序C 冒泡排序(正确答案)D 优化的冒泡排序(正确答案)51.以下排序算法，比较次数与待排序列初始化有关的（）。 *A 直接插入排序(正确答案)B 希尔排序(正确答案)C 冒泡排序D 优化的冒泡排序(正确答案)52.以下属于交换排序类的排序（）。 *A 冒泡排序(正确答案)B 直接插入排序C 快速排序(正确答案)D 希尔排序53.O(n*n)是以下哪种算法的复杂度（）。 *A 直接插入排序(正确答案)B 顺序查找C 冒泡排序(正确答案)D 折半查找54.以下是稳定排序的排序有（）。 *A 直接插入排序(正确答案)B 希尔排序C 冒泡排序(正确答案)D 优化的冒泡

13、排序(正确答案)55.排序分为哪些大类（）。 *A 插入排序(正确答案)B 选择排序(正确答案)C 交换排序(正确答案)D 归并排序(正确答案)56.冒泡排序属于（）。 *A.稳定排序(正确答案)B.不稳定排序C.插入排序D.交换排序(正确答案)57.以下使用递归可以实现的（）。 *A.n！(正确答案)B.青蛙跳河(正确答案)C.斐波那契数列(正确答案)D.汉诺塔(正确答案)58.青蛙跳河游戏中，假设有2个荷叶，2个石柱，可以跳过去的青蛙的数量可以是（）。 *A.8(正确答案)B.10(正确答案)C.12(正确答案)D.1459.以下应用使用递归的（）。 *A.八皇后问题(正确答案)B.背包问

14、题(正确答案)C.荷兰国旗(正确答案)D.迷宫问题(正确答案)60.属于交换排序的有（）。 *A: 冒泡排序(正确答案)B: 快速排序(正确答案)C: 希尔排序D: 直接插入排序61.冒泡排序按照各种分类可以是（）。 *A: 稳定排序(正确答案)B: 交换排序(正确答案)C: 内排序(正确答案)D: 以上答案都正确(正确答案)62.30个记录的序列进行冒泡排序，则有可能（）。 *A: 29次比较就完成排序(正确答案)B: 进行29趟排序才结束排序(正确答案)C: 不能完成排序D: 可能10趟就结束了排序。(正确答案)63.( )和( )都属于交换排序（）。 *A.快速排序(正确答案)B.直接插

15、入排序C.简单选择排序D.冒泡排序(正确答案)64.下列排序中是稳定排序的是（）。 *A.希尔排序B.快速排序C.直接插入排序(正确答案)D.冒泡排序(正确答案)65.快速排序的特性描述正确的是（）。 *A.快速排序是稳定排序B.快速排序不稳定排序(正确答案)C.快速排序的时间复杂度是O(nlog2n)(正确答案)D.快速排序的时间复杂度是O(n*n)66.关于快速排序描述不正确的是（）。 *A.快速排序是稳定排序(正确答案)B.快速排序的时间复杂度是O(nlog2n)C.快速排序不存在不相邻的记录之间的交换(正确答案)D.快速排序的时间复杂度是O(n*n)(正确答案)67.以下的排序是内排序

16、的是（）。 *A.希尔排序(正确答案)B.快速排序(正确答案)C.希尔排序(正确答案)D.快速排序(正确答案)68.下列排序中是不稳定排序的是（）。 *A.希尔排序(正确答案)B.快速排序(正确答案)C.希尔排序(正确答案)D.快速排序(正确答案)69.稳定排序是排序前后不同关键字的记录相对位置不变。 判断题 *对错(正确答案)70.优化的冒泡排序的时间复杂度和数组的初始排序有关。 判断题 *对(正确答案)错71.冒泡排序的时间复杂度是O(n*n)，而直接插入排序的时间复杂度是O(n)。 判断题 *对错(正确答案)72.冒泡排序在一趟排序中没有记录交换，则说明记录已经有序，停止排序。 判断题

17、*对(正确答案)错73.冒泡排序需要比较不相邻元素之间的大小，以便交换。 判断题 *对错(正确答案)74.冒泡排序是不稳定的排序。 判断题 *对错(正确答案)75.冒泡排序优化算法中需要使用一个标识变量，来判断一趟排序中是否有数据发生交换。 判断题 *对(正确答案)错76.对于一组待排序列是升序序列的元素，排序成从小到大的序列，则排序的趟数为0。 判断题 *对错(正确答案)77.稳定排序是排序前后相同关键字的记录相对位置变化。 判断题 *对错(正确答案)78.稳定排序是排序前后不同关键字的记录相对位置不变。 判断题 *对错(正确答案)79.递归的基本思想是把规模小的问题转化为规模大的相似的子问

18、题来解决。(错) 单选题 *80.以(50,30,40,15,70,60,90)关键字进行动态查找，生成二叉排序树，则二叉排序树的右子树的根结点是 90。(错)(正确答案)81.哈希表的装填因子的值在0-1之间。 判断题 *对(正确答案)错82.直接插入排序有40个记录，其最坏情况比较39次。 判断题 *对错(正确答案)83.希尔排序是缩小增量排序，增量序列对时间复杂度是无影响的。 判断题 *对错(正确答案)84.若哈希表的装填因子<1，则可避免冲突的产生。 判断题 *对错(正确答案)85.折半查找的速度总是比顺序查找要快，因为折半查找的时间复杂度低，是对数级的。 判断题 *对错(正确答案)86.哈希表的装填因子越大越好，这样能尽可能小的发生冲突。 判断题 *对错(正确答案)87.快速排序在记录已经基本有序时，不利于发挥其优势。 判断题 *对(正确答案)错88.稳定排序是指排序前后相同关键字的记录相对位置不变。 判断题 *对(正确答案)错89.冒泡排序与快速排序都是交换排序。 判断题 *对(正确答案)错90.交换排序是通过记录之间的交换达到排序的目的。 判断题 *对(正确答案)错91.快速排序的时间复杂度是O(nlog2n)。 判断题 *对(正确答案)错92.快速排序是不稳定排序。 判断题 *对(正确答案)错