数据结构知识点总结（一）

1、判断

(1)大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。

(2)快速排序在任何情况下都比其他排序方法速度快。 

(3)快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。 

(4)如果某种排序算法不稳定，则该排序方法就没有实际应用价值。 

(5)对 n 个记录的进行快速排序，所需要的平均时间是 O ( nlog2n)。 

(6)冒泡排序是不稳定的排序。 

(7)堆排序所需的时间与待排序的记录个数无关。 

(8)当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。 

(9)对快速排序来说，初始序列为正序或反序都是最坏的情况。

参考答案：(1） √    (2） ×     (3） √    (4） ×     (5） √

参考答案：(6） ×    (7)  ×     (8)  ×    (9)  √  

2、选择

(1)假设待排序数据元素序列的关键字序列为 2 , 1 , 2 ' ，应用选择排序方法排降序得到的结果为（  ）。 

A. 2 ’ , 2 , 1       B. 1 , 2 ’, 2        C. 2 , 2 ’ , 1      D. l , 2 , 2 ’ 

(2)假设待排序数据元素序列的关键字序列为 1 , 2 , 2 ' , 1 ' ，应用冒泡（插入、归并）排序方法按递增序排序得到的结果为（  ）。 

A. 1 , l ' , 2 , 2 '                        B. 1 , 1 ' , 2 ’ , 2

C. l ' , l , 2 , 2 ’                       D. 1 ' , 1 , 2 ’ , 2

(3)快速排序每次划分的效果好坏和以下何种因素有直接关系（  ）。 

A．关键字的排列情况   B．数据元素的个数     C．轴的相对大小       D．关键字值的最大值 

(4)对以下几个关键字序列进行快速排序，以第一个元素为轴，一次划分效果最好的是 (  ）。 

A. 1 , 2 , 3 , 4 , 5                        B. 2 , l , 3 , 4 , 5

C. 3 , l , 2 , 4 , 5                        D. 5 , 3 , l , 2 , 4

(5)对以下几个关键字序列进行快速排序，以第一个元素为轴，一次划分效果不好的是(  ）。 

A. 4 , l , 2 , 3 , 6 , 5 , 7                B. 4 , 3 , l , 7 , 6 , 5 , 2

C. 4 , 2 , l , 3 , 6 , 7 , 5                D. l , 2 , 3 , 4 , 5 , 6 , 7

(6)对以下几个关键字序列进行快速排序，每次划分效果都好的是（  ）。

A. 2 , 3 , l , 4 , 6 , 5 , 7                B. 4 , 3 , l , 7 , 6 , 5 , 2

C. 2 , l , 3 , 4 , 6 , 7 , 5                D. 4 , 1 , 2 , 3 , 5 , 6 , 7

(7)堆排序属于（   ）。 

A．插入排序           B．交换排序           C．选择排序           D．归并排序

(8)假设待排序数据元素序列为 [4 , 2 , 3 , 1 , 8 , 7 , 6 , 5 , 9 ] ，应用一种排序方法进行按递增序排序，己知一趟的结果为［ 2 , 4 , 1 , 3 , 7 , 8 , 5 , 6 , 9 ] ，则所选用的排序方法为(  ）。                             

A．冒泡（从后向前）                  B．直接选择

C．二路归并排序                      D．快速（以 2 为枢轴） 

(9)设待排序数据元素序列为［ 4 , l , 2 , 3 ] ，应用一种排序方法进行递增序排序，已知两趟后的结果为［ 1 , 2 , 3 , 4 ] ，则所选用的排序方法为（   ）。 

A．直接插入           B．直接选择           C．冒泡（从前向后）   D. 冒泡（从后向前） 

(10)设待排序数据元素序列为［ 2 , 4 , 1 , 3 , 7 , 1 ' ] ，应用一种排序方法进行递增序排序，已知最终的结果为［ 1 ' , 1 , 2 , 3 , 4 , 7 ] ，则所选用的排序方法为（  ）。 

A．直接插入          B．直接选择           C．冒泡（从前向后）   D．二路归并 

参考答案： (1） C    (2） A     (3） C    (4） C     (5） D   

(6） B    (7)  C     (8)  C    (9)  C     (10) B     

来源：我是码农，转载请保留出处和链接！

本文链接：http://www.54manong.com/?id=349