数据结构与算法模拟试题六

数据结构与算法模拟试题六

您的姓名：［填空题］*

L数据结构与算法里，折半查找中，low指向低端的记录，high指向高端的记录，

每次计算中间位置mid的公式是()。［单选题］*

A.(low&high)/2

B.(low+high)/2(正确答案)

C.(low-high)/2

D.low/2+high/2

2.数据结构与算法里，折半查找的时间复杂度是()o［单选题］*

A.O(l)

B.O(log2n)(正确答案)

C.O(n)

D.O(n*n)

3.数据结构与算法里，哈希表的装填因子()o［单选题］*

A.越大，发生冲突的可能越小

B.越小，发生冲突的可能越大

C.与是否发生冲突无关

D.越大，发生冲突的可能性越大勺答案)

4.数据结构与算法里，排序前序列为：11101389间经过一趟直接插入排序(按从

小到大排序)后的序列是0o［单选题］*

A.10111389(正确答案)

B.10118913

C.ll108913

D.891()1113

5.数据结构与算法里，二叉排序树的第5层多有多少个结点()。［单选题］*

A.4

B.16(正确答案)

C.8

D.32

6.数据结构与算法里，就性能而言，希尔排序的时间复杂度是()o［单选题］*

A.O(n*n)

B.O(nlog2n)

C.O(n)

D.O(n3/2)(正确答案)

7.数据结构与算法里，改进的冒泡排序的任一趟排序过程中，如果没有发生()，则

说明已经有序；排序完毕()。［单选题］*

A.数据交换

B.数据删除

C.数据删除

D渚B不对

8.数据结构里，二叉树是非线性数据结构，所以()。［单选题］*

A.它不能用顺序存储结构存储

B.它不能用链式存储结构存储

C.顺序存储结构和链式存储结构都能存储

D.顺序存储结构和链式存储结构都不能使用

9.某二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则该二叉树的后

序遍历的结果为（）o［单选题］*

A.CBEFDA

B.FEDCBA

C.CBEDFA

D.不定

10.有n个终端结点的哈夫曼树的结点总数为（）。［单选题］*

A.2n

B.不确定

C.2n+1

D.2n-1（正确答案）

11.已知某完全二叉树上有结点1001个，其中度为0的结点的个数是（）。［单选

题］*

A.250

B.都不对

C.500

D.505

12.若一棵二叉树具有15个度为2的结点，8个度为1的结点，则度为0的结点个

数是（）o［单选题1*

A.9

B.16（正确答案）

C.15

D.23

13.数据结构与算法里，数据序列（2,1,4,9,8,1（）,6,20）只能是下列排序算法

中的（）的两趟排序后的结果。［单选题］*

A.快速排序

B.冒泡排序

C.以上都不对

D.直接插入

14.循环队列的最大容量M,队头f,队尾r,用人为浪费一个单元格区分空和满，

队满的条件是（）。［单选题］*

A.（r+l）%M==f（正确答案）

B.r%M==f

C.（r-l）%M==f

D.（r+l）==f

15.数据结构与算法里，完数是完美数，它等于（）。［单选题］*

A.所有因子之和（正确答案）

B只能被1和它本身整除

C.是该范围内最大的质数

D.所有小于它的数之和

16.数据结构与算法里，完数N的因子（真因子）为a,b,c,则有（）。［单选题］*

A.N=a+b+c

B.N-l=a+b+c

C.N=a+b-c

D.N=a*b*c

17.数据结构与算法里，inti,j;

for(i=l;i<=3;i++)

(

for(j=l；j<4;j++)

(

printf("*");

}

printf("\n");

}该程序输出的图形是()o［单选题］［单选题1*

A.三行四列的矩形方阵

B.三行三列的矩形方阵

C.三行的直角三角形

D.四行的直角三角形

18.数据结构与算法里，以下不是回文字符串的是()。［单选题］*

A.aba

B.11811

C.abcabc(正确答案)

D.xyzyx

19.数据结构与算法里，以下经典著作中，哪本记载了最早的鸡兔同笼问题()o

［单选题］*

A.孙子算经

B.孙子兵法

C.九章算术

D.九章算经

