南京工业大学-数据结构-作业答案-作业7

第七次作业1.用某种排序方法对线性表（25,84，21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下：25,84，21,47,15,27,68,35,20→20,15,21,25，47,27,68,35,84→15,20,21,25，35,27,47,68,84→15,20,21,25，27,35,47,68,84，问采用的是什么排序方法？2.对于整数序列100，99，98，…3，2，1，如果将它完全倒过来，分别用冒泡排序和快速排序法，它们的比较次数和交换次数各是多少？3.以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？①直接插入排序②希尔排序③冒泡排序④快速排序⑤直接选择排序⑥堆排序⑦归并排序⑧基数排序（8分）4.序列的“中值记录”指的是：如果将此序列排序后，它是第[n/2]个记录。试写一个求中值记录的算法。1.用某种排序方法对线性表（25,84，21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下：25,84，21,47,15,27,68,35,20→20,15,21,25，47,27,68,35,84→15,20,21,25，35,27,47,68,84→15,20,21,25，27,35,47,68,84，问采用的是什么排序方法？答：用的是快速排序方法。注意每一趟要振荡完全部元素才算一个中间结果。2.对于整数序列100，99，98，…3，2，1，如果将它完全倒过来，分别用冒泡排序和快速排序法，它们的比较次数和交换次数各是多少？答：冒泡排序的比较和交换次数将最大，都是1+2+…+n-1=n(n-1)/2＝50×99=4545次快速排序则看按什么数据来分子表。如果按100来分，则很惨，也会是n(n-1)/2！若按中间数据50或51来分表，则：第1轮能确定1个元素，即在1个子表中比较和交换了n－1个元素；n－（21-1）第2轮能再确定2个元素，即在2个子表中比较和交换了n－3个元素；n－（22-1）第3轮能再确定4个元素，即在4个子表中比较和交换了n－7个元素；n－（23-1）第4轮能再确定8个元素，即在8个子表中比较和交换了n－15个元素；n－（24-1）……第6轮能再确定32个元素，即在32个子表中比较和交换了n－65个元素；n－（26-1）第7轮则能全部确定，（因为27=128），在100个子表中比较和交换了n－（100－1）个元素；比较和交换总次数为：7n－(21－1＋22－1＋23－1……＋26－1＋100－1)＝7n+7－(1＋2＋4＋……＋64+100)=7n－(8+16+32+164)=700-220=480次若从中间选择初始元素，则ASL=（n+1）log2n－(21＋22＋23+……＋2m)=nlog2n+log2n－(21＋22＋23+……＋n)≈O（nlog2n）3.以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？①直接插入排序②希尔排序③冒泡排序④快速排序⑤直接选择排序⑥堆排序⑦归并排序⑧基数排序（8分）解：先回答第2问：①⑤⑦⑧皆易于在链表上实现。①直接插入排序的中间过程如下：②希尔排序的中间过程如下：③冒泡排序的中间过程如下：④快速排序的中间过程如下：⑤直接选择排序的中间过程如下：⑥堆排序（大根堆）的中间过程如下：⑦归并排序排序的中间过程如下：⑧基数排序的中间过程如下：4.序列的“中值记录”指的是：如果将此序列排序后，它是第[n/2]个记录。试写一个求中值记录的算法。10.42typedefstruct{intgt;//大于该记录的个数intlt;//小于该记录的个数}place;//整个序列中比某个关键字大或小的记录个数intGet_Mid(inta[],intn)//求一个序列的中值记录的位置{placeb[MAXSIZE];for(i=0;in;i++)//对每一个元素统计比它大和比它小的元素个数gt和ltfor(j=0;jn;j++){if(a[j]a[i])b[i].gt++;elseif(a[j]a[i])b[i].lt++;}mid=0;min_dif=abs(b[0].gt-b[0].lt);for(i=0;in;i++)//找出gt值与lt值最接近的元素,即为中值记录if(abs(b[i].gt-b[i].lt)min_dif)mid=i;returnmid;}//Get_Mid