《数据结构与算法模拟试题 (3).docx》由会员分享,可在线阅读,更多相关《数据结构与算法模拟试题 (3).docx(19页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构与算法模拟试题1.以下属于哈希函数的构造方法的是()。 A: 直接定址法(正确答案)B: 哈希再散列法C: 线性探测再散列法D: 二次探测再散列法2.下列关于二叉排序树中说法正确的是()。 A: 二叉排序树的定义具有反复性B: 二叉排序树的定义具有递归性(正确答案)C: 二叉排序树的定义具有回溯性D: 二叉排序树的定义具有反弹性3.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?()。 A: k-1次B: k次C: k+1次D: k(k+1)/2次(正确答案)4.哈希表的查找是依靠()来计算出元素的存储地址的。 A: 哈希函数(正确答案)B:
2、 逐一比对C: 折半比较D: 集合5.在各种查找方法中,平均查找长度ASL与结点个数n无关的查找方法是()。 A: 顺序查找B: 折半查找C: 哈希查找(正确答案)D: 分块查找6.装填因子又称为()。 A: 负载因子(正确答案)B: 平衡因子C: 外力因子D: 合力因子7.先序遍历一颗二叉排序树的顺序是()。 A: 左子树 根结点 右子树B: 根结点 左子树 右子树(正确答案)C: 左子树 右子树 根结点D: 都不对8.关于二叉排序树的遍历顺序说法正确的是()。 A: 中序遍历一颗二叉排序树的顺序是:左子树 根结点 右子树(正确答案)B: 中序遍历一颗二叉排序树的顺序是:根结点 左子树 右子
3、树C: 中序遍历一颗二叉排序树的顺序是:左子树 右子树 根结点D: 无正确答案9.关于二叉排序树的结点个数为0时称为什么描述正确的是()。 A: 二叉排序树可以含有0个结点,这时它是一棵空二叉排序树(正确答案)B: 二叉排序树可以含有0个结点,这时它是一棵满二叉排序树C: 二叉排序树可以含有0个结点,这时它是一棵完全二叉排序树D: 无正确答案10.关于二叉排序树的作用描述正确的是()。 A: 二叉排序树是应用于静态查找的结构B: 二叉排序树是应用于动态查找的结构(正确答案)C: 二叉排序树是应用于随机查找的结构D: 无正确答案11.动态查找表:边查找,边改变集合中的元素,改变的方式可以是()。
4、 A: 增加(正确答案)B: 删除(正确答案)C: 交换D: 移动12.数据结构与算法里,关于哈希表的装填因子,以下正确的有()。 A: 装填因子的值越小,发生冲突的概率越小(正确答案)B: 装填因子越大,表中填入的记录越多,在填入的时候发生冲突的可能性就越大,在进行查找时候,查找的次数也就越多。(正确答案)C: 装填因子=表中填入的记录数/哈希表的总长度(正确答案)D: 装填因子的值越小,就可以避免冲突的发生13. 数据结构与算法里,设哈希表长度为11,哈希函数H(K)=(K的第一个字母在字母表中的序号)MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),采用内散列表,处
5、理冲突方法为线性探测法,要求构造哈希表,在等概率情况下查找成功平均查找长度错误的是()。 A: 4(正确答案)B: 3(正确答案)C: 20/9D: 23/9(正确答案)14.关于二叉排序树描述有误的是()。 A: 二叉排序的右子树上结点的关键字小于左子树上的结点的关键字(正确答案)B: 二叉排序的左子树上结点的关键字小于右子树上的结点的关键字C: 二叉排序的根节点的关键大于右子树上结点的关键字(正确答案)D: 二叉排序的根节点的关键大于左子树上结点的关键字15.下列关于查找表描述正确的是()。 A: 查找表分为静态查找表和动态查找表(正确答案)B: 动态查找表边查找,边改变集合内的元素(正确
6、答案)C: 静态查找表只查找不改变集合中的元素(正确答案)D: 其它选项说法都正确(正确答案)16.装填因子是哈希表的一个重要参数,它反映哈希表的装满程度。 对(正确答案)错17.动态查找表属于树形结构,因为这里涉及二叉排序树。 对错(正确答案)18如果哈希表的长度足够大,就可以避免发生冲突。 对错(正确答案)19.二叉排序树的右子树也应该一定是棵二叉排序树。 对(正确答案)错20.哈希函数是一个映像。 对(正确答案)错1.哪种排序可能发生:在最后一趟排序开始之前,所有记录均不在其最终位置上()。 A: 直接插入排序(正确答案)B: 简单选择排序C: 冒泡排序D: 快速排序2.直接插入排序的稳
7、定性和希尔排序的稳定性是()。 A: 一样的B: 不一样(正确答案)C: 可能一样也可能不一样D: 不确定3.数组中有25个元素,若使用直接插入排序对其进行排序,则需要()趟才能完成排序。 A: 24(正确答案)B: 25C: 26D: 234.直接插入排序的时间复杂度和折半查找的时间复杂度分别是()。 A: O(nn)和O(log2n)(正确答案)B: O(nn)和O(n)C: O(1)和)O(n)D: O(n)和O(1)5.就性能而言,希尔排序的时间复杂度是()。 A: O(nn)B: O(nlog2n)C: O(n)D: O(n3/2)(正确答案)6.排序前序列为:34 15 88 66
8、 72 问经过一趟直接插入排序(按从小到大排序)后的序列是()。 A: 15 34 88 66 72(正确答案)B: 34 15 88 66 72C: 15 34 66 72 88D: 15 34 66 88 727.排序前序列为:11 10 13 8 9 问经过一趟直接插入排序(按从小到大排序)后的序列是()。 A: 10 11 13 8 9(正确答案)B: 10 11 8 9 13C: 11 10 8 9 13D: 8 9 10 11 138.直接插入排序的时间复杂度和顺序查找的时间复杂度分别是()。 A: O(n)和O(log2n)B: O(nn)和O(n)(正确答案)C: O(1)和)
9、O(n)D: O(n)和O(1)9.直接插入排序的稳定性和时间复杂度分别是()。 A: 稳定排序且时间复杂度是O(nn)(正确答案)B: 不稳定排序且时间复杂度是O(n)C: 稳定排序且时间复杂度是O(log2n)D: 不稳定排序且时间复杂度是O(log2n)10.下列选项关于直接插入排序比较次数说法正确的是()。 A: N个记录采用直接插入排序的最好的情况是记录倒序只要比较N-1次,不需要插入就可以排序完成B: N个记录采用直接插入排序的最好的情况是记录有序只要比较N-1次,不需要插入就可以排序完成(正确答案)C: N个记录采用直接插入排序的最好的情况是记录乱序只要比较N-1次,不需要插入就
10、可以排序完成D: N个记录采用直接插入排序的最好的情况是记录顺序只要比较N-1次,不需要插入就可以排序完成11.下列排序中属于插入排序的有()。 A: 希尔排序(正确答案)B: 直接插入排序(正确答案)C: 快速排序D: 简单选择排序12.按照待排记录是否全部在内存中,排序可分为()。 A: 内排序(正确答案)B: 外排序(正确答案)C: 稳定排序D: 不稳定排序13.属于插入排序的有()。 A: 希尔排序(正确答案)B: 直接插入排序(正确答案)C: 冒泡排序D: 简单选择排序14.排序是稳定排序或不稳排序的插入排序是()。 A: 希尔排序(正确答案)B: 直接插入排序(正确答案)C: 堆排
11、序D: 快速排序15.排序可以分为四大类,主要包含有()。 A: 插入排序(正确答案)B: 交换排序(正确答案)C: 选择排序(正确答案)D: 归并排序(正确答案)16.希尔排序是不稳定排序是因为存在不相邻的元素之间的交换。 对(正确答案)错17.就排序稳定性而言,希尔排序是不稳定排序,且时间复杂度是O(n3/2)。 对(正确答案)错18.在直接插入排序中可以使用for循环来完成。 对(正确答案)错19.希尔排序的时间复杂度是O(nn)。 对错(正确答案)20.直接插入排序必须需要使用switch语句才能实现。 对错(正确答案)1.快速排序是()。 A: 不稳定排序(正确答案)B: 稳定排序C
12、: 不确定D: 都不对2.下列那个是直接递归形式函数()。 A: void tell_stroy( ) tell_stroy(); (正确答案)B: void tell_stroy( ) void tell_stroy(); C: void tell_stroy( ) stroy(); D: void tell_stroy( ) tell(); 3.从时间复杂度的角度来看,快速排序的时间复杂度是()。 A: O(nn)B: O(nlog2n)(正确答案)C: O(1)D: 都不对4.冒泡排序的每一趟的过程是要比较()元素,如果逆序进行交换。 A: 相邻(正确答案)B: 不相邻C: 首尾D: 都
13、不对5.快速排序在()情况下,不利于发挥其长处。 A: 完全乱序B: 基本有序(正确答案)C: 杂乱无章D: 都不对6.冒泡排序核心思想是()。 A: 比较不相邻记录,如果逆序则交换B: 比较相邻记录,如果逆序则交换(正确答案)C: 随机比较两个记录,如果逆序则交换D: 都不对7.快速排序是()的一种。 A: 插入排序B: 选择排序C: 交换排序(正确答案)D: 归并排序8.冒泡排序的时间复杂度()。 A: O(n)B: O(nn)(正确答案)C: O(1)D: 都不对9.数据结构与算法里,冒泡排序需要使用()来完成排序。 A: 单层循环B: 循环嵌套(正确答案)C: 多分支结构D: 都不对1
14、0.冒泡排序最好的情况是,记录完全有序,20个记录待排序只需要比较()次即可完成排序。 A: 20B: 19(正确答案)C: 18D: 19011.关于冒泡排序的比较次数和排序趟数描述正确的是()。 A: N个记录最多N-1趟排序即可完成(正确答案)B: N个记录最少比较N-1次,可完成排序,这是记录完全有序的情况(正确答案)C: N个记录最多比较N(N-1)/2次可完成排序,这是记录完全逆序的情况。(正确答案)D: 在一趟排序中若无记录交换,就会停止排序。(正确答案)12.以下的排序是内排序的是()。 A: 希尔排序(正确答案)B: 快速排序(正确答案)C: 希尔排序(正确答案)D: 快速排
15、序(正确答案)13.关于快速排序描述不正确的是()。 A: 快速排序是稳定排序(正确答案)B: 快速排序的时间复杂度是O(nlog2n)C: 快速排序不存在不相邻的记录之间的交换(正确答案)D: 快速排序的时间复杂度是O(nn)(正确答案)14.下列排序中是稳定排序的是()。 A: 希尔排序B: 快速排序C: 直接插入排序(正确答案)D: 冒泡排序(正确答案)15.冒泡排序是()。 A: 稳定排序(正确答案)B: 内排序(正确答案)C: 时间复杂度为O(nn)的排序(正确答案)D: 交换排序(正确答案)16.把规模小的问题转换为规模大的相似问题,这是递归的思想。 对错(正确答案)17.从排序的
16、稳定性上讲,快速排序是不稳定排序。 对(正确答案)错18.从排序的稳定性上讲,快速排序是稳定排序。 对错(正确答案)19.递归就是在过程或函数里调用自身。 对(正确答案)错20. 快速排序是不稳定排序。 对(正确答案)错1.假设从小到大排序,简单选择排序的第一趟排序是要选择()的记录放在第一个位置。 A: 不确定B: 最大C: 最小(正确答案)D: 都不对2.时间复杂度是O(nn)的算法是()。 A: 简单选择排序(正确答案)B: 顺序查找C: 折半查找D: 快速排序3.选择最小的记录放在第一个位置,在剩余记录中选择最小的放在第二个位置,以此类推。是()的思想。 A: 简单选择排序(正确答案)
17、B: 快速排序C: 冒泡排序D: 直接插入排序4.简单选择排序和冒泡排序是()排序。 A: 同一类B: 不同类(正确答案)C: 不确定D: 都不对5.简单选择排序,每趟最多进行()次交换。 A: 1(正确答案)B: 2C: 3D: 46.简单选择排序的时间复杂度是()。 A: O(nn)(正确答案)B: O(nlog2n)C: O(1)D: 都不对7.从排序大类上讲,简单选择排序和冒泡排序是()排序。 A: 同一类B: 不同类(正确答案)C: 不确定D: 都不对8.简单选择排序存在不相邻的元素之间的交换,所有它是()。 A: 不稳定排序(正确答案)B: 稳定排序C: 不确定D: 都不对9.下列
18、选项中关于简单选择排序说法正确的是()。 A: 简单选择排序的每趟是要插入最小的记录放在某一位置B: 简单选择排序的每趟是要递归最小的记录放在某一位置C: 简单选择排序的每趟是要选择最小的记录放在某一位置(正确答案)D: 简单选择排序的每趟是要查找最小的记录放在某一位置10.简单选择排序算法里,每一趟选择最小的记录的过程,则每一趟排序的时间复杂度是()。 A: O(n)(正确答案)B: O(nn)C: O(1)D: O(nlog2n)11.比快速排序时间复杂度高的排序有()。 A: 简单选择排序(正确答案)B: 直接插入排序(正确答案)C: 冒泡排序(正确答案)D: 改进的冒泡排序(正确答案)
19、12.时间复杂度是O(nn)的排序是()。 A: 简单选择排序(正确答案)B: 冒泡排序(正确答案)C: 直接插入排序(正确答案)D: 快速排序13.从排序的大的分类上讲,属于交换排序的是()。 A: 简单选择排序B: 堆排序C: 快速排序(正确答案)D: 冒泡排序(正确答案)14.从排序大类上看,属于选择排序的是()。 A: 简单选择排序(正确答案)B: 堆排序(正确答案)C: 快速排序D: 冒泡排序15.下列排序中属于不稳定排序的有()。 A: 快速排序(正确答案)B: 直接插入排序C: 简单选择排序(正确答案)D: 冒泡排序16.简单选择排序是一种交换排序。 对错(正确答案)17.简单选
20、择排序是和冒泡排序的时间复杂度一样。 对(正确答案)错18.从未排序序列中挑选元素,并将其依次插入已排序序列(初始时为空)的一端的方法,称为冒泡排序。 对错(正确答案)19.排序算法中,第一趟排序后,任一元素都不能确定其最终位置的算法是插入排序。 对(正确答案)错22.简单选择排序的稳定性与快速排序的稳定性不一样。 对错(正确答案)1. for(;)printf(hello worldn);关于本程序段说法正确的是()。 A: for语句使用有误,两个分号中间的表达式不能省略B: 这是一个死循环,不停的输出hello world。(正确答案)C: 这语句还可以简化,省略掉两个分号。D: n是一
21、种转义字符,作用是水平制表。2.#include stdio.hvoid main()int i,s;for(i=1,s=0;i=5;i+)s=i;printf(%d,s);以上代码的执行结果是:()。单选题 A: 是0(正确答案)B: 是24C: 是6D: 是1203.鸡兔同笼是()经典算法解决的一类问题。 A: 穷举法(正确答案)B: 递推法C: 分治法D: 迭代法4.已知dowhile结构的基本语法如下dowhile();单选题 D不用管占位符C不用管占位符B不用管占位符A不用管占位符下面对于dowhile 的叙述正确的是(D)。单选题A: 里面的语句只能放一条语句。B: while后面
22、小括号里的表达式只能放关系表达式。C: while 小括号后面的分号可以省略D: while 小括号后面的分号不可以省略(正确答案)E不用管占位符5.一个大人一餐吃2个面包,两个小孩一餐吃1个面包,现在有大人和小孩共99人,一餐刚好吃了99个面包,大人、小孩各有多少人()。 A: 大人33人,小孩66人(正确答案)B: 大人66人,小孩33人C: 大人22人,小孩77人D: 大人44人,小孩55人6.以下经典著作中,哪本记载了最早的鸡兔同笼问题()。 A: 孙子算经(正确答案)B: 孙子兵法C: 九章算术D: 九章算经7.如孙子算经中描述的鸡兔同笼问题之穷举算法的时间复杂度是()。 A: O(
23、n)B: O(nn)(正确答案)C: O(nlog2n)D: O(1)8.一次数学竞赛共有20道题.做对一道题得5分,做错一题倒扣3分,刘冬考了52分,你知道刘冬做对了几道题()。 A: 刘冬做对14道题(正确答案)B: 刘冬做对12道题C: 刘冬做对16道题D: 刘冬做对15道题9.在一个单层循环中的循环体某处想停止本次循环,继续下一次循环,应在该处使用()语句。 A: break语句B: return语句C: continue语句(正确答案)D: exit(0)语句10.鸡兔同笼问题可以用那种经典算法来解决()。 A: 迭代法B: 穷举法(正确答案)C: 递推法D: 分治法11.鸡兔同笼算
24、法具有的特性包括()。 A: 有穷性(正确答案)B: 确定性(正确答案)C: 可行性(正确答案)D: 正确性12.解决鸡兔同笼算法使用的双层循环可以是()。 A: for嵌套for(正确答案)B: while嵌套while(正确答案)C: do-while嵌套for(正确答案)D: for嵌套do-while(正确答案)13.今有雉(鸡)兔同笼,上有三十五头,下有九十四足。问雉兔各几何?答案不正确的是()。 A: 鸡23兔12B: 鸡12兔23(正确答案)C: 鸡22兔13(正确答案)D: 鸡13兔22(正确答案)14.if(a=1)printf(one);else if(a=2)printf
25、(two);else printf(other);关于这段代码运行说法正确的是()。 A: 若a的值是1,则输出one。(正确答案)B: 若a的值是2,则输出two。(正确答案)C: 若a的值是5,则输出other。(正确答案)D: 若a的值是-1,则无输出结果15.关于do-while和while;下面描述不正确的是()。 A: dowhile结构先做while后面表达式的判断,若为真,则执行循环体,即里面的语句。(正确答案)B: dowhile结构先做while后面表达式的判断,若为假,则执行循环体,即里面的语句。(正确答案)C: do(条件) while(判断);是先执行后判断的一种循环结构.(正确答案)D: while与do.while两者无任何区别.(正确答案)16.for语句小括号中间的两个分号不可省略,两分号之间的表达式可以省略,若省略,循环将成为死循环或无限循环。 对(正确答案)错17.循环结构是用来描述可以重复执行的程序。 对(正确答案)错18.鸡兔同笼不仅仅限于孙子算经中描述,也可以其它类似问题,如大人小孩吃面包的问题,或者是大小油瓶的问题。 对(正确答案)错19.当表达式的值第一次为假时,while的循环体一次都不执行,dowhile则执行一次循环体。 对(正确答案)错20. break语句可用于循环结构中用来终止循环。 对(正确答案)错
限制150内