20.数据结构与算法里，循环语句中加break的作用的是()。［单选题］*

A.break用于循环语句的作用是结束本层循环

B.break用于循环语句的作用是结束本次循环，继续下一下循环

C.break不能用于switch语句

D.break语句不能用do-while语句开会

21.数据结构与算法里，关于二叉排序树相关描述正确的是（）。*

A.二叉排序树是应用于动态查找的结构（正确答案）

B.二叉排序树的中序列是升序序列【正确答案।

C.二叉排序树的左子树也是二叉排序树：再答案）

D.二叉排序树的定义具有递归性

22.数据结构与算法里，设哈希表长度为11,哈希函数H（K）=（K的第一个字母在字母

表中的序号）M0D11,若输入顺序为（》出人月2乂。,1,10（；^）,采用内散列表,处理冲

突方法为线性探测法，要求构造哈希表，在等概率情况下查找成功平均查找长度错误

的是（）。*

A.4（正确答案）

B.3（正确答案）

C.20/9

D.23/9（正确答案）

23.数据结构与算法里，直接插入排序最好、最坏两种情况的时间复杂度分别是

0o*

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）的是（）。*

A.冒泡排序

B.直接插入排序

C.折半查找

D.希尔排序

26.数据结构与算法里，关于快速排序描述正确的是（）。*

A.快速排序是不稳定排序:正确答案）

B.快速排序的时间复杂度是O（nlog2n）。B确答案）

C.快速排序是一种交换排序（正确答案）

D.快速排序是内排序的一种

27.数据结构与算法里，今有雉（鸡）兔同笼，上有三十五头，下有九十四足。问雉兔

各几何？答案不正确的是（）o*

A.鸡23兔12

B.鸡12兔23

C.鸡22兔13（正确答案）

D.鸡13兔22正确答案）

28.数据结构与算法里，汉诺塔算法描述正确的是（）。*

A.使用递归来完成算法：:确答案）

B.时间复杂度是0（2?）正确答案）

C.递归出口是盘子数量为1时

D.递归出口是盘子数量为1时

29.数据结构与算法里，求两个数的最大公约数，依照方式不同其时间复杂度可能

是（）。*

A.O（n）（正确答案）

B.O（log2n）（正确答案）

C.O（n*n）

D.O（l）

30.顺序队存储在Q中，front是队头，rear是队尾，rear总指向队尾元素之后的空

间，用e接收出队的元素，则出队应该记为：（）。*

A.e=Q[front];front++;

B.front++;e=Q[front];

C.Q[frontl=e;front++;

D.e=Q[fix）nt++];（正确答案）

31数据结构与算法里，迭代算法的时间复杂度不可能是O（n）。[判断题]*

对

错（正确答案）

32数据结构与算法里，汉诺塔是一类递归的算法，也应具有算法的可行性。[判断

题]*

对

错

33数据结构与算法里，字符数组可能没有'\0’,但是字符串一定有‘\0'。[判断题]*

对

错

34数据结构与算法里，strcpy和strcat的返回值类型不一样。［判断题］*

对

错(正确答案)

35二叉排序树的充要条件：二叉排序树的任意结点的关键字都大于其左孩子的关

键字，且小于其右孩子的关键字。［判断题］*

对

错(正确答案)

36动态查找表属于树形结构，因为这里涉及二叉排序树。［判断题］*

对

错(正确答案)

37荷兰国旗算法的时间复杂度是0(n)。［判断题］*

对

错

38小明的烦恼问题要用二维字符串数组存储代表电话号码的字母。［判断题］*

对

错

39数据结构与算法里，对不同的关键字可能得到同一哈希地址，即keyrkey2面

f(keyl)=f(key2)这种现象称冲突(collision)。具有相同函数值的关键词对该哈希函数

来说称作同义词。［判断题］*

对

错

40.若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列425,6,3,1。［判断题］*

对

错（正确答案）

1.以下算法中时间复杂度最高的是（）。［单选题］*

A:冒泡排序算法

B:顺序表的插入算法

C:快速排序算法

D:汉诺塔问题算法

2.#include"windows.h"

voidtell_story（）

（

printf（"从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚\n"）；

printf（"老和尚正在给小和尚讲故事。讲的是什么故事呢？他说:\n"）；

tell_story（）;

}

