数据结构与算法模拟题与答案.docx

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