数据结构第十章排序作业

墨蓝 2021-11-11 12:00 661阅读 0赞

*  **排序作业**
 *  **答案链接[链接][Link 1]**
 *  选择题（每题2分，共22分）。

1．若表R在排序前已按键值递增顺序排列，则（   ）算法的比较次数最少。

A．直接插入排序            B．快速排序

C．归并排序                D．选择排序

2．对各种内部排序方法来说，（   ）。

A．快速排序时间性能最佳

B．归并排序是稳定的排序方法

C．快速排序是一种选择排序

D．堆排序所用的辅助空间比较大

3.  排序算法的稳定性是指（   ）。

A．经过排序之后，能使值相同的数据保持原顺序中的相对位置不变。

B．经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变。

C．排序算法的性能与被排序元素的数量关系不大

D．排序算法的性能与被排序元素的数量关系密切

4. 如下序列中，（   ）序列是大顶堆。

A.  \{4,5,3,2,1\}               B.  \{5,3,4,1,2\}

C.  \{1,2,3,4,5\}               D.  \{1,2,3,5,4\}

5. 若将\{3,2,5,4,1\}排为升序，则实施快速排序一趟后的结果是（   ）（其中，枢轴记录取首记录）。

A.  \{1,2,3,4,5\}                  B.  \{1,2,4,5,3\}

C.  \{1,3,5,4,2\}                  D.  \{2,5,4,1,3\}

6. 若将\{1,2,3,4,5,6,7,9,8\}排为升序，则（   ）排序方法的“比较记录”次数最少。

A.  快速排序                   B.  简单选择排序

C.  直接插入排序               D.  冒泡排序

7. 若将\{5,4,3,2,1\}排为升序，则（   ）排序方法的“移动记录”次数最多。

A.  快速排序                                B.  冒泡排序

C.  直接插入排序                       D.  简单选择排序

8. 用简单选择排序将顺序表\{2,3,1 ,3′,2′\}排为升序，实施排序1趟后结果是\{1 ,3,2 ,3′,2′\}，则排序3趟后的结果是（   ）。

A.  \{1 ,2,3 ,3′,2′\}                       B.  \{1 ,2 ,2′,3 ,3′\}

C.  \{1 ,2′,2 ,3 ,3′\}                      D.  \{1 ,2 ,2′,3′,3 \}

9．下列排序算法中，（    ）排序在某趟结束后不一定选出一个元素放到其最终的位置上。

A．选择             B．冒泡           C．归并           D．堆

10．下列排序算法中，稳定的排序算法是（  ）。

A．堆排序                B．直接插入排序

C．快速排序              D．希尔排序

11．堆排序的时间复杂度是（    ）。

A．O(n\*n)                 B．O(n\*log n)

C．O(n)                   D．O(log n)

*  填空题（每空4分，共4分）。

1.  对n个元素进行归并排序，空间复杂度为         。

*  综合题（共24分）。

1. （共12分）有一组待排序的关键字如下：

(54，38，96，23，15，72，60，45，83)

分别写出希尔排序(d=5)、快速排序、堆排序、归并排序第一趟升序排序后的结果（其中堆排序的第一趟指序列完成初始建堆、将堆顶元素置为最末位置后其余元素调整为堆的结果）（每个3分）。

希尔排序：

快速排序：

堆排序：

归并排序：

2. （共12分）已知数据序列为（12，5，9，20，6，31，24），对该项数据序列进行排序，分别写出直接插入排序、简单选择排序、快速排序、堆排序、二路归并排序及基数排序第一趟升序排序结果（其中堆排序的第一趟指序列完成初始建堆、将堆顶元素置为最末位置后其余元素调整为堆的结果）（每个2分）。

直接插入排序：

简单选择排序：

快速排序：

堆排序：

二路归并排序：

基数排序：

**答案链接[链接][Link 1]**

[Link 1]: https://download.csdn.net/download/weixin_41360517/11603702

发表评论取消回复

表情：

评论列表（有 1 条评论，661人围观）

蒲公英云0A4954V铁粉 2022-12-19 10:08

答案呢

相关阅读

相关【MOOC-浙大数据结构】第十周的编程作业——排序

.[**统计工龄**][Link 1] int a[105]; int main() { memset(a,0,sizeof a); ...

偏执的太偏执、/ 2024年04月17日 05:43/ 0 赞/ 64 阅读

相关数据结构 | 第九章排序

文章目录一、排序 1、概念以及分类 1.1 排序的稳定性

亦凉/ 2022年09月03日 02:25/ 0 赞/ 239 阅读

相关数据结构第十章内部排序之插入排序

PS:后面的元素的数值比前面的元素的小就插入 1.直接插入排序 \include <stdio.h> \define MAXSIZE 20 //定义一个顺序表最大长度为

谁践踏了优雅/ 2022年08月22日 11:25/ 0 赞/ 216 阅读

相关数据结构第十章内部排序简介

排序主要分为以下几类：插入排序：直接插入排序，折半插入排序，希尔排序交换排序：冒泡排序，快速排序选择排序：简单选择排序，外部排序归并排序：2-路归并排序 ..

骑猪看日落/ 2022年08月22日 11:24/ 0 赞/ 217 阅读

相关数据结构第八章排序

数据结构笔记链接： [第一章绪论][Link 1] [第二章线性表][Link 2] [第三章栈和队列][Link 3] [第四章串][Link 4] [第五

太过爱你忘了你带给我的痛/ 2022年06月08日 11:39/ 0 赞/ 281 阅读

相关数据结构-第九章排序

/ 冒泡排序的思想：不断的交换,通过交换完成最终的排序 / include <iostream> using namespa

墨蓝/ 2022年05月25日 01:58/ 0 赞/ 279 阅读

相关《大话数据结构》第九章排序

《大话数据结构》第九章排序内排序插入类排序直接插入排序希尔排

蔚落/ 2022年03月11日 02:50/ 0 赞/ 327 阅读

相关数据结构第十章排序作业

排序作业答案链接[链接][Link 1] 选择题（每题2分，共22分）。 1．若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A．

墨蓝/ 2021年11月11日 12:00/ 0 赞/ 662 阅读

相关数据结构第九章查找作业

查找作业答案链接[链接][Link 1] 选择题（每题3分，共24分）。 1．对于二叉排序树，下面的说法（）是正确的。 A．二叉排序树是动态树

- 日理万妓/ 2021年11月11日 11:58/ 0 赞/ 573 阅读

相关数据结构第三章作业栈与队列作业

栈与队列作业（共50分）答案连接[链接][Link 1] 选择题（每题 3 分，共27 分）。 1. 经过以下栈运算后，x的值是（）。

桃扇骨/ 2021年11月11日 11:54/ 5 赞/ 911 阅读