数据结构与算法第5次

第第页数据结构与算法第5次您的本次作业分数为：97分

单项选择题

1.从原理上讲，折半查找法要求查找表中各元素的键值需要是____

A递增或递减

B递增

C递减

D无序

正确答案:A

单项选择题

2.关于判定树，以下说法不正确的选项是____

A判定树是对有序序列进行二分查找得到的树

Bn个结点的判定树的深度为[log2n]+1

C判定树的叶子结点都在同一层

D判定树除去最末一层结点以后是满二叉树或空二叉树

正确答案:C

单项选择题

3.在顺次表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做____次关键码比较

A2

B3

C4

D5

正确答案:C

单项选择题

4.对线性表进行二分查找时，要求线性表需要____

A以顺次方式存储

B以顺次方式存储且元素有序

C以链式方式存储

D以链式方式存储且元素有序

正确答案:B

单项选择题

5.折半查找算法的时间繁复度是____

AO(n2)

BO(n)

CO(log2n)

DO(nlog2n)

正确答案:C

单项选择题

6.假设用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至____

A该中间位置

B该中间位置－1

C该中间位置＋1

D该中间位置／2

正确答案:B

单项选择题

7.对包含N个元素的散列表进行查找，平均查找长度____

A为O(log2N)

B为O(N)

C不径直依靠于N

D上述三者都不是

正确答案:D

单项选择题

8.假设构造一棵具有n个结点的二叉排序树，最坏的状况下其深度不会超过____

An/2

Bn

C(n+1)/2

Dn+1

正确答案:B

单项选择题

9.分别以以下序列构造二叉排序树，那么与其它几个序列构造的结果不同的是____

A〔80，70，60，75，90，85，100，10〕

B〔80，90，85，70，60，10，75，100〕

C〔80，90，70，85，10，60，75，100〕

D〔80，90，100，70，85，60，10，75〕

正确答案:C

单项选择题

10.假如某二叉树的左右子树的高度差的绝对值不大于1，那么肯定是平衡二叉树

A正确

B不正确

正确答案:A

单项选择题

11.AVL树的任何子树都是AVL树。

A正确

B不正确

正确答案:A

单项选择题

12.在散列表中，所谓同义词就是具有相同散列地址的两个元素

A正确

B不正确

正确答案:A

单项选择题

13.设有1000个无序的元素,盼望用最快的速度选择出其中前10个最大的元素,最好____排序法

A起泡排序

B快速排序

C堆排序

D基数排序

正确答案:C

单项选择题

14.假设要求尽可能快地对实数数组进行稳定的排序，那么应选____

A快速排序

B堆排序

C归并排序

D基数排序

正确答案:C

单项选择题

15.以下排序算法的时间繁复度最小的是____

A

冒泡排序

B希尔排序

C简约选择排序

D归并排序

正确答案:D

单项选择题

16.在以下排序算法中，时间繁复度不受数据初始特性影响，恒为O(n2)的是____

A插入排序

B冒泡排序

C选择排序

D堆排序

正确答案:C

单项选择题

17.插入排序算法在每一趟都能选取出一个元素放在其最终的位置上。

A正确

B不正确

正确答案:B

单项选择题

18.已知10个数据元素为〔54，28，16，34，73，62，95，60，26，43〕，对该数列按从小到大排序，经过一趟冒泡排序后的序列为____

A16，28，34，54，73，62，60，26，43，95

B28，16，34，54，62，73，60，26，43，95

C28，16，34，54，62，60，73，26，43，95

D16，28，34，54，62，60，73，26，43，95

正确答案:B

单项选择题

19.径直插入排序是不稳定的排序方法。

A正确

B不正确

正确答案:B

单项选择题

20.排序方法中，从未排序序列中依次取出元素与已排序序列〔初始时为空〕中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为____

A希尔排序

B冒泡排序

C插入排序

D选择排序

正确答案:C

单项选择题

21.一组记录的关键字为〔46,79,56,38,40,84〕,那么利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为

A38,40,46,56,79,84

B40,38,46,79,56,84

C40,38,46,56,79,84

D40,38,46,84,56,79

正确答案:C

单项选择题

22.快速排序方法在____状况下最不利于发挥其优点

A要排序的数据量太大

B要排序的数据在含有多个相同值

C要排序的数据已基本有序

D要排序的数据个数为奇数

正确答案:C

单项选择题

