广东开放大学形考任务数据结构（本，2021春）第八章形成性考核八（10%）答案

1144766066

拿答案：2937748743  来源 www.ybaotk.com第八章形成性考核八（10%）答案1、 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是
回答
。
2、 在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（ ）。（难度系数：易 ）
直接插入排序
冒泡排序
直接选择排序
希尔排序3、 从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为（ ）。（难度系数：易 ）
插入排序
选择排序
交换排序
归并排序4、 依次将每两个相邻的有序表合并成一个有序表的排序方法称为（ ）。（难度系数：易 ）
交换排序
插入排序
选择排序
归并排序5、 希尔排序在较率上较直接接入排序有较大的改进。但是不稳定的。
对
错6、 冒泡排序是一种比较简单的（ ）排序方法（难度系数：易 ）
交换
堆
主
内部7、 若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ ）。（难度系数：易 ）
84，79，56，38，40，46
84，79，56，46，40，38
84，56，79，40，46，38
79，46，56，38，40，848、 冒泡排序在最好情况下的时间复杂度为O（ ）（难度系数：易 ）
1
2
n
39、 以下时间复杂性是O(n2)的排序方法是（ ）。（难度系数：易 ）
直接选择排序
冒泡排序
二路归并排序
直接插入排序10、 在堆排序和快速排序中，若原始记录接近正序和反序，则选用（ ）排序（难度系数：易 ）
堆
快速
内部
交换11、 对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ ）。（难度系数：易 ）
O(nlog2n)
O(n2)
Ohttps://course.ougd.cn/theme/image.php/fordson/core/1623317895/s/no
O(n3)12、 （ ）是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作（难度系数：易 ）
折半
关键字
顺序
主关键字13、 从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）。（难度系数：易 ）
选择排序
冒泡排序
插入排序
归并排序14、 下述几种排序方法中，（ ）是稳定的排序方法。（难度系数：易 ）
快速排序
希尔排序
堆排序
归并排序15、 高度为8的平衡二叉树至少有
回答
个结点。
16、 若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。（难度系数：易 ）
38，40，46，56，79，84
40，38，46，56，79，84
40，38，46，79，56，84
40，38，46，84，56，7917、 排序算法理想的空间复杂度为O( )（难度系数：易 ）
2
n
3
118、 二路归并时，被归并的两个子序列中的关键字个数一定要相等。
对
错19、 每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（ ）。（难度系数：易 ）
归并排序
插入排序
堆排序
快速排序20、 快速排序法是一种稳定性排序法。
对
错21、 下面是实现对一个含10个整数从小到大冒泡排序的代码，（1）处应该填写（ ）。
 for(j=1;j<=9;j++) 
   for(i=1;i<=10-j;i++) 
     if(（1）)
       
