15 数构上机实验题目第四次上机.pdf

第1页：第四次上机验证试验（必作题）封面

第四次上机验证试验（必作题）：题目1：直接插入排序算法的实验验证[实验目的]验证直接插入排序算法。[实验内容及要求]1、实现直接插入排序算法。2、理论分析并实验验证直接插入排序算法的时间复杂度。3、为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式展现、存储计算结果。

4、为程序制定测试方案。题目2：设计并实现对半插入排序算法。实验内容及要求：对半插入排序的思想是：在插入Ri时（这时R1，R2，…，Ri–1已经排序），取K⌊i/2⌋与Ki进行比较，如果Ki<K⌊i/2⌋，则Ri只能插在R1与R⌊i/2⌋之间，故可以在R1与R⌊i/2⌋–1之间递归上述过程，否则可以在R⌊i/2⌋+1与Ri–1之间递归上述过程。

如此进行直到最后确定插入位置为止。设计对半插入排序算法；编制程序实现该算法，制定测试方案，并调试通过。1、设计并实现对半插入排序算法。2、理论分析并实验验证算法的时间复杂度，即关键词的比较次数和记录的移动次数。3、为便于观察程序的运行结果，设计输出函数，该函数能在输出设备上以图形、表格或其它直观的形式展现程序的运行结果。

4、为程序制定测试方案。设计实验（选作题）：题目：设计并实现计数排序算法。实验内容及要求：有一种简单的排序算法，叫做计数排序(CountSorting).这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。计数排序算法针对表中的每个记录Ri，扫描待排序的表一趟，统计表中有多少个记录的关键词比Ri的关键词小。

例如：统计出的有3个记录的关键字比R5小，那么，R5在新的有序表中的存放位置即为第3位（存储下标从0开始）。1、设计并实现计数排序算法。2、理论分析并实验验证算法的时间复杂度，即关键词的比较次数和记录的移动次数。3、为便于观察程序的运行结果，设计输出函数，该函数能在输出设备上以图形、表格或其它直观的形式展现程序的运行结果。