数据结构与算法模拟题 (2).docx

数据结构与算法模拟题1. 二叉排序树的叶子结点个数为5个，则度为2的结点的数目是（）。 A、6B、5C、4(正确答案)D、32. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测（） 。 A、k-1次B、k次C、k+1次D、k(k+1)/2次(正确答案)3. 直接插入排序的时间复杂度和顺序查找的时间复杂度分别是（）。 A、O(n)和O(log2n)B、O(nn)和O(n)(正确答案)C、O(1)和)O(n)D、O(n)和O(1)4. 在排序中，对于关键字相等的记录，排序前后相对位置不变。这时称排序为（）。 A、稳定排序(正确答案)B、不稳定排序C、不确定是稳定排序还是不稳定排序D、基数排序5. 就性能而言，希尔排序的时间复杂度是（）。 A、O(nn)B、O(nlog2n)C、O(n)D、O(n3/2)(正确答案)6. 希尔排序又称为（）。 A、缩小增量排序(正确答案)B、二分插入排序C、多路归并排序D、锦标赛排序7. N个记录进行冒泡排序最多需要（）趟排序，可以完成排序。 A、N-1(正确答案)B、NC、N-2D、(N+1)/28. 30个记录进行冒泡排序，使用未改进的冒泡排序，则需要（）趟排序才能完成排序。 A、29(正确答案)B、30C、28D、279. 递归概念指的是（）。 A、程序调用自身的编程技巧(正确答案)B、特定功能的模块C、相同数据类型的有序的集合D、从小到大进行排列10. 青蛙过河案例中，如果河中没有石柱，有y片荷叶的话，那么从左岸到右岸可以过去（）只青蛙。 A、y+1只(正确答案)B、y+2只C、y+3只D、y+4只11. 一趟快速排序是将记录一分为（），返回中轴所在的位置。 A、二(正确答案)B、三C、四D、都不对12. 简单选择排序中，每一趟选择最小的记录的过程，则每一趟排序的时间复杂度是（）。 A、O(n)(正确答案)B、O(nn)C、O(1)D、O(nlog2n)13. N个记录，采用简单选择排序，每趟最多进行（）次交换。 A、1(正确答案)B、2C、N-2D、N-114. 从排序大类上讲，简单选择排序和冒泡排序是（）排序。 A、同一类B、不同类(正确答案)C、不确定D、都不对15. N个记录是有序的使用什么查找效率更高（）。 A、顺序查找B、折半查找(正确答案)C、分块查找D、随机查找16. 数据结构与算法中，在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。 A、希尔排序B、冒泡排序C、直接插入排序D、简单选择排序(正确答案)17. 采用快速排序进行排序，问题规模为n，则时间复杂度是（）。 A、O(n3/2)B、O(nn)C、O(n)D、O(nlog2n)(正确答案)18. 快速排序在（）情况下不利于发挥其长处或优势。 A、记录有相同的关键字时B、记录完全乱序时C、记录已经基本有序时(正确答案)D、记录的关键字较大时19. ACM算法的素数和计算中，sum变量用于累加素数之和，那么它的初值应赋值为（）。 A、0(正确答案)B、1C、100D、不赋初值20. 数据结构与算法中，素数的特点是（）。 A、只能被1和本身整除(正确答案)B、可以被2整除C、素数和完数是相同的概念D、素数就是合数21下列那个是直接递归形式函数（）。 A: void tell_stroy( ) tell_stroy(); (正确答案)B: void tell_stroy( ) void tell_stroy(); C: void tell_stroy( ) stroy(); D: void tell_stroy( ) tell(); 22冒泡排序最好的情况是，记录完全有序，20个记录待排序只需要比较（）次即可完成排序。 A: 20B: 19(正确答案)C: 18D: 19023.排序前序列为：34 15 88 66 72 问经过一趟直接插入排序(按从小到大排序)后的序列是（）。 A: 15 34 88 66 72(正确答案)B: 34 15 88 66 72C: 15 34 66 72 88D: 15 34 66 88 7224.装填因子又称为（）。 A: 负载因子(正确答案)B: 平衡因子C: 外力因子D: 合力因子25.以下属于哈希函数的构造方法的是（）。 A: 直接定址法(正确答案)B: 哈希再散列法C: 线性探测再散列法D: 二次探测再散列法26.数据结构与算法里，数据序列(2，1，4，9，8，10，6，20)只能是下列排序算法中的（）的两趟排序后的结果。 A.快速排序(正确答案)B.冒泡排序C.以上都不对D.直接插入27.数据结构与算法里，完数是完美数，它等于（）。 A.所有因子之和(正确答案)B只能被1和它本身整除C.是该范围内最大的质数D.所有小于它的数之和28.数据结构与算法里，完数N的因子(真因子)为a，b，c，则有（）。 A.N=a+b+c(正确答案)B.N-1=a+b+cC.N=a+b-cD.N=abc29. 关于希尔排序描述正确的是（）。 A、希尔排序是不稳定排序(正确答案)B、希尔排序是属于插入排序(正确答案)C、希尔排序的时间复杂度是O(n3/2)(正确答案)D、希尔排序又称为缩小增量排序(正确答案)30. 下列排序中是不稳定排序的是（）。 A、希尔排序(正确答案)B、快速排序(正确答案)C、直接插入排序D、冒泡排序31. 从排序大类上看，属于选择排序的是（）。 A、简单选择排序(正确答案)B、堆排序(正确答案)C、快速排序D、冒泡排序32. switch语句中，在()中的表达式类型可以是（）。 A、整型(正确答案)B、字符型(正确答案)C、字符串D、浮点型33. 6是完数，其因子包括（）。 A、1(正确答案)B、2(正确答案)C、3(正确答案)D、6(正确答案)33. 哈希表的平均查找长度与哪些（）因素有关。 A、处理冲突的方法(正确答案)B、哈希函数(正确答案)C、装填因子(正确答案)D、待存记录的大小34. 排序可以分为四大类，主要包含有（）。 A、插入排序(正确答案)B、交换排序"(正确答案)C、选择排序(正确答案)D、归并排序(正确答案)35. 排序是稳定排序或不稳排序的插入排序是（）。 A、希尔排序(正确答案)B、直接插入排序(正确答案)C、堆排序D、快速排序36关于冒泡排序的比较次数和排序趟数描述正确的是（）。 A: N个记录最多N-1趟排序即可完成(正确答案)B: N个记录最少比较N-1次，可完成排序，这是记录完全有序的情况(正确答案)C: N个记录最多比较N(N-1)/2次可完成排序，这是记录完全逆序的情况。(正确答案)D: 在一趟排序中若无记录交换，就会停止排序。(正确答案)37关于快速排序描述不正确的是（）。 A: 快速排序是稳定排序(正确答案)B: 快速排序的时间复杂度是O(nlog2n)C: 快速排序不存在不相邻的记录之间的交换(正确答案)D: 快速排序的时间复杂度是O(nn)(正确答案)38下列排序中是稳定排序的是（）。 A: 希尔排序B: 快速排序C: 直接插入排序(正确答案)D: 冒泡排序(正确答案)39动态查找表：边查找，边改变集合中的元素，改变的方式可以是（）。 A: 增加(正确答案)B: 删除(正确答案)C: 交换D: 移动40.数据结构与算法里，关于哈希表的装填因子，以下正确的有（）。 A: 装填因子的值越小，发生冲突的概率越小(正确答案)B: 装填因子越大，表中填入的记录越多，在填入的时候发生冲突的可能性就越大，在进行查找时候，查找的次数也就越多。(正确答案)C: 装填因子=表中填入的记录数/哈希表的总长度(正确答案)D: 装填因子的值越小，就可以避免冲突的发生41数据结构与算法里，设哈希表长度为11,哈希函数H(K)=(K的第一个字母在字母表中的序号)MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),采用内散列表,处理冲突方法为线性探测法,要求构造哈希表,在等概率情况下查找成功平均查找长度错误的是()。 A: 4(正确答案)B: 3(正确答案)C: 20/9D: 23/9(正确答案)42关于二叉排序树描述有误的是（）。 A: 二叉排序的右子树上结点的关键字小于左子树上的结点的关键字(正确答案)B: 二叉排序的左子树上结点的关键字小于右子树上的结点的关键字C: 二叉排序的根节点的关键大于右子树上结点的关键字(正确答案)D: 二叉排序的根节点的关键大于左子树上结点的关键字43下列关于查找表描述正确的是（）。 A: 查找表分为静态查找表和动态查找表(正确答案)B: 动态查找表边查找，边改变集合内的元素(正确答案)C: 静态查找表只查找不改变集合中的元素(正确答案)D: 其它选项说法都正确(正确答案)44.数据结构与算法里，直接插入排序最好、最坏两种情况的时间复杂度分别是（）。 A.O(nlog2n)B.O(n)(正确答案)C.O(log2n)D.O(nn)(正确答案)45. 二叉树的先序遍历和中序遍历如下：先序遍历:EFHIGJK；中序遍历：HFIEJKG该二叉树根的右子树的根不可能是:()。 占位符不用管A、E(正确答案)B、F(正确答案)C、GD、H(正确答案)46. 装填因子的计算方法是（）。 A、1-(表中未填入记录的数目/哈希表的总长度)(正确答案)B、表中未填入记录的数目/哈希表的总长度C、 (表中未填入的记录数-1)/哈希表的总长度D、表中填入的记录数/哈希表的总长(正确答案)47.数据结构与算法里，关于希尔排序描述正确的是（）。 A.希尔排序是不稳定排序(正确答案)B.希尔排序是属于插入排序(正确答案)C.希尔排序的时间复杂度是O(n3/2)(正确答案)D.希尔排序又称为缩小增量排序(正确答案)48.数据结构与算法里，以下算法时间复杂度是O(nn)的是（）。 A.冒泡排序(正确答案)B.直接插入排序(正确答案)C.折半查找D.希尔排序49.数据结构与算法里，关于快速排序描述正确的是（）。 A.快速排序是不稳定排序(正确答案)B.快速排序的时间复杂度是O(nlog2n)。(正确答案)C.快速排序是一种交换排序(正确答案)D.快速排序是内排序的一种(正确答案)50.数据结构与算法里，关于二叉排序树相关描述正确的是（）。 A.二叉排序树是应用于动态查找的结构(正确答案)B.二叉排序树的中序列是升序序列(正确答案)C.二叉排序树的左子树也是二叉排序树(正确答案)D.二叉排序树的定义具有递归性(正确答案)51. 数组在内存中是连续存放的，不会被间隔开。 对(正确答案)错52. 数据结构与算法里，研究完数最早的是中国的九章算术。 对错(正确答案)53. 数据结构与算法里，完数N的所有因子为x，y，z，则必有N等于x+y+z。 对(正确答案)错54从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为冒泡排序。 对错(正确答案)55简单选择排序的稳定性与快速排序的稳定性不一样。 对错(正确答案)56动态查找表属于树形结构，因为这里涉及二叉排序树。 对错(正确答案)57哈希函数是一个映像。 对(正确答案)错58数据结构与算法里，对不同的关键字可能得到同一哈希地址，即keykey2面f(key1)=f(key2)这种现象称冲突(collision)。具有相同函数值的关键词对该哈希函数来说称作同义词。 对(正确答案)错59. 二叉排序树的充要条件：二叉排序树的任意结点的关键字都大于其左孩子的关键字，且小于其右孩子的关键字。 对错(正确答案)60. 若哈希表的装填因子<1，则可避免冲突的产生。 对错(正确答案)