（难度系数：易 ）{
=a[i]>a[i+1]
~a[i] ~a[i]=a[i+1]
~a[i]
}
22、 对记录序列排序是指按记录的某个关键字排序，记录序列按（ ）关键字排序结果是唯一的（难度系数：易 ）
交换
主
内部
堆23、 堆是一种（ ）排序。（难度系数：易 ）
选择
交换
归并
插入24、 基数排序的空间复杂度为O（ ）（难度系数：易 ）
n+rd
2
1
n25、 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，需要内存容量最多的是
回答
。
26、 在对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较（ ）次（难度系数：易 ）
3
4
2
127、 下述几种排序方法中，（ ）不是稳定的排序方法。（难度系数：易 ）
快速排序
简单选择排序
冒泡排序
希尔排序
归并排序
堆排序28、 快速排序在下列（ ）情况下最易发挥其长处。（难度系数：易 ）
被排序的数据中的最大值和最小值相差悬殊
被排序的数据已基本有序
被排序的数据中含有多个相同排序码
被排序的数据完全无序29、 二叉排序树是用来进行排序的
对
错30、 在插入排序和选择排序中，若初始数据基本正序，则选用
回答
；
31、 直接选择排序是一种不稳定的排序方法。
对
错32、 在平均情况下，快速排序法最快，堆积排序法最节省空间。
对
错33、 向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。
对
错34、 从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。（难度系数：易 ）
归并排序
插入排序
选择排序
冒泡排序35、 对n个元素的序列进行冒泡排序时，最少的比较次数是
回答
。
36、 在插入排序和选择排序中，若初始数据基本反序，则选用
回答
。
37、 非空二叉排序树的任意一棵子树也是二叉排序树。
对
错38、 有数据，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（ ）。（难度系数：易 ）
12,24,30,37,45,53,96
37,24,12,30,53,45,96
45,24,53,12,37,96,30
30,24,12,37,45,96,5339、 对于关键字序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为
回答
的关键字开始。
40、 对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ ）。（难度系数：易 ）
n+1
n
n-1
n(n-1)/241、 堆排序的空间复杂度为O（ ）（难度系数：易 ）
n
2
1
342、 衡量排序算法的两个主要性能指标是执行排序算法所需要的时间和执行排序算法所需要的附加空间。
对
错43、 键值序列是一个堆。
{TRUE#回答错误#回答正确}
44、 下列关键字序列中，（ ）是堆。（难度系数：易 ）
16，23，53，31，94，72
16，53，23，94，31，72
16，72，31，23，94，53
94，23，31，72，16，5345、 外部排序是指在排序的整个过程中，全部数据在计算机的外存储器中完成的排序。
对
错46、 顺序文件是指文件中的物理记录按其在文件中的逻辑记录顺序依次存入存储介质而建立的。
对
错47、 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第8个记录45插入到有序表时，为寻找插入位置需比较
回答
次。
48、 回答
排序不需要进行记录关键字间的比较。
49、 根据排序过程中所用的存储器不同，可以将排序方法分为（ ）排序和外部排序（难度系数：易 ）
堆
交换
内部
主50、 下列排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。（难度系数：易 ）
快速排序
堆排序
希尔排序
冒泡排序51、 用某种排序的方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下： （1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 其所采用的排序方法是（ ）。 （难度系数：易 ）
希尔排序
归并排序
直接选择排序
快速排序52、 选择排序过程中元素之间的比较次数与原始序列的状态无关。
对
错53、 如果待排序的记录数目很大，无法一次性调入内存，整个排序过程就必须借助外存分批调入（ ）才能完成（难度系数：易 ）
内存
内部
外部
交换54、 只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。
对
错55、 快速排序是排序算法中最快的一种。
对
错56、 下述几种排序方法中，要求内存最大的是（ ）。（难度系数：易 ）
快速排序
归并排序
希尔排序
堆排序57、 数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )算法最节省时间。（难度系数：易 ）
冒泡排序
堆排序
快速排序
简单选择排序58、 在堆排序和快速排序中，若原始记录无序，则最好选用
回答
。
59、 从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（ ）（难度系数：易 ）
选择排序
交换排序
插入排序
归并排序60、 在堆排序和快速排序中，若原始记录接近正序或反序，则选用
回答
。
61、 当两个元素出现逆序的时候就交换位置，这种排序方法称为（ ）。（难度系数：易 ）
归并排序
插入排序
选择排序
交换排序62、 快速排序在任何情况下圴可得到最块的排序效果。
对
错63、 堆的形状是一棵（ ）。（难度系数：易 ）
完全二叉树
平衡二叉树
二叉排序树
满二叉树64、 已知一个有序表为，则顺序查找元素55需要比较（ ）次。（难度系数：易 ）
4
5
6
365、 对n个记录的表r[1…n]进行简单选择排序，所需要进行的关键字间的比较次数为
回答
。
66、 对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。（难度系数：易 ）
从小到大排列好的
元素无序
从大到小排列好的
元素基本有序67、 直接插入排序在最好情况下的时间复杂度为O（ ）（难度系数：易 ）
1
2
3
n68、 当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。
对
错69、 冒泡排序的空间复杂度为O（ ）（难度系数：易 ）
2
n
1
3

BillieLen

浙江电大形考作业有答案吗？

1670029079

国家开放大学形考怎么做？

Edwardfancy

国家开放大学形考怎么做？

LUMBLEY29

福建电大形考作业可以做吗？

KarenAsync

奥鹏吉林大学作业有答案吗？

mercedesuc60

一体化电大平台形考作业有答案吗？