23.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的改变状况如下(1)20,15,21,25,47,27,68,35,84(2)15,20,21,25,35,27,47,68,84(3)15,20,21,25,27,35,47,68,84那么所采纳的排序方法是____

A选择排序

B希尔排序

C归并排序

D快速排序

正确答案:D

单项选择题

24.在待排序的元素序列基本有序的前提下，效率最高的排序方法是____

A插入排序

B快速排序

C归并排序

D选择排序

正确答案:A

单项选择题

25.以下关键码序列中，属于堆的是____

A〔15，30，22，93，52，71〕

B〔15，71，30，22，93，52〕

C〔15，52，22，93，30，71〕

D〔93，30，52，22，15，71〕

正确答案:A

单项选择题

26.径直插入排序的最坏状况是初始序列为____序

A正

B反

C正和反

D无

正确答案:B

单项选择题

27.一组记录的排序码为〔20,29,1

1,74,35,3,8,56〕，那么利用堆排序方法建立的初始(小顶)堆为____

A20,29,11,74,35,3,8,56

B3,29,8,56,35,20,11,74

C3,8,11,20,29,35,56,74

D20,29,3,8,11,35,

74,56

正确答案:B

单项选择题

28.排序方法中，从未排序序列中选择元素，并将其依次放入已排序序列〔初始时为空〕的一端的方法，称为____

A希尔排序

B归并排序

C插入排序

D选择排序

正确答案:D判断题

29.一般来说，二分查找比顺次查找快,但二分查找有时候不能实施正确错误正确答案:对判断题

30.n(n0)个结点的二叉排序树至多有log2n层正确错误正确答案:错判断题

31.对二叉排序树进行中序遍历得到的序列肯定有序表正确错误正确答案:对判断题

32.二叉排序树一般用于查找某个元素正确错误正确答案:对判断题

33.哈希表是用于排序的技术之一正确错误正确答案:错判断题

34.通过比

较的方法进行排序，其时间繁复性至少是O(log2n)正确错误正确答案:对判断题

35.堆的结构是完全二叉树正确错误正确答案:对判断题

36.序列｛12,23,15,24,22,18,16,30,27｝是一个堆正确错误正确答案:错

您的本次作业分数为：97分

单项选择题

1.从原理上讲，折半查找法要求查找表中各元素的键值需要是____

A递增或递减

B递增

C递减

D无序

正确答案:A

单项选择题

2.关于判定树，以下说法不正确的选项是____

A判定树是对有序序列进行二分查找得到的树

Bn个结点的判定树的深度为[log2n]+1

C判定树的叶子结点都在同一层

D判定树除去最末一层结点以后是满二叉树或空二叉树

正确答案:C

单项选择题

3.在顺次表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做____次关键码比较

A2

B3

C4

D5

正确答案:C

单项选择题

4.对线性表进行二分查找时，要求线性表需要____

A以顺次方式存储

B以顺次方式存储且元素有序

C以链式方式存储

D以链式方式存储且元素有序

正确答案:B

单项选择题

5.折半查找算法的时间繁复度是____

AO(n2)

BO(n)

CO(log2n)

DO(nlog2n)

正确答案:C

单项选择题

6.假设用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至____

A该中间位置

B该中间位置－1

C该中间位置＋1

D该中间位置／2

正确答案:B

单项选择题

7.对包含N个元素的散列表进行查找，平均查找长度____

A为O(log2N)

B为O(N)

C不径直依靠于N

D上述三者都不是

正确答案:D

单项选择题

8.假设构造一棵具有n个结点的二叉排序树，最坏的状况下其深度不会超过____

An/2

Bn

C(n+1)/2

Dn+1

正确答案:B

单项选择题

9.分别以以下序列构造二叉排序树，那么与其它几个序列构造的结果不同的是____

A〔80，70，60，75，90，85，100，10〕

B〔80，90，85，70，60，10，75，100〕

C〔80，90，70，85，10，60，75，100〕

D〔80，90，100，70，85，60，10，75〕

正确答案:C

单项选择题

10.假如某二叉树的左右子树的高度差的绝对值不大于1，那么肯定是平衡二叉树

A正确

B不正确

正确答案:A

单项选择题

11.AVL树的任何子树都是AVL树。

A正确

B不正确

正确答案:A

单项选择题

12.在散列表中，所谓同义词就是具有相同散列地址的两个元素

A正确