数据结构第10章作业

第10章排序作业作业一：对人意的7个关键字进行排序，至少要进行_______次关键字之间的两两比拟。A.13B.11C.15D.16E.19【参考答案】C【解题思路】任何一个借助“比拟”进行排序的算法，在最坏的情况下所需进行得比拟次数至少为[]。[]=15。排序方法中，从未排序序列中依次取出元素与已排序序列〔初始时为空〕中的元素进行比拟，将其放入已排序序列的正确位置上的方法，称为_________。A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序【参考答案】C【解题思路】插入排序的思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排序的序列中的适当位置。直到全部的记录插入完成为止。对记录的关键字为{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：5026388070908304020508304020902638807026830402080503890708202630384050708090其使用的排序方法是_________。A.快速排序 B.希尔排序 C.基数排序 D.归并排序【参考答案】B【解题思路】由排序的结果直接可以确知〔即使不知道其他几中排序方法〕该排序是增量序列为5,3,1的希尔排序。序列{70，83，100，65，10，32，7，9},请给出采用插入排序法对该序列作升序排序时的每一趟的结果。【参考答案】采用插入排序方法排序的各趟的结果如下：初始：〔70〕，83，100，65，10，32，7，9第一趟：〔70，83〕，100，65，10，32，7，9第二趟：〔70，83，100〕，65，10，32，7，9第三趟：〔65，70，83，100〕，10，32，7，9第四趟：〔10，65，70，83，100〕，32，7，9第五趟：〔10，32，65，70，83，100〕，7，9第六趟：〔7，10，32，65，70，83，100〕，9第七趟：〔7，9，10，32，65，70，83，100〕作业二：快速排序方法在_____情况下最不利于发挥其长处。A.要排序的数据量太大 B.要排序的数据中含有多个相同值 C.要排序的数据已根本有序 D.要排序的数据个数为奇数【参考答案】C【解题思路】要排序的数据〔个数为n〕已根本有序，采用快速排序那么需要n-1趟，其时间复杂度升至O(n2)。用快速排序方法对线性表(24,84,20,47,15,26,68,35,19)进行排序时，写出元素序列的变化情况：【参考答案】〔1〕24,84,20,47,15,26,68,35,19〔2〕19,15,20,24,47,26,68,35,84〔3〕15,19,20,24,35,26,47,68,84〔4〕15,19,20,24,26,35,47,68,84【解题思路】每一次将一个子序列以第一个元素为基准分为两段。作业三：采用简单项选择择排序，比拟的次数与移动次数分别是________.A.B.C.D.【参考答案】C【解题思路】简单项选择择排序过程是：每趟从n-i+1个记录中选取关键字最小的记录〔每趟比拟的时间复杂度为O(n)〕,并和第i个记录交换〔每趟移动的时间复杂度为O(1)〕，因此，总的比拟次数与移动次数分别是。对n个元素的序列进行排序时，堆排序所需要的附加存储空间是_______.A.B.C.D.【参考答案】B【解题思路】堆排序本质上是就地排序。序列{503，87，512，61，908，170，897，275，653，462}，给出采用堆排序法对该序列做降序排序时的每一趟的结果。【参考答案】排序结果为908,897,653,512,503,462,275,170,87,61。503503875121708979086127565334621初始堆90865389717051246250327561872建堆3交换908和87,输出9083交换908和87,输出90889765351217087462503275614筛选调整87653897170512462503275615交换897和61,输出8975交换897和61,输出89765350351217087462275616筛选调整61653512170874625032757交换653和61,输出6537交换653和61,输出65351250317061874622758筛选调整61503512170874622759交换512和87,输出5129交换512和87,输出512503462170618727510筛选调整875031706146227511交换503和61,输出50311交换503和61,输出503462275170876112筛选调整462170872756113交换462和87,输出46213交换462和87,输出462275871706114筛选调整275170618715交换275和61,输出27515交换275和61,输出275170-876116筛选调整871706117交换170和61,输出17017交换170和61,输出17087-6118筛选调整876119交换87和61,输出8719交换87和61,输出8720输出6161作业四：一组纪录的排序码为{25，48，16，35，79，82，23，40，36，72}，其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为_______.A.16253548234079823672B.16253548798223364072C.16234835798223364072D.16253548792336407282【参考答案】A【解题思路】一趟归并过程如下：25，48，16，35，79，82，23，40，36，7225，48，16，35，79，82，23，40，36，7216，25，35，48，23，40，79，82，36，72就排序的算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是_______。A.堆排序<快速排序<归并排序B.堆排序<归并排序<快速排序C.堆排序>归并排序<快速排序D.堆排序>快速排序>归并排序【参考答案】A【解题思路】堆排序、快速排序、归并排序所用的辅助空间依次是:O(1)、、O(n)。3)序列{10,18,4,3,6,12,1,9,15,8},请给出采用归并排序法对该序列作升序排序的每一趟结果。【参考答案】初始:10,18,4,3,6,12,1,9,15,8第1趟：[10,18]