安阳工学院软件工程专业大二2017-2018数据结构与算法模拟试题七 (1)

1、安阳工学院软件工程专业大二2017-2018数据结构与算法模拟试题七您的姓名： 填空题 *_1.数据结构与算法里，折半查找中，low指向低端的记录，high指向高端的记录，每次计算中间位置mid的公式是（）。 单选题 *A.(low&high)/2B.(low+high)/2(正确答案)C.(low-high)/2D.low/2+high/22.数据结构与算法里，折半查找的时间复杂度是（）。 单选题 *A.O(1)B.O(log2n)(正确答案)C.O(n)D.O(n*n)3.数据结构与算法里，哈希表的装填因子（）。 单选题 *A.越大，发生冲突的可能越小B.越小，发生冲突的可能越大C

2、.与是否发生冲突无关D.越大，发生冲突的可能性越大(正确答案)4.数据结构与算法里，排序前序列为：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 135.数据结构与算法里，二叉排序树的第5层多有多少个结点（）。 单选题 *A.4B.16(正确答案)C.8D.326.数据结构与算法里，就性能而言，希尔排序的时间复杂度是（）。 单选题 *A.O(n*n)B.O(nlog2n)C.O(n)D.O(n3/2)(正确答案)7.数据结构与算法

3、里，改进的冒泡排序的任一趟排序过程中，如果没有发生()，则说明已经有序；排序完毕（）。 单选题 *A.数据交换(正确答案)B.数据删除C.数据删除D.都不对8.数据结构里，二叉树是非线性数据结构，所以（）。 单选题 *A.它不能用顺序存储结构存储B.它不能用链式存储结构存储C.顺序存储结构和链式存储结构都能存储(正确答案)D.顺序存储结构和链式存储结构都不能使用9.某二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则该二叉树的后序遍历的结果为（）。 单选题 *A.CBEFDA(正确答案)B.FEDCBAC.CBEDFAD.不定10.有n个终端结点的哈夫曼树的结点总数为（）。 单

4、选题 *A.2nB.不确定C.2n+1D.2n-1(正确答案)11.已知某完全二叉树上有结点1001个，其中度为0的结点的个数是（）。 单选题 *A.250B.都不对(正确答案)C.500D.50512.若一棵二叉树具有15个度为2的结点，8个度为1的结点，则度为0的结点个数是（）。 单选题 *A.9B.16(正确答案)C.15D.2313.数据结构与算法里，数据序列(2，1，4，9，8，10，6，20)只能是下列排序算法中的（）的两趟排序后的结果。 单选题 *A.快速排序(正确答案)B.冒泡排序C.以上都不对D.直接插入14.循环队列的最大容量M，队头f，队尾r，用人为浪费一个单元格区分空和

5、满，队满的条件是（）。 单选题 *A.(r+1)%M=f(正确答案)B.r%M=fC.(r-1)%M=fD.(r+1)=f15.数据结构与算法里，完数是完美数，它等于（）。 单选题 *A.所有因子之和(正确答案)B只能被1和它本身整除C.是该范围内最大的质数D.所有小于它的数之和16.数据结构与算法里，完数N的因子(真因子)为a，b，c，则有（）。 单选题 *A.N=a+b+c(正确答案)B.N-1=a+b+cC.N=a+b-cD.N=a*b*c17.数据结构与算法里， int i,j;for(i=1;i<=3;i+)for(j=1;j<4;j+)printf("*&qu

6、ot;);printf("n");该程序输出的图形是（）。单选题 单选题 *A.三行四列的矩形方阵B.三行三列的矩形方阵(正确答案)C.三行的直角三角形D.四行的直角三角形18.数据结构与算法里，以下不是回文字符串的是（）。 单选题 *A.abaB.11811C.abcabc(正确答案)D.xyzyx19.数据结构与算法里，以下经典著作中，哪本记载了最早的鸡兔同笼问题（）。 单选题 *A.孙子算经(正确答案)B.孙子兵法C.九章算术D.九章算经20.数据结构与算法里，循环语句中加break的作用的是（）。 单选题 *A.break用于循环语句的作用是结束本层循环(正确答案)

