数据结构第10章习题.ppt

第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 ) AN B2N-1 C2N DN-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、设待排序的文件用单链表作存储结构，其形式如 下： TYPE