资源描述：
《数据结构第10章 习题答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1．下列排序算法中，其中（D）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序2．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为(A)（按递增序）。A．下面的B，C，D都不对。B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7D.9，4，7，8，7，-1，15，203.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（B）。A.直接插入排序B.快
2、速排序C.直接选择排序D.堆排序4．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（D）方法最快。A．起泡排序B．快速排列C．Shell排序D．堆排序E．简单选择排序5．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为(A)排序法。A.插入B.选择C.希尔D.二路归并6.在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（A）。A.选择B.冒泡C.插入D.堆7.若用冒泡排序方
3、法对序列{10,14,26,29,41,52}从大到小排序，需进行（C）次比较。A.3B.10C.15D.258.对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是(B)A.lB.4C.3D.29.堆排序是（E）类排序A.插入B.交换C.归并D.基数E.选择10．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入
4、已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。（1）--（5）:A．选择排序B．快速排序C．插入排序D．起泡排序E．归并排序F．shell排序G．堆排序H．基数排序10.1C52A3D4B5G1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。比较,移动2．分别采
5、用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。冒泡,快速3.设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__________趟，写出第一趟结束后，数组中数据的排列次序__________。3,(10,7,-9,0,47,23,1,8,98,36)4．对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第
6、一遍的排序过程。答案：初始序列：[28],07,39,10,65,14,61,17,50,2121移动：21,07,39,10,65,14,61,17,50,[]39移动：21,07,[],10,65,14,61,17,50,3917移动：21,07,17,10,65,14,61,[],50,3965移动：21,07,17,10,[],14,61,65,50,3914移动：21,07,17,10,14,[28],61,65,50,395．已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，
7、填写完整下示各步骤结果。建立堆结构：_____________交换与调整：（1）877026614512397;（2）____________________;（3）614526312708797;（4）____________________;（5）261234561708797;（6）____________________;（7）312264561708797;答案：建立堆结构:97,87,26,61,70,12,3,45(2)70,61,26,3,45,12,87,97(4)45,12,26,3,61,70,87
8、,97(6)12,3,26,45,61,70,87,971．全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为什么？答案：在内部排序方法中，一趟排序后只有简单选择排序和冒泡排序可以选出一个最大（或最小）元素，并