7、B.break用于循环语句的作用是结束本次循环，继续下一下循环C.break不能用于switch语句D.break语句不能用do-while语句开会21.数据结构与算法里，关于二叉排序树相关描述正确的是（）。 *A.二叉排序树是应用于动态查找的结构(正确答案)B.二叉排序树的中序列是升序序列(正确答案)C.二叉排序树的左子树也是二叉排序树(正确答案)D.二叉排序树的定义具有递归性(正确答案)22.数据结构与算法里，设哈希表长度为11,哈希函数H(K)=(K的第一个字母在字母表中的序号)MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),采用内散列表,处理冲突方法为线性探测法

8、,要求构造哈希表,在等概率情况下查找成功平均查找长度错误的是()。 *A.4(正确答案)B.3(正确答案)C.20/9D.23/9(正确答案)23.数据结构与算法里，直接插入排序最好、最坏两种情况的时间复杂度分别是（）。 *A.O(n*log2n)B.O(n)(正确答案)C.O(log2n)D.O(n*n)(正确答案)24.数据结构与算法里，关于希尔排序描述正确的是（）。 *A.希尔排序是不稳定排序(正确答案)B.希尔排序是属于插入排序(正确答案)C.希尔排序的时间复杂度是O(n3/2)(正确答案)D.希尔排序又称为缩小增量排序(正确答案)25.数据结构与算法里，以下算法时间复杂度是O(n*n

9、)的是（）。 *A.冒泡排序(正确答案)B.直接插入排序(正确答案)C.折半查找D.希尔排序26.数据结构与算法里，关于快速排序描述正确的是（）。 *A.快速排序是不稳定排序(正确答案)B.快速排序的时间复杂度是O(nlog2n)。(正确答案)C.快速排序是一种交换排序(正确答案)D.快速排序是内排序的一种(正确答案)27.数据结构与算法里，今有雉(鸡)兔同笼，上有三十五头，下有九十四足。问雉兔各几何？答案不正确的是（）。 *A.鸡23兔12B.鸡12兔23(正确答案)C.鸡22兔13(正确答案)D.鸡13兔22(正确答案)28.数据结构与算法里，汉诺塔算法描述正确的是()。 *A.使用递归来

10、完成算法(正确答案)B.时间复杂度是O(2n)(正确答案)C.递归出口是盘子数量为1时(正确答案)D.递归出口是盘子数量为1时(正确答案)29.数据结构与算法里，求两个数的最大公约数，依照方式不同其时间复杂度可能是（）。 *A.O(n)(正确答案)B.O(log2n)(正确答案)C.O(n*n)D.O(1)30.顺序队存储在Q中，front是队头，rear是队尾，rear总指向队尾元素之后的空间，用e接收出队的元素，则出队应该记为：（）。 *A.e=Qfront;front+;(正确答案)B.front+;e=Qfront;C.Qfront=e;front+;D.e=Qfront+;(正确答案

11、)31数据结构与算法里，迭代算法的时间复杂度不可能是O(n)。 判断题 *对错(正确答案)32数据结构与算法里，汉诺塔是一类递归的算法，也应具有算法的可行性。 判断题 *对(正确答案)错33数据结构与算法里，字符数组可能没有'0',但是字符串一定有'0'。 判断题 *对(正确答案)错34数据结构与算法里，strcpy和strcat的返回值类型不一样。 判断题 *对错(正确答案)35二叉排序树的充要条件：二叉排序树的任意结点的关键字都大于其左孩子的关键字，且小于其右孩子的关键字。 判断题 *对错(正确答案)36动态查找表属于树形结构，因为这里涉及二叉排序树。 判断

12、题 *对错(正确答案)37荷兰国旗算法的时间复杂度是O(n)。 判断题 *对(正确答案)错38小明的烦恼问题要用二维字符串数组存储代表电话号码的字母。 判断题 *对(正确答案)错39数据结构与算法里，对不同的关键字可能得到同一哈希地址，即keykey2面f(key1)=f(key2)这种现象称冲突(collision)。具有相同函数值的关键词对该哈希函数来说称作同义词。 判断题 *对(正确答案)错40.若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列4,2,5,6,3,1。 判断题 *对错(正确答案)1.以下算法中时间复杂度最高的是（）。 单选题 *A: 冒泡排序算法B: 顺序表的