voidmain（）

（

tell_story（）;

}函数的这种调用方式属于（）。［单选题］［单选题］*

A穷举

B递归（正确答案）

C迭代

D分治

3.汉诺塔的算法使用递归算完成，那么递归是（）。［单选题］

A:嵌套调用的典型代表

B:函数自身调用自身的编程技巧

C:函数的普通调用

D:以上选项都不对

4.从算法的设计要求上讲，汉诺塔应具有（）。［单选题］*

A:有穷性

B:确定性

C:可行性

D:可读性

5.对于汉诺塔问题，最早的来源于哪个国家（）。［单选题］*

A:古埃及

B:印度（正确答案）

C:波斯

D:罗马帝国

6.n个盘子的汉诺塔问题，移动步数是（）。［单选题］*

A:2的n次鬲减1

B:2*n-l

C:2*n+l

D:log2n

7.汉诺塔的算法是递归算法解决的，所谓递归即（）。［单选题］*

A:函数自身调用自身的编程技巧。（正确答案）

B:函数嵌套调用的方式

C:函数调用的普通方式

D:无参函数是不能使用递归的

8.break语句可以用于下列语法中的那个语法（）。［单选题］*

A:if-else

B:for（正确答案）

C:if

D:if-else—if

9.do{printf（"Tobeornottobeisaquestion\n"）;}while（3>=3）;对于本程序段描述正确

的是（）o［单选题］*

A:该程序是一个死循环程序

B:输出一遍Tobeornottobeisaquestion

C:do-while是先判断后执行，条件成立继续执行循环体

D:该程序不能执行，因为第一次条件就不满足

10.折纸算法是一种（）方法解决的问题。［单选题］*

A:迭代（正确答案）

B：穷举

C:递推

D:分治

11.汉诺塔问题的递归分为（）几部分。*

A:递归前进段

B:递归返回段

C:递归出口（正确答案）

D:递归问题

12.汉诺塔问题的求解方式不属于以下哪类算法（）。*

A:穷举（正确答案）

B:分治

C:递归

D:迭代（正确答案）

13.汉诺塔问题是算法的一种，因此具有算法的特性（）。*

A:有穷性（正确答案）

B:确定性（正确答案）

C:可行性（正确答案）

D:输入、输出

14.递归问题经常使用栈帮助实现，栈的应用有（）。*

A:八皇后问题

B:汉诺塔问题

C:迷宫问题

D:表达式求值问题

15.修公路问题算法：

voidmain（）

（

inth=l（）（）（）,count=0;

printf（"一条待修公路1000公里，每天修55公里，问多少天后还有不足60公里未

修?\n"）;

while（h>=60）

（

printf（"%d\t",h）;

（填空）；

count++；

printf（"\n总计需要％d天后还有不足60公里未修\n",count）;

｝则填空处可以填写（）。［多选题］*

A:h-=55（正确答案）

B:h=h-55正确答案）

C:h=h*2

D:h*=2

16.蜗牛爬井问题和折纸问题是一类问题，都是可以用迭代法解决的。［判断题］

对（正确答案）

错

17.汉诺塔算法具有可读性，这是算法的特性之一。［判断题］*

对

错（正确答案）

18.折纸超珠峰问题的时间复杂度是O（n*n）。［判断题］*

对

错（正确答案）

19.汉诺塔问题的时间复杂度上讲，应为O（2M）（人表示鬲）。［判断题］*

对（正确答案）

错

20.汉诺塔问题的求解方式，是用分治算法，一步一步计算而得的。［判断题］*

对

错（正确答案）

1.下面程序执行后的结果是0

#include"stdio.hn

voidmain()

intarr[4][4]={{2,2,3,4},{5,6,7,8},{9,10,ll,12},{13,14,15,15}),i,sum=0;

for(i=0;i<4;i++)

(

sum=sum+arr[i][i];

)

printf("%d",sum);

}o[单选题][单选题]*

A28

B34(正确答案)

C40

D10

2.已知二维数组inta[3][3]={l,2,7,4,10,6,3,8,9};printf("%d",a[l][l]);则程序输出的结

