数据结构（中国海洋大学）章节测试课后答案2024春

第九章测试

1. 1.设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4 的一趟希尔排序结束后前4条记录关键字为（   ）。
A:40，50，20，95 B:45，40，15，20 C:15，40，60，20 D:15，20，40，45
答案:C
2. 2.快速排序方法在情况下最不利于发挥其长处。(    )
A:要排序的数据已基本有序 B:要排序的数据个数为奇数 C:要排序的数据中含有多个相同值 D:要排序的数据量太大。 3. 一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（   ）。
A:84,79,56,46,40,38 B:79,46,56,38,40,80 C:84,56,79,40,46,38 D:84,79,56,38,40,46 4. 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（   ）。
A: 15，25，35，50，80，20，36，40，70，85 B:15，25，35，50，80，20，85，40，70，36 C: 15，25，35，50，20，40，80，85，36，70 D:15，25，35，50，80，85，20，36，40，70 5. 试以L.r[k+1]作为监视哨改写教科书10.2.1节中给出的直接插入排序算法。其中，L.r[1..k]为待排序记录且k<MAXSIZE。void InsertionSort ( SqList &L ) {   // 对顺序表 L 作直接插入排序。   for ( i=k-1-1; i>=1; --i )    {    if (L.r[i+1].key < L.r[i].key)   {           L.r[k+1] = L.r[i];            // 复制为监视哨for ( j=i+1; L.r[k+1].key > L.r[j].key;  ++ j )L.r[j-1] = L.r[j];        // 记录前移}//end if                    }//end for    } // InsertSort
A:L.r[j] = L.r[k]; B:A.L.r[j+1] = L.r[k+1]; C:L.r[j] = L.r[k+1]; D:L.r[i] = L.r[k+1]; 6.1.编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：(1)采用顺序存储结构，至多使用一个记录的辅助存储空间；(2)算法的时间复杂度为O(n);void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前{low=0;high=n-1;while(              ){while(low<high&&a[high]>=0) high--; //以0作为虚拟的枢轴记录a[low]<->a[high];while(low<high&&a[low]<0) low++;a[low]<->a[high];}}//Divide
A:low!=high B:low< =(high+1) C:low< high D:(low+1)< high