13、插入算法C: 快速排序算法D: 汉诺塔问题算法(正确答案)2.#include "windows.h"void tell_story( )printf("从前有座山,山上有座庙,庙里有一个老和尚和一个小和尚n");printf("老和尚正在给小和尚讲故事。讲的是什么故事呢？他说:n");tell_story ( ); void main()tell_story( );函数的这种调用方式属于（）。单选题 单选题 *A 穷举B递归(正确答案)C迭代D分治3.汉诺塔的算法使用递归算完成，那么递归是（）。 单选题 *A: 嵌套调用的典型代表B

14、: 函数自身调用自身的编程技巧(正确答案)C: 函数的普通调用D: 以上选项都不对4.从算法的设计要求上讲，汉诺塔应具有（）。 单选题 *A: 有穷性B: 确定性C: 可行性D: 可读性(正确答案)5.对于汉诺塔问题，最早的来源于哪个国家（）。 单选题 *A: 古埃及B: 印度(正确答案)C: 波斯D: 罗马帝国6.n个盘子的汉诺塔问题，移动步数是（）。 单选题 *A: 2的n次幂减1(正确答案)B: 2*n-1C: 2*n+1D: log2n7.汉诺塔的算法是递归算法解决的，所谓递归即（）。 单选题 *A: 函数自身调用自身的编程技巧。(正确答案)B: 函数嵌套调用的方式C: 函数调用的普通

15、方式D: 无参函数是不能使用递归的8.break语句可以用于下列语法中的那个语法（）。 单选题 *A: if-elseB: for(正确答案)C: ifD: if-elseif9.doprintf("To be or not to be is a questionn");while(3>=3);对于本程序段描述正确的是（）。 单选题 *A: 该程序是一个死循环程序(正确答案)B: 输出一遍To be or not to be is a questionC: do-while是先判断后执行，条件成立继续执行循环体D: 该程序不能执行，因为第一次条件就不满足10.折纸算法

16、是一种（）方法解决的问题。 单选题 *A: 迭代(正确答案)B: 穷举C: 递推D: 分治11.汉诺塔问题的递归分为（）几部分。 *A: 递归前进段(正确答案)B: 递归返回段(正确答案)C: 递归出口(正确答案)D: 递归问题12.汉诺塔问题的求解方式不属于以下哪类算法（）。 *A: 穷举(正确答案)B: 分治(正确答案)C: 递归D: 迭代(正确答案)13.汉诺塔问题是算法的一种，因此具有算法的特性（）。 *A: 有穷性(正确答案)B: 确定性(正确答案)C: 可行性(正确答案)D: 输入、输出(正确答案)14.递归问题经常使用栈帮助实现，栈的应用有（）。 *A: 八皇后问题(正确答案)B

17、: 汉诺塔问题(正确答案)C: 迷宫问题(正确答案)D: 表达式求值问题(正确答案)15.修公路问题算法：void main()int h=1000,count=0;printf("一条待修公路1000公里，每天修55公里，问多少天后还有不足60公里未修？n");while(h>=60)printf("%dt",h);(填空);count+; printf("n总计需要%d天后还有不足60公里未修n",count); 则填空处可以填写（）。多选题 *A: h-=55(正确答案)B: h=h-55(正确答案)C: h=h*2D:

18、h*=216.蜗牛爬井问题和折纸问题是一类问题，都是可以用迭代法解决的。 判断题 *对(正确答案)错17.汉诺塔算法具有可读性，这是算法的特性之一。 判断题 *对错(正确答案)18.折纸超珠峰问题的时间复杂度是O(n*n)。 判断题 *对错(正确答案)19.汉诺塔问题的时间复杂度上讲，应为O(2n)(表示幂)。 判断题 *对(正确答案)错20.汉诺塔问题的求解方式，是用分治算法，一步一步计算而得的。 判断题 *对错(正确答案)1.下面程序执行后的结果是()#include "stdio.h"void main() int arr44=2,2,3,4,5,6,7,8,9,10

