数据结构与算法周考三1

数据结构与算法周考三1

您的姓名：［填空题］*

1.二叉排序树的叶子结点个数为5个，则度为2的结点的数目是()。［单选题］*

A、6

B、5

C、4

D、3

2.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，

至少要进行多少次探测()o［单选题］*

A、k-1次

B、k次

C、k+1次

D、k(k+l)/2次

3.直接插入排序的时间复杂度和顺序查找的时间复杂度分别是()o［单选题］*

A、0(n)和O(log2n)

B、O(n*n)和0(n)

C、0(1)和)0(n)

D、0(n)和0(1)

4.在排序中，对于关键字相等的记录，排序前后相对位置不变。这时称排序为

0o［单选题］*

A、稳定排序

B、不稳定排序

C、不确定是稳定排序还是不稳定排序

D、基数排序

5.就性能而言，希尔排序的时间复杂度是（）o［单选题］*

A、O（n*n）

B、O（nlog2n）

C、0（n）

D、O（n3/2）E确答案）

6.希尔排序又称为（）。［单选题］*

A、缩小增量排序（正确答案）

B、二分插入排序

C、多路归并排序

D、锦标赛排序

7.N个记录进行冒泡排序最多需要（）趟排序，可以完成排序。［单选题］*

A、N-1（正确答案）

B、N

C、N-2

D、（N+l）/2

8.30个记录进行冒泡排序，使用未改进的冒泡排序，则需要（）趟排序才能完成

排序。［单选题］*

A、29（正确答案）

B、30

C、28

D、27

9.递归概念指的是()。［单选题］*

A、程序调用自身的编程技巧

B、特定功能的模块

C、相同数据类型的有序的集合

D、从小到大进行排列

1().青蛙过河案例中，如果河中没有石柱，有y片荷叶的话，那么从左岸到右岸可

以过去()只青蛙。［单选题］*

A、y+1只确答案)

B、y+2只

C、y+3只

D、y+4只

11.一趟快速排序是将记录一分为(),返回中轴所在的位置。［单选题］*

A、二(正确答案)

B、三

C、四

D、都不对

12.简单选择排序中，每一趟选择最小的记录的过程，则每一趟排序的时间复杂度

是0o［单选题】*

A、O(n)

B、O(n*n)

C、0(1)

D、O(n*log2n)

13.N个记录，采用简单选择排序，每趟最多进行（）次交换。［单选题］*

A、1E确答案）

B、2

C、N-2

D、N-1

14.从排序大类上讲，简单选择排序和冒泡排序是（）排序。［单选题］*

A、同一类

B、不同类（正确答案）

C、不确定

D、都不对

6N个记录是有序的使用什么查找效率更高（）o［单选题］*

A、顺序查找

B、折半查找（正确答案）

C、分块查找

D、随机查找

16数据结构与算法中，在所有的排序方法中，关键字比较的次数与记录的初始排

列次序无关的是（）。［单选题］*

A、希尔排序

B、冒泡排序

C、直接插入排序

D、简单选择排序（正确答案）

17.采用快速排序进行排序，问题规模为n,则时间复杂度是（）。［单选题］*

A、O(n3/2)

B、O(n*n)

C、0(n)

D、O(n*log2n)(正确答案)

18.快速排序在()情况下不利于发挥其长处或优势。［单选题］*

A、记录有相同的关键字时

B、记录完全乱序时

C、记录已经基本有序时

D、记录的关键字较大时

19.ACM算法的素数和计算中，sum变量用于累加素数之和，那么它的初值应赋值

为0o［单选题］*

A、0(正确答案)

B、1

C、10()

D、不赋初值

20.数据结构与算法中，素数的特点是()。［单选题］*

A、只能被1和本身整除

B、可以被2整除

C、素数和完数是相同的概念

D、素数就是合数

21下列那个是直接递归形式函数()o［单选题］*

A:voidtell_stroy(){tell_stroy();}

B:voidtell_stroy(){voidtell_stroy();}

C:voidtell_stroy(){stroy();}

D:voidtell_stroy(){tell();}

22冒泡排序最好的情况是，记录完全有序，20个记录待排序只需要比较（）次即

可完成排序。［单选题］*

A:20

B:19（正确答案）

C:18

D:190

23.排序前序列为：3415886672问经过一趟直接插入排序（按从小到大排序）后的

序列是（）。［单选题】*

A:1534886672（正确答案）

B:3415886672

C:1534667288

D:1534668872

24.装填因子又称为（）。［单选题］*

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,则有（）o［单选题］*

A.N=a+b+c（正确答案）

B.N-l=a+b+c

C.N=a+b-c

D.N=a*b*c

29.关于希尔排序描述正确的是（）o*

A、希尔排序是不稳定排序

B、希尔排序是属于插入排序

