数据结构单元练习10

《数据结构单元练习10》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、WORD文档可编辑单元测验10一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（ㄨ）（1）如果某种排序算法不稳定，则该排序方法就没有实用价值。（√）（2）希尔排序是不稳定的排序。（ㄨ）（3）冒泡排序是不稳定的排序。（√）（4）对n个记录的进行快速排序，所需要的平均时间是O(nlog2n)。（ㄨ）（5）堆排序所需的时间与待排序的记录个数无关。（√）（6）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。（ㄨ）（7）快速排序在任何情况下都比其它排序方法

2、速度快。（√）（8）对快速排序来说，初始序列为正序或反序都是最坏情况。（√）（9）采用归并排序可以实现外排序。（√）（10）采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。二．填空题（1）大多数排序算法都有两个基本的操作：比较和移动。（2）评价排序算法优劣的主要标准是时间复杂度和算法所需的附加空间。（3）根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序和外排序。（4）外排序是指在排序过程中，数据的主要部分存放在计算机的外存中。（5）对n个关键字进行冒泡排序，其可能的最小比较次数为

3、：n-1次。（6）在最坏情况下，在第i趟直接插入排序中，要进行i-1次关键字的比较。（7）对n个关键字进行冒泡排序，时间复杂度为O(n2)。（8）快速排序在最坏情况下的时间复杂度是O(n2)。（9）对于n个记录的集合进行归并排序，所需要的平均时间为：O(log2n)。（10）对于n个记录的集合进行归并排序，所需要的附加空间是O(n)。（11）若原始数据接近无序，则选用快速排序最好。（12）在排序前，关键字值相等的不同记录，排序后相对位置保持不变的排序方法，称为稳定排序方法。（13）在插入排序和选择排序中

4、，若初始数据基本正序，则选用插入排序较好。（14）当增量为1时，该趟希尔排序与直接插入排序基本一致。（15）第一趟排序后，序列中键值最大的记录交换到最后的排序算法是冒泡排序。（16）依次将每个记录插入到一个有序的子文件中的排序方法称为直接插入排序。（17）在插入排序、选择排序和归并排序中，排序是不稳定的为：选择排序。（18）在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较3次。（19）两个序列分别为：L1={2

5、5，57，48，37，92，86，12，33}L2={25，37，33，12，48，57，86，92}。技术资料专业分享WORD文档可编辑用冒泡排序法对L1和L2进行排序，交换次数较少的是序列：L2。（20）对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第四次选择和交换后，未排序记录是54，72，60，96，80。三．选择题（1）排序是根据（A）的大小重新安排各元素的顺序。A．关键字B．数组C．元素件D．结点（2）评价排序算法好坏的标准主要是（D）。A．执行时间B

6、．辅助空间C．算法本身的复杂度D．执行时间和所需的辅助空间（3）直接插入排序的方法是（B）的排序方法。A．不稳定B．稳定C．外部D．选择（4）直接插入排序的方法要求被排序的数据（B）存储。A．必须链表B．必须顺序C．顺序或链表D．可以任意（5）排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为(D)。A．希尔排序B．归并排序C．插入排序D.选择排序（6）每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不

7、小于基准元素的值，此种排序方法叫做（C）。A．冒泡排序B．堆排序C．快速排序D.归并排序（7）快速排序在（C）情况下最易发挥其长处。A．待排序的数据中含有多个相同的关键字B．待排序的数据已基本有序C．待排序的数据完全无序D．待排序的数据中最大值与最小值相差悬殊（8）下述几种排序方法中，要求内存量最大的是：（D）。A．插入排序B．选择排序C．快速排序D.归并排序（9）直接插入排序的方法是从第（B）个元素开始，插入到前边适当位置的排序方法。A．1B．2C．3D．n（10）堆的形状是一棵（C）。A．二叉排序树

8、B．满二叉树C．完全二叉树D．平衡二叉树（11）内排序是指在排序的整个过程中，全部数据都在计算机的（A）中完成的排序。A．内存B．外存C．内存和外存D．寄存器（12）快速排序的方法是（A）的排序方法。A．不稳定B．稳定C．外部D．选择（13）下列排序方法中，关键字比较次数与记录的初始排列次序无关的是（A）。A．选择排序B．希尔排序C．插入排序D．冒泡排序（14）下述几种排序方法中，平均时间复杂度最小的是（A）。A．希尔排序B．插入排序C．冒