19、,11,12,13,14,15,15,i,sum=0;for(i=0;i<4;i+)sum=sum+arrii;printf("%d",sum);。单选题 单选题 *A 28B 34(正确答案)C 40D 102.已知二维数组int a33= 1,2,7,4,10,6,3,8,9;printf("%d”,a11);则程序输出的结果是(C)。单选题 单选题 *占位不用管A: 1B: 2C: 10(正确答案)D: 73.字符串处理函数是字符串连接的是（）。 单选题 *A: strcat(正确答案)B: strcpyC: strcmpD: strlen4.回文字符

20、串存与字符数组中，若求字符串的长度可以使用函数（）。 单选题 *A: strlen(正确答案)B: strcatC: strcpyD: strcmp5.strcat的参数个数是（）。 单选题 *A: 2(正确答案)B: 1C: 3D: 46.回文字符串之非递归循环解决方案，设置flag标志位的作用是（）。 单选题 *A: 保存：判定是否存在这样的一对第i个字符与倒数第i个字符不等的情况(正确答案)B: 没有关键性作用C: 标志位不可以赋值为0、1以外的数。D: 标志位flag的作用是判断回文字符串的长度的7.char s100="abc" 则执行strcpy(s,strca

21、t(s,"123");后s的结果是（）。 单选题 *A: abc123(正确答案)B: 123abcC: abcD: 1238.字符串处理函数是字符串比较的是（）。 单选题 *A: strcatB: strcpyC: strcmp(正确答案)D: strlen9.计算字符串的长度的函数是（）。 单选题 *A: strcpyB: strcatC: strcmpD: strlen(正确答案)10.若有说明:int a34;，则对a数组元素的非法引用是：（）。 单选题 *A: a02*1B: a13C: a4-20D: a04(正确答案)11.在C语言中，系统函数strcmp的返

22、回值类型不是（）。 *A: intB: char(正确答案)C: char*(正确答案)D: float(正确答案)12.荷兰国旗的算法使用的到的技术有（）。 *A: 循环(正确答案)B: 分支判断(正确答案)C: 一维数组(正确答案)D: 循环嵌套13.以下是回文字符串的是（）。 *A: aba(正确答案)B: 11811(正确答案)C: abcabcD: xyzyx(正确答案)14.回文字符串的判断可以使用的方法有（）。 *A: 递归方式(正确答案)B: 非递归方式利用循环解决(正确答案)C: 非递归方式用系统函数解决(正确答案)D: 以上答案都正确(正确答案)15.以下字符串中，是回文字

23、符串的是（）。 *A: abcba(正确答案)B: 12321(正确答案)C: 1221(正确答案)D: abcdef16.荷兰国旗算法的基本写法循环中套分支结构。 判断题 *对(正确答案)错17.C语言中，数组是具有不相同数据类型的有序集合。 判断题 *对错(正确答案)18.如有定义int a23;则数组a的最后一个元素为a12。 判断题 *对(正确答案)错19.在C语言中，实现求字符串长度的函数是strlen()。 判断题 *对(正确答案)错20.引用数组元素时，其数组下标的数据类型允许的是：整型常量或整型表达式。 判断题 *对(正确答案)错1.数据结构与算法内，从时间复杂度的角度来看，快

24、速排序的时间复杂度是（）。 单选题 *A: O(n*n)B: O(nlog2n)(正确答案)C: O(1)D: 都不对2.荷兰国旗问题，需要使用一维数组存储0,1,2；那么一维数组的元素在内存中（）。 单选题 *A: 占有一片连续的存储空间(正确答案)B: 是不连续的存储空间C: 可能是连续的也可能是不连续的D: 都不对3.以下英文字符串中是回文字符串的是（）。 单选题 *A: aabbaa(正确答案)B: aabbccddC: ABCABCD: AABBB4.数据结构与算法内，哈希表的装填因子（）。 单选题 *A: 越大，发生冲突的可能越小B: 越小，发生冲突的可能越大C: 与是否发生冲突无关D: 越大，发生冲突的可能性越大(正确答案)5.数据结构与算法内，折半查找的时间复杂度是（）。 单选题 *A: O(1)B: O(log2n)(正确答案)C: O(n*n)D: O(n)6.鸡与兔共有100只，鸡脚比兔脚多80只，问鸡有（）只。 单选题 *A: 80(正确答案)B: 75C: 70D: 657.15和10的最小公倍数是（）。 单选题 *A: 10B: 15C: 150D: 30(正确答案)8.完数又称完美数，下面的整数中是完数的是（）。 单选题 *A: 28