资源描述
第10章习题,一、选择题,1下列内部排序算法中：【北京工业大学2000一、1(10分每问2分)】A快速排序B.直接插入排序C.二路归并排序D.简单选择排序E.起泡排序F.堆排序（1）其比较次数与序列初态无关的算法是（dc）（2）不稳定的排序算法是（adf）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k归并排序E以上答案都不对【西安交通大学1996三、1(3分)】13将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是(a)ANB2N-1C2NDN-1,二、判断题,1在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（f）【上海交通大学1998一、18】2.中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（t）【中山大学1994一、4（2分）】3在任何情况下，归并排序都比简单插入排序快。（f）【北京邮电大学2000一、4（1分）】4在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（t）【合肥工业大学2000二、10（1分）】5内排序要求数据一定要以顺序方式存储。（f）【南京理工大学1997二、2（2分）】,三、填空题,1.设用希尔排序对数组98，36，-9，0，47，23，1，8，10，7进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需_趟，写出第一趟结束后，数组中数据的排列次序_。【南京理工大学1997三、5（2分）】2若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_和记录的_。【北京邮电大学2001二、7（4分）】3分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_算法，最费时间的是_算法。【福州大学1998二、10(2分)】,4.用链表表示的数据的简单选择排序，结点的域为数据域data，指针域next；链表首指针为head，链表无头结点。selectsort(head)p=head;while(p_)q=p;r=(2)_while(3)_)if(4)_)q=r;r=(5)_;tmp=q-data;q-data=p-data;p-data=tmp;p=(6)_;【南京理工大学2000三、2（6分）】,5设有字母序列Q,D,F,X,A,P,N,B,Y,M,C,W,请写出按2路归并排序方法对该序列进行一趟扫描后的结果_【北方交通大学2001二、7】,四、应用题,1我们知道，对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：【西安电子科技大学2001计应用五（12分）】【中国矿业大学2000六（10分）】（1）当n=7时，在最好情况下需进行多少次比较？请说明理由。（2）当n=7时，给出一个最好情况的初始排序的实例。（3）当n=7时，在最坏情况下需进行多少次比较？请说明理由。（4）当n=7时，给出一个最坏情况的初始排序的实例。,(1)在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k-1，那么第一遍划分得到两个长度均为n/2的子文件，第二遍划分得到4个长度均为n/4的子文件，以此类推，总共进行k=log2(n+1)遍划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一遍需比较6次，第二遍分别对两个子文件（长度均为3，k=2）进行排序，各需2次，共10次即可。(2)在最好情况下快速排序的原始序列实例：4,1,3,2,6,5,7。(3)在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(或右)子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为O(n2)。所以当n=7时，最坏情况下的比较次数为21次。(4)在最坏情况下快速排序的初始序列实例：7,6,5,4,3,2,1，要求按递增排序。,快速排序在_的情况下最易发挥其长处。【长沙铁道学院1998二、5(2分)】最好每次划分能得到两个长度相等的子文件。设文件长度n=2k-1，第一遍划分得到两个长度n/2的子文件，第二遍划分得到4个长度n/4的子文件，以此类推，总共进行k=log2(n+1)遍划分，各子文件长度均为1，排序结束。,五、算法设计题：1、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。【吉林大学2001二、3（9分）】2、设待排序的文件用单链表作存储结构，其形式如下：TYPEpointer=node;node=RECORDkey:integer;next:pointer;END;写出以head为头指针的选择排序算法。【中山大学1999二（10分）】3、非递归的快速排序算法,
展开阅读全文