数据结构上机基本课后习题.ppt

《数据结构上机基本课后习题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单元实验二排序算法排序的分类内部排序外部排序插入排序（直插排序、二分插入排序、希尔排序）交换排序（冒泡排序、快速排序）选择排序（简单选择排序、树型排序、堆排序）归并排序（二路归并排序、多路归并排序）分配排序（多关键字排序、基数排序）多路平衡归并排序置换－选择排序最佳归并树排序直接插入排序直接插入排序(StraightInsertionSorting)的基本思想是：n个待排序的元素由一个有序表和一个无序表组成，开始时有序表中只包含一个元素。排序过程中，每次从无序表中取出第一个元素，将其插入到有序表中的适当位置，使有序表的长度不断加长，完成排序过程。有序序列R[1..i-1]R[i]无序序

2、列R[i..n]有序序列R[1..i]无序序列R[i+1..n]冒泡排序冒泡排序(BubbleSorting)的基本思想是：将相邻位置的关键字进行比较，若为逆序则交换之。无序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1无序序列R[1..n-i]有序序列R[n-i+1..n]比较相邻记录，将关键字最大的记录交换到n-i+1的位置上第i趟起泡排序若在一趟排序过程中没有进行过交换记录的操作，则整个排序过程终止。简单选择排序简单选择排序的基本思想是：第一趟在n个记录中选取最小记录作为有序序列的第一个记录，第二趟在n-1个记录中选取最小记录作为有序序列的第二个记录，第i趟在

3、n-i+1个记录中选取最小的记录作为有序序列多中的第i个记录。有序序列R[1..i-1]无序序列R[i..n]第i趟简单选择排序从中选出关键字最小的记录有序序列R[1..i]无序序列R[i+1..n]基本要求1．用随机函数产生1000个（或更多）整数（或浮点数），保存在文件（intfile.dat/realfile.dat）中，然后将文件中的所有整数（或浮点数）读入一个数组A。（1）用冒泡法对数组A排序；（2）用简单选择排序方法对数组A排序；（3）用直接插入排序法对数组A排序；将上述排序算法分别用函数实现，输出每种排序过程中元素的比较次数、交换（或移动）次数，以及排序过程所消耗的时间（

4、以s或ms为单位）；基本要求2．将问题1中所有1000个（或更多）整数读入数组A，用快速排序算法对数组A中的元素排序，输出排序结果、排序过程中元素的比较和交换（移动）次数、排序算法消耗的时间;3.利用上面实现的任意一种排序算法，对实验题目一所产生的学生信息文件studinfo.dat，读取其中的所有学生信息：（1）按学号排序输出学生信息；（2）按姓名排序输出学生信息；（3）按三门课程的平均分从高到低排序输出学生信息（除了学生基本信息外，还要输出每个学生的平均成绩），最后再加一行输出信息：每门课程的平均成绩。快速排序快速排序(QuickSorting)是迄今为止所有内排序算法中速度最快的

5、一种。其基本思想是：取待排序序列中的某个元素作为基准（也成为枢轴元素，一般取第一个元素），通过一趟排序，将待排序列划分为左右两个子序列，左子序列元素的关键字均小于或等于基准元素的关键字，右子序列的关键字则大于或等于基准元素的关键字，然后分别对两个子序列继续进行排序，直至整个序列有序。无序的记录序列无序的左子序列无序的右子序列枢轴一次划分分别进行快速排序386597132749551234567849049pivotij快速排序中的一趟划分386597132749551234567804949pivotija[j]与pivot比较，a[j]小则a[j]→a[i]3865971327495

6、51234567804949pivotij快速排序中的一趟划分i386597132749551234567804949pivotja[i]与pivot比较，a[i]大则a[i]→a[j]；否则i增1386597132749551234567804949pivotij快速排序中的一趟划分i386597132749551234567804949pivotja[i]与pivot比较，a[i]大则a[i]→a[j]；否则i增1快速排序中的一趟划分i386597132749551234567804949pivotja[j]与pivot比较，a[j]小则a[j]→a[i]；否则j减11234567

7、89i386597132749550449pivotj快速排序中的一趟划分i386597132749551234567804949pivotja[i]与pivot比较，a[i]大则a[i]→a[j]；否则i加1123456789i3865971349550449pivotj27快速排序中的一趟划分i386597132749551234567804949pivotja[j]与pivot比较，a[j]小则a[i]→a[j]；否则j减1i386597