果是(C)。[单选题][单选题]*

占位不用管

A:1

B:2

C:10(正确答案)

D:7

3.字符串处理函数是字符串连接的是()。[单选题]*

A:strcat

B:strcpy

C:strcmp

D:strlen

4.回文字符串存与字符数组中，若求字符串的长度可以使用函数（）o［单选题］*

A:strlen

B:strcat

C:strcpy

D:strcmp

5.strcat的参数个数是（）o［单选题］*

A:2（正确答案）

B:1

C:3

D:4

6.回文字符串之非递归循环解决方案，设置flag标志位的作用是（）。［单选题］*

A:保存：判定是否存在这样的一对第i个字符与倒数第i个字符不等的情况

答案）

B:没有关键性作用

C:标志位不可以赋值为0、1以外的数。

D:标志位flag的作用是判断回文字符串的长度的

7.chars［100］="abc";则执行strcpy（s,streams,"123"））;后s的结果是（）。［单选题］*

A:abc123A答案）

B:123abc

C:abc

D:123

8.字符串处理函数是字符串比较的是（）。［单选题］*

A:strcat

B:strcpy

C:strcmp

D:strlen

9.计算字符串的长度的函数是（）。[单选题]*

A:strcpy

B:strcat

C:strcmp

D:strlen

10.若有说明:inta[3][4];,则对a数组元素的非法引用是:（）。[单选题]*

A:a[0][2*l]

B：a[l][3]

C:a[4-2][0]

D:a[0][4],E确答案）

11.在C语言中，系统函数strcmp的返回值类型不是（）。*

A:int

B:char（正确答案）

C:char*

D:floatE确答案）

12.荷兰国旗的算法使用的到的技术有（）o*

A:循环

B:分支判断

C:一维数组（正确答案）

D:循环嵌套

13.以下是回文字符串的是（）。*

A:aba

B:11811E确答案）

C:abcabc

D:xyzyx

14.回文字符串的判断可以使用的方法有（）。*

A:递归方式（正确答案）

B:非递归方式利用循环解决

C:非递归方式用系统函数解决

D:以上答案都正确与答案）

15.以下字符串中，是回文字符串的是（）。*

A:abcba

B:12321（正确答案）

C:1221（正确答案）

D:abcdef

16.荷兰国旗算法的基本写法循环中套分支结构。［判断题］*

对

错

17.C语言中，数组是具有不相同数据类型的有序集合。［判断题］*

对

错（正确答案）

18.如有定义inta⑵⑶;则数组a的最后一个元素为a［ll［2］o［判断题］*

对（正国

错

19.在C语言中，实现求字符串长度的函数是strlen()。［判断题］*

对(正确答案)

错

20.引用数组元素时，其数组下标的数据类型允许的是：整型常量或整型表达式。

［判断题］*

对(正确答案)

错

L数据结构与算法内，从时间复杂度的角度来看，快速排序的时间复杂度是0o

［单选题］*

A:O(n*n)

B:O(nlog2n)(正确答案)

C:0(1)

D:都不对

2.荷兰国旗问题，需要使用一维数组存储(),1,2；那么一维数组的元素在内存中

()o［单选题］*

A:占有一片连续的存储空间

B:是不连续的存储空间

C:可能是连续的也可能是不连续的

D:都不对

3.以下英文字符串中是回文字符串的是()o［单选题］*

A:aabbaa

B:aabbccdd

C:ABCABC

D:AABBB

4.数据结构与算法内，哈希表的装填因子()o［单选题］*

A:越大，发生冲突的可能越小

B:越小，发生冲突的可能越大

C:与是否发生冲突无关

D:越大，发生冲突的可能性越大;正确答案)

5.数据结构与算法内，折半查找的时间复杂度是()o［单选题］*

A:0(1)

B:O(log2n)

C:0(n*n)

D:O(n)

6.鸡与兔共有100只，鸡脚比兔脚多80只，问鸡有()只。［单选题］*

A:80(正确答案)

B:75

C:70

D:65

7.15和10的最小公倍数是()o［单选题］*

A:10

B:15

C:150

D:3()

8.完数又称完美数，下面的整数中是完数的是()o［单选题］

A:28皤答案）

B