C、希尔排序的时间复杂度是O（n3/2）

D、希尔排序又称为缩小增量排序

3（）.下列排序中是不稳定排序的是（）。*

A、希尔排序

B、快速排序

C、直接插入排序

D、冒泡排序

31.从排序大类上看，属于选择排序的是（）。*

A、简单选择排序（正确答案）

B、堆排序

C、快速排序

D、冒泡排序

32.switch语句中，在（）中的表达式类型可以是（）o*

A、整型（正确答案）

B、字符型答案）

C、字符串

D、浮点型

33.6是完数，其因子包括（）o*

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-l）/2次可完成排序，这是记录完全逆序的情况。

答案）

D:在一趟排序中若无记录交换，就会停止排序。

37关于快速排序描述不正确的是（）。*

A:快速排序是稳定排序

B:快速排序的时间复杂度是O（nlog2n）

C:快速排序不存在不相邻的记录之间的交换

D:快速排序的时间复杂度是O（n*n）

38下列排序中是稳定排序的是（）o*

A:希尔排序

B：快速排序

C：直接插入排序

D:冒泡排序前答案）

39动态查找表：边查找，边改变集合中的元素，改变的方式可以是（）o*

A:增加（正确答案）

B:删除（正确答案）

C:交换

D:移动

40.数据结构与算法里，关于哈希表的装填因子，以下正确的有（）o*

A:装填因子的值越小，发生冲突的概率越小”答案）

B:装填因子越大，表中填入的记录越多，在填入的时候发生冲突的可能性就越

大，在进行查找时候，查找的次数也就越多。

C:装填因子=表中填入的记录数/哈希表的总长度腕捽至）

D:装填因子的值越小，就可以避免冲突的发生

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

表中的序号）MOD11,若输入顺序为（口用人月?4可©,1,10（；^）,采用内散列表,处理冲

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

的是（）。*

A:4（正确答案）

B:3（正确答案）

C:20/9

D:23/9（正确答案）

42关于二叉排序树描述有误的是（）。*

A:二叉排序的右子树上结点的关键字小于左子树上的结点的关键字用答案）

B:二叉排序的左子树上结点的关键字小于右子树上的结点的关键字

C：二叉排序的根节点的关键大于右子树上结点的关键字:确答案」

D:二叉排序的根节点的关键大于左子树上结点的关键字

43下列关于查找表描述正确的是（）o*

A:查找表分为静态查找表和动态查找表

B:动态查找表边查找，边改变集合内的元素

C:静态查找表只查找不改变集合中的元素

D:其它选项说法都正确

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

0o*

A.O（n*log2n）

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

C.O（log2n）

D.O（n*n）（正确答案）

45.二叉树的先序遍历和中序遍历如下：先序遍历:EFHIGJK；中序遍历：HFIEJKG

该二叉树根的右子树的根不可能是:（）。［多选题］*

占位符不用管

A、E（正确答案）

B、F（正确答案）

C、G

D、H（正确答案）

46.装填因子的计算方法是（）。*

A、1-俵中未填入记录的数目/哈希表的总长度）

B、表中未填入记录的数目/哈希表的总长度

C、(表中未填入的记录数/)/哈希表的总长度

D、表中填入的记录数/哈希表的总长

47.数据结构与算法里，关于希尔排序描述正确的是()o*

A.希尔排序是不稳定排序

B.希尔排序是属于插入排序正确答案)

C.希尔排序的时间复杂度是O(n3/2)

D.希尔排序又称为缩小增量排序

48.数据结构与算法里，以下算法时间复杂度是O(n*n)的是()o*

A.冒泡排序

B.直接插入排序

C.折半查找

D.希尔排序

49.数据结构与算法里，关于快速排序描述正确的是()o*

A.快速排序是不稳定排序;正确等案)

B.快速排序的时间复杂度是O(nlog2n)。

C.快速排序是一种交换排序(正确答案)

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

50.数据结构与算法里，关于二叉排序树相关描述正确的是()o*

A.二叉排序树是应用于动态查找的结构

B.二叉排序树的中序列是升序序列

C.二叉排序树的左子树也是二叉排序树而答案)

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

51.数组在内存中是连续存放的，不会被间隔开。［判断题］*

对

错

52.数据结构与算法里，研究完数最早的是中国的《九章算术》。［判断题］*

对

错（正确答案）

53.数据结构与算法里，完数N的所有因子为x,y,z,则必有N等于x+y+z。］判

断题］*

对（正确答案）

错

54从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方

法，称为冒泡排序。［判断题］*

对

错（正确答案）

55简单选择排序的稳定性与快速排序的稳定性不一样。［判断题］*

对

错（正确答案）

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

对

错（正确答案）

57哈希函数是一个映像。［判断题］*

